卡拉苏巴在 C 中的实现

Question

我正在尝试在c中实现kartsuba的算法，我遵循了维基百科上的伪代码，但问题是我并不总是得到正确的结果。

以下是实现：

long long karatsuba(char* a,char* b){
if (atoi(a)<10 || atoi(b)<10)
    return atoi(a)*atoi(b);
int m = ((strlen(a)<strlen(b))?strlen(a):strlen(b))/2;
char* high1 = slice(a,0,m);
char* low1 = slice(a,m,strlen(a)-m);
char* high2 = slice(b,0,m);
char* low2 = slice(b,m,strlen(b)-m);

long long z0 = karatsuba(low1,low2);
long long z1 = karatsuba(add(low1,high1),add(low2,high2));
long long z2 = karatsuba(high1,high2);
free(low1);
free(high1);
free(low2);
free(high2);    
return (z2*pow(10,m*2))+((z1-z2-z0)*pow(10,m)) + z0;
}

这是slice函数，它用于将一个数字划分为 2：

char* slice(char* s,int a,int n){
    char* r = calloc(n+1,sizeof(char));
    strncpy(r,s+a,n);
    return r;
}

这是用于将 2 个数字相加的add函数：

char* add(char* a,char* b){
char* r = calloc((strlen(a)>strlen(b)?strlen(a):strlen(b))+2,sizeof(char));
sprintf(r,"%lld",atoi(a)+atoi(b));
return r;
}

PS：只是出于好奇，我在许多实现中看到使用 max(size(num1(，size(num2((而不是min，可以吗，它会改变什么吗？

Answer 1

多

亏了@greybeard的评论，显然问题是我以一种最有效的部分有 m 位的方式对数字进行了分区，而不是它应该是最不重要的部分，所以要修复它：

我更改了这部分：

char* high1 = slice(a,0,m);
char* low1 = slice(a,m,strlen(a)-m);
char* high2 = slice(b,0,m);
char* low2 = slice(b,m,strlen(b)-m);

自：

char* high1 = slice(a,0,strlen(a)-m);
char* low1 = slice(a,strlen(a)-m,m);
char* high2 = slice(b,0,strlen(b)-m);
char* low2 = slice(b,strlen(b)-m,m);