The well-known Fibonacci series \\(F_n\\) can be defined as follows:<\/p>\n
\\(F_n =
\n\\begin{cases}
\n0 & n = 0 \\\\
\n1 & n = 1 \\\\
\nF_{n-2} + F_{n-1} & n \\ge 2\\\\
\n\\end{cases}\\)<\/p>\n
Let’s use a few facts about matrices to find a quick way to calculate terms in this famous series.<\/p>\n
Lemma<\/strong><\/p>\n Let \\(A = \\begin{bmatrix} Proof<\/strong><\/p>\n The \\(n = 1\\) case follows immediately from the definitions of \\(A \\text{ and } F_n\\).<\/p>\n Suppose the statement is true for n. Then And our result follows by induction. QED<\/p>\n Now, notice that<\/p>\n \\(\\begin{align} Using this identity, we can write \\(F_{2n}\\) and \\(F_{2n+1}\\) in terms of \\(F_n\\) and \\(F_{n+1}\\).<\/p>\n \\(\\begin{align} \\(F_{2n+1} = F_{n}^2 + F_{n+1}^2\\)<\/p>\n We now have a way of calculating \\(F_{2n}\\) and \\(F_{2n+1}\\) by calculating only a few of the smaller terms in the sequence. This yields some wildly efficient Python code:<\/p>\n <\/code><\/p>\n And it’s fast! It’s \\(O(\\log N)\\) in fact:<\/p>\n Compare to the na\u00efve, iterative version, which is \\(O(N)\\):<\/p>\n <\/code><\/p>\n This post was inspired by a post<\/a> by Lee Phillips and as an excuse to play around with MathJax<\/a>. The best guide I found for getting started is on Stack Exchange<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":" The well-known Fibonacci series \\(F_n\\) can be defined as follows: \\(F_n = \\begin{cases} 0 & n = 0 \\\\ 1 & n = 1 \\\\ F_{n-2} + F_{n-1} & n \\ge 2\\\\ \\end{cases}\\) Let’s use a few facts about matrices to find a quick way to calculate terms in this famous series. Lemma Let \\(A … Continue reading Calculating Fibonacci Numbers, Quickly and Exactly<\/span>
\n0 & 1 \\\\
\n1 & 1
\n\\end{bmatrix}\\). Then \\(A^n = \\begin{bmatrix} F_{n-1} & F_n \\\\ F_n & F_{n+1} \\end{bmatrix}\\).<\/p>\n
\n$$\\begin{align}
\nA^{n+1} & = A^n A \\\\
\n & = \\begin{bmatrix} F_{n-1} & F_n \\\\ F_n & F_{n+1} \\end{bmatrix} \\begin{bmatrix} 0 & 1 \\\\ 1 & 1 \\end{bmatrix} \\\\
\n & = \\begin{bmatrix} F_n & F_{n-1} + F_n \\\\ F_{n+1} & F_n + F_{n+1} \\end{bmatrix} \\\\
\n & = \\begin{bmatrix} F_n & F_{n+1} \\\\ F_{n+1} & F_{n+2} \\end{bmatrix}
\n\\end{align}$$<\/p>\n
\n\\begin{bmatrix} F_{2n-1} & F_{2n} \\\\ F_{2n} & F_{2n+1} \\end{bmatrix} & = A^{2n} \\\\
\n& = A^n A^n \\\\
\n& = \\begin{bmatrix} F_{n-1} & F_n \\\\ F_n & F_{n+1} \\end{bmatrix} \\begin{bmatrix} F_{n-1} & F_n \\\\ F_n & F_{n+1} \\end{bmatrix} \\\\
\n& = \\begin{bmatrix} F_{n-1}^2 + F_n ^ 2 & F_{n-1} F_n + F_n F_{n+1} \\\\ F_{n-1} F_n + F_n F_{n+1} & F_n^2 + F_{n+1} ^ 2 \\end{bmatrix}
\n\\end{align}\\)<\/p>\n
\nF_{2n} & = F_{n-1} F_n + F_n F_{n+1} \\\\
\n& = (F_{n+1} – F_n) F_n + F_n F_{n+1} \\\\
\n& = F_n F_{n+1} – F_n^2 + F_n F_{n+1} \\\\
\n& = 2 F_{n+1} F_n – F_n ^ 2
\n\\end{align} \\)<\/p>\n<\/p>\n\r\ndef fib2(N):\r\n if N == 0: return (0, 1)\r\n half_N, is_N_odd = divmod(N, 2)\r\n f_n, f_n_plus_1 = fib2(half_N)\r\n f_n_squared = f_n * f_n\r\n f_n_plus_1_squared = f_n_plus_1 * f_n_plus_1\r\n f_2n = 2 * f_n * f_n_plus_1 - f_n_squared\r\n f_2n_plus_1 = f_n_squared + f_n_plus_1_squared\r\n if is_N_odd:\r\n return (f_2n_plus_1, f_2n + f_2n_plus_1)\r\n return (f_2n, f_2n_plus_1)\r\n\r\ndef fib(N):\r\n return fib2(N)[0]\r\n<\/pre>\n
\r\n$ pypy -m timeit -s 'import expfib' 'expfib.fib(500000)'\r\n10 loops, best of 3: 22.4 msec per loop\r\n<\/pre>\n
<\/p>\n\r\ndef fib2_linear(N):\r\n f_n, f_n_plus_1 = (0, 1)\r\n while N > 0:\r\n N -= 1\r\n f_n, f_n_plus_1 = f_n_plus_1, f_n + f_n_plus_1\r\n return (f_n, f_n_plus_1)\r\n\r\ndef fib_linear(N):\r\n return fib2_linear(N)[0]\r\n<\/pre>\n
\r\n$ pypy -m timeit -s 'import myfib' 'myfib.fib_linear(500000)'\r\n10 loops, best of 3: 2.76 sec per loop\r\n<\/pre>\n