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_1 = 1,\; F_2 = 1$

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 are 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

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