Modulus with a Negative Offset

A modulus or (modulo) operation returns the remainder of a division operation. Its operand is usually the percent sign % and it is very useful in programing when we are grouping data and operating at intervals. For example:

i = 0;
cookie = null;
while ((cookie = getNextCookie()) !== null)
{
    eat(cookie);

    ++i;

    print("Ate " + i + " cookies.");

    if (i % 3 == 0)
    {
        drinkMilk();
        print("Drank milk.");
    }
}

The above code will drink milk after every 3rd cookie eaten. The output would look like the following:

Ate 1 cookies.
Ate 2 cookies.
Ate 3 cookies.
Drank milk.
Ate 4 cookies.
Ate 5 cookies.
Ate 6 cookies.
Drank milk.
Ate 7 cookies.
Ate 8 cookies.
Ate 9 cookies.
Drank milk.
...

Offsets

What if you wanted to drink milk after every 3rd cookie after the 8th cookie (mod 3 with an offset of 8)?

You could change your if-statement to read:

if (i > 8 && (i - 8) % 3 == 0)

That works! You can think of it as you are making i relative to 0, then taking the modulus of that.

The problem with this solution comes when you want to use the majority of a signed numeric type's value range. For this example I will assume integers have a range of -256 to 255 for simplicity. If I want to store 500 cookies I will need to use the full range of our numeric type (first value of i is -256). I will need to use an offset of -256 as this will make my first cookie relative to 0 (-256 - -256 = 0).

if ((i - -256) % 3 == 0)

Once i has a value of -1, i - -256 hits the upper range of what our type can hold (-1 - -256 = 255). When i gets to 0, we will have an overflow. As you can see, this only allows us to use half of our value range. That's no good.

Solution

Instead of making i relative to 0, we can make it relative to any value of which value % 3 = 0 (the start of a "group"). Let's look at some numbers to show why that is possible:

    0  1  2 |  3  4  5 |  6  7  8 |  9 10 11 | 12 13 14 | 15
% 3
    0  1  2 |  0  1  2 |  0  1  2 |  0  1  2 |  0  1  2 |  0

 2 % 3 = 2;
 5 % 3 = 2;
 8 % 3 = 2;
11 % 3 = 2;
14 % 3 = 2;

As you can see, adding the "group size" (3) to any value has no effect on the result of the modulus. And that makes sense. You are jumping between groups.

How does this help us? If we can figure out a number that we can add to our offset so that (offset + someNumber) % 3 = 0, we can use that number to make any other value relative to the start of a group.

For example, if our offset was 4 - we know that 4 is 2 away from 6 (4 - 6 = -2) and we know 6 is the start of a group (6 % 3 = 0). So, if we know that we can subtract -2 from 4 to get the start of a group, we know we can subtract -2 from any value and it will be relative to the start of a group. Let's see that:

    4  5  6 |  7  8  9 | 10 11 12 | 13 14 15
- -2
    6  7  8 |  9 10 11 | 12 13 14 | 15 16 17
% 3
    0  1  2 |  0  1  2 |  0  1  2 |  0  1  2

We already know one possible answer: -offset as we proved above. But, as we have discovered, that number is too large for our case.

Finding this number is as simple as offset % 3. This gives us the difference between the offset and the start of the next group. Let's look at some more numbers:

-256 % -3 = -1

offset -|     |- factor of 3 (start of a group)
        | -1  |
  *-----*-----*-----*
-257  -256  -255  -254

-256 - -1 = -255 % 3 = 0
-255 - -1 = -254 % 3 = 1
-254 - -1 = -253 % 3 = 2
-253 - -1 = -252 % 3 = 0
-252 - -1 = -251 % 3 = 1
-251 - -1 = -250 % 3 = 2

As you can see, these numbers don't lie. Every 3rd value starting with our offset produces a remainder of 0. And, our useable range is now -256 to 254 (x - -1 < 255 : x < 254).