# 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.

The assignment says:

• 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 = -2Output: 0.25000Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25`

## Brute 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()3000`

## Fast 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                    | 1n is > 0 AND n is even | (a^n/2)^2n 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 `1` as a numerator and an absolute value of the result as a denominator