Re: [Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.

When discussing the complexity of fib don't forget that integer operations for bignums are no longer constant time. -- Lennart On Nov 7, 2007 6:55 AM, Henning Thielemann <lemming@henning-thielemann.de> wrote:

On Tue, 6 Nov 2007 ajb@spamcop.net wrote:

...

However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms.

You mean computing the matrix power of

/1 1\ \0 1/

? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe