Modular Arithmetic is an interesting fundamental in Mathematics that falls under the category of "number theory". It doesn't get a lot of explicit attention in most educational systems until its applications are taught in usually higher level course work. Modular Arithmetic is used in public-key encryption, coding theory, computer algebra, and a host of other things we interact with daily whether we know it or not. Even though its applications are advanced, the core concept is simple.
Practical Examples
To set up modular arithmetic, I will give two examples from everyday life.
The Clock Analogy
As a refresher, an analog 12 hour clock is a disk with three "hands" radiating from the center: representing seconds, minutes, and hours respectively. For each second that passes, the second hand moves clockwise 1/60th of the circumference of the clock. With each full revolution of the second hand, the minute hand also moves 1/60th of the clock. Finally, with each full revolution of the minute hand, the hour hand moves 1/12th of the circumference of the clock.
This may vary by culture, but in the US, the modular aspect of the clock is part of language. Phrases like "Bottom of the Hour" or "Quarter past the hour" implicitly divide a full revolution of the minute hand on the clock (i.e. 1 hour) into quarters with each quarter representing 15 minutes. At every "top of the hour", the minute hand is at 0, regardless of what hour it is. At every "quarter of an hour", the minute hand is at 15. At every "bottom of the hour", 30. etc. Again, this happens regardless of the hour.
Pardon me for over explaining an analog clock, but it occurred to me many younger people may have only ever experienced digital clocks. It also helps set up the concept really well.
An Odd Bag
I will add one more example for good measure - a binary one. You and your friend purchase a bag of apples and decide to evenly share them. If the bag contains an even number of apples, you both get an equal amount of apples. However, if the bag contains an odd number of apples, you still both get an equal number of apples but there will be one left over.
Concept: The Modulus
At the foundation of modular arithmetic is the modulo operation which is often shortened to mod or represented as %. Like addition (+) or multiplication (×), it is a function applied to 2 arguments and returns a value. You're probably familiar with the return value from grade school math as "the remainder" when performing division. The modulo of two numbers a mod m is related to the division of a by m (referred to as the modulus) and returns the remainder of the division. If m divides a evenly, then there is no remainder (0). Otherwise, there will be some number left over. In the apples example above, our modulus m is 2 (you and your friend). Let's say the bag contains 10 apples, 2 evenly divides 10 and thus we have no remainder (10 mod 2 = 0). However, 2 does not evenly divide 11 for example (11 mod 2 = 1). Now I'm hungry.
Reduction Algorithm
In number theory, there is an algorithm called the "reduction algorithm" which allows you to do division with remainders programmatically as well as covert numbers between bases (base 10 to base 2 for example) in a generic algorithm. This is a handy little algorithm. The algorithm is based on the following:
Let N, q, m, r be integers with integer q and 0 <= r <= |m|
then N = q × m + r
Non negative m is the modulus, r is the remainder.
This essentially says our original number N is something (q) multiplied by the modulus (m) + some
left over stuff (r). We are interested in the left over stuff, which is the remainder.
If you feel up to it, you can rearrange this equation to get the standard division
syntax.
Applying the Algorithm to the Examples
Next, we'll use the algorithm to represent the different scenarios from the examples above.
In the binary apple example (modulus = 2):
0 mod 2 = 0 since 0 = 2 * (0) + 0
1 mod 2 = 1 since 1 = 2 * (0) + 1
2 mod 2 = 0 since 2 = 2 * (1) + 0
3 mod 2 = 1 since 3 = 2 * (1) + 1
4 mod 2 = 0 since 4 = 2 * (2) + 0
Notice that for every even number, the remainder is 0.
For the clock example, let's use a modulus of 4 to represent quarter hours. Then our N value is the number of quarters. i.e. 8 = 8 quarter hours or 2 whole hours
0 mod 4 = 0 since 0 = 4 * (0) + 0
1 mod 4 = 1 since 1 = 4 * (0) + 1
2 mod 4 = 2 since 2 = 4 * (0) + 2
3 mod 4 = 3 since 3 = 4 * (0) + 3
4 mod 4 = 0 since 4 = 4 * (1) + 0
5 mod 4 = 1 since 5 = 4 * (1) + 1
6 mod 4 = 2 since 6 = 4 * (1) + 2
7 mod 4 = 3 since 7 = 4 * (1) + 3
8 mod 4 = 0 since 8 = 4 * (2) + 0
Takeaways
- Notice that numbers that are q "away" from each other have equal remainders
- Similarly, the modulo of any number times the modulus is 0. (m mod q×m = 0)
- The remainder is always less than the m.
Practical Applications in Development
Even if you are not working with public-key encryption or other more complex applications of modular arithmetic, modular arithmetic does popup in everyday development. Here are two simple examples.
Alternating Rows
My first experience working with modular arithmetic was creating alternating row colors in HTML tables. This can more easily be achieved with CSS rules, but prior to the spec you had to do it manually.
Here is some JSX for accomplishing this the old fashioned way
const TableExample = () => (
<table border="2" width="400px">
{Array.from(Array(10).keys()).map((i) => {
const color = i % 2 === 0 ? '#cccccc' : '#eeeeee';
return <tr style={{ backgroundColor: color }}><td>{i}</td></tr>;
})}
</table>
);
Checkerboard
A similar but more complex example is creating a checker board:
const CheckersExample = () => (
<table>
{Array.from(Array(8).keys()).map((i) => (
<tr>
{Array.from(Array(8).keys()).map((j) => {
const color = j % 2 !== i % 2 ? 'black' : 'red';
return <td style={{ backgroundColor: color, width: 30, height: 30 }}> </td>;
})}
</tr>
))}
</table>
);
Conclusion
Modular Arithmetic is another neat math concept we rarely use directly in development. However, its applications are widespread. In a future post, I'll explore some additional applications for base conversion and optimizing data batching. Until then check out my series: Applied Math for other ways math pops up in software development.
Discussion Topics
- Have you used modular arithmetic before in programming? For what purpose?
- When was the last time you saw an analog clock?
I originally wrote this article for the defunct TCPHP mailing list in 2005. It has been updated for clarity and using JSX rather than PHP/XSLT.
Photo by Nidhi Shah from Pexels
