我实现了卡拉苏巴乘法算法。我想以这种方式改进它，我可以将 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 位数字返回。我们正在做一个 64 位乘 64 位乘法，通过做 4 个 32 位乘法和一些加法。
作为旁注，这是为数不多的情况之一，编写这是汇编通常比 C 更容易。例如，在 x64 汇编中，这实际上是一条mul指令，它将两个 64 位无符号整数相乘，并在两个 64 位寄存器中返回 128 位结果。
即使您没有 64 位到 128 位的乘法指令，仍然在汇编中编写它更容易(因为adc或类似的指令，例如上面的整个代码在普通 x86 汇编中只有两个mov、四个mul、四个add和四个adc。 即使你不想用汇编来写， 您应该检查编译器的"内部函数"。它可能有一个用于大乘法的(但您将依赖于平台。
要在较低的位宽算法上应用 Karatsuba 或任何其他乘法，您需要将数字分成较小的"数字"。首先，您需要访问这些"数字"，因此以下是操作方法：
您有数字1234，并希望将其除以10^1位数，因此
1234 = 1*1000 + 2*100 + 3*10 + 4
您可以像这样获取数字：
x=1234;
a0=x%10; x/=10; // 4
a1=x%10; x/=10; // 3
a2=x%10; x/=10; // 2
a3=x%10; x/=10; // 1
如果您想要10^2位数，则：
x=1234;
a0=x%100; x/=100; // 34
a1=x%100; x/=100; // 12
现在的问题是，要做到这一点，你需要对你没有的全数进行除法。如果您将数字作为字符串，那么它很容易完成，但让我们假设您没有。计算机基于二进制计算，因此最好使用 2 的幂作为"数字"的基础，因此：
x = 1234 = 0100 1101 0010 bin
现在，如果我们想要例如2^4=16基数，那么：
a0=x%16; x/=16; // 0010
a1=x%16; x/=16; // 1101
a2=x%16; x/=16; // 0100
现在，如果您意识到除以 2 的幂只是位右移，余数可以表示为 AND，然后：
a0=x&15; x>>=4; // 0010
a1=x&15; x>>=4; // 1101
a2=x&15; x>>=4; // 0100
位移可以堆叠到任何位宽数字，所以现在你得到了你需要的一切。但这还不是全部，如果您选择"数字"，例如2^8这是BYTE那么您可以使用指针代替，例如：
DWORD x=0x12345678; // 32 bit number
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x
a0=db[0]; // 0x78
a1=db[1]; // 0x56
a2=db[2]; // 0x34
a3=db[3]; // 0x12
因此，您可以直接访问数字或从数字重建 X：
DWORD x; // 32 bit number
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x
db[0]=0x78;
db[1]=0x56;
db[2]=0x34;
db[3]=0x12;
// here x should be 0x12345678
请注意，订单取决于平台 MSB 或 LSB 第一订单。现在您可以应用乘法。例如，在 16 位乘法上完成的 32*32=64 位是这样用朴素O(n^2)方法完成的：
x(a0+a1<<16) * y(b0+b1<<16) = a0*b0 + a0*b1<<16 + a1*b0<<16 + a1*b1<<32
其中 a0，a1，b0，b1 是操作数的数字。请注意，每个ai*bj乘法的结果都是 2 位宽的，因此您需要将其拆分为数字并存储为位移寻址的结果数字。请注意，添加可能会导致溢出到更高的数字。要解决这个问题，您需要使用至少两倍的算术宽度进行加法(16*16 位 mul -> 32 位加法)或使用 carry 标志。可悲的是，除了在C++中使用程序集之外，您无法访问 Carry 标志。幸运的是，可以模拟它，请参阅：
- 无法通过进位使价值传播
现在您可以构建您的卡拉苏巴或更高级的乘法以获取更多信息，请参阅：
- 快速大南平方计算