# Different ways to calculate fibonacci numbers

15 Mar 2014**NOTE**: All code below are written in a dialect of Scheme called Racket.

## Naive approach

Problem: exponential complexity, even can’t calculate *(fibonacci 1000)*.

## Improved approach

This version is not only faster, but also takes constant space, as the tail recursion can be optimized by compiler.

Problem: if *(fibonacci 1000)* is called twice, it performs the same computation twice!

## Memoization

Idea: Use a table to remember computation resutls.

## Even faster

Idea: A faster approach to compute is to compute , which only requires 4 steps of computation. If the power *n* is large, it can reduce the complexity logarithmically.

In the *fibonacci-iter* above, the operation *a’ = b* and *b’ = a + b* is performed *n* times, which is equivalent to multiply the matrix *n* times. This fact allows us to perform the same optimization as in computing exponentiation.

You can verify that computes the n-th and (n+1)-th fibonacci numbers. The multiplier vector just selects the element *c* and *d* from the result matrix , so it can be omitted, as whenever we know the matrix, we know the result.

Another useful fact is that in the result matrix we have *b = c* and *d = a + b*. So the matrix can be written as .

Also note that according to matrix multiplication, following formula holds:

where and .

From the mathematical facts above, the implementation comes naturally.

The version above works, but we can do better to use tail recursion.

The improved version utilizes another mathematical fact:

where and .

It’s also helpful to know that for any integer *n* and matrix *X*:

where is either 0 or 1.

The formula above means that is the binary representation of *n*. The improved version uses *p* and *q* to accumulate the result of the first *i* terms, *a* and *b* remembers . If *n* can be divided by *2* for *i* times, it means the *i*-th position of n(i.e. ) is 0, then *i* can be increased, accumulator unchanged. Otherwise, it means the *i*-th position of n(i.e. ) is 1, then the accumulator *p* and *q* is updated, and *i* will be increased in the next recursion call as we’ve changed the last bit in to *0* through *n - 1*. The process stops if *n* is equal to zero, which means for every *i* bigger than its current value, is zero.

The complexity of this fast method is , compared to of the second approach above.

## Reference

- SCIP
*section 1.2 and 3.3*