有没有一种算法可以准确地将两个任意长的整数相乘？我正在使用的语言限制为 64 位无符号整数长度（最大整数大小为 18446744073709551615）。实际上，我希望能够通过分解每个数字来做到这一点，使用无符号 64 位整数以某种方式处理它们，然后能够将它们重新组合成一个字符串（这将解决相乘结果的问题贮存）。
有任何想法吗？
Valdemarick
问问题
15095 次
7 回答
13
大多数语言都有执行此操作的函数或库，通常称为 Bignum 库（GMP是一个很好的库。）
如果你想自己做，我会像人们在纸上做长乘法一样做。为此，您可以使用包含数字的字符串，也可以使用按位运算以二进制形式进行。
例子：
45
x67
---
315
+270
----
585
或二进制：
101
x101
----
101
000
+101
------
11001
编辑：在二进制中完成之后，我意识到使用按位运算而不是包含以 10 为基数的字符串进行编码会更简单（当然也更快）。我已经编辑了我的二进制乘法示例以显示一个模式：对于底部数字中的每个 1 位，添加顶部数字，将 1 位时间的位置向左移位到一个变量。最后，该变量将包含产品。
要存储产品，您必须有两个 64 位数字，并想象其中一个是产品的前 64 位，另一个是产品的第二个 64 位。您必须编写代码，将第二个数字的第 63 位加到第一个数字的第 0 位。
于 2008-10-11T00:00:13.460 回答
4
如果您不能使用现有的 bignum 库，如 GMP，请查看Wikipedia 上关于计算机二进制乘法的文章。为此，有许多好的、有效的算法。
于 2008-10-11T09:56:37.920 回答
3
最简单的方法是使用教科书机制，将任意大小的数字分成 32 位的块。
给定 ABCD * EFGH（每个块 32 位，总共 128 位）
您需要一个 9 个双字宽的输出数组。将 Out[0..8] 设置为 0
你首先要做： H * D + out[8] => 64 位结果。
将低 32 位存储在 out[8] 中，将高 32 位作为进位
下一步：(H * C) + out[7] + 进位
再次将低 32 位存储在 out[7] 中，使用高做 H*A + out[4] + 进位后32 位作为进
位，你需要继续循环，直到你没有进位。
然后用 G、F、E 重复。
对于 G，您将从 out[7] 而不是 out[8] 开始，依此类推。
最后，遍历并将大整数转换为数字（这将需要“将大数除以一个单词”例程）
于 2008-10-11T05:27:26.090 回答
1
是的，您使用的数据类型实际上是一串数字（就像普通的“字符串”是一串字符一样）。你如何做到这一点高度依赖于语言。例如，Java 使用 BigDecimal。您使用什么语言？
于 2008-10-10T23:57:18.537 回答
1
这通常作为家庭作业给出。你在小学学到的算法会起作用。如果您需要将其用于实际应用程序，请使用库（其他帖子中提到了几个）。
于 2008-10-10T23:59:03.883 回答
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;
}
于 2013-08-03T19:25:39.980 回答
0
//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)于 2018-10-18T08:19:51.060 回答