% Is Not Modulo

Note: This post doesn't actually apply to all languages. Only many of them. To see if it applies to your chosen language, check if -4 % 3 equals -1. If it's 2, your % is actually modulo. If you get something else, let me know, because I'm curious!

You may have seen % used in a few places. Maybe someone was generating a random number in a range:

rand() % max

or cycling through an array:

index = (index + 1) % array.length;

You've probably heard this referred to as "modulo", too. If you know anything about modular arithmetic, at first glance it seems to be accurate, too. But it's... not quite. The difference might seem insignificant, but if you find yourself implementing any math that uses real modular arithmetic, it's important.

Vocab

First, quick vocab lesson:

A / B = C means "A divided by B is equal to C". A is the divisor, B is the dividend, and C is the quotient. If I refer to "division" without specifying, in this article I mean integer or floored division. That's when you do a division without keeping track of the decimal component (so, for example, 14 / 5 is 2, not 2.8).

Right, with that out of the way...

What's %?

% gets the remainder of an integer division. If you think of integer division as splitting a lot of objects evenly into a number of groups, the remainder is how many objects are left over. For example, 14 / 5 is 2, because each of the 5 groups can have 2 objects in it, and there are 4 objects left over which can't be evenly split into the groups.

Or, more mathematically, the remainder is the difference of the divisor and the product of the dividend and quotient. For example, 14 / 5 is 2, so the remainder is 14 - (2 * 5) = 4.

For the sake of clarity, I'll be using "rem" as an operator to specify that I want to get the remainder of a division. So, for example, 14 rem 5 is 4.

Note: Getting the remainder is rarely implemented like that on actual hardware. The effect is the same, though, so I'll leave that for another day.

What's modulo?

Modulo, or modular arithmetic, is a little different. First of all, it's not an operation. It's more of a system of doing math. It's just like normal arithmetic, but whenever you perform an operation, it wraps in a. That range is from zero to what's called the "modulus".

That might be a little technical and abstract, so think about telling time. Whether you use a 12-hour or correct 24-hour clock, think about 1:00, just after midnight. Now think about what time is two hours before that. It's not -1:00, it's either 11:00 or 23:00. Or, going the other way, you don't go from 11:00 to 13:00 in 12-hour time or 23:00 to 25:00 in 24-hour time. Instead, you wrap around, going back to the start of the range -- from 0 to 12 or 24 -- when you pass the end, or ahead to the end when you go back behind the start.

In math, because it's an arithmetic system, modulo is usually used as a sort of modifier for the entire equation. In programming, though, it's not exactly easy to redefine how arithmetic works for a single expression (at least, not in most programming languages), so it's used as an operator. To use the time example from before with a 24-hour clock, 25 mod 24 = 1.

You might be wondering what happens if you're still outside the range when you wrap around. For example, what's 14 mod 5? If you just wrap once, then you get 9, which is still outside of the range. You just keep wrapping in that case, down to 4, which is in the range.

So... what's the difference?

Up until now, I've only used positive integers for both divisors and dividends. Under those conditions, remainder and modulo perform the same. I won't be getting into all reals in this post, if ever, because remainder and modulo are almost always used with integer arithmetic in programming.

But there's still a massive area that I just... haven't covered yet: Negative numbers. So how do things differ there?

Well, let's start with the simplest case. To go back to the clock example, what's -1 rem 24 and -1 mod 24?

The remainder is pretty easy to calculate. -1 / 24 is 0, so the difference is -1.

The modulo is also simple. -1 is under 0, so it wraps back around to 23.

The same problem happens, but backwards, if we use a negative modulo. 12 / -5 is -2, so 12 rem -5 is the difference between 12 and 10, or 2. Wrapping 12 around to fit in the range from 0 to -5 can't give us a positive number, though, and in fact it gives us -3.

With two negative numbers, things go right back to working normally. -12 rem -5 and -12 mod -5 are both -2.

How do I fix it?

You may have already noticed a pattern about the difference between remainder and modulo. Specifically, the difference, when there is one, is always exactly the divisor. Also, as mentioned before, the divisor and dividend are different signs. Both of those are provably true, but I'm not going to get into the actual math here -- just take my word for it.

That makes the fix pretty easy. First, check whether % means remainder or modulo in your language. It's very likely to be remainder, but there are some large ones, like Python, where it's modulo. You can do that pretty easily by using any of the examples I've used in the previous section and seeing which answer you get.

If your language's % is a remainder, then chances are there's a standard library function to do modulo. If not, though, here's a C function to do "real" modulo based on the remainder:

int mod(int dividend, int divisor) {
  if (dividend == 0) return 0;
  if ((dividend > 0) == (divisor > 0)) // if they're the same sign
    // then remainder is the same as modulo
    return dividend % divisor;
  else // otherwise, if they're different signs
    // account for the difference
    return (dividend % divisor) + divisor;
}

Note: Zero has to be special-cased because whichever way you check the sign (both positive or both negative) it always ends up with zero being wrong on one of the branches. If you have any ideas for how to make the code cleaner, let me know!

That should be fairly simple to port to just about any language, though the check to see if they're the same sign may need to be written differently if binary XOR isn't available in yours.

Why did things work?

At this point, you might be wondering about how things have worked, given this discrepancy. In most cases, it boils down to things always being positive. For example, the rand() example I gave at the beginning:

rand() % max

In C, and therefore most C-derived languages, the builtin rand-like function returns numbers from 0 to some maximum value, and the max value is always positive. Of course, more modern languages typically offer another, more clear way to get random numbers anyway, and you should use those instead.

The array-index example is similar:

index = (index + 1) % array.length;

This gets the next index in the array, wrapping back around to the beginning once the end is reached. Because the index starts out positive and, aside from when it wraps to zero, only increases, the negatives are never reached. Though if you were trying to do it backwards, it'd break:

index = (index - 1) % array.length;

In this case, when index is 0, (0 - 1) % array.length will give you -1, which is an out of bounds access. You'd have to do a proper modulo add to account for this.

---

So, have you ever encountered any issues with the difference between modulo and remainder? I have; fixing one such bug is what inspired this post, actually.

Comments

[Mikael Klages]

I've learnt to always check that when dealing with potential negative numbers in new languages, and sometimes in ones 8 know already, too just to be safe. Though I must admit I sometimes take the lazy route of (a%n+n)%n since it's faster to write.

[Nic Hartley]

As neat as that one-liner is, I'm not a huge fan of it. The "correct" function is only a few lines in any language, and makes it explicitly clear what you're trying to do.

...that said, I have used it more than a few times when I just need something working correctly, and I'd be surprised if the compiler couldn't optimize it into something better.

[Reese Poirier]

Thanks for the tip. I've only done any serious math in python or perl so I didn't know it's not real modulo in other languages.