计算两个区间的模数

Question

我想了解当应用于两个区间时，模运算符如何工作。将两个区间相加、相减和相乘在代码中很容易实现，但是如何对取模运算进行处理呢？

如果有人能向我展示公式、示例代码或解释它的链接，我会很高兴。

背景信息：你有两个整数 x_lo < x < x_hi 和 y_lo < y < y_hi。那么 mod(x, y) 的下限和上限是什么？

编辑：我不确定是否有可能以有效的方式（而不必计算所有 x 或所有 y 的模数）得出最小边界。如果可以，那么我会接受一个准确但非最优的边界答案。显然，[-inf，+inf] 是一个正确的答案 :) 但我希望边界更为有限。

- Björn Lindqvist

---

一个区间的模是如何定义的？ - user3235832

这不是我要的。我想要的操作是两个区间的模运算，就像你可以对两个区间进行除法一样。 - Björn Lindqvist

如果 y 固定不变，我们可以通过查看 mod(x_lo, y) 和 mod(x_hi, y) 来确定范围。但是由于 y 的改变，mod 值中没有简单的模式。我认为在此情况下除了计算每个 y 的 mod(x_lo, y) 和 mod(x_hi, y)，并取它们所限制的区间的并集之外，别无他法。 - user3717023

Answer 1

事实证明，这是一个有趣的问题。我做的假设是，对于整数区间，模运算是相对于截断除法（朝0取整）定义的。

因此，所有a、m都有mod(-a,m) == -mod(a,m)。此外，sign(mod(a,m)) == sign(a)。

开始前的定义

从a到b的闭区间： [a,b]
空区间： [] := [+Inf,-Inf]
否定： -[a,b] := [-b,-a]
联合： [a,b] u [c,d] := [min(a,c),max(b,d)]
绝对值： |m| := max(m,-m)

简单情况：固定模数m

从固定的m开始会更容易些。我们稍后将把这个概念推广到两个区间之间的模操作上。该定义可以递归构建。在您喜欢的编程语言中实现这一点应该不成问题。伪代码如下：

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]

到目前为止，我们无法做得比这更好了。在 (5) 中得到的区间可能是一个过度逼近，但这是我们能得到的最好结果。如果我们被允许返回一组区间，我们可以更精确。

一般情况

相同的思路适用于模数本身是一个区间的情况。具体如下：

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

玩得开心！:)

- user1564913

Answer 2

让我们看一下mod(x, y) = mod。

通常情况下，0 <= mod <= y。因此，以下始终成立：y_lo < mod < y_hi

但是我们可以看到以下特定情况：

- 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

....

- Hien Nguyen

---

你正在考虑的是类似的余数运算，但它对负数没有定义。但在 mod([2,2], [-3,-3]) = [2,2] 中，y_lo < mod < y_hi 不成立。 - Björn Lindqvist

y € [2,4]，x € [2,4] -> 取x = 3，y = 3，结果：0。观察您上面的陈述并填充数值得出1 < 0 < 1 ... 很明显是不正确的。 - Daniel Jour