我正在尝试实现递归 Karatsuba 算法,用于两个多项式(相同程度(的乘法。我的代码仍然不适用于次数大于 1 的多项式。谁能向我解释我在职能中做错了什么?它应该适用于偶数系数,也适用于奇数系数。
多项式存储在long
数组中。每个元素代表一个系数,因此1 2 3 4
表示1 + 2x + 3x^2 + 4x^3
,参数size
是系数的数量。
long* karatsuba(const long *A, const long *B, int size) {
long *lowA, *highA, *lowB, *highB, *midA, *midB;
if (size == 1)
return naive(A, B, size, size);
int half = size / 2;
lowA = new long[half];
lowB = new long[half];
midA = new long[half];
midB = new long[half];
highA = new long[half];
highB = new long[half];
// init low coefficients
for(int i=0; i<half; i++){
lowA[i] = A[i];
lowB[i] = B[i];
}
// init high // init low coefficients
for(int i=half; i<size; i++){
highA[i-half] = A[i];
highB[i-half] = B[i];
}
// init mid // init low coefficients
for(int i=0; i<half; i++){
midA[i] = lowA[i] + highA[i];
midB[i] = lowB[i] + highB[i];
}
long *z0 = karatsuba(lowA, lowB, half);
long *z1 = karatsuba(midA, midB, half);
long *z2 = karatsuba(highA, highB, half);
// compute the result
long *result = new long[2*size-1];
for(int i=0; i<half; i++){
result[i + 2*half] = z2[i];
result[i + half] = z1[i] - z0[i] - z2[i];
result[i] = z0[i];
}
return result;
}
我的主要问题是这个函数不能计算正确的结果。
我注意到一个半关于正确性的问题:
- "组合循环"中的索引仅限于递归调用参数长度而不是结果长度(几乎是参数长度的两倍(
- 当极限正确时,中间结果"重叠",需要累积而不是分配。
我从来没有"愤怒地"使用"现代C++"——如果这有效,但让你对代码不满意,请考虑在代码审查上发布你的疑虑。