将两个溢出的整数乘以第三个模数
给定三个整数， 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位整数类型，您可以使用它来执行此计算而不会溢出。