Ternary Exponentiation

In mathematics, the process of calculating $a^n$, where $a$ is the base and $n$ is the exponent, can be done in several ways. One of the most efficient methods is called binary exponentiation, which allows you to calculate $a^n$ in logarithmic time. But there is a little-known algorithm called the ternary exponentiation that also allows us to calculate $a^n$ in logarithmic time. In this post, we will discuss the difference between binary and ternary exponentiation, their implementation, and why one may be better than the other.

Say we wanted to calculate $a^n$, one way we could do this is to iterate from $1$ to $n$, multiplying the value of $a$ on every iteration:

long long pow(int a, int n) {
    long long res = 1;
    for (int i = 0; i < n; ++i) {
        res *= a;
    }
    return res;
}

This is a naive approach, and the problem with it is that it's not practical for large $a$ or $n$.

Binary exponentiation

Binary exponentiation is a trick which allows to calculate $a^n$ in logarithmic time (instead of linearly as required by the naive approach above).

If you know how this works, just skip this part.

The idea of binary exponentiation is, that we split the work using the binary representation of the exponent.

$a = 2, n = 13$

Say we wanted to calculate $a^n$

$2^{13}$ $=$ $2^{1101_2}$ $=$ $2 ^ 8$ $⋅$ $2 ^ 4$ $⋅$ $2 ^ 1$

Since the number $n$ has exactly $⌊log$$_2$ $n$⌋$+1$ digits in base $2$, we only need to perform O($log_2$ $⁡n$) multiplications, if we know the powers $a^1$, $a^2$, $a^4$, $a^8$, $…$, $a^{⌊log_2n⌋}$

So we only need to know a fast way to compute those. This is very easy, since an element in the sequence is just the square of the previous element.

$2^1 = 2$

$2^2 = (2^1)^2 = 2^2 = 4$

$2^4 = (2^2)^2 = 4^2 = 16$

$2^8 = (2^4)^2 = 16^2 = 256$

So to get the final answer for $2^{13}$, we only need to multiply three of them (skipping $2^2$ because the corresponding bit in n is not set 1101):

$2^{13} = 256⋅16⋅2 = 8192$

The final complexity of this algorithm is $O(log_2n)$: we have to compute $log⁡_2n$ powers of $a$, and then have to do at most $log_2n$ multiplications to get the final answer from them.

Implementation

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;
}

Go here Binary Exponentiation, to learn more about this technique.

Ternary exponentiation

Instead of using the binary representation of the exponent to split the work, we use the ternary representation

$a = 2, n = 7$

The ternary representation of $n$ is $21_3$, which is ($2\times3^1 + 1 \times 3^0$)

$2 ^ 7 = 2^{21_3}$ $=$ $2 ^ {2 ⋅ 3^1}$ $⋅$ $2 ^ {1⋅3^0}$ $=$ $2^6$ $⋅$ $2^1$

It may seem that we would be performing just $log_3n$ multiplications, but thats not the case.
Take the above case for example,

$2^7 = 2^6 ⋅ 2^1$
$6$ isn't a power of $3$ ($\not\exists n \in N, 3^n = 6$)

And the essence of the trick is that if we know the powers $a^1$, $a^3$, $a^9$, $…$, $a^{⌊log_3n⌋}$, we only need to perform O($log_3$ $⁡n$) multiplications. So what do we do.

The reason why in the binary exponentiation, the sum of the exponent can be represented as a sum of powers of 2 is because '$n\% 2 \in \{0,1\}$',
or in words,
the digits in a binary number is either $0$ or $1$, so when converting back to decimal we multiply a power of 2 by $0$ or by $1$, multiplying by $1$ doesn't change the result (it still remains a power of 2).

While in the ternary numbering system, '$n\%3 \in \{0,1,2\}$', if we multiply a power of $3$ by $2$ , it's no longer a power of 3, but the result can be represented as a sum of powers of $3$.

$2^6 = 2^{3+3}$

Which is also the same as $(2^3)^2$, so

$2^7 = 2^3 ⋅ 2 ^ 3 ⋅ 2 ^ 1$

Thats an extra multiplication there

We have to compute $log⁡_3n$ powers of $a$, computing each power requires $2$ multiplications $a = a \times (a \times a)$ so thats $2log_3n$ multiplications for $a$, and then we have to do at most $2log_3n$ multiplications to get the final answer.
The the final complexity of the algorithm is $O(log_3n)$

Implementation

long long ternpow(long long a, long long b) {
    long long r, res = 1;
    
    while (b) {
        r = b % 3;
        if (r == 2) res = res * a * a;
        else if (r == 1) res = res * a;
        a = a * a * a;
        b /= 3;
    }
    return res;
}

Recursive Definition:

$a^n = \begin{cases} 1 &\text{if } n == 0 \\ \left(a^{\frac{n}{3}}\right)^3 &\text{if } mod(n, 3) == 0\\ \left(a^{\frac{n - 1}{3}}\right)^3 \cdot a &\text{if } mod(n, 3) == 1\\ \left(a^{\frac{n - 2}{3}}\right)^3 \cdot a \cdot a &\text{if } mod(n, 3) == 2\\ \end{cases}$

Computing $a^b \mod m$

long long ternpow_mod(long long a, long long b, long long m) {
    a %= m;
    long long r, res = 1;
    while (b) {
        r = b % 3;
        if (r == 2) res = res * (a * a % m) % m;
        else if (r == 1) res = res * a % m;
        a = a * a % m * a % m;
        b /= 3;
    }
    return res;
}

long long binpow_mod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1; // b /= 2
    }
    return res;
}

At their worst case the ternary version performs $4log_3n$ multiplications, while the binary version does $2log_2n$ multiplications, it can be easily shown that $4log_3n > 2log_2n$

Hence the binary version should be faster.

Summary

Ternary exponentiation is a method for calculating $a^n$, where a is a base and n is an exponent, using the ternary representation of the exponent instead of the binary representation. Like binary exponentiation, it allows for the calculation of $a^n$ in logarithmic time, but it is less commonly used than binary exponentiation. The idea is to split the work using the ternary representation of the exponent and compute the powers of a using the same method as before. However, since ternary has three digits, it's more complex than binary exponentiation. It's generally not used because it's less efficient than binary exponentiation.