I did.

All retained data is of type ARR_WORDS. Retainer profiling shows that the majority is retained by the cost center SYSTEM.

I suspected that a strict, tail recursive version of `matrixPower` may be more efficient and implemented it:

    http://github.com/sebfisch/fibonacci/blob/tailrec/Data/Numbers/Fibonacci.hs

But it's worse. Still, the only retained data is of type ARR_WORDS mostly retained by SYSTEM but even more of it now. Additional bang patterns on `square` and `times` make no difference.

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. Are (even large) Integers evaluated completely when forcing their head-normal form?

Any insight of a performance guru is welcome ;)

Cheers,

Sebastian

[off topic post scriptum]

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?