模函数可避免C ++中的整数溢出 [英] Modulus Function to Avoid Integer Overflow in C++

问题描述

如果我有2个 int 或 long long 变量，则将它们称为 a 和 b ，我想要要计算总和(a + b)mod p ，其中p是一个大素数，如何在C ++中利用模运算符获得所需的结果?

If I have 2 int or long long variables, call them a and b, and I want to compute the sum (a + b) mod p, where p is a large prime integer, how can I utilize the modulo operator in C++ to achieve the desired result?

我已经尝试过(a + b)％p ，但这有时会导致溢出，因为 a + b 将在应用mod之前溢出.

I have tried (a + b) % p, but this gives overflow sometimes, since a + b will overflow before the mod is applied.

我尝试过的其他类似方法似乎避免了溢出，但是给出了错误的结果.

Other similar approaches I have tried seem to avoid overflow, but give an incorrect result.

在这种情况下，如何使用模运算符正确计算所需的总和，同时避免溢出?

How can I use the modulo operator in this case to correctly compute the desired sum, while avoiding overflow?

推荐答案

a %= p
b %= p
c = p-a

if(b==c)
  sum = 0
if (b<c)
 sum = a+b
if (b>c)
 sum = b-c

诀窍是避免在不知道限制在哪里的情况下进行任何可能导致溢出的计算.我们所知道的是给定的a，b和p低于限制-可能恰好低于限制.

The trick is to avoid any calculation that might cause overflow, without knowing where the limit is. All we know is that the given a, b and p are below the limit -- maybe just below the limit.

在前两个步骤( a％= p; b％= p; )之后，我们知道了 a< p 和 b< p .我们仍然不添加 a + b ，因为该总和可能超过p并超出限制 ^* .但是我们可以看到 c = pa 还剩下多少空间，这是安全的，因为我们知道 c< = p 和 c> 0 .(声明的类型是无符号的，但是我们最好避免使用负数，即使仅仅是因为它们的限制有时以一种我永远不会记住的方式与 positive 限制的负数相差一个即可.)

After the first two steps (a%=p;b%=p;) we know a<p and b<p. We still daren't add a+b, because that sum might exceed p and break the limit^*. But we can see how much room we have left with c = p-a, which is safe because we know that c<=p and c>0. (The stated types are unsigned, but we may as well avoid negative numbers, if only because their limits are sometimes off by one from the negatives of the positive limits, in ways I can never remember.)

如果b = c，则b = p-a，所以a + b = p，所以和(模p)为零.

If b=c, then b=p-a, so a+b=p, so the sum (mod p) is zero.

如果 b< c ，则 a + b< p ，因此我们可以安全地计算 a + b (而不必应用模).

If b<c, then a+b<p, so we can safely compute a+b (and need not apply the modulo).

如果 b> c ，则计算 a + b 不是是安全的，但是我们知道我们要查找的数字for是 a + bp ，我们可以将其重写为 b-(pa)，并且我们已经有 b 和 pa ，这样我们就可以安全地执行该减法了.

if b>c, then it is not safe to compute a+b, but we know that the number we're looking for is a+b-p, which we can rewrite as b-(p-a), and we already have b and p-a, so we can safely perform that subtraction.

(*)_{是的，我说不敢".这是一个非常好的词.}

这篇关于模函数可避免C ++中的整数溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！