Re: [Haskell-cafe] Question about memory usage

On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote:

That is an interesting trick. So there exists an algorithm that calculates Fibonacci numbers in O(log n) time.

This is what my program does. But it's only O(long n) if you assume multiplication is constant time (which it is not for large numbers). Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)