Is there a simple algorithm for exponentiating large numbers to large powers?

Question

I've been thinking about this for some days, a multiplication is a lot of sums, so:

$$75\times 75=\overbrace{75+75+75+75+75+75+75+75+\cdots}^{\text{75 times}}$$

But then, there is a simple algorithm that enable us to multiply without having to sum all those numbers. In the same way, exponentiation is repeated multiplication - but I wasn't taugth about such algorithm for exponentiation. I've been thinking in representing the number with a polynomial, for example:

$$1038=10^3+3\cdot 10^1+8\cdot10^0$$

Then:

$$1038^{1038}=(10^3+3\cdot 10^1+8\cdot10^0)^{1038}$$

But from here (considering what I currently know) I'd have to multiply it $1038$ times. The mentioned multiplication would be:

$$(10^3+3\cdot 10^1+8\cdot10^0)^{1038}=\overbrace{(10^3+3\cdot 10^1+8\cdot10^0)\cdot (10^3+3\cdot 10^1+8\cdot10^0)\cdot \dots}^{\text{1038 times}}$$

The first idea I had: There might be some connection with the binomial theorem, but I don't see how it fits. The second idea would be to find a way to write:

$$(10^\color{red}{3}+3\cdot 10^\color{red}{1}+8\cdot10^\color{red}{0})^{1038}$$

In which the red exponents are multiplied in some way by $1038$. There might be some connection with logarithms here, but I don't see it. And it could be the case that these techniques won't yield the results I'm looking for, so: Is there a simple algorithm for large numbers elevated to large exponents?

Answer 1

This is probably not a complete answer but still worth knowing. In general, to compute $a^n$, you do not need to multiply it $n-1$ times. You can get away with at-most $\mathcal{O}(\log_2(n))$ multiplications as shown below.

Write $1038$ in binary as $2^{10} + 2^3 + 2^2 + 2$. Now to compute $a^{1038}$, it is now sufficient to compute only $a^2$, $a^4$, $a^8$ and $a^{1024}$.

First computing $a^2$ as $a \cdot a$, which involves one multiplication.

Next compute $a^4$ as $a^2 \cdot a^2$, which involves one multiplication.

Next compute $a^8$ as $a^4 \cdot a^4$, which involves one multiplication.

and all the way upto $a^{1024}$.

So far, it has involved $10$ multiplications. Finally, put together $a^2 \cdot a^4 \cdot a^8 \cdot a^{1024}$, which involves $4$ multiplications. Hence, we only need a total of $14$ multiplications.

Answer 2

You can use the binomial theorem as follows $$(a+b+c)^n=((a+b)+c)^n=\sum{n \choose i}(a+b)^i c^{n-i}=\sum_i^n{n \choose i} c^{n-i}\sum_j^i{i \choose j}a^jb^{i-j}$$

In practice however, repeated squaring is the way to go.

Answer 3

You wanted to draw an analogy between multiplication and exponentiation, and see if efficient algorithms also exist for the later as they do for the former. There are well-known Binary algorithms for exponentiation which may appear similar to the long-multiplication.

In the long-multiplication, we break one of the integers into its component digits, and multiply the other integer with each digit one by one. Then we add these individual results (after required shifting).

For exponentiation ($a^b$), we have a few algorithms which break the exponent $b$ into its component bits (base-2 representation), and process these bits one by one, while also computing appropriate powers of $a$. Two such algorithms are Binary Exponentiation variants, which process bits of $b$ left-to-right or right-to-left. The number of multiplications are at most twice the number of bits in $b$.

What you had done is expanded $a=1038$ in its base-10 form. These binary algorithms are based on the expansion of $b$ in its base-2 form.

For details about such algorithms, one can read this and this.