c - 将两个溢出的整数以三分之一为模相乘

Question

给定三个整数 ,a和bwithc我a,b <= c < INT_MAX需要计算(a * b) % c，但a * b如果值太大会溢出，这会给出错误的结果。

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

Answer 1

这里并不真正需要 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可以立即计算，其余的可以通过交替执行32x <<= 1或x %= c64 次来计算（因为 (u*v)%c=((u%c)*v)%c）。如果c >= 2^63. 然而，好消息是这对操作不需要按字面意思执行。要么x < c/2然后你只需要一个班次（并且没有溢出），或者x >= c/2和

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

（并且没有再次溢出）。

Answer 2

一些主要的编译器提供 128 位整数类型，您可以使用它进行此计算而不会溢出。