Binary Exponentiation

This is how we do super fast exponents, i.e. powers.

Let’s say that we want to calculate $x^n$. Binary exponentiation will divide $n$ by 2 recursively. For example,

$$\begin{array}{r}{3}^9=3\times (3^4{)}^2=3\times ((3^2{)}^2{)}^2\end{array}$$

So the recursive formula is:

$$x^n=\{\begin{array}{ll}1& \text{if }n==0\\ (x^2{)}^{n/2}& \text{if }n>0\text{ and }n\text{ even}\\ x\times (x^2{)}^{(n-1)/2}& \text{if }n>0\text{ and }n\text{ odd}\end{array}$$

In terms of code:

def pow(x, n):
	if n == 0: return 1.0
	# if n is -ve, we need to take reciprocals
	if n < 0: return 1/pow(x, -n)
	# if even, we just divide
	if n % 2 == 0:
		return pow(x*x, n/2)
	# if odd, we take out one of x
	else:
		return x * pow(x*x, (n-1)/2)