It's interesting to note that if you add a modulus to the calculation (i.e. if you calculate F(n) mod M), you can calculate ridiculously large values using the

It's interesting to note that if you add a modulus to the calculation (i.e. if you calculate F(n) mod M), you can calculate ridiculously large values using the matrix/doubling method. You can, for instance, calculate the last 10 digits of the Googolth Fibonacci number instantly (since you only need O(log n) multiplications, it's just a few hundred for 10^100 ). Doing it the "naive" dynamic programming way, it would take you far longer than the age of the universe. It's a neat illustration of asymptotic running times.