In mathematics, the process of calculating an, 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 an in logarithmic time. But there is a little-known algorithm called the ternary exponentiation that also allows us to calculate an 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 an, 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 an 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 an
213 = 211012 = 28 ⋅ 24 ⋅ 21
Since the number n has exactly ⌊log2 n⌋+1 digits in base 2, we only need to perform O(log2 n) multiplications, if we
know the powers a1, a2, a4, a8, …, a⌊log2n⌋
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.
21=2
22=(21)2=22=4
24=(22)2=42=16
28=(24)2=162=256
So to get the final answer for 213, we only need to multiply three of them (skipping 22 because the corresponding bit in n is not set 1101):
213=256⋅16⋅2=8192
The final complexity of this algorithm is O(log2n): we have to compute log2n powers of a, and then have to do at most log2n 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 213, which is (2×31+1×30)
27=2213 = 22⋅31 ⋅ 21⋅30 = 26 ⋅ 21
It may seem that we would be performing just log3n multiplications, but thats not the case.
Take the above case for example,
27=26⋅21
6 isn't a power of 3 (∃n∈N,3n=6)
And the essence of the trick is that if we know the powers a1, a3, a9, …, a⌊log3n⌋, we only need to perform O(log3 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 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∈{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.
26=23+3
Which is also the same as (23)2, so
27=23⋅23⋅21
Thats an extra multiplication there
We have to compute log3n powers of a, computing each power requires 2 multiplications a=a×(a×a) so thats 2log3n multiplications for a, and then we have to do at most 2log3n multiplications to get the final answer.
The the final complexity of the algorithm is O(log3n)
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:
an=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧1(a3n)3(a3n−1)3⋅a(a3n−2)3⋅a⋅aif n==0if mod(n,3)==0if mod(n,3)==1if mod(n,3)==2
Computing abmodm
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;
}
return res;
}
At their worst case the ternary version performs 4log3n multiplications, while the binary version does 2log2n multiplications, it can be easily shown that
4log3n>2log2n
Hence the binary version should be faster.
Summary
Ternary exponentiation is a method for calculating an, 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 an 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.