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