我正在研究一种算法，它将 2 n 位数字乘以 3 n/2 位的乘法。该算法被认为是有效的。虽然我知道空间显然是守恒的，但如果我在 n 位机器上工作，那么 n/2 位乘法将如何更好。这些 n/2 位乘法将转换为 n 位乘法，因为 CPU 只能理解 n 位数字。
先感谢您。
问问题
129 次
1 回答
1
Karatsuba 乘法或Toom-Cook等算法通常用于“bignums”的实现——具有无限大小的数字的计算。一般来说，算法越复杂，需要更大的数字才能使其值得做。
有多种 bignum 包；比较常用的一种是 Gnu Multiprecision 库gmplib，其中包含大量不同的乘法算法，根据被乘数的长度选择合适的算法。（根据维基百科，基于快速傅里叶变换算法的Schönhage–Strassen 算法直到被乘数达到 33,000 个十进制数字时才使用。这样的计算相对较少，但是当你必须进行这样的计算时，你可能关心它是否有效地完成。）
于 2013-09-22T01:08:23.873 回答