Is there an expression using modulo to do backwards wrap-around ("reverse overflow")?

Question

For any whole number input W restricted by the range R = [x,y], the "overflow," for lack of a better term, of W over R is W % (y-x+1) + x. This causes it wrap back around if W exceeds y.

As an example of this principle, suppose we iterate over a calendar's months:

int this_month = 5;
int next_month = (this_month + 1) % 12;

where both integers will be between 0 and 11, inclusive. Thus, the expression above "clamps" the integer to the range R = [0,11]. This approach of using an expression is simple, elegant, and advantageous as it omits branching.

Now, what if we want to do the same thing, but backwards? The following expression works:

int last_month = ((this_month - 1) % 12 + 12) % 12;

but it's abstruse. How can it be beautified?

---

tl;dr - Can the expression ((x-1) % k + k) % k be simplified further?

Note: C++ tag specified because other languages handle negative operands for the modulo operator differently.

Solution 1

Your expression should be ((x-1) + k) % k. This will properly wrap x=0 around to 11. In general, if you want to step back more than 1, you need to make sure that you add enough so that the first operand of the modulo operation is >= 0.

Here is an implementation in C++:

int wrapAround(int v, int delta, int minval, int maxval)
{
  const int mod = maxval + 1 - minval;
  if (delta >= 0) {return  (v + delta                - minval) % mod + minval;}
  else            {return ((v + delta) - delta * mod - minval) % mod + minval;}
}

This also allows to use months labeled from 0 to 11 or from 1 to 12, setting min_val and max_val accordingly.

Since this answer is so highly appreciated, here is an improved version without branching, which also handles the case where the initial value v is smaller than minval. I keep the other example because it is easier to understand:

int wrapAround(int v, int delta, int minval, int maxval)
{
  const int mod = maxval + 1 - minval;
  v += delta - minval;
  v += (1 - v / mod) * mod;
  return v % mod + minval;
}

The only issue remaining is if minval is larger than maxval. Feel free to add an assertion if you need it.

Solution 2

k % k will always be 0. I'm not 100% sure what you're trying to do but it seems you want the last month to be clamped between 0 and 11 inclusive.

(this_month + 11) % 12

Should suffice.

Solution 3

The general solution is to write a function that computes the value that you want:

//Returns floor(a/n) (with the division done exactly).
//Let ÷ be mathematical division, and / be C++ division.
//We know
//    a÷b = a/b + f (f is the remainder, not all 
//                   divisions have exact Integral results)
//and
//    (a/b)*b + a%b == a (from the standard).
//Together, these imply (through algebraic manipulation):
//    sign(f) == sign(a%b)*sign(b)
//We want the remainder (f) to always be >=0 (by definition of flooredDivision),
//so when sign(f) < 0, we subtract 1 from a/n to make f > 0.
template<typename Integral>
Integral flooredDivision(Integral a, Integral n) {
    Integral q(a/n);
    if ((a%n < 0 && n > 0) || (a%n > 0 && n < 0)) --q;
    return q;
}

//flooredModulo: Modulo function for use in the construction
//looping topologies. The result will always be between 0 and the
//denominator, and will loop in a natural fashion (rather than swapping
//the looping direction over the zero point (as in C++11),
//or being unspecified (as in earlier C++)).
//Returns x such that:
//
//Real a = Real(numerator)
//Real n = Real(denominator)
//Real r = a - n*floor(n/d)
//x = Integral(r)
template<typename Integral>
Integral flooredModulo(Integral a, Integral n) {
    return a - n * flooredDivision(a, n);
}

Solution 4

Easy Peasy, do not use the first module operator, it is superfluous:

 int last_month = (this_month - 1 + 12) % 12;

which is the general case

In this instance you can write 11, but I would still do the -1 + 11 as it more clearly states what you want to achieve.

Solution 5

Note that normal mod causes the pattern 0...11 to repeat at 12...23, 24...35, etc. but doesn't wrap on -11...-1. In other words, it has two sets of behaviors. One from -infinity...-1, and a different set of behavior from 0...infinity.

The expression ((x-1) % k + k) % k fixes -11...-1 but has the same problem as normal mod with -23...-12. I.e. while it fixes 12 additional numbers, it doesn't wrap around infinitely. It still has one set of behavior from -infinity...-12, and a different behavior from -11...+infinity.

This means that if you're using the function for offsets, it could lead to buggy code.

If you want a truly wrap around mod, it should handle the entire range, -infinity...infinity in exactly the same way.

There is probably a better way to implement this, but here is an easy to understand implementation:

// n must be greater than 0
func wrapAroundMod(a: Int, n: Int) -> Int {
    var offsetTimes: Int = 0

    if a < 0 {
        offsetTimes = (-a / n) + 1
    }

    return (a + n * offsetTimes) % n
}

View more solutions