re := {fib(n+2) = fib(n+1) + fib(n)}; inits := {fib(0) = 1, fib(1) = 1}; {fib(n + 2) = fib(n + 1) + fib(n)} {fib(0) = 1, fib(1) = 1} gfun[rectoproc](re union inits, fib(n));
Since we're off-topic... Any sequence of numbers given by a linear recurrence equation with constant coefficients can be computed quickly using asymptotically efficient matrix operations. In fact, the code to do this can be derived automatically from the recurrence itself. Here is what you get for Fibonacci (using Maple): proc (n) local i1, loc0, loc1, loc2, tmp2, tmp1, i2; if n <= 44 then loc0 := 1; loc1 := 1; if n < 0 then error "index must be %1 or greater", 0 elif n = 0 then return loc0 elif n = 1 then return loc1 end if; for i1 to n-1 do loc2 := loc0+loc1; loc0 := loc1; loc1 := loc2 end do; loc1 else tmp2 := Matrix(2, 2, {(1, 1) = 1, (1, 2) = 1, (2, 1) = 1, (2, 2) = 0}); tmp1 := Vector(2, {(1) = 1, (2) = 1}); i2 := convert(n-1, base, 2); if i2[1] = 1 then tmp1 := Vector(2, {(1) = 2, (2) = 1}) end if; for i1 in subsop(1 = (), i2) do tmp2 := LinearAlgebra:-MatrixMatrixMultiply(tmp2, tmp2); if i1 = 1 then tmp1 := LinearAlgebra:-MatrixVectorMultiply(tmp2, tmp1) end if end do; tmp1[1] end if end proc Direct computation is done for small n, and then asymptotically fast linear algebra is used for larger n. This should be a nice Template Haskell exercise. Jacques Sebastian Fischer wrote:
[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