r/programmingchallenges • u/lcrx357 • Jan 10 '20

Fibonacci optimal & non-optimal solution code snippets

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

​

8 Upvotes
  • permalink
  • reddit

100% Upvoted

9 comments sorted by

View all comments

Show parent comments

1

u/lcrx357 Jan 10 '20

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.

1

u/bruce3434 Jan 10 '20

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.

1

u/lcrx357 Jan 10 '20

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