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

Both sides previous revision Previous revision Next revision | Previous revision | ||

fibonacci [2013/02/10 09:32] 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 | + | ===== Recursive ===== |

- | | + | |

- | $F_1 = 1,\; F_2 = 1$ | + | |

- | | + | |

- | ===== Recursive algorithm ===== | + | |

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

- | ===== Fast doubling algorithm ===== | + | ===== 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] | [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.1360517562.txt.gz · Last modified: 2015/02/02 08:24 (external edit)