[Haskell-cafe] Question about memory usage

[Daniel Fischer]

On Monday 16 August 2010 14:37:34, Roel van Dijk wrote:
> On Sat, Aug 14, 2010 at 5:41 PM, Andrew Coppin
>
> <andrewcoppin at btinternet.com> 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