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

fibonacci [2013/02/09 22:59] will |
fibonacci [2015/02/02 08:28] |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | ====== Fibonacci ====== | ||

- | The Fibonacci number or sequence is: | ||

- | |||

- | $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: | ||

- | |||

- | $F_n = F_{n-1} + F_{n-2}$ | ||

- | |||

- | where | ||

- | |||

- | $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). | ||

- | |||

- | [algorithm fibonacci-recursive] | ||

- | |||

- | ===== Fast doubling algorithm ===== | ||

- | |||

- | |||

- | [algorithm fibonacci-doubling] |

fibonacci.txt ยท Last modified: 2015/02/02 08:28 (external edit)