Calculation modulo two intervals
I want to understand how the modulus operator works when applied to two bins. Adding, subtracting and multiplying two intervals is trivial to implement in code, but how do you do it for a module?
I would be glad if someone can show me a formula, sample code, or link that explains how it works.
Background information: you have two integers x_lo < x < x_hi
and y_lo < y < y_hi
. What are the lower and upper bounds for mod(x, y)
?
Edit: I'm not sure if minimal estimates can be used effectively (without calculating the mod for all x or for all y). If so, I will take an accurate but suboptimal answer out of bounds. Obviously [-inf, + inf] is the correct answer then :), but I need a border that is more limited in size.
source to share
It turns out to be an interesting problem. I am assuming that truncated division (rounding to 0) is defined for integer intervals modulo .
As a consequence, mod(-a,m) == -mod(a,m)
for all a, m. In addition, sign(mod(a,m)) == sign(a)
.
Definitions before we start
Closed Spacing a to b: [a,b]
Blank Spacing: [] := [+Inf,-Inf]
Negation: -[a,b] := [-b,-a]
Union: [a,b] u [c,d] := [min(a,c),max(b,d)]
Absolute Value: |m| := max(m,-m)
|m| := max(m,-m)
Simplified case: fixed module m
It's easier to start with a fixed one m
. We will later generalize this to a modulus of two intervals. The definition is constructed recursively . It shouldn't be a problem to implement this in your favorite programming language. pseudocode:
def mod1([a,b], m):
// (1): empty interval
if a > b || m == 0:
return []
// (2): compute modulo with positive interval and negate
else if b < 0:
return -mod1([-b,-a], m)
// (3): split into negative and non-negative interval, compute and join
else if a < 0:
return mod1([a,-1], m) u mod1([0,b], m)
// (4): there is no k > 0 such that a < k*m <= b
else if b-a < |m| && a % m <= b % m:
return [a % m, b % m]
// (5): we can't do better than that
else
return [0,|m|-1]
Up to this point, we cannot do better than this. The resulting interval in (5)
may be more than -a p-approximation, but this is the best we can get. If we were allowed to return a set of intervals, we could be more precise.
General case
The same ideas apply when our module is the interval itself. Like this:
def mod2([a,b], [m,n]):
// (1): empty interval
if a > b || m > n:
return []
// (2): compute modulo with positive interval and negate
else if b < 0:
return -mod2([-b,-a], [m,n])
// (3): split into negative and non-negative interval, compute, and join
else if a < 0:
return mod2([a,-1], [m,n]) u mod2([0,b], [m,n])
// (4): use the simpler function from before
else if m == n:
return mod1([a,b], m)
// (5): use only non-negative m and n
else if n <= 0:
return mod2([a,b], [-n,-m])
// (6): similar to (5), make modulus non-negative
else if m <= 0:
return mod2([a,b], [1, max(-m,n)])
// (7): compare to (4) in mod1, check b-a < |modulus|
else if b-a >= n:
return [0,n-1]
// (8): similar to (7), split interval, compute, and join
else if b-a >= m:
return [0, b-a-1] u mod2([a,b], [b-a+1,n])
// (9): modulo has no effect
else if m > b:
return [a,b]
// (10): there is some overlapping of [a,b] and [n,m]
else if n > b:
return [0,b]
// (11): either compute all possibilities and join, or be imprecise
else:
return [0,n-1] // imprecise
Have fun! :)
source to share
Let the form mod (x, y) = mod. In general, 0 <= mod <= y. So this is always true: y_lo <mod <y_hi
But we can see some specific cases below:
- if: x_hi < y_lo then div(x, y) = 0, then x_low < mod < x_hi
- if: x_low > y_hi then div(x, y) > 0, then y_low < mod < y_hi
- if: x_low < y_low < y_hi < x_hi, then y_low < mod < y_hi
- if: x_low < y_low < x_hi < y_hi, then y_low < mod < x_hi
- if: y_low < x_low < y_hi < x_hi, then y_low < mod < y_hi
....
source to share