Differences

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

 fibonacci [2013/02/10 21:31]will fibonacci [2015/02/02 08:28] (current) Both sides previous revision Previous revision 2013/02/26 20:40 will 2013/02/25 21:10 will 2013/02/25 20:21 will 2013/02/25 20:20 will 2013/02/10 22:13 will [Fast doubling] 2013/02/10 21:31 will 2013/02/10 15:13 will 2013/02/10 15:12 will 2013/02/10 15:01 will 2013/02/10 14:21 will 2013/02/10 09:32 will 2013/02/09 22:59 will 2013/02/09 22:51 will 2013/02/09 16:05 will created Next revision Previous revision 2013/02/26 20:40 will 2013/02/25 21:10 will 2013/02/25 20:21 will 2013/02/25 20:20 will 2013/02/10 22:13 will [Fast doubling] 2013/02/10 21:31 will 2013/02/10 15:13 will 2013/02/10 15:12 will 2013/02/10 15:01 will 2013/02/10 14:21 will 2013/02/10 09:32 will 2013/02/09 22:59 will 2013/02/09 22:51 will 2013/02/09 16:05 will created 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 22: Line 24: ===== Fast doubling ===== ===== Fast doubling ===== + + The fast doubling method is even better, running in $O(\log(n))$ time. \[ \[ Line 31: 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]