A question about Fibonacci's numbers generator

Jun 22, 2008 at 1:19 PM
Edited Jun 23, 2008 at 6:45 AM
I looked at the Fibonacci's generator and I would ask a question about it: why did you choose to implement the generator using the iterative formula instead of the closed form version? With the iterative formula f(n)=f(n-1)+f(n-2) one has to do 'n' passes to get the n-th fibonacci's number and in this case the complexity is obviously O(n). However, the iterative formula can be "rolled up" and rewritten in closed form (the so called Binet's formula); this formula requires only the 'n' to output the n-th number and the complexity drops to O(1) (a constant time!).

Here is the Binet's closed formula of the Fibonacci's series:
f(n) = floor((1/2)+((g^n)/sqrt(5))); where 'g' is the golden ratio equal to g=(1+sqrt(5))/2;


Jun 23, 2008 at 2:27 PM
Hi Gianluca, i'm glad you are giving us interesting feedback and focus on Fibonacci complexity. Binet's formula it's very surprising and interesting at the same time but in real world there are some built-in limits for the number of decimal places one can accurately compute (floating point limited precision). Sometimes these inaccuracies will make numbers round to the wrong values and carry to inappropriate result. The approach we adopted improves the classical algorithm definition using the memory during the computation in such a way  that the values of two consecutive terms of the Fibonacci sequence are always stored in the memory thus avoiding unnecessary computing...
Hear you soon, Luca