Fibonacci

The Fibonacci numbers 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{\phi^n}{\sqrt 5}\bigg]$

fibonacci.txt · Last modified: 2015/02/02 08:28 (external edit)