Code: https://github.com/ikriv-samples/logarthmic-fibonacci.

Fibonacci sequence is defined as a sequence starting with 0, 1 where each subsequent member is calculated as `fib(n) = fib(n-1)+fib(n-2)`

. This yields an infinite sequence 0, 1, 1, 2, 3, 5, 8, 13, …

This repository compares several approaches to calculating n*th* Fibonacci number:

- A naïve recursive solution
- A simple linear solution
- A solution that runs in logarithmic time

# Running The Samples

`python main.py {algorithm} n`

Algorithm can be one of `linear`

, `recursive`

, or `logarithmic`

. If the algorithm is omitted, `logarthmic`

is used.

# Naïve Solution

It is very easy to program Fibonacci sequence exactly as defined, but it leads to a slow and inefficient solution:

def fib(n: int) -> int: if n==0: return 0 if n==1: return 1 return fib(n-1)+fib(n-2)

This solution has exponential runtime, so it hits extremely long calculation times for relatively small values of n. On my machine `python main.py recursive 40`

takes over 20 seconds.

# Linear Solution

def fib(n: int) -> int: if n==0: return 0 if n==1: return 1 prev,current=0,1 for i in range(n-1): prev,current=current,prev+current return current

This solution works well up to n=100,000 or so, but then it starts to lag.

# Logarithmic Solution

This solution is based on the fact that 2×2 matrix

```
| 1 1 |
A = | |
| 1 0 |
```

when raised to the power of n yields

```
| fib(n+1) fib(n) |
A**n == | |
| fib(n) fib(n-1) |
```

## Proof

The above property can be proved by induction. It is obviously true for n=1. Now, supposed it is true for n=k, so

```
| fib(k+1) fib(k) |
A**k == | |
| fib(k) fib(k-1) |
```