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(n1)+f(n2) one has to do 'n' passes
to get the nth 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
nth 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;
Bye!
Gianluca


Developer
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 builtin 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

