[Haskell-cafe] Question about memory usage

Sebastian Fischer sebf at informatik.uni-kiel.de
Mon Aug 16 11:36:13 EDT 2010

[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  

     /1 1\^n
     \1 0/

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


My Haskell implementation of this approach is on Hackage:


and github:


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)!


Underestimating the novelty of the future is a time-honored tradition.

More information about the Haskell-Cafe mailing list