On div and mod

The % operator in most programming language computes the remainder after integer division. This works as expected when both operands are positive, but when one of the operands is negative we start to see differences between different programming languages:

As you can see, all languages agree when both operands are positive, but there are three different ways to define the % operator when one of the operands is negative. The question I want to answer in this post is: which of these three options is the best?

To answer this question, we need to first understand the relationship between the div and mod operators.

The relation between div and mod

The mod operator x%n is intimately related to the integer div operator x/n. To distinguish this from mathematical division, I’ll write this x//n like Python. In order for the choice of div-mod pair to make sense, we want these operators to satisfy the following equation:

x%n = x - (x//n)*n

That is, we want the mod operator to actually give us the remainder after division. This means that if we define integer division, then we have no choice for the mod operator because it is already determined by that equation.

Option 1: C, Rust, OCaml, Java, Pascal, Julia

These languages define the div operator as truncated division, which means that the result is rounded toward zero:

We then define the mod operator in terms of the div operator:

Option 2: Python, Ruby, Racket, Mathematica, R, Haskell

These languages define the div operator as floored division, which means that the result is rounded toward negative infinity:

We then define the mod operator in terms of the div operator:

Option 3: Koka

Koka takes a different approach, and instead defines the mod operator first. Koka defines x%n as the smallest non-negative number that makes x - x%n evenly divisible by n:

We can then define the div operator in terms of the mod operator:

This works because x - x%n is always divisible by n, so the result is always an integer.

Which is best?

Firstly, note that option 2 and option 3 agree about x%n whenever n is positive: they always give a result in the range 0..n-1 in that case. Option 1, on the other hand, will give a negative result for x%n when x is negative, even when n is positive. This is bad, because it means that if you do something like x % some_array.length, you may get an index that is not even in bounds of the array. The second reason it’s bad, is that x%n doesn’t give you a unique representative of the equivalence class x mod n.

Option 1 is bad. If you’re developing a new language, don’t do this.

Now, let’s compare option 2 and option 3. The main difference is that option 2 gives you a more natural definition of the div operator, whereas option 3 gives you a more natural definition of the mod operator. The question is: which one is more useful?

This is less clear, and I’d argue that both options are acceptable. The advantage of option 3 is that it lets you more straightforwardly convert numbers to negative base. The same code that works for positive base also works for negative base.

On the other hand, option 2 is more natural for the div operator, and it is easy to get the Euclidean mod using the floored mod: mod_euclid(x,n) = x % abs(n). I would argue that if your code is doing mod with negative divisors, then it is in fact clearer to have that explicit abs in your code as a signifier that something is going on.

Option 2 and 3 are both good. If you’re developing a new language, choose one of these.

They only differ for x%n when n is negative. That’s not a common case, so it’s not a big deal. I can see arguments in favor of both options. Which one would you choose? Let me know in the comments.

Further reading

There are two great articles investigating this question, which I recommend reading:

1. Division and Modulus for Computer Scientists by Daan Leijen
2. The Euclidean Definition of the Functions div and mod by Raymond Boute