Binary Powering

true

2022-04-27

Impress your friends, rapidly compute exponents

Written by: Ned

Background

Recall that $a^n$ is just $a$ multiplied by itself $n$ times $a\cdot a \cdot...\cdot a$. This means that to find $a^n$ we’d need to do $n$ multiplications. Hurray! We have linear time. But can we do better? We can.

What if we wanted to find $a^4$ ? It’s fairly easy— we just evaluate $a \cdot a \cdot a \cdot a$. But remember that by exponent laws $a^na^m = a^{n+m}$ and also that $(a^n)^m = a^{nm}$. So $a^4 = a^1a^3 = a^2a^2$. So if we want $a^4$, we can calculate $a^2 = a*a$ and then multply $a^2a^2$ to get $a^4$ in only two multiplications instead of three. Similarly, if wanted $a^3 = a^1a^2$ we could calculate $a^2$ and then multiply it by $a$—that isn’t any faster than doing it the long way, but it isn’t any slower either.

Binary Powering

Binary powering is the idea of splitting the exponent into powers to two and then multiplying the results together. For example $a^61 = a^{32+16+8+4+1}$ So we can so it in many fewer multiplications than the naive linear approach. We already have a, so we need to calculate $a^4 = (a^2)^2$ then noting that $a^2 = (a^1)^2$, $a^8 = (a^4)^2$, $a^{16} = (a^8)^2$, and $a^{32} = (a^{16})^2$ we have a total of 5 multiplications so far. Then we need to multiply the terms that we need together $a^1 a^4 a^8 a^{16}a^{32}$ to get $a^{61}$ which is another 4 multiplications. So instead of 60 multiplications 60 multiplications we have 5+4.

We can follow a similar process by breaking down any exponent $n$ in terms of its powers of two and then calculating $a^{2i}$ where $2i <= n$. Since numbers already stored as binary, we can just check where the one bits of $n$ are for a very convenient algorithm.

Efficiency

This runs in $O(\log n)$ since the sum of $n$ will contain at most $1$ of each power of 2 we have at most $\log n$ terms. Calculating up to n then requires at most $\log n$ multiplications of a, and once we have those terms, we’ll have at most $\log n$ more multiplications to actually calculate $a^n$. $O(\log n + \log n) = O(\log n)$.

A summary of the approach

Calculate $a^n$.

Calculate and store $a^{2i}$ in an array, while $2i <= n$ for $i \in \N$.

Break $n$ into a sum of powers of $2$. This is just the binary representation of n.

For every power of $2$ in the sum of $n$, multiply the associated array positions that correspond to the powers of $2$ that sum to $n$.

Return the result.

Algorithm pseudo-code

function exponent(a, n) {
    arr := [a ** 0, a]

    for (i := 1; i < n; i := i * 2) {
        tmp := arr[arr.length-1] * arr[arr.length-1]
        arr.push(tmp)
    }

    result := 1
    count = 0
    while (n > 0) {
        if (n % 2 != 0) {
            result := result * arr[count]
        }
        ++count
        n := n / 2

    }

    return result
}

Implementation (JS)

function exponent(a, n) {
    const arr = [a**0, a]

    for (let i = 1; i <= n; i = i * 2) {
        let tmp = arr[arr.length-1] * arr[arr.length-1]
        arr.push(tmp)
    }

    let result = arr[0]
    let count = 1
    while (n > 0) {
        if (n % 2 != 0) {
            result = result * arr[count]
        }
        ++count
        n = Math.floor(n / 2)

    }

    return result
}

Conclusion

I hope that was useful. Binary powering is a pretty neat trick and gives a nice introduction to creating algorithms that run in logarithmic time. It’s worth noting that in special cases ($a = 0$ or $a = 1$ for instance) checking to see what $a$ is could optimize the algorithm to avoid even the logarithmic time complexity, but even in the worst case it’s still $O(\log n)$ which is pretty good.

Generally, it would be wise to implement this with arbitrary precision arithmetic since it shines when $n$ is large, but that’s a problem for another time.