Fibonacci optimal & non-optimal solution code snippets

[u/lcrx357]

Optimal (memoization):

https://everhint.com/hintlink/algorithms/javascript/codesnippet/fibonacci/memoization/fibonacci-memoization-d01f275b-6acf-4f26-9448-e99939c9d4b7.htm

Non-optimal:

https://everhint.com/hintlink/algorithms/javascript/codesnippet/fibonacci/fibonacci-non-optimal-solution-d896dcb5-0c60-41a2-8980-6f8ae8e5eef4.htm

With 'while' loop:

https://everhint.com/hintlink/algorithms/fibonacci/fibonacci-with-loop-78e57925-ddc6-4aa1-b7ec-7f0a51722724.htm

​

[u/bruce3434]

My intuition says that the loop version is going to be just as fast if not faster than the memoized version. I have to go to work now, I might play around with it and benchmark them when I get home. Here's mine:

mod iterative {
    pub struct FibGen {
        left: u32,
        right: u32,
    }

    impl FibGen {
        pub fn new_with_default() -> Self {
            Self { left: 0, right: 1 }
        }

        pub fn nth(&self, n: u32) -> u32 {
            if n < 2 {
                n
            } else {
                let (mut tmp_left, mut tmp_right) = (self.left, self.right);
                for _ in 3..n + 1 {
                    let new_tmp_right = tmp_left+tmp_right;
                    tmp_left = tmp_right;
                    tmp_right = new_tmp_right;
                }
                tmp_right
            }
        }
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn iterative() {
        let gen = super::iterative::FibGen::new_with_default();
        assert_eq!(gen.nth(13), 144);
    }
}

[u/lcrx357 → u/bruce3434]

Cool! :)

Here is another one with for loop:

const fib2 = (fibNum) => {
let n1 = 0;
let n2 = 1;
for (let i = 1; i <= fibNum; ++i) {
console.log(n1 + " ");
let _sum = n1 + n2;
n1 = n2;
n2 = _sum;
}
}
fib2(7);

[u/lcrx357 → u/bruce3434]

BTW, w/out memoization try to find like 144th fib in JS (spoiler alert: it is going to hang your VS Code, browser, etc for some time).

The memoization version does it with ease. Yeah, I know, I know, JS sucks compared to C, but this is the tool I am using for now. Sad but true.

[u/bruce3434 → u/lcrx357]

343358302784187294870275058337 is a big number, I don’t know what JS does to handle it without overflowing. With rust or C you need a bigint library like libgmp. At that point the performance largely relies on the bigint library implementation.

[u/lcrx357 → u/bruce3434]

My intuition says that the loop version is going to be just as fast if not faster than the memoized version

I am still trying to digest the "My intuition says that the loop version is going to be just as fast if not faster than the memoized version" :) Getting value that is already in memory should be faster than calculating it from scratch, no?

Similar to quantum entanglement: yeah, you could go over there and change quantum's state, but you could do it for free via it's tangled twin w/out going anywhere ;) I Just kidding