Fibonacci numbers. There is an alternative way of computing Fibonacci numbers involving

matrices. Note that we have: Fn

Fn$+1$

$=$

$01$

$11$

$$

Fn$1$

Fn

$.$

If we write the latter equation recursively, we can get

Fn

Fn$+1$

$=$

$01$

$11$

n F$0$

F$1$

$.$ Let X $=$

$01$

$11$

$.$

$($a$)$ Show that two $2\backslash$times $2$ matrices can be multiplied using $4$ additions and $8$ multiplications.

$($b$)$ Show that for all i $<$ n$,$ all entries of Xi have O$($n$)$ bits. $($Hint: Consider the effect of each matrix

multiplication on the bit count$).$

$($c$)$ The following recursive algorithm can be used to efficiently compute Xn$.$

Show that the running time of this algorithm is O$($M$($n$)$ log n$),$ where M$($n$)$ is the time it takes to

multiply two n$-$bit numbers. $($Hint: first show that there are O$($log n$)$ recursive calls, and then show

each call takes at most O$($M$($n$)),$ you may use the results of parts $($a$)$ and $($b$)$ to show the latter$).$Algorithm $4$ matrix$($X$,$n$)$

Input: X $,$ n

if n $=1$ then

return X

end if

if n is even then

Z $=$ matrix$($X$,$ n

$2)$

return Z $$ Z

end if

if n is odd then

Z $=$ matrix$($X$,$ n$1$

$2)$

return Z $$ Z $$ X

end if

Output: matrix$($X$,$n$)$