[Haskell-cafe] Question about memory usage

[Jacques Carette]

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