Pointer Walk

Modular Arithmetic

Arithmetic that wraps around, like a clock. It is behind hash tables, ring buffers, weekdays and most of cryptography.

Maths for ProgrammersBeginner7 min read

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.

Counting with 12 positionsInteractive
Example
01234567891011

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 %:

python
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.

TaskCodeWhy it works
Is a number even?n % 2 == 0Even numbers leave no remainder when divided by 2
Every third itemi % 3 == 0True for 0, 3, 6, 9
Pick a hash buckethash(key) % bucketsAny number becomes a valid bucket index
Take turns between serversservers[turn % len(servers)]The count goes up for ever, and the index cycles
Move around a ring buffer(position + 1) % sizePast the last slot comes slot 0
Minutes on a clocktotal_minutes % 60Whole hours drop out
Last digit of a numbern % 10The 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 % 5 is 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress