[Haskell-cafe] Question about memory usage

[John van Groningen]

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