3 ms·
vs Pure Reason Reason gets you a closed form for F(n), the nth Fibonacci number. The author's naive fib with memoization is O(n). The closed form is O(1) if yo
by goldenkey 6y ago
vs Pure Reason
Reason gets you a closed form for F(n), the nth Fibonacci number. The author's naive fib with memoization is O(n). The closed form is O(1) if you consider exponentiation to be a constant time operation.
https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form...
Quite a thing to overlook in an article about efficiency of algorithms... why am I not surprised?
- ketzu 6y agoMy understanding why this is usually not discussed is the following: The fibonacci sequence is usually used as an illustrative example or motivating problem for a given topic, not as a problem in itself. I believe a side note might most likely detract from the overall point for a technicality. For the same reason you only wrote "if you consider exponentiation to be a constant time operation" instead of including a side analysis of how everything changes once you can't do that anymore, possible problems with accuracy of floating point representations of phi and it's exponentiation and everything else one has to consider once we leave the comfortable home of architecture native integers. It is usually very valid to do so.
- bidirectional 6y agoWhy are you assuming exponentiation is constant time? For machine integers it near-enough is, but there are fewer than 100 Fibonacci numbers that fit in a 64-bit integer so you may as well use a lookup table. For arbitrary precision integers it definitely isn't.