Binary Exponentiation

Binary exponentiation is a trick that allows us to calculate $a^n$ in $O(\log n)$ instead of $O(n)$.

Resources

• https://cp-algorithms.com/algebra/binary-exp.html

I still need to understand, this recursive relationship (Specifically how to deal with these odd powers), but I get the overall idea.

$a^n=\{\begin{array}{ll}1& n==0\\ (a^{\frac{n}{2}}{)}^2& n>0\text{ and n even}\\ (a^{\frac{n-1}{2}}{)}^2\cdot a& n>0\text{ and n odd}\end{array}$ Recursive code

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

You always get the largest power, and you halve it each time.

Iterative version (faster, duh)

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Modular Exponentiation

This is from CPH The following function calculates the value of $x^n\mathrm{mod}m$:

int modpow(int x, int n, int m) {
	if (n == 0) return 1%m;
	long long u = modpow(x,n/2,m);
	u = (u*u)%m;
	if (n%2 == 1) u = (u*x)%m;
	return u;
}