# Algorithm Wiki

### Site Tools

This is an old revision of the document!

# Fibonacci

The Fibonacci number or sequence is:

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;$

Each number is the sum of the previous two numbers. In mathematical terms: $F_n = F_{n-1} + F_{n-2}$ where $F_0 = 0,\; F_1 = 1$

Fibonacci numbers can be computed in several different ways. Here are four algorithms ordered from worst to best in time complexity.

## Recursive

The recursive algorithm to calculate a fibonacci number is very simple and is a direct translation from the mathematical definition. Unfortunately it is very slow. It uses $O(\phi^n)$ time, where $\phi=\frac{\sqrt{5}+1}{2}$ (the golden ratio).

WARNING: Javascript math uses floating point for integers. After fib(78) the Javascript implementation of these algorithms is not exact.

## Dynamic programming

Dynamic programming is the other obvious solution. The algorithm calculates each fibonacci number in sequence. This algorithm uses $O(n)$ time.

## Fast doubling

The fast doubling method is even better, running in $O(\log(n))$ time.

\begin{aligned} F_{2n} & = F_{n}(2*F_{n+1}-F_{n}) \\ F_{2n+1} & = F_{n+1}^2+F{n}^2 \end{aligned}

## Rounding

Computation by rounding, assuming constant time mathematical operators (which is true for basic Javascript maths) runs in $O(1)$ time. See http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding for a more complete explanation.

$F_n=\bigg[\frac{\varphi^n}{\sqrt 5}\bigg],\ n \geq 0.$