The expression X^n, for an interger power n and any X, can be computed using the following formulae, which represent a negative power in terms of a positive power (-n), and a positive power in terms of a smaller non-negative power (either n/2 or n-1), and use only multiplication and division:
X^n = 1/X^(-n) if n < 0
X ^n = I*d if n = 0
X ^n = X^(n/2) * X^(n/2) if n is even
X^n = X*X^(n-1) if n is odd.
These formulae lead to an efficient recursive algorithm for computing integer powers using the minimal number of multiplications.
(a) Write a procedure MatPow(X,n::integer) to implement this algorithm for computing powers of matrices. Test MatPow(<<1|2>,<3|4>>,12) and MatPow(<<1|2>,<3|4>>,-12).
(b) Write a procedure PolyPow(X,n::integer) to implement this algorithm for computing powers of numbers and polynomials. Your procedure needs to exapnd each product of polynomials in order to be effective. Test PolyPow(123,12), PolyPow(123,-12), PolyPow(x^2+1,12) and PolyPow(x^2+1,-12).