$($Optional for $2\%$ extra credit: An algorithm with logarithmic efficiency$)$

Now we want to get better efficiency for the Fibonacci numbers. A new property

is needed to achieve this goal. From our textbook, we have the following matrix

formula,

$\left[\begin{array}{cc}F(n-1)& F(n)\\ F(n)& F(n+1)\end{array}\right]={\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}^n,$ for $,n1.$

In order to apply this formula, you need to know how to calculate the matrix

multiplication. To calculate the powers of a matrix as fast as possible, we can

use the repeated squaring technique. We still use the Java BigInteger class to do

calculation for this part. If you use Python, it can handle big integers automatically

without any special treatment.

You still pass the problem size $n$ as before. If $n$ is not provided, use the default

value $n=1000.$

For each of your program$/$method$,$ write appropriate messages for the users to under$-$

stand what you are doing.