I've been thinking about this a bit and concluded (surprisingly!) that it is probably not an asymptotic speed up!
First thoughts: The memoization algorithm is linear in n, and the repeated squaring algorithm is logarithmic in n, so the second one is faster.
Second thoughts: Fibonacci numbers grow exponentially, so we should consider the speed of actually adding and multiplying them. Adding is linear in the number of digits, so linear in n (because F(n) grows exponentially). Multiplication is quadratic in n! The memoization algorithm is repeated adding, so we get an extra linear factor, total complexity O(n^2). The repeated squaring uses multiplication, so we get an extra quadratic factor, total complexity O(n^2 log n). The first is faster!
Third thoughts: the fastest known algorithm for multiplying numbers is actually O(n log n) in the number of digits. We're down to O(n log n log n). The second is faster! That's probably terribly impractical, but there are apparently multiplication algorithms that are less impractical, with a smaller exponent than 2, so still an improvement over the first method.
But without specialized multiplication routines, the first is asymptotically faster.
As an unimportant bit of trivia, that's only true on the non-existent platforms with O(1) bignum operations. The output size is exponential in the input, guaranteeing that any non-approximate answer requires O(exp(n)) computations to produce on a real-world register machine.
matheist|1 year ago
First thoughts: The memoization algorithm is linear in n, and the repeated squaring algorithm is logarithmic in n, so the second one is faster.
Second thoughts: Fibonacci numbers grow exponentially, so we should consider the speed of actually adding and multiplying them. Adding is linear in the number of digits, so linear in n (because F(n) grows exponentially). Multiplication is quadratic in n! The memoization algorithm is repeated adding, so we get an extra linear factor, total complexity O(n^2). The repeated squaring uses multiplication, so we get an extra quadratic factor, total complexity O(n^2 log n). The first is faster!
Third thoughts: the fastest known algorithm for multiplying numbers is actually O(n log n) in the number of digits. We're down to O(n log n log n). The second is faster! That's probably terribly impractical, but there are apparently multiplication algorithms that are less impractical, with a smaller exponent than 2, so still an improvement over the first method.
But without specialized multiplication routines, the first is asymptotically faster.
hansvm|1 year ago