Constant time fibonacci is derived as an example for linear basis change in the superb book "Vector Calculus, Linear Algebra, and Differential Forms: A Unified

Constant time fibonacci is derived as an example for linear basis change in the superb book "Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach". It's all contained in the sample pages http://matrixeditions.com/VC5.Chap2.219-221.pdf http://matrixeditions.com/VC5.Chap2.219-221.pdf However, even though the formula is O(1), the runtime of the algorithm might be larger. Simply because a standard 64bit integer might be too small. And the BigNum implementation needs more time to multiply all the bits.