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

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.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 | 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
`1`

as a numerator and an absolute value of the result as a denominator

- This is the visualized recursion stack of 3 to the 15th (14348907)