Re: [Haskell-cafe] Question about memory usage

On Monday 16 August 2010 14:37:34, Roel van Dijk wrote:

On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin

wrote:

...

(Then again, the Fibonacci numbers can be computed in O(1) time, and nobody ever needs Fibonacci numbers in the first place, so this is obviously example code.)

A bit off-topic, but I don't think there exists a function that computes fibonacci numbers in O(1) time. There exists a closed-form expression to calculate the nth Fibonacci number, but the complexity of that expression is not O(1):

phi = (1 + sqrt 5) / 2 fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5

The use of (**) should make the complexity at least O(n).

Using Double for phi and n, that expression is calculated in constant time. If you use (^) or (^^) instead of (**) and use Int [or Integer and neglect the compexity of Integer arithmetic, assuming additions and divisions of Integers to be O(1)] for n, it's O(log n). However, whether using (**), (^) or (^^), with Double for phi, that formula gives wrong results even for rather small n (> 70 resp. > 75). You can calculate the n-th Fibonacci number in O(log n) steps using Integer arithmetic to get correct results. Multiplying two Integers with k bits takes O(k^(1+ x)) with 0 < x <= 1, the exact value of x depends on the used algorithm of course. I don't remember what's the best found so far, but x < 0.5 is reached. Since the abovementioned O(log n) steps algorithm includes multiplication of Integers with Theta(n) bits, its complexity is O(n^(1 + y)) for some y

= x.

Please correct me if I'm wrong (or sloppy).

Regards, Roel