Comment Comment by asdftemp I really like this analysis, which also discusses the “fast doubling” method: https://extratricky.com/blog/fibonacci-complexityit points out that the bit complexity of the traditional algorithm is actually quadratic. and apparently, restricted to fixed width integers, there is a constant time method. parent asdftemp 3 years ago
it points out that the bit complexity of the traditional algorithm is actually quadratic. and apparently, restricted to fixed width integers, there is a constant time method.