Explaining Fast Power Algorithm in Python
The aim of this page📝 is to solve LeetCode > Pow(x, n) with the help of Jeff Erikson’s Algorithms.
2 min readJan 17, 2023
The assignment says:
Implement pow(x, n), which calculates x raised to the power n (i.e., x**n).
- x is not an int
- n is an integer and can be negative
- -231 <= n <= 231–1
- -100.0 < x < 100.0
- -10⁴ <= xn <= 10⁴
EXAMPLE
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25Brute force fails, because of the limits to the size of the recursion stack
- The number of function calls increase linearly with the exponent
- This is inefficient, however a recursion stack limit on my machine is
3000
>>> import sys
>>> sys.getrecursionlimit()
3000Fast Power Algorithm is quick because the reduction step halves the remaining cases
- Fast Power is an algorithm from an Indian mathematician Pingala from the 2nd century BCE
PINGALAPOWER(base, exponent):
if exponent = 0:
return 1
else
x ⟸ PINGALAPOWER(base, floor(exponent/2))
if exponent is even
return base * base
else
return base * base * exponentSCENARIO | RESULT
-----------------------|--------------
n=0 | 1
n is > 0 AND n is even | (a^n/2)^2
n is > 0 AND n is odd | (a^[n/2])^2*a
- In brute force, the reduction step is decremental, and therefore the time complexity is linear to the size of the input here
- Here, the reduction step is logarithmic, i.e. each recursion is halving the input
- Note that, the reduction contains flooring of the halved exponent
- ..of course, an exponent can only be an integer
- ..therefore, if you halve 5, you pass 2 (5/2 => 2.5 => floored => 2)
You still need to account for negative input
- To achieve this (for example 2^-3 => 1/2³ => 1/8 => 0.125), the algorithm is wrapped in a case analysis that puts in a fraction under with
1as a numerator and an absolute value of the result as a denominator
- This is the visualized recursion stack of 3 to the 15th (14348907)
