I want to understand how the modulus operator works when applied to two intervals. Adding, subtracting and multiplying two intervals is trivial to implement in code, but how do you do it for modulus?
I'd be happy if someone can show me the formula, sample code or a link which explains how it works.
Background info: You have two integers x_lo < x < x_hi
and y_lo < y < y_hi
. What is the the lower and upper bound for mod(x, y)
?
Edit: I'm unsure if it is possible to come up with the minimal bounds in an efficient manner (without calculating the mod for all x or for all y). If so, then I'll accept an accurate but non-optimal answer for the bounds. Obviously, [-inf,+inf] is a correct answer then :) but I want a bound that is more limited in size.
I'll assume both intervals are positive, in other words
0 <= x_lo
and0 < y_lo
— only because negative numbers make things more complicated.Let's look at the definition of
mod
:Division isn't too complicated when applied to non-negative intervals:
floor(x_lo / y_hi) <= k <= floor(x_hi / y_lo)
. Call those boundsk_lo
andk_hi
. If we calculate thatk_lo = k_hi = k
, then we can substitute back into the equation above and solve formod(x, y)
.So
x_lo - k*y_hi <= mod(x, y) <= x_hi - k*y_lo
whenk_lo = k_hi
.If you look at a 3d graph of
mod(x, y)
alongsidek = floor(x/y)
, then you'll see large regions that share a value ofk
, which look linear (flat planes) inx
andy
. The calculation above is for finding the bounds when the result is confined to a single one of those regions, wherek
has a particular value. The linearity makes it easy to calculate the bounds. These 3d regions remind me of how a 2d graph ofmod(x, c)
for a constantc
has a sawtooth pattern, divided into linear regions. Next we'll look at when the modulo result can span between multiple regions.In all other cases where
k_lo < k_hi
, the possible results of span across multiple values ofk
. Each of the regions is a plane/linear, so if we're looking for upper and lower bounds, they'll be along the boundaries of regions or the edges of the intervals. (I'm sure there's a justification in terms of derivatives and discontinuities.) Take everything that follows with a grain of salt.Those boundaries between values of
k = floor(x/y)
are whenx/y
is an integer, that is wheneverx
is a multiple ofy
. If x and y were real numbers, the lines where x is a multiple of y would be wheremod(x, y)
approaches0
from above, andy
from below. We know the intervals for x and y contain a value on both sides of one of these boundaries sincek_lo < k_hi
, hencelower_bound = 0
.I think there are two ways for a point to be the maximum output of
mod(x, y)
within a region. Ak
region boundary intersected with either thex = x_hi
plane or they_hi
plane. (If nok
region boundary intersected either of them, thenk_lo
would equalk_hi
.)Setting
x = x_hi
as constant, then the maximum value ofmod(x_hi, y)
is at the smallesty
such thatk = floor(y / x_hi)
is at its maximum (i.e.k = k_hi
). I'm going by the graph here. So one possible upper bound ismod(x_hi, clamp(k_hi*x_hi, y_lo, y_hi))
. Unfortunately, my calculations don't lead to the right answer here, so you might need to figure this part out and test.Setting
y = y_hi
as constant, then the maximum will depend on whether the plane spans over ak
region boundary, i.e. whether or notfloor(x_lo / y_hi) < floor(x_hi / y_hi)
.mod(x, y_hi)
is justy_hi - 1
. (Justification: ifk = floor(x/y_hi)
for some x, butk-1 = floor((x-1)/y_hi)
, thenx
is congruent to 0mod y_hi
.x-1
is congruent to 0-1mod y_hi
, in other wordsmod(x-1, y_hi) = y_hi - 1
which gives the upper bound.)k
region boundary, then the maximum will just bemod(x_hi, y_hi)
(simple because within eachk
region it's linear in x). I think this case will never matter anyway, because the maximum will be smaller than the result of settingx = x_hi
anyway, but I'm not certain enough to leave it out.That gives us the other upper bound.
If my maths is correct, we can just take the max of these two upper bounds for the case when
k_lo < k_hi
.So all in all, it would look something like: