Question

If you understand how the above recursive algorithm to compute y^z works, you can turn it into a more efficient iterative algorithm that basically uses the same strategy (though it is not a tail recursive algorithm). Some parts of this iterative algorithm is given below. Fill in the blanks:

Power-iterative(y: number; z: non-negative integer)

1. answer=1

2. while z > 0

3.    if z is odd then answer=__________

4.    z = ________

5.    y = _________

6. return answer

Answer 1

Power-iterative(y: number; z: non-negative integer)

1. answer=1

2. while z > 0

3.    if z is odd then answer = answer * y

4.    z = z/2 // now number is even

5.    y = y*y // change y to y^2

6. return answer

/* C Program */

#include <stdio.h>

/* Iterative Function to calculate (x^y) in O(log y) */
int power(int x, unsigned int y)
{
   int res = 1;   // Initialize result

  
   while (y > 0)
   {
       // If y is odd, multiply x with result
       if (y % 2)
           res = res*x;

       // y must be even now
       y = y/2;
       x = x*x;
   }
   return res;
}

// Driver program to test above functions
int main()
{
int x = 2;
int y = 5;
int p = 13;
printf("Power is %u", power(x, y));
return 0;
}
/* Output */

Power is 32