需要一个有效的减法算法模数

Question

对于给定的数字x,y并且n,我想计算x-y mod n在C.在这个例子来看一下:

int substract_modulu(int x, int y, int n)
{
    return (x-y) % n;
}

只要x>y,我们没事.然而,在另一种情况下,modulu操作是未定义的.

你可以想到x,y,n>0.我希望结果是正的,所以如果(x-y)<0,那么((x-y)-substract_modulu(x,y,n))/ n应该是一个整数.

您知道的最快算法是什么？有没有避免任何电话if和operator?？

Answer 1

正如许多人所指出的那样,在当前的C和C++标准中,x % n不再为任何x和的值定义实现n.在未定义的情况下,它是未定义的行为x / n[1].此外,x - y在整数溢出的情况下是未定义的行为,如果符号x和y可能不同的话,这是可能的.

因此,一般解决方案的主要问题是避免整数溢出,无论是在除法还是减法中.如果我们知道x并且y是非负的并且n是正的,则溢出和除零是不可能的,我们可以自信地说这(x - y) % n是定义的.不幸的是,x - y可能是否定的,在这种情况下,%运营商的结果也是如此.

如果我们知道这n是积极的,那么很容易纠正结果是否定的; 我们所要做的就是无条件地添加n并执行另一个modulo操作.这不太可能是最好的解决方案,除非你的计算机的分区比分支更快.

如果条件加载指令可用(这些天很常见),那么编译器可能会很好地使用以下代码,这些代码是可移植的并且定义明确,受以下约束x,y ≥ 0 ∧ n > 0:

((x - y) % n) + ((x >= y) ? 0 : n)

例如,gcc为我的核心I5生成了这个代码(虽然它足够通用,可用于任何非古生代的intel芯片):

    idivq   %rcx
    cmpq    %rsi, %rdi
    movl    $0, %eax
    cmovge  %rax, %rcx
    leaq    (%rdx,%rcx), %rax

这是愉快的无分支.(条件移动通常比分支快很多.)

另一种方法是(除了sign需要编写函数):

((x - y) % n) + (sign(x - y) & (unsigned long)n)

其中sign是全1如果它的参数是负的,并且否则返回0.一种可能的实施标志(改编自bithacks)被

unsigned long sign(unsigned long x) {
  return x >> (sizeof(long) * CHAR_BIT - 1);
}

这是可移植的(定义了无符号的负整数值),但在缺少高速移位的架构上可能会很慢.它不可能比之前的解决方案更快,但是YMMV.TIAS.

对于可能存在整数溢出的一般情况,这些都不会产生正确的结果.处理整数溢出非常困难.(一个特别令人讨厌的情况是n == -1,虽然你可以测试它并且在没有任何使用的情况下返回0.%)此外,你需要决定你对模数为负的结果的偏好n.我个人更喜欢定义哪里x%n是0或者具有相同的符号n- 否则为什么你会担心负除数 - 但应用程序不同.

Tom Tanner提出的三模解决方案如果n不存在-1且n + n不会溢出将会起作用.n == -1如果任一会失败x或y是INT_MIN,以及使用的简单的解决abs(n),而不是n如果将失败n是INT_MIN.在案件n具有较大的绝对值可以用比较来代替,但也有很多的极端情况,并提出了由事实更为复杂,该标准不要求2码算术运算,所以它不容易预测的极端案例是什么[2].

最后,一些诱人的解决方案不起作用.你不能只取绝对值(x - y):

(-z) % n == -(z % n) == n - (z % n) ≠ z % n(除非z % n碰巧n / 2)

而且,出于同样的原因,你不能只取模数结果的绝对值.

此外,你不能只是转换(x - y)为无符号:

(unsigned)z == z + 2k (for some k) if z < 0
(z + 2k) % n == (z % n) + (2k % n) ≠ z % n 除非 (2k % n) == 0

[1] x/n并且x%n都是未定义的n==0.但是,x%n如果x/n"不可表示"(即存在整数溢出),这也将是未定义的,这将发生在二进制补码机器上(即所有你关心的)如果x是最负面可表示的数字和n == -1.很明显为什么x/n在这种情况下应该是未定义的,但在这种情况下稍微不那么明确x%n,因为该值是(数学上)0.

[2]大多数抱怨难以预测浮点运算结果的人都没有花太多时间来编写真正可移植的整数算术代码:)