Daniel Fischer daniel.is.fischer at web.de
Mon Aug 16 09:13:41 EDT 2010

```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
```