Your Daily Geekery

modulo of negative numbers

ruby,java,c,python

The modulo operator returns the remainder of a division. In programming it's often used to restrict an index to the bounds of an array or length limited data structure.

values = [ 1, 2, 3 ]
value = [ index % values.length ]

Whether this really is the ultimate guard against an invalid index is revealed when trying negative numbers. What does -1 mod 13 really mean?

Turns out there is no exact definition. In fact it depends on the language you are using. While the code looks pretty much the same in most languages

a = -1
b = 13
c = a % b

printing out c shows two different camps.

Language -1 mod 13
C -1
Java -1
Python 12
Ruby 12

So beware that in some languages you have do a bit more work to restrict access to your arrays. Either by doing a sign check

int mod(a, b) {
  c = a % b
  return (c < 0) ? c + b : c
}

or chaining a second modulo.

int mod(a, b) {
  (((a % b) + b) % b)
}

At least for practical reasons the Python/Ruby interpretation is more convinient. From a mathmatical point of view the java/C interpretation probably makes more sense.

mod(a, n) = a - n * floor(a / n)
mod(-1, 13) = (-1) - 13 * floor(-1 / 13) = -1

For a more detailed discussion see the wikipedia article.