Arithmetic that wraps around
It is 9 o'clock. What time will it be in 5 hours?
You did not say 14 o'clock. You said 2. Without thinking about it, you did arithmetic on a number line that is bent into a circle: after 12, it starts again.
That is modular arithmetic. It is ordinary arithmetic with one change: there is a fixed number of positions, and going past the last one brings you back to the start.
Start. It is 9 o'clock. What time is it 5 hours later? There are only 12 positions, numbered 0 to 11. After the last one comes 0 again.
- Start
- 9
- Steps taken
- 0 / 5
- Position now
- 9
The mod operation
The number of positions is called the modulus. The operation that does the wrapping is called mod, and it means: divide, and keep the remainder.
Example
14 mod 12
14 divided by 12 is 1, with 2 left over. So 14 mod 12 = 2.
9 + 5 = 14, and 14 mod 12 = 2. Two o'clock.
In most programming languages it is written %:
14 % 12 # 2
17 % 5 # 2
20 % 5 # 0 (divides exactly, nothing left over)
3 % 5 # 3 (smaller than the modulus: unchanged)With modulus n, the result is always one of 0, 1, 2, up to n − 1. That is n possible answers, however large the input.
Try the other two examples in the demo. Days of the week are arithmetic mod 7. And "which of 5 buckets does hash 17 go in?" is 17 mod 5.
It is in code you already write
Any time something cycles, or a large number has to be squeezed into a small range, there is a mod.
| Task | Code | Why it works |
|---|---|---|
| Is a number even? | n % 2 == 0 | Even numbers leave no remainder when divided by 2 |
| Every third item | i % 3 == 0 | True for 0, 3, 6, 9 |
| Pick a hash bucket | hash(key) % buckets | Any number becomes a valid bucket index |
| Take turns between servers | servers[turn % len(servers)] | The count goes up for ever, and the index cycles |
| Move around a ring buffer | (position + 1) % size | Past the last slot comes slot 0 |
| Minutes on a clock | total_minutes % 60 | Whole hours drop out |
| Last digit of a number | n % 10 | The remainder after removing the tens |
Several pages on this site are built on it: Hash Tables, Ring Buffers, Load Balancing and Consistent Hashing.
A useful property
You can take the remainder at any point in a calculation of additions and multiplications, and the final answer is the same.
Example
Reduce as you go
What is (9 + 5 + 8 + 11) mod 12?
The long way: 9 + 5 + 8 + 11 = 33, and 33 mod 12 = 9.
Reducing as you go: 9 + 5 = 14, which is 2. Then 2 + 8 = 10. Then 10 + 11 = 21, which is 9.
Same answer, and the numbers never got large.
This matters when the numbers would otherwise be astronomically big. To find the remainder of a number raised to a huge power, you never compute the power. You multiply and reduce, multiply and reduce.
That trick is at the centre of modern cryptography. See Public-Key Cryptography, where a message is raised to a power "mod 33". With real keys, the modulus has hundreds of digits.
Easy forwards, hard backwards
Modular arithmetic has a property that makes it valuable for security: it throws information away.
Given 17, computing 17 mod 5 = 2 is trivial. Given only the 2, you cannot tell what the original was. It could have been 2, 7, 12, 17, 22, or any of infinitely many others.
Combine that with multiplication and powers, and you get operations that are quick to perform and practically impossible to reverse. Hash functions, key exchange and digital signatures are all built from them.
Things to watch
- Negative numbers. Languages disagree. In Python,
-1 % 5is 4, which is what you want for wrapping backwards. In C, Java and JavaScript it is -1. To step back safely anywhere, write(position - 1 + size) % size. - Modulus of zero is a division by zero, and an error.
- Slightly uneven results. If you turn a random number from 0 to 9 into a choice between 3 options with
% 3, option 0 gets four of the ten values and the others get three each. For games it does not matter. For security it does.
Key takeaways
- Modular arithmetic is arithmetic on a circle: past the last position, counting starts again at 0.
- a mod n is the remainder after dividing a by n, written a % n in code.
- It turns any number into one of n values, which is how hash buckets, ring buffers and taking turns work.
- You can reduce at any step of a sum or product without changing the result.
- It is easy to compute and hard to reverse, which is why cryptography relies on it.