lve*_*lla 4 c algorithm math modular-arithmetic
我有3个大的64位数字:A,B和C.我想计算:
(A x B) mod C
考虑到我的寄存器是64位,即写入a * b实际产生(A x B)mod2⁶⁴.
最好的方法是什么？我在C编码,但在这种情况下不认为语言是相关的.
在获得指向此解决方案的评论之后:
(a * b) % c == ((a % c) * (b % c)) % c
让我具体一点:这不是一个解决方案,因为((a%c)*(b%c))可能仍然大于2⁶⁴,寄存器仍会溢出并给我错误的答案.我会:
(((A mod C)x(B mod C))mod2⁶⁴)mod C.
正如我在评论中指出的那样,Karatsuba的算法可能有所帮助.但是仍然存在问题,需要单独的解决方案.
假设
A =(A1 << 32)+ A2
B =(B1 << 32)+ B2.
当我们乘以那些:
A*B =((A1*B1)<< 64)+((A1*B2 + A2*B1)<< 32)+ A2*B2.
所以我们有3个数字我们想要求和,其中一个肯定大于2 ^ 64而另一个可能是.
但它可以解决!
一旦我们将它分成较小的移位并且每次移位时都进行模运算,而不是移位64位.结果将是相同的.
如果C本身大于2 ^ 63,这仍然是一个问题,但我认为即使在这种情况下它也可以解决.