User Tools

Site Tools


Differences

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

Link to this comparison view

Next revision
Previous revision
fibonacci [2013/02/09 16:05]
will created
fibonacci [2015/02/02 08:28] (current)
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)$ timewhere $\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]
fibonacci.1360454712.txt.gz · Last modified: 2015/02/02 08:24 (external edit)