Is there a faster way to compute the nth Fibonacci number than by fib2 (page 4)? One idea...

Is there a faster way to compute the nth Fibonacci number than by fib2 (page 4)? One idea involves matrices.

We start by writing the equations F1 = F1 and F2 = F0 + F1 in matrix notation:

So, in order to compute Fn, it suffices to raise this 2 x 2 matrix, call it X, to the nth power.

(a) Show that two 2 x 2 matrices can be multiplied using 4 additions and 8 multiplications.

But how many matrix multiplications does it take to compute Xn?

(b)   Show that O (log n) matrix multiplications suffice for computing Xn. (Hint: Think about computing X8.)

Thus the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is just O(log n), as compared to O(n) for fib2. Have we broken another exponential barrier?

The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time of fib2 becomes O (n2).

(c)    Show that all intermediate results of fib3 are O (n) bits long.

(d)   Let M(n) be the running time of an algorithm for multiplying n-bit numbers, and assume that M(n) = O (n2) (the school method for multiplication, recalled in Chapter 1, achieves this). Prove that the running time of fib3 is O (M(n) log n).

(e)    Can you prove that the running time of fib3 is O (M(n))? Assume M (n) = Θ(na) for some 1 ≤ a ≤ 2. (Hint: The lengths of the numbers being multiplied get doubled with every squaring.)