计算两个区间的模

问题描述 投票:0回答:3

我想了解模数运算符应用于两个区间时如何工作。两个区间的加、减、乘在代码中实现起来很简单,但是对于模数如何实现呢?

如果有人可以向我展示公式、示例代码或解释其工作原理的链接,我会很高兴。

背景信息:您有两个整数

x_lo < x < x_hi
y_lo < y < y_hi
mod(x, y)
的下限和上限是多少?

编辑:我不确定是否可以以有效的方式得出最小界限(无需计算所有 x 或所有 y 的 mod)。如果是这样,那么我将接受准确但非最佳的边界答案。显然,[-inf,+inf] 是一个正确的答案:)但我想要一个大小更有限的界限。

math intervals modulo integer-arithmetic
3个回答
4
投票

事实证明,这是一个有趣的问题。我所做的假设是,对于整数间隔,模是相对于截断除法定义的(向0舍入)。

因此,

mod(-a,m) == -mod(a,m)
对于所有 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

玩得开心! :)


0
投票

让我们看看 mod(x, y) = mod。 一般来说 0 <= mod <= y. So it's always true: 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

....


0
投票

我假设两个区间都是正数,换句话说

0 <= x_lo
0 < y_lo
- 只是因为负数会让事情变得更复杂。

我们来看看

mod
的定义:

x = k*y + mod(x, y)
k = floor(x/y)

应用于非负区间时,除法并不太复杂:

floor(x_lo / y_hi) <= k <= floor(x_hi / y_lo)
。将这些边界称为
k_lo
k_hi
。如果我们计算出
k_lo = k_hi = k
,那么我们可以代入上面的方程并求解
mod(x, y)

mod(x, y) = x - k*y

所以

x_lo - k*y_hi <= mod(x, y) <= x_hi - k*y_lo
k_lo = k_hi
时。


如果您在 mod(x, y)

 旁边查看 
k = floor(x/y)
3d 图,那么您会看到共享
k
值的大区域,这些区域在
x
y
中看起来是线性(平面)的。上面的计算是为了当结果仅限于这些区域中的单个区域时找到边界,其中
k
具有特定值。线性使得计算边界变得容易。这些 3d 区域让我想起常数
mod(x, c)
c
的 2d 图如何具有锯齿图案,并分为线性区域。接下来我们将看看模结果何时可以跨越多个区域。

k_lo < k_hi
的所有其他情况下,跨越多个
k
值的可能结果。每个区域都是平面/线性的,因此如果我们正在寻找上限和下限,它们将沿着区域的边界。 (我相信导数和不连续性是有道理的。)

k = floor(x/y)
值之间的边界是当
x/y
是整数时,即每当
x
y
的倍数时。如果 x 和 y 是实数,则 x 是 y 的倍数的线将是
mod(x, y)
从上方接近
0
以及从下方接近
y
的位置。我们知道间隔跨越了这些边界之一,因此只需再向前迈出一小步即可看到我们的
lower_bound = 0
。万岁!

现在为了找到该区间内的上限,我们正在寻找

y
的最大值,使得
x
y
的倍数。

我手头没有这个公式,但是一旦你计算了它 - 让我们称之为

y_best
-
mod(x, y)
的最大值是小于
y_best
的最大整数。

所以当

k_lo < k_hi
0 <= mod(x, y) <= ceil(y_best) - 1
。如果我的数学正确的话。

© www.soinside.com 2019 - 2024. All rights reserved.