是否有一种算法可以准确地将两个任意长的整数相乘？我正在使用的语言仅限于64位无符号整数长度（最大整数大小为18446744073709551615）。现实情况是，我希望能够通过分解每个数字，使用无符号64位整数进行处理，然后能够将它们组合成一个字符串（这将解决乘积结果存储的问题）。
有什么想法吗？
7个回答
14
大多数编程语言都有函数或库可以实现此功能，通常称为Bignum库（GMP是一个好的选择）。
如果您想自己实现，我建议您采用人们在纸上进行长乘法的方式。要做到这一点，您可以使用包含数字的字符串，也可以使用位运算来进行二进制计算。
例如：
45
x67
---
315
+270
----
585
或者用二进制表示：
101
x101
----
101
000
+101
------
11001
编辑：在用二进制计算后，我意识到使用按位运算符比包含十进制数字的字符串更简单（当然也更快）。我已编辑我的二进制乘法示例以显示一个模式：对于底数中的每个1位，将顶数左移1位所在的位置乘以一个变量。最后，该变量将包含乘积。
要存储乘积，您需要有两个64位数字，并将其中一个想象为产品的前64位，另一个想象为产品的后64位。您需要编写代码，将第二个数字的63位加到第一个数字的0位。
- Jeremy Ruten
2
3恭喜，你刚刚重新发明了“农民乘法”。 ;) - Nick Johnson
4有比“农民乘法”更快的乘法算法。 - DanielOfTaebl
3
最简单的方法是使用学校教科书机制，将任意大小的数字分成每个32位的块。
给定A B C D * E F G H（每个块32位，总共128位），您需要一个输出数组，宽度为9个双字。将Out [0..8]设置为0。
首先执行：H * D + out [8] => 64位结果。将低32位存储在out [8]中，并将高32位作为进位。接下来：（H * C）+ out [7] + carry。同样，将低32位存储在out [7]中，使用高32位作为进位。在执行H * A + out [4] + carry之后，需要继续循环，直到没有进位。
然后重复G，F，E。对于G，您将从out [7]开始而不是out [8]，依此类推。
最后，遍历并将大整数转换为数字（这将需要一个“将大数除以单个字”例程）。
给定A B C D * E F G H（每个块32位，总共128位），您需要一个输出数组，宽度为9个双字。将Out [0..8]设置为0。
首先执行：H * D + out [8] => 64位结果。将低32位存储在out [8]中，并将高32位作为进位。接下来：（H * C）+ out [7] + carry。同样，将低32位存储在out [7]中，使用高32位作为进位。在执行H * A + out [4] + carry之后，需要继续循环，直到没有进位。
然后重复G，F，E。对于G，您将从out [7]开始而不是out [8]，依此类推。
最后，遍历并将大整数转换为数字（这将需要一个“将大数除以单个字”例程）。
- Procedural Throwback
2
是的，您可以使用一种有效地将数字串（就像普通的“字符串”是字符串一样）作为数据类型来完成此操作。如何实现这一点高度依赖于编程语言。例如，Java使用BigDecimal。您使用的是什么编程语言？
- Draemon
1
Freebasic并没有内置这个功能，但如果我能了解所使用的算法，我愿意编写它。 - Valdemarick
2
这通常被作为一项家庭作业。你在小学学到的算法可以使用。如果你需要在实际应用中使用，可以使用库（其他帖子中提到了几个库）。
- ejgottl
1
//Here is a JavaScript version of an Karatsuba Algorithm running with less time than the usual multiplication method
function range(start, stop, step) {
if (typeof stop == 'undefined') {
// one param defined
stop = start;
start = 0;
}
if (typeof step == 'undefined') {
step = 1;
}
if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
return [];
}
var result = [];
for (var i = start; step > 0 ? i < stop : i > stop; i += step) {
result.push(i);
}
return result;
};
function zeroPad(numberString, zeros, left = true) {
//Return the string with zeros added to the left or right.
for (var i in range(zeros)) {
if (left)
numberString = '0' + numberString
else
numberString = numberString + '0'
}
return numberString
}
function largeMultiplication(x, y) {
x = x.toString();
y = y.toString();
if (x.length == 1 && y.length == 1)
return parseInt(x) * parseInt(y)
if (x.length < y.length)
x = zeroPad(x, y.length - x.length);
else
y = zeroPad(y, x.length - y.length);
n = x.length
j = Math.floor(n/2);
//for odd digit integers
if ( n % 2 != 0)
j += 1
var BZeroPadding = n - j
var AZeroPadding = BZeroPadding * 2
a = parseInt(x.substring(0,j));
b = parseInt(x.substring(j));
c = parseInt(y.substring(0,j));
d = parseInt(y.substring(j));
//recursively calculate
ac = largeMultiplication(a, c)
bd = largeMultiplication(b, d)
k = largeMultiplication(a + b, c + d)
A = parseInt(zeroPad(ac.toString(), AZeroPadding, false))
B = parseInt(zeroPad((k - ac - bd).toString(), BZeroPadding, false))
return A + B + bd
}
//testing the function here
example = largeMultiplication(12, 34)
console.log(example)- Pianistprogrammer
3
你的代码有很多语法错误，导致编译失败。我已经修复了其中一些，但代码仍然无法正常工作。 - phuclv
你确定这个能用吗？为什么要移除JS标签以便人们验证？ - phuclv
那不是故意的，我只是用可工作的代码重新替换了它。你可以为此创建一个 Plunkr 或 JSFiddle。 - Pianistprogrammer
1
这是我的C代码片段。好老的乘法方法。
char *multiply(char s1[], char s2[]) {
int l1 = strlen(s1);
int l2 = strlen(s2);
int i, j, k = 0, c = 0;
char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string
int temp;
strrev(s1);
strrev(s2);
for (i = 0;i <l1+l2; i++) {
r[i] = 0 + '0';
}
for (i = 0; i <l1; i ++) {
c = 0; k = i;
for (j = 0; j < l2; j++) {
temp = get_int(s1[i]) * get_int(s2[j]);
temp = temp + c + get_int(r[k]);
c = temp /10;
r[k] = temp%10 + '0';
k++;
}
if (c!=0) {
r[k] = c + '0';
k++;
}
}
r[k] = '\0';
strrev(r);
return r;
}
- ron
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接