乘两个整数四溢模第三 [英] Multiply two overflowing integers modulo a third

问题描述

由于三个整数， A ， B 和 C 与 A，b＆LT; = C＆LT; INT_MAX 我需要计算（A * B）％C ，但 A * B CAN溢出如果值太大，这给错误的结果。

Given three integers, a, band c with a,b <= c < INT_MAX I need to compute (a * b) % c but a * b can overflow if the values are too large, which gives the wrong result.

有没有办法直接通过bithacks计算这一点，即不使用类型不会溢出有问题的价值？

Is there a way to compute this directly through bithacks, i.e. without using a type that won't overflow for the values in question?

推荐答案

是不是真的在这里需要Karatsuba算法。这是不够的，只是一次分裂您的操作数。

Karatsuba's algorithm is not really needed here. It is enough to split your operands just once.

比方说，为简单起见，你的号码是64位无符号整数。令k = 2 ^ 32。然后

Let's say, for simplicity's sake, that your numbers are 64-bit unsigned integers. Let k=2^32. Then

a=a1+k*a2
b=b1+k*b2
(a1+k*a2)*(b1+k*b2) % c = 
   a1*b1 % c + k*a1*b2 % c + k*a2*b1 % c + k*k*a2*b2 % c

现在 A1 * B1％C 可以立即计算，其余可通过交替执行电子计算机X＆LT;＆LT; = 1 和 X％= C 32或64倍（因为（U * v）％C =（（U％C）* v）％C）。这可能表面上溢出，如果 C＆GT; = 2 ^ 63 。然而，好处是，这对操作不需要逐字进行。无论是 X＆LT; C / 2 然后你只需要一个转变（而且也没有溢出），或 X＆GT; = C / 2 和

Now a1*b1 % c can be computed immediately, the rest could be computed by alternately performing x <<= 1 and x %= c 32 or 64 times (since (u*v)%c=((u%c)*v)%c). This could ostensibly overflow if c >= 2^63. However, the nice thing is that this pair of operations need not be performed literally. Either x < c/2 and then you only need a shift (and there's no overflow), or x >= c/2 and

2*x % c = 2*x - c = x - (c-x).

（并再次没有溢出）。

(and there's no overflow again).

这篇关于乘两个整数四溢模第三的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！