User Tools

Site Tools


Differences

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

Link to this comparison view

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)