For base 3:
3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...
That is the units digit has only 4 possibilities and then it repeats in ever the same cycle.
With the help of Euler's theorem we can show that this holds for any integer n, meaning their units digit will repeat after at most 4 consecutive exponents. Looking only at the units digit of an arbitrary product is equivalent to taking the remainder of the multiplication modulo 10, for example:
2^7 % 10 = 128 % 10 = 8
It can also be shown (and is quite intuitive) that for an arbitrary base, the units digit of any power will only depend on the units digit of the base itself - that is 2013^2013 has the same units digit as 3^2013.
We can exploit both facts to come up with an extremely fast algorithm (thanks for the help - with kind permission I may present a much faster version).
The idea is this: As we know that for any number 0-9 there will be at most 4 different outcomes, we can as well store them in a lookup table:
{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4,
5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }
That's the possible outcomes for 0-9 in that order, grouped in fours. The idea is now for an exponentiation n^a to
- first take the base mod 10 => :=
i
- go to index
4*i in our table (it's the starting offset of that particular digit)
- take the exponent mod 4 => :=
off (as stated by Euler's theorem we only have four possible outcomes!)
- add
off to 4*i to get the result
Now to make this as efficient as possible, some tweaks are applied to the basic arithmetic operations:
- Multiplying by 4 is equivalent to shifting two to the left ('<< 2')
- Taking a number
a % 4 is equivalent to saying a&3 (masking the 1 and 2 bit, which form the remainder % 4)
The algorithm in C:
static int table[] = {
0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4,
5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};
int /* assume n>=0, a>0 */
unit_digit(int n, int a)
{
return table[((n%10)<<2)+(a&3)];
}
Proof for the initial claims
From observing we noticed that the units digit for 3^x repeats every fourth power. The claim was that this holds for any integer. But how is this actually proven? As it turns out that it's quite easy using modular arithmetic. If we are only interested in the units digit, we can perform our calculations modulo 10. It's equivalent to say the units digit cycles after 4 exponents or to say
a^4 congruent 1 mod 10
If this holds, then for example
a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10
that is, a^5 yields the same units digit as a^1 and so on.
From Euler's theorem we know that
a^phi(10) mod 10 = 1 mod 10
where phi(10) is the numbers between 1 and 10 that are co-prime to 10 (i.e. their gcd is equal to 1). The numbers < 10 co-prime to 10 are 1,3,7 and 9. So phi(10) = 4 and this proves that really a^4 mod 10 = 1 mod 10.
The last claim to prove is that for exponentiations where the base is >= 10 it suffices to just look at the base's units digit. Lets say our base is x >= 10, so we can say that x = x_0 + 10*x_1 + 100*x_2 + ... (base 10 representation)
Using modular representation it's easy to see that indeed
x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10
where a_i are coefficients that include powers of x_0 but finally not relevant since the whole product a_i * (10 * x_i)^y-i will be divisible by 10.
