On Aug 17, 2010, at 12:33 AM, Jason Dagit wrote:
So next I would use heap profiling to find out where and what type
of data the calculation is using.
I did.
I would do heap profiling and look at the types.
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]
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?
--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
