Sebastian Fischer wrote:
.. Interesting. It uses the same amount of memory but is faster probably because it allocates less.
But I prefer programs for people to read over programs for computers to execute and I have a hard time to verify that your algorithm computes
According to: http://en.wikipedia.org/wiki/Fibonacci_number F(2n-1) = F(n)^2 + F(n-1)^2 -- 1 F(2n) = (2*F(n-1) + F(n)) * F(n) -- 2 therefore: F(2n) = (2*(F(n+1) - F(n)) + F(n)) * Fn -- use F(n-1)=F(n+1)-F(n) in 2 = (2* F(n+1) - F(n)) * Fn F(2n+1) = F(n+1)^2 + F(n)^2 -- substite n+1 in 1 F(2n+2) = F (2*(n+1)) -- use 2 = (2*F(n) + F(n+1)) * F(n+1) So if we know F(n) and F(n+1) we can compute F(2n), F(2n+1) and F(2n+2). dfibo computes (F(n),F(n+1)) using these equations.
..
Kind regards, John van Groningen