Question

4. (15 points) Give an algorithm that takes as input a positive integer n and a number x, and computes xn (i.e., x raised to the power n) by performing O(lgn) multiplications. Your algorithm CANNOT use the exponentiation operation, and may use only the basic arithmetic operations (addition, subtraction, multiplication, division, modulo). Moreover, the total number of basic arithmetic operations used should be O(lgn).

Answer 1

The algorithm is as follows:

Exponent(x, n):

if(n == 0):

return 1

pr = Exponent(x, int(n / 2))

if (n % 2 == 0):

Return pr* pr

else:

if(n > 0):

Return x * pr* pr

else:

Return (pr* pr) / x

Step-by-step explanation:

In order to get a O(log n) time complexity, a recursive procedure is implemented by the algorithm

The algorithm begins here

Exponent(x, n):

If n is 0, the procedure returns 1

if(n == 0):

return 1

This recursively calculates the product of x, n/2 times

pr= Exponent(x, int(n / 2))

If n is even, the square of prod (above) is calculated

if (n % 2 == 0):

Return pr* pr

If otherwise (i.e. odd)

else:

If n is above 0, the square of prod multiplied by x is calculated

if(n > 0):

Return x * pr* pr

If otherwise, the square of prod divide by x is calculated

else:

Return (
`pr* pr`) / x

The time complexity is: O(log|n|)