Блог

Главная - Вопросы по программированию - Не могли бы вы, пожалуйста, определить ошибку, которую я допустил в реализации алгоритма Карацуба на языке Си

Не могли бы вы, пожалуйста, определить ошибку, которую я допустил в реализации алгоритма Карацуба на языке Си

#c #algorithm #multiplication #karatsuba

Вопрос:

Мне нужно внедрить алгоритм карацубы в код на языке си для моей домашней работы, и я провел свое исследование и придумал следующий код:

 long int karatsuba(long int x,long int y)
{
    if((x<10)||(y<10)) \if the numbers have 1 digit, I just multiply them
        return x*y;
    else
    {
        long int a, b, c, d, ac, bd, z;
        int n=uzunluk(x);
        
        a=floor(x/ust(10, ceil(n/2)));
        b=x%ust(10, ceil(n/2));;
        c=floor(y/ust(10, ceil(n/2)));
        d=y%ust(10, ceil(n/2));;
        
        ac=a*c;
        bd=b*d;
        z=(a b)*(c d)-ac-bd;
    
        long int res=ust(10, 2*ceil(n/2))*ac ust(10, ceil(n/2))*z bd;
    
        return res;
    }       
}

int main(void)
{
    printf("%ld", karatsuba(837487, 368498));
    return 0;
}

ust(x, n) — это функция для получения степени числа x:

 long int ust(long x, long n)
{
    long int res=1;
    int i;
    for(i=0; i<n; i  )
    {
        res*=x;
    }
    return res;
}

И uzunluk(x) получает количество цифр в данном вводе:

 int uzunluk(long int x)
{
    int lx;
    while(x>0)
    {
        x/=10;
        lx =1;
    }
    return lx;      
}

проблема в том, что этот код ничего не печатает 😀
Я был бы рад, если бы кто-нибудь заметил мою ошибку.

Комментарии:

1. Если вы не проверяете весь свой код, ваша uzunluk функция неверна, потому что она использует значение неинициализировано lx при вычислении.

2. Целочисленные деления выполняются, floor(x/ust(10, ceil(n/2))) и результаты усекаются до целых чисел, поэтому функция floor и ceil не будет работать должным образом.

3. В дополнение к ошибкам в реальном алгоритме попробуйте добавить символ 'n' в конце печатной строки. printf печально известен тем, что иногда отказывается печатать строки, которые не заканчиваются на а 'n' . Следовательно, линия должна быть лучше: printf("%ldn", karatsuba(837487, 368498));

4. @MikeCAT решил проблему отсутствия печати результата, но теперь это дает неправильный результат. Напечатанный результат-отрицательное целое число, где у меня даже нет отрицательного ввода :d

5. @MahmutMahmudov Пожалуйста, не редактируйте свой код, чтобы исправить ошибки, на которые указывают люди. Теперь их комментарии недействительны.

Ответ №1:

Таким образом, получается, что проблема заключалась в том, что умножение 7-значных чисел не приводит к правильному результату при идентификации длинных целых чисел. Когда я изменил его на long long int, он начал работать должным образом. Спасибо всем вам за вашу помощь

Метки: , , ,