[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.)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
