Efficiently implement power function – Iterative and Recursive
Given two integers, x and n, where n is non-negative, efficiently compute the power function pow(x, n).
For example,
pow(-3, 4) = 81
pow(5, 0) = 1
pow(-2, 3) = -8
1. Naive Iterative Solution
A simple solution to calculate pow(x, n) would multiply x exactly n times. We can do that by using a simple for loop. This is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <stdio.h> // Naive iterative solution to calculate `pow(x, n)` long power(int x, unsigned n) { // initialize result by 1 long pow = 1L; // multiply `x` exactly `n` times for (int i = 0; i < n; i++) { pow = pow * x; } return pow; } int main(void) { int x = -2; unsigned n = 10; printf("pow(%d, %d) = %d", x, n, power(x, n)); return 0; } |
Output:
pow(-2, 10) = 1024
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { // Naive iterative solution to calculate `pow(x, n)` public static long power(int x, int n) { // initialize result by 1 long pow = 1L; // multiply `x` exactly `n` times for (int i = 0; i < n; i++) { pow = pow * x; } return pow; } public static void main(String[] args) { int x = -2; int n = 10; System.out.println("pow(" + x + ", " + n + ") = " + power(x, n)); } } |
Output:
pow(-2, 10) = 1024
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Naive iterative solution to calculate `pow(x, n)` def power(x, n): # initialize result by 1 pow = 1 # multiply `x` exactly `n` times for i in range(n): pow = pow * x return pow if __name__ == '__main__': x = -2 n = 10 print(f'pow({x}, {n}) =', power(x, n)) |
Output:
pow(-2, 10) = 1024
The time complexity of the above solution is O(n).
2. Using Divide and Conquer
We can recursively define the problem as:
n is evenpower(x, n) = x × power(x, n / 2) × power(x, n / 2); // if
n is odd
Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <stdio.h> // Naive recursive solution to calculate `pow(x, n)` // using divide-and-conquer long power(int x, unsigned n) { // base condition if (n == 0) { return 1L; } if (n & 1) { // if `n` is odd return x * power(x, n / 2) * power(x, n / 2); } // otherwise, `n` is even return power(x, n / 2) * power(x, n / 2); } int main(void) { int x = -2; unsigned n = 10; printf("pow(%d, %d) = %d", x, n, power(x, n)); return 0; } |
Output:
pow(-2, 10) = 1024
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Main { // Naive recursive solution to calculate `pow(x, n)` // using divide-and-conquer public static long power(int x, int n) { // base condition if (n == 0) { return 1L; } if ((n & 1) == 1) { // if `n` is odd return x * power(x, n / 2) * power(x, n / 2); } // otherwise, `n` is even return power(x, n / 2) * power(x, n / 2); } public static void main(String[] args) { int x = -2; int n = 10; System.out.println("pow(" + x + ", " + n + ") = " + power(x, n)); } } |
Output:
pow(-2, 10) = 1024
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Naive recursive solution to calculate `pow(x, n)` # using divide-and-conquer def power(x, n): # base condition if n == 0: return 1 if n & 1: # if `n` is odd return x * power(x, n // 2) * power(x, (n // 2)) # otherwise, `n` is even return power(x, n // 2) * power(x, (n // 2)) if __name__ == '__main__': x = -2 n = 10 print(f'pow({x}, {n}) =', power(x, n)) |
Output:
pow(-2, 10) = 1024
The time complexity of the above solution is O(n).
3. Optimized Divide and Conquer Solution
The problem with the above solution is that the same subproblem is computed twice for each recursive call. We can optimize the above function by computing the solution of the subproblem once only.
The implementation can be seen below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> // Optimized recursive solution to calculate `pow(x, n)` // using divide-and-conquer long power(int x, unsigned n) { // base condition if (n == 0) { return 1L; } // calculate subproblem recursively int pow = power(x, n / 2); if (n & 1) { // if `y` is odd return x * pow * pow; } // otherwise, `y` is even return pow * pow; } int main(void) { int x = -2; unsigned n = 10; printf("pow(%d, %d) = %d", x, n, power(x, n)); return 0; } |
Output:
pow(-2, 10) = 1024
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Main { // Optimized recursive solution to calculate `pow(x, n)` // using divide-and-conquer public static long power(int x, int n) { // base condition if (n == 0) { return 1L; } // calculate subproblem recursively long pow = power(x, n / 2); if ((n & 1) == 1) { // if `y` is odd return x * pow * pow; } // otherwise, `y` is even return pow * pow; } public static void main(String[] args) { int x = -2; int n = 10; System.out.println("pow(" + x + ", " + n + ") = " + power(x, n)); } } |
Output:
pow(-2, 10) = 1024
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# Optimized recursive solution to calculate `pow(x, n)` # using divide-and-conquer def power(x, n): # base condition if n == 0: return 1 # calculate subproblem recursively pow = power(x, n // 2) if n & 1: # if `y` is odd return x * pow * pow # otherwise, `y` is even return pow * pow if __name__ == '__main__': x = -2 n = 10 print(f'pow({x}, {n}) =', power(x, n)) |
Output:
pow(-2, 10) = 1024
The time complexity of the above solution is O(log(n)).
4. Using Low-Level Programming (Binary Operators)
We can also use binary operators to compute pow(x, n) in O(log(n)) time.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <stdio.h> // Iterative function to calculate `pow(x, n)` using // binary operators long power(int x, unsigned n) { // initialize result by 1 long pow = 1L; // loop till `n` become 0 while (n) { // if `n` is odd, multiply the result by `x` if (n & 1) { pow *= x; } // divide `n` by 2 n = n >> 1; // multiply `x` by itself x = x * x; } // return result return pow; } int main(void) { int x = -2; unsigned n = 10; printf("pow(%d, %d) = %d", x, n, power(x, n)); return 0; } |
Output:
pow(-2, 10) = 1024
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Main { // Iterative function to calculate `pow(x, n)` using binary operators public static long power(int x, int n) { long pow = 1L; // loop till `n` become 0 while (n > 0) { // if `n` is odd, multiply the result by `x` if ((n & 1) == 1) { pow *= x; } // divide `n` by 2 n = n >> 1; // multiply `x` by itself x = x * x; } // return result return pow; } public static void main(String[] args) { int x = -2; int n = 10; System.out.println("pow(" + x + ", " + n + ") = " + power(x, n)); } } |
Output:
pow(-2, 10) = 1024
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# Iterative function to calculate `pow(x, n)` using binary operators def power(x, n): pow = 1 # loop till `n` become 0 while n: # if `n` is odd, multiply the result by `x` if n & 1: pow *= x # divide `n` by 2 n = n >> 1 # multiply `x` by itself x = x * x # return result return pow if __name__ == '__main__': x = -2 n = 10 print(f'pow({x}, {n}) =', power(x, n)) |
Output:
pow(-2, 10) = 1024
The time complexity of the above solution is O(log(n)).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)