 Monday, March 15, 2010

Computing the last digit of b^e efficiently

Geek PSA: Yesterday was PI day (3.14, get it?). Lets celebrate with this spiked math comic:

Last week I saw the following problem which peaked my interest:

Compute the last (decimal) digit of 2 raised to the power e where e might be very large.

We assume that we are talking about positive, integer exponents here. The key observation here is that the last digit form a cycle:

```...2 * 2 = ...4
...4 * 2 = ...8
...8 * 2 = ...6
...6 * 2 = ...2```

So you can compute the last digit by calculating e MOD 4, which gives us the position in the cycle. Next, I wondered if all the digits have this cycling going on, so I searched around a little bit and found this page which gives the cycle for all ten digits. Now you can compute the last digit of the formula b^e with the following algorithm:

• Take the last digit of b
• compute e MOD (length of cycle for last digit of b)
• return the given element of the cycle

This is very nice, since we can operate on arbitrary sized b, but we still need to be able to perform the modulo operation on e, which might be inconvenient if e is large. Fortunately we can make the following observation:

• The length of the cycle is either 1, 2 or 4
• For x in [1,2,4] you have ...ab MOD x = ab MOD x (ie you can take only the last two digits and compute the modulo) since 100 is a multiple of both 2 and 4 (meaning that a number in the form of ...00 will always be divisible by both 2 and 4, hence it contributes nothing to the modulo operation)

So here is the final algorithm which works quickly even for very large values of b and e

• Take the last digit of b
• compute e MOD length_of_cycle by using the last two digits of e
• return the given element of the cycle

Give it a try below if you have javascript enabled:

Math is fun :-).

Finally, I would like to leave you with the following question: is it possible to efficiently compute an arbitrary digit of b^e? My intuition is that there are cycles in all of them, however they might be quite long...

1. Interesting, I never thought about that. It might just come in handy in some of the project Euler challenges. :-)

2. Wow, that is amazing! I teach math at a local highschool in Holland and I'm always on the lookout for new, intereseting tasks for them. This might be one of them.

You mind if I use this stuff in class?

3. I am definitely in favor of any initiative which would result in young people having more interest in math / science. As such I don't mind at all and I would be in fact honored if you would use these ideas to teach people.

All the content on this blog (if not noted otherwise) is under the Creative Commons Attribution, Share Alike 3.0 license, which means that it can be used freely as long as it is properly attributed (for details see this link: http://creativecommons.org/licenses/by-sa/3.0/).

To make things even simpler: I hereby grant anyone permission to use this post (including the simple javascript embedded in it) for any purpose for free and with no additional obligations.

Regards.