[Haskell-cafe] Question about memory usage

[Sebastian Fischer]

[continuing off topic]

On Aug 16, 2010, at 3:13 PM, Daniel Fischer wrote:

> You can calculate the n-th Fibonacci number in O(log n) steps using  
> Integer
> arithmetic to get correct results.

Yes, I was delighted when I saw this for the frist time. It works be  
computing

     /1 1\^n
     \1 0/

(This is meant to be a matrix to the nth power) by repeated squaring.  
Wikipedia knows the details:

     http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

My Haskell implementation of this approach is on Hackage:

     http://hackage.haskell.org/package/fibonacci

and github:

     http://github.com/sebfisch/fibonacci/blob/master/Data/Numbers/Fibonacci.hs

With this implementation,  printing  the result of a call to, say

     fib 100000000

takes *much* longer than  computing  it.

[almost on topic again]

I am a bit concerned about the memory usage. If you know how to fix  
it, please send me patches (ideally via github)!

Cheers,
Sebastian


-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)