Ternary Exponentiation

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

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're performing $log_3n$ multiplications, but we're not.
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 = \{0,1\}$',
or in words,
the representation of 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 make any difference.

While in the ternary numbering system, '$n\%3 = \{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 * (a * 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 in faster.