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

问题描述

是否有一个算法，精确乘2任意长的整数在一起吗？我有工作语言是仅限于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

或者二进制：

Or in binary:

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

编辑：做二进制我意识到，这将是更简单（当然更快）使用逐位操作，而不是包含基本-10数字的字符串code之后。我已经编辑我的二进制乘法为例，说明​​一个规律：在底部的数量每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.

要保存的产品，你就必须有2个64位的数字，想象其中之一是前64位，另一个第二64位的产品。你必须写code携带另外从第二号位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屋！