nth fibonacci number in sublinear time

Question

Is there any algorithm to compute the nth fibonacci number in sub linear time?

Accepted Answer

The `n`th Fibonacci number is given by

```
f(n) = Floor(phi^n / sqrt(5) + 1/2) 
```

where

```
phi = (1 + sqrt(5)) / 2
```

Assuming that the primitive mathematical operations (`+`, `-`, `*` and `/`) are `O(1)` you can use this result to compute the `n`th Fibonacci number in `O(log n)` time (`O(log n)` because of the exponentiation in the formula).

In C#:

```
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
```

nth fibonacci number in sublinear time

Solution

Problem

Related problems