**This is an old revision of the document!**

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.

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 is the other obvious solution. The algorithm calculates each fibonacci number in sequence. This algorithm uses $O(n)$ time.

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} \]

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.$

fibonacci.1361855408.txt.gz · Last modified: 2015/02/02 08:24 (external edit)