User Tools

Site Tools


Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
fibonacci [2013/02/10 14:21]
will
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:
  
 $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]
fibonacci.1360534866.txt.gz · Last modified: 2015/02/02 08:24 (external edit)