# Differences

This shows you the differences between two versions of the page.

 fibonacci [2013/02/09 16:05]will created fibonacci [2015/02/02 08:28] (current) 2013/02/26 20:40 will 2013/02/25 21:10 will 2013/02/25 20:21 will 2013/02/25 20:20 will 2013/02/10 22:13 will [Fast doubling] 2013/02/10 21:31 will 2013/02/10 15:13 will 2013/02/10 15:12 will 2013/02/10 15:01 will 2013/02/10 14:21 will 2013/02/10 09:32 will 2013/02/09 22:59 will 2013/02/09 22:51 will 2013/02/09 16:05 will created Next revision Previous revision 2013/02/26 20:40 will 2013/02/25 21:10 will 2013/02/25 20:21 will 2013/02/25 20:20 will 2013/02/10 22:13 will [Fast doubling] 2013/02/10 21:31 will 2013/02/10 15:13 will 2013/02/10 15:12 will 2013/02/10 15:01 will 2013/02/10 14:21 will 2013/02/10 09:32 will 2013/02/09 22:59 will 2013/02/09 22:51 will 2013/02/09 16:05 will created Line 1: Line 1: ====== Fibonacci ====== ====== Fibonacci ====== - The Fibonacci ​number ​or sequence is: + The Fibonacci ​numbers ​or sequence is: - $1,​\;​1,​\;​2,​\;​3,​\;​5,​\;​8,​\;​13,​\;​21,​\;​34,​\;​55,​\;​89,​\;​144,​\;​ \ldots\;$ + $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: + 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$ - $F_n = F_{n-1} + F_{n-2}$ + Fibonacci numbers can be computed in several different ways. Here are four algorithms ordered from worst to best in time complexity. - where + ===== Recursive ===== - $F_1 = 1,\; F_2 = 1$ + 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). - ===== Recursive Algorithm ===== + WARNING: [[Javascript math]] uses floating point for integers. After fib(78) ​the Javascript implementation of these algorithms ​is not exact. - + - The recursive algorithm to calculate a fibonacci number is very simple and copied directly from the mathematics. Unfortunately it is very slow. + [algorithm fibonacci-recursive] [algorithm fibonacci-recursive] + + ===== Dynamic programming ===== + + Dynamic programming is the other obvious solution. The algorithm calculates each fibonacci number in sequence. This algorithm uses $O(n)$ time. + + [algorithm fibonacci-dynamic] + + ===== 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} + + + [algorithm fibonacci-doubling] + + ===== 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]$ + + [algorithm fibonacci-rounding]