Write an iterative O(Log y) function for pow(x, y)

Software Development
#1

Hello Everyone,

Given an integer x and a positive number y, write a function that computes xy under following conditions.
a) Time complexity of the function should be O(Log y)
b) Extra Space is O(1)
Examples:

Input: x = 3, y = 5 Output: 243 Input: x = 2, y = 5 Output: 32

Following is implementation to compute xy.

  • C
  • Java
  • Python3
  • C#
  • PHP
  • Javascript

// Iterative C program to implement pow(x, n)

#include <stdio.h>

/* Iterative Function to calculate (x^y) in O(logy) */

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 & 1)

res = res * x;

// n must be even now

y = y >> 1; // y = y/2

x = x * x; // Change x to x^2

}

return res;

}

// Driver program to test above functions

int main()

{

int x = 3;

unsigned int y = 5;

printf ( "Power is %d" , power(x, y));

return 0;

}

Output:

Power is 243

Extra Note: In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n -th approximation is derived from the previous ones. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method. An iterative method is called convergent if the corresponding sequence converges for given initial approximations. A mathematically rigorous convergence analysis of an iterative method is usually performed; however, heuristic-based iterative methods are also common.