Tuesday, November 2, 2021

Don't Use Modular Arithmetic With Negative Numbers

Most programmers are familiar with the "modulus" operator, which is the percent symbol in the language C and many other programming languages that have followed.  Anyone who remembers learning division in elementary school will recall that when you divide a number, say 21 by a smaller number, say 5, you get a whole number part, 4 in this case, but there's a little left over.  Later in arithmetic, you learned to continue the division and get 4.2, but when first learning, you would be told to stop at 4 and say you had a remainder of 1.  This concept turns out to be incredibly useful given that computers do a lot of work with integers.

In C, when working with integer math, you will observe:

   21 / 5 = 4
   21 % 5 = 1

When I was a math major in college, we worked with modular arithmetic quite a bit both in my number theory class and in my modern algebra class when working with ring theory.  Number theory in particular was a wonderful class for a computer scientist, as it is the mathematical basis for pretty much all integer computing, as well as the basis for cryptography.

Now in modular arithmetic, as any mathematician knows, if you're working with mod 5, you always end up with numbers from 0 through 4.  Here, 4+1 is 0, and 0-1 is 4.  You've just taken the number line and wrapped it into a tight circle.

In computers, this is used in many applications.

Anything needing random numbers typically calls a function that returns a random unsigned integer from zero to however large the integer is (about four billion for a 32-bit integer).  If you're writing code to simulate rolling dice for Dungeons and Dragons, then you'll often want a random number from 1 through 20, so you'll take your huge random number, mod it by 20 to get a number from 0 through 19, and add one.

Another common data structure is an array.  It doesn't matter here what the elements are, they could be simple integers or complex structures.  What matters is that the array has a known number of elements, and you reference elements using integer indices of zero through one less than the array length.  So if the array has 50 elements, they're 0 through 49.  Now sometimes we have an array where we are keeping a history of events, so we save the index of the next event to write, and after writing it, we add one to move to the next element.  But to avoid going past the end, we mod the index by the array length to make it wrap around at the end.

That all works great.

Now suppose we have a circular array as I described, and we want to read it backwards.  We should be able to simply keep subtracting one and taking the result mod the array size so that when we go from zero to negative one it will jump back instead to the end (49 in the above example).  But we have two problems here.

First, often programmers use unsigned integers, especially for array indices.  When you subtract 1 from 0 with an unsigned number, it's an integer underflow, which wraps around to be the largest possible integer (that 4 billion-ish number for 32-bit integers).  And unless your array size is a power of 2, that modular arithmetic will not work out right.  If you think back to how modular arithmetic is like wrapping the number line into a circle, you can see this if you imagine wrapping a 72-inch tape measure into a 5-inch circle.  This would work great most of the way, but since you would have that last two inches at the end, moving backwards from zero would be as if the tape connected instantly back to 72, so subtracting one would go to 71, which would be read mod 5 as 1, not 4 like a mathematician would expect.

Second, even if you're carefully using signed integers for the array indices, the modular operator doesn't follow arithmetic rules as mathematicians would expect.  In fact, it's not really a modular operator at all, but really a remainder operator.  But those are the same thing, right?  Not really.  The catch is how the division operator works.

What is -1/5 in integer arithmetic?

Is that 0 or -1?

If it's -1, then you would have a remainder of 4.  That's also what you would want from a modular operator, keeping the value always in the 0 through 4 range.

If it's 0, then you would have a remainder of -1.  That's not how modular arithmetic works, as you can't have a negative modular result.

In C, the answer is 0.  And the so-called modular operator will tell you that -1%5 is -1.

In C, division of negative numbers rounds towards zero instead of negative infinity, which breaks true modular arithmetic.

Fortunately, it's not hard to work around this problem.

Say you're moving backwards through a circular array, and what you want to do is:

   previous_index = ( current_index - 1 ) % number_of_elements;

But since that breaks at zero, just add in the array size:

   previous_index = ( number_of_elements + current_index - 1 ) % number_of_elements;

That simple change prevents the index from ever going negative, and except when wrapping around below zero, the added array size is just erased by the modular operator.