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

ajb at spamcop.net ajb at spamcop.net
Thu Nov 8 01:03:16 EST 2007

G'day all.

I 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.

Quoting Henning Thielemann <lemming at henning-thielemann.de>:

> You mean computing the matrix power of
> /1 1\
> \0 1/
> ?

I mean all of the most efficient ones.  The Gosper-Salamin algorithm
is the matrix power algorithm in disguise, more or less.

Andrew Bromage

More information about the Haskell-Cafe mailing list