很长整数的乘法 [英] Multiplication of very long integers

问题描述

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

Is there an algorithm for accurately multiplying two arbitrarily long integers together? The language I am working with is limited to 64-bit unsigned integer length (maximum integer size of 18446744073709551615). Realistically, I would like to be able to do this by breaking up each number, processing them somehow using the unsigned 64-bit integers, and then being able to put them back together in to a string (which would solve the issue of multiplied result storage).

有什么想法吗?

推荐答案

大多数语言都有执行此操作的函数或库，通常称为 Bignum 库 (GMP 是一个不错的选择.)

Most languages have functions or libraries that do this, usually called a Bignum library (GMP is a good one.)

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

If you want to do it yourself, I would do it the same way that people do long multiplication on paper. To do this you could either work with strings containing the number, or do it in binary using bitwise operations.

示例:

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

或二进制:

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

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

After doing it in binary I realized that it would be much simpler (and faster of course) to code using bitwise operations instead of strings containing the base-10 numbers. I've edited my binary multiplying example to show a pattern: for each 1-bit in the bottom number, add the top number, bit-shifted left the position of the 1-bit times to a variable. At the end, that variable will contain the product.

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

To store the product, you'll have to have two 64-bit numbers and imagine one of them being the first 64 bits and the other one the second 64 bits of the product. You'll have to write code that carries the addition from bit 63 of the second number to bit 0 of the first number.

这篇关于很长整数的乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！