高效地计算两个数之和的模

Question

我有三个N位数字，A、B和C。我无法轻松地计算(A + B) % C，但我可以轻松计算A % C和B % C。如果模运算是无符号的，并且我事先知道A + B不会超过N位，则可以计算((A % C) + (B % C)) % C。然而，在模运算为有符号或者A和B的加法可能导致环绕的情况下，是否有什么方法可以解决这些问题呢？

看起来有些混淆的是，为什么((A % C) + (B % C)) % C不能始终可靠地工作。以下是一个无符号示例：

unsigned A = 0x1U;
unsigned B = 0xFFFFFFFFU;
unsigned C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U

这是一个已签名的示例：

int A = 0x1;
int B = 0xE27F9803;
int C = 0x3U;
((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2

- user4315149

---

我认为你的公式适用于有符号数和无符号数。否则，有人能否提供一个反例？ - SlySherZ

此外，mod()有很多不同的实现方式。例如在JavaScript中，-10 % 3 = -1。而数学理论和R则表示-10 %% 3 = 2。 - Dinesh

什么是环绕？你的加法溢出了吗？ - Cimbali

@Dinesh 我们在这里谈论 C 语言中模运算符的使用，而 -10%3 应该是 -1：-10 / (3*(-3)) = -1。我不明白它怎么可能是 2。 - Tchou

((A % C) + (B % C)) % C 已经处理了 A+B 可能的溢出问题。 - barak manos

Answer 1

你想要的是：

((a+b)%2^n)%c

Let

a+b = k 2^n + d

当 k = 0 或 1 且 d < 2^n 时。

代入得到：

 ((k 2^n + d) % 2^n) % c = (d % 2^n) % c = d % c

将先前的表达式模除 c ，得到：

 (a + b) % c = (k 2^n + d) % c => d % c = a % c + b % c - k 2^n % c

在C语言中，当n = 32时：

unsigned myMod(unsigned a, unsigned b, unsigned c)
{
     // k = 1 if the sum overflows
     unsigned k = ( a > UINT_MAX - b or b > UINT_MAX - a);

     return ( a % c + b % c -  k*(UINT_MAX%c + 1))%c;
}

myMod(0x1U,0xFFFFFFFFU,0x3U) == 0 

- sbabbi

Answer 2

在数学中，整数除法通常向负无穷舍入，模运算的符号与“除数”相同或为零：-10 mod 3 = 2，10 mod -3 = -2（商向下舍入为-4）。在C / C ++中，整数除法向零舍入，％的符号与“被除数”或“分子”的符号相同或为零，-10 mod 3 = -1，10 mod -3 = 1（商向零舍入为-3）。在使用C / C ++进行有限域类型数学运算时，需要进行后期校正，以使结果与模数学定义匹配。例如，如果X％3 = -1，则添加3，使得X mod 3 = +2。

假设C为正数，则数学域模C由数字{0、1、... C-1}组成，没有任何负数。如果C为负数（这对于模数不寻常），则该域为{0、-1、-2、... C + 1}。假设C为正数，则如果A或B为负数，则仍然可以安全地使用((A％C) +（B％C）)％C，然后如果结果为负数，则通过将C添加到结果来进行后期校正。

- rcgldr

---

问题在于整数加法由于截断而插入了一个隐式模数。 - user4315149

@rcgldr，您能否引用一下您的定义参考文献？模数应该是一个正数。 - Dinesh

@Dinesh - 链接：取模运算维基百科 - 注意 Knuth 的定义 r = a - (floor(a/n) * n)，其中 floor 向负无穷舍入。素域维基百科 - 请注意，这样一个域的元素是模 p 的整数，它们是 0、...、p-1（对于正的 p 没有负数）。模算术维基百科 对于像 APL（来自 1960 年代）和 Python 这样的语言，模运算符的结果与除数具有相同的符号（或为零）。 - rcgldr

@Dinesh - 继续说，需要注意的是在APL或Python中定义的模运算函数更具数学一致性。使用整数运算：rem = (a + m*b) % b，在任何m（正数、零或负数）下都会返回相同的结果。此外，对于输入（被除数或分子）的符号，模的范围(图像)也是一致的，对于正b，它是{0、1、...，b-1}，对于负b，它是{0、-1、...，b+1}。 - rcgldr

@rcgldr 你说得对。我多年前从R语言移植到C/C++时遇到了一些问题，当时真的很难解决！ - Dinesh