[Haskell-cafe] Question about memory usage

[Daniel Fischer]

On Tuesday 17 August 2010 08:59:29, Sebastian Fischer wrote:
>
> I wonder whether the numbers in a single step of the computation
> occupy all the memory or whether old numbers are retained although
> they shouldn't be.

BTW, what sort of memory usage are we talking about here?
I have now tried your code and I didn't find the memory usage too extreme.
Be aware that fib (10^8) requires about 70 million bits and you need 
several times that for the computation.
If you actually print out the entire number, the String will of course 
require an enormous amount of memory.

Concerning the effect of strictifying, at least part of it is due to the 
fact that with a strict matrix, you need to make a few more multiplications 
of large Integers, those take time and the results occupy more space than 
the thunks. Considering that the recursion isn't deep (you simply don't 
have the memory to calculate fib (2^64)), laziness hasn't the chance to 
cause a space leak here, so bangifying doesn't help.

> Are (even large) Integers evaluated completely when
> forcing their head-normal form?

Yes, when you force the weak head normal form of an Integer, it is 
completely evaluated.

>
> Any insight of a performance guru is welcome ;)
>
> Cheers,
> Sebastian
>
> [off topic post scriptum]
>
> On Aug 16, 2010, at 6:03 PM, Jacques Carette wrote:
> > 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.
>
> This is neat. Is it always M^n for some matrix M? How does it work?

Yes, it's always M^n.

If the relation is

a_n = c_1*a_(n-1) + ... + c_k*a_(n-k)

you have the k×k matrix

c_1 c_2 ... c_(k-1) c_k
1 0 ...    0 0
0 1 0 ... 0 0
0 0 1 0 ... 0
0 ... 0 1 0 0
0 ... 0 0 1 0

to raise to the n-th power, multiply the resulting matrix with the vector 
of initial values (a_(k-1), a_(k-2), ..., a_0) and take the last component 
(a propos of this, your Fibonacci numbers are off by one, fib 0 = 0, fib 9 
= 34, fib 10 = 55).

It works because 
M*(a_(n-1), ..., a_(n-k))
= (c_1*a_(n-1) + ... + c_k*a_(n-k), a_(k-1), ..., a_(n-(k-1)))
= (a_n, a_(n-1), ..., a_(n-(k-1)))

However, for large k, this isn't particularly efficient since standard 
matrix multiplication is O(k^3). These matrices have a special structure 
that allows doing a multiplication in O(k^2).
You might want to look into the Cayley-Hamilton theorem for the latter.