# Differences

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]