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