将两个溢出的整数乘以第三个模数
给定三个整数, a
, b
和c
, a,b <= c < INT_MAX
我需要计算(a * b) % c
但如果值太大则a * b
会溢出,这会产生错误的结果。
有没有办法直接通过bithacks计算它,即不使用不会溢出的值的类型?
这里并不真正需要Karatsuba的算法。 仅仅拆分一次操作数就足够了。
让我们说,为简单起见,您的数字是64位无符号整数。 设k = 2 ^ 32。 然后
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 <<= 1
和x %= c
32或64次来计算(因为(u * v)%c =((u%c)* v)的%C)。 如果c >= 2^63
这表面上可能会溢出。 然而,好的一点是,这对操作不需要按字面意思执行。 要么x < c/2
然后你只需要一个移位(并且没有溢出),或者x >= c/2
并且
2*x % c = 2*x - c = x - (cx).
(并且没有再次溢出)。
一些主要的编译器提供128位整数类型,您可以使用它来执行此计算而不会溢出。