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 22:13]
will [Fast doubling]
fibonacci [2013/02/26 20:40]
will
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: $F_n = F_{n-1} + F_{n-2}$ where $F_0 = 0,\; F_1 = 1$ 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$
 +
 +Fibonacci numbers can be computed in several different ways. Here are four algorithms ordered from worst to best in time complexity.
  
 ===== Recursive ===== ===== Recursive =====
Line 33: Line 35:
  
 [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.txt ยท Last modified: 2015/02/02 08:28 (external edit)