We are going to learn about how it can be optimized or make the fast computation of the power of numbers as compared to the traditional method using Python.
What is Exponentiation?
It is a mathematical operation in which we compute the expression ab by repeating the multiplication of a by b a number of times. Where ‘a’ is known as base and ‘b’ is known as power. Let’s take an example of exponentiation as explained below:
Example:
Let’s assume we have to calculate the 54. So 54 can be expanded by multiplying the 5 itself 4 times as number mentioned in the superscript(or power) as explained below:-
Base = 5, Power = 4
54 = 5*5*5*5 = 625
Fast Exponentiation in Python
Fast Exponentiation is the optimization of the traditional methods of computing the powers. Optimization can be done by reducing extra iteration from the for-loop conditional statement. Let’s understand the implementation. We will optimize by two methods:
- By using the pow() function from the Math module
- Without using the pow() function.
- By using divide and conquer method
Fast Exponentiation using pow() function
Here, we are computing the half power for the optimization method, e.g. if we have to calculate 54 then we calculate 52. If the power is odd then one value gets multiple with remain result to get the desired result.
Python3
def optimize(val, power): result = pow(val, power//2) result = result * result if power % 2 != 0: result = result * val return resultcal = optimize(2, 5)print(cal) |
Output:
32
Time Complexity: O(log n)
Auxiliary Space: O(1)
Fast Exponentiation without using pow() function
In this, we are optimizing without using the power function. If the power is positive it means we have to multiply it directly, and if the power is negative we will have to multiply the 1/val repeatedly. Here we have reduced the number of iterations from the exponentiation to optimize the code for larger numbers.
Python3
def optimize(val, power): result = 1 if val == 0: return 0 if power > 0: for i in range(1, (power//2)+1): result = result * val result = result * result if power % 2 != 0: result = result * val elif power < 0: for i in range(1, ((-power//2) + 1)): result = result * 1/val result = result * result if power % 2 != 0: result = result * 1/val else: pass return resultcal = optimize(2, -2)print(cal) |
Output:
0.25
Time Complexity: O(power/2)
Auxiliary Space: O(1)
Fast Exponentiation using: the divide and conquer method
In this approach, we will be dividing the exponent into the subproblem and will multiply the number by calling the function recursively.
Python3
# Function to calculate x raised to the power y in O(logn)def power(x, y): temp = 0 if(y == 0): return 1 temp = power(x, int(y / 2)) if y % 2 == 0: return temp * temp else: return x * temp * tempresult1 = power(2, 5)print(result1) result2 = power(3, 6)print(result2) # This code is contributed by Aditya Sharma |
32 729
Time Complexity: O(log n)
Auxiliary Space: O(log n)
