[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.)