реализация Карацубы в c

Я пытаюсь реализовать алгоритм Карцубы на c, я следовал псевдокоду в Википедии, но проблема в том, что я не всегда получаю правильный результат.

вот реализация:

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;
}

А это функция 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;
}

P.S: Просто из любопытства я видел во многих реализациях использование max (size(num1),size(num2)) вместо min, это нормально и что-то меняет?


c algorithm karatsuba
person LonelyDaoist    schedule 24.03.2019    source источник
comment
Я не всегда получаю правильный результат — какие данные вы вводите, какие результаты вы ожидаете и какие на самом деле получаете?   -  person ForceBru    schedule 24.03.2019
comment
алгоритм используется для умножения двух чисел a и b в строковом формате. например, для a=1234 и b=5678 я получаю 6592652, а результат должен быть 7006652   -  person LonelyDaoist    schedule 24.03.2019
comment
Вы пытались следовать псевдокоду en.wikipedia. Чтобы масштабирование с помощью 10 ^ m2 было правильным, какая часть, возвращаемая, скажем, split_at(num1, m2), должна иметь длину m2: более или менее значимая часть? Перечитайте абзац Основной шаг.   -  person greybeard    schedule 24.03.2019
comment
Это должна быть наименее значимая часть, верно? спасибо за ответ попробую исправить   -  person LonelyDaoist    schedule 24.03.2019

Ответы (1)


arrow_upward
0
arrow_downward

благодаря комментарию @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);

to:

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);
person LonelyDaoist    schedule 24.03.2019