乘以很长的整数

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位的代码.

Answer 2

如果您无法使用现有的 bignum 库（例如 GMP），请查看维基百科关于计算机二进制乘法的文章。有许多优秀、高效的算法可以实现这一点。