algorithm - 非常长的整数的乘法

Question

是否有一种算法可以将两个任意长的整数精确相乘？我使用的语言限于 64 位无符号整数长度(最大整数大小为 18446744073709551615)。实际上，我希望能够通过分解每个数字，使用无符号 64 位整数以某种方式处理它们，然后能够将它们重新组合成一个字符串来做到这一点(这将解决相乘结果的问题存储)。

有什么想法吗？

Answer 1

大多数语言都有执行此操作的函数或库，通常称为 Bignum 库(GMP 是一个很好的库。)

如果你想自己做，我会像人们在纸上做长乘法一样做。为此，您可以使用包含数字的字符串，或者使用按位运算以二进制形式执行此操作。

例子:

  45
 x67
 ---
 315
+270
----
 585

或者二进制:

   101
  x101
  ----
   101
  000
+101
------
 11001

编辑:在用二进制完成后，我意识到使用按位运算而不是包含以 10 为底的数字的字符串进行编码会更简单(当然也更快)。我编辑了我的二进制乘法示例以显示一个模式:对于底部数字中的每个 1 位，将顶部数字添加到一个变量中，向左移动 1 位的位置 .最后，该变量将包含产品。

要存储产品，您必须有两个 64 位数字，并且假设其中一个是产品的前 64 位，另一个是产品的第二个 64 位。您必须编写代码，将第二个数字的第 63 位与第一个数字的第 0 位相加。