3 ms·

I really like this analysis, which also discusses the “fast doubling” method: https://extratricky.com/blog/fibonacci-complexity https://extratricky.com/blog/fib

• gjm11 3y ago
  There's less to the "constant time method" thing than meets the eye. If you work modulo M for some fixed M, then the Fibonacci sequence is periodic with period at most M^2 (because if two consecutive numbers are known, so is the whole rest of the sequence), which is a constant. Therefore, for any particular M, you can just write down the at-most-M^2 repeating sequence and what the actual period is (call that p), and then for any n the algorithm goes: reduce n mod p, and then look up the result in your big lookup table. (Actually, this isn't constant-time, because if n is large then reducing it mod p isn't constant-time. For that matter, no algorithm can possibly be constant-time, because unless you pick a modulus for which the period is a power of 2 you always need to look at all the bits of n.)