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.
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.