[Haskell-cafe] Question about memory usage
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
> arithmetic to get correct results.
Yes, I was delighted when I saw this for the frist time. It works be
(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:
With this implementation, printing the result of a call to, say
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