Jacques Carette carette at mcmaster.ca
Mon Aug 16 12:03:32 EDT 2010

```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:
>
>
> 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
>
>

```