What is the best way to find the trailing zeros of an exponentiation result without explicit computation?

40 Views Asked by At

I am trying to find the trailing zeros of powers using a programming language.

Computing small numbers, such as $300^2$ is straightforward. However, as both the base and exponent increase in magnitude, the computational cost escalates accordingly (think $6854000^{95671}$).

What would be a good way to find the trailing zeros of an exponentiation result without explicit computation? I do not need to get the result of $b^e$, just the trailing zeroes of the result of the operation.

1

There are 1 best solutions below

0
On BEST ANSWER

To expand on an answer given in a comment:

We can write our base as $a = 10^{m} n$ where $m$ is the number of trailing zeros it has and $n$ is the value you get when you remove them. For example, $6854000 = 10^3 \times 6854$, while $3 = 10^0 \times 3$.

Then when we exponentiate, we get $a^b = (10^m n)^b = 10^{mb} n^b$. Now $10^{mb}$ is a $1$ followed by $mb$ zeros, while $n^b$ has none, so their product will then have $mb$ trailing zeros. (Proof of all three of these statements is fairly simple and left as an exercise.)