The "compute the eigenvalues of Matrix([[1,1],[1,0]]) raised to the power N" approach to computing the Nth Fibonacci number is only constant time if you assume

The "compute the eigenvalues of Matrix([[1,1],[1,0]]) raised to the power N" approach to computing the Nth Fibonacci number is only constant time if you assume exponentiation is constant time, which it is not on any computer or realistic model of computation. I still think this is a really cool technique though, even if it only works in "math land." http://bit.ly/fib_using_eigenvals http://bit.ly/fib_using_eigenvals