[Haskell-cafe] Question about memory usage
John van Groningen
johnvg at cs.ru.nl
Wed Aug 18 08:53:35 EDT 2010
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
More information about the Haskell-Cafe
mailing list