Karatsuba Recursion
Karatsuba Recursion
提问于 2018-05-23 15:54:17
我试图实现一个递归的Karatsuba算法。我成功地为乘法编写了一个递归算法，但它计算了ad和bc。但是，对于这个程序，我试着记下每个中间值，即ac、bd、total、sum。许多值不显示为期望值。我不知道我的代码在哪里搞砸了。我仍然是一个业余程序员，我已经花了几个小时试图调试，但是现在我别无选择，只能在这里发布我的大型代码：
#include <iostream>
using namespace std;
int approxLog(int n, int b) {
return !(n/b < 1) ? 1+approxLog(n/b, b) : 1;
}
int power(int b, int e) {
return (e < 1) ? 1 : b*power(b, e-1);
}
int odd1(int n) {
if(n%2 != 0)
return n-1;
else
return n;
}
int odd2(int n) {
if(n%2 == 0)
return n/2;
else
return n/2 + 1;
}
void num_split (int num, int d, int *a, int *b) {
int i = 1, tmp = 0, j = 1, k = 0;
while (i <= d/2) {
tmp += (num%10)*power(10, i-1);
num /= 10;
i++;
}
*b = tmp;
tmp = 0;
while (i <= d) {
tmp += (num%10)*power(10, j-1);
num /= 10;
i++;
j++;
}
*a = tmp;
tmp = 0;
}
long long int multiply(int x, int y, int n) {
int a = 0, b = 0, c = 0, d = 0;
int ac = 0, bd = 0, total = 0, sum = 0;
int *ptr_a = &a;
int *ptr_b = &b;
int *ptr_c = &c;
int *ptr_d = &d;
num_split(x, n, ptr_a, ptr_b);
num_split(y, n, ptr_c, ptr_d);
if((x < 10) || (y < 10)) {
return x*y;
}
else {
ac = multiply(a, c, odd2(n));
bd = multiply(b, d, n/2);
total = multiply((a+b), (c+d), odd2(n));
// cout << total << endl;
sum = total - ac - bd;
return power(10, odd1(n))*ac + power(10, n/2))*sum + bd;
}
}
int main() {
int x = 1234, y = 1234;
int n = approxLog(x, 10);
long long int product = multiply(x, y, n);
cout << product << endl;
return 0;
}回答 1
Stack Overflow用户
回答已采纳
发布于 2018-05-23 16:40:54
问题是，在每一次递归中，您都应该采用近似的方法。x和y大的日志。因此，代码中的以下修改将解决问题(也注意注释掉的部分！)：
long long int multiply(int x, int y)//, int n)
{
int a = 0, b = 0, c = 0, d = 0;
int ac = 0, bd = 0, total = 0, sum = 0;
int *ptr_a = &a;
int *ptr_b = &b;
int *ptr_c = &c;
int *ptr_d = &d;
int n = (x>y)?approxLog(x, 10):approxLog(y, 10);
num_split(x, n, ptr_a, ptr_b);
num_split(y, n, ptr_c, ptr_d);
if((x < 10) || (y < 10)) {
return x*y;
}
else {
ac = multiply(a, c);//, odd2(n));
bd = multiply(b, d);//, n/2);
total = multiply((a+b), (c+d));//, odd2(n));
cout << total << endl;
sum = total - ac - bd;
return power(10, odd1(n))*ac + power(10, (n/2))*sum + bd;
}
}
int main() {
int x = 134546, y = 1234;
//int n = approxLog(x, 10);
long long int product = multiply(x, y);//, n);
cout<<"Karatsuba: "<<product<<endl;
cout<<"Normal: "<<x*y<<endl;
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50492747
复制相关文章
相似问题
腾讯云开发者
