# Differences

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

 fibonacci [2013/02/10 14:21]will fibonacci [2015/02/02 08:28] (current) Both sides previous 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 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: $0,​\;​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 + - + - $F_1 = 1,\; F_2 = 1$ + ===== Recursive ===== ===== 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). 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. [algorithm fibonacci-recursive] [algorithm fibonacci-recursive] ===== Dynamic programming ===== ===== 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] [algorithm fibonacci-dynamic] Line 25: Line 25: ===== Fast doubling ===== ===== 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] [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]