我已经实现了 karatsuba 乘法算法。我想以这种方式改进它,我可以将 2 个 64 位数字相乘,但我不知道该怎么做。我得到一个提示,这两个数字都包含 2 的幂的位数,但它没有给我任何提示。你能给任何其他提示吗?数学提示或算法改进提示。
#include <iostream>
#include <math.h>
using namespace std;
int getLength(long long value);
long long multiply(long long x, long long y);
int getLength(long long value)
{
int counter = 0;
while (value != 0)
{
counter++;
value /= 10;
}
return counter;
}
long long multiply(long long x, long long y)
{
int xLength = getLength(x);
int yLength = getLength(y);
// the bigger of the two lengths
int N = (int)(fmax(xLength, yLength));
// if the max length is small it's faster to just flat out multiply the two nums
if (N < 10)
return x * y;
//max length divided and rounded up
N = (N / 2) + (N % 2);
long long multiplier = pow(10, N);
long long b = x / multiplier;
long long a = x - (b * multiplier);
long long d = y / multiplier;
long long c = y - (d * N);
long long z0 = multiply(a, c);
long long z1 = multiply(a + b, c + d);
long long z2 = multiply(b, d);
return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N)));
}
int main()
{
long long a;
long long b;
cin >> a;
cout << '\n';
cin >> b;
cout << '\n' << multiply(a, b) << endl;
return 0;
}
最佳答案
这里有一个提示:
(A + kB) * (C + kD) = AC + k(BC + AD) + k^2(BD)
如果 k
是您保留数字的底数的幂,这会有所帮助。例如,如果 k
是 1'000'000'000 并且您的数字以 10 为底,然后乘以 k
只需简单地移动数字(加零)即可完成。
无论如何,请考虑将您的 64 位数字分成两部分,每部分 32 位,然后像上面那样进行数学运算。要计算 AC
、BC
、AD
和 BD
,您需要将一对 32 位数字相乘,该数字可以以类似方式完成。
由于您的位数是 2 的幂,因此您可以继续将数字分成两半,直到达到可管理的数字大小(例如 1 位数)。
顺便说一句,从你的问题中不清楚你是在谈论 64 位还是 64 位十进制数字。如果您要查找的只是 64 位数字的乘法,只需执行以下操作:
// I haven't actually run this code, so...
typedef unsigned long long u64;
u64 high32 (u64 x) {return x >> 32;}
u64 low32 (u64 x) {return x & 0xFFFFFFFF;}
u64 add_with_carry (u64 a, u64 b, u64 * carry)
{
u64 result = a + b;
*carry = (result < a ? 1 : 0);
return result;
}
void mul (u64 a, u64 b, u64 * result_low, u64 * result_high)
{
u64 a0 = low32(a), a1 = high32(a);
u64 b0 = low32(b), b1 = high32(b);
u64 a0b0 = a0 * b0;
u64 a0b1 = a0 * b1;
u64 a1b0 = a1 * b0;
u64 a1b1 = a1 * b1;
u64 c0 = 0, c1 = 0;
u64 mid_part = add_with_carry(a0b1, a1b0, &c1);
*result_low = add_with_carry(a0b0, (low32(mid_part) << 32, &c0);
*result_high = high32(mid_part) + a1b1 + (c1 << 32) + c0; // this won't overflow
}
这个实现与上面概述的想法相同。由于在标准 C/C++ 中,我们可以在乘法结果中拥有的最大有意义位数是 64,那么我们一次只能将两个 32 位数字相乘。这就是我们在这里所做的。
最终结果将是 128 位,我们以两个无符号 64 位数字返回。我们通过执行 4 个 32 位乘法和一些加法来执行 64 位 x 64 位乘法。
作为旁注,这是为数不多的用汇编编写通常比用 C 编写更容易的情况之一。例如,在 x64 汇编中,这实际上是一个单一的 mul
指令,它乘以两个 64 位无符号整数,并将 128 位结果返回到两个 64 位寄存器。
即使你没有 64 位到 128 位的乘法指令,用汇编编写它仍然更容易(因为 adc
或类似的指令,例如上面的整个代码只是两个 mov
、四个 mul
、四个 add
和四个 adc
在普通 x86 汇编中。) 即使您不想用汇编语言编写,您也应该检查编译器的“内在函数”。它可能有一个用于大型乘法的函数(但您将依赖于平台。)
关于c++ - C++中2个64位数字的乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41718565/