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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
