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.