Faster Recursive Fibonacci Numbers

SigmundV sigmundv at gmail.com
Fri May 20 06:53:34 EDT 2011


There is a nice matrix representation of consecutive Fibonacci
numbers: [[1, 1], [1, 0]] ** n = [[F_n+1, F_n], [F_n, F_n-1]]. Using
the third party mpmath module, which uses arbitrary precision floating
point arithmetic, we can calculate the n'th Fibonacci number for an
arbitrary n as follows:

import mpmath
A = mpmath.matrix([[1, 1], [1, 0]])
F = A ** n

The n'th Fibonacci number is then found as the elements [0, 1] and [1,
0] in the matrix F.

This is more expensive than the formula involving the golden ratio,
but I like the compact representation.



More information about the Python-list mailing list