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}

Math

Computation by rounding.

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