Реализация Карацубы C ++ - PullRequest
Новая
       78

Реализация Карацубы C ++

0 голосов
/ 12 июля 2020

Итак, я решил попробовать реализовать алгоритм Карацубы на C ++ (не использовал этот язык с момента моего второго класса кодирования, время жизни go, поэтому я очень сильно заржавел). В любом случае, я считаю, что я следил за псевдокодом построчно, но мой алгоритм по-прежнему появляется с неправильным ответом. 


    x = 1234, y = 5678
    Actual Answer: x*y ==> 7006652
    Program output: x*y ==> 12272852

* Примечание: я использую ma c и используя следующее, чтобы создать исполняемый файл для запуска c++ -std=c++11 -stdlib=libc++ karatsuba.cpp

Anywho, вот набросок кода и не стесняйтесь делать некоторые замечания о том, что я делаю неправильно или как улучшить C ++.

Спасибо!

Код: 

    #include <iostream>
    #include <tuple>
    #include <cmath>
    #include <math.h>
    
    using namespace std;
    
    /** Method signatures **/
    tuple<int, int> splitHalves(int x);
    int karatsuba(int x, int y, int n);
    
    int main()
    {
        int x = 5678;
        int y = 1234;
        int xy = karatsuba(x, y, 4);
        cout << xy << endl;
        return 0;
    }
    
    int karatsuba(int x, int y, int n)
    {
        if (n == 1)
        {
            return x * y;
        }
        else
        {
            int a, b, c, d;
            tie(a, b) = splitHalves(x);
            tie(c, d) = splitHalves(y);
            int p = a + b;
            int q = b + c;
            int ac = karatsuba(a, c, round(n / 2));
            int bd = karatsuba(b, d, round(n / 2));
            int pq = karatsuba(p, q, round(n / 2));
            int acbd = pq - bd - ac;
            return pow(10, n) * ac + pow(10, round(n / 2)) * acbd + bd;
        }
    }
    
    
    /** 
     * Method taken from https://stackoverflow.com/questions/32016815/split-integer-into-two-separate-integers#answer-32017073
     */
    tuple<int, int> splitHalves(int x)
    {
        const unsigned int Base = 10;
        unsigned int divisor = Base;
        while (x / divisor > divisor)
            divisor *= Base;
        return make_tuple(round(x / divisor), x % divisor);
    }

1 Ответ

2 голосов
/ 12 июля 2020

В вашем коде много проблем ...

Во-первых, у вас неправильный коэффициент: 

            int q = b + c;

Должен быть: 

            int q = c + d;

Далее, реализация splitHalves не работает. Попробуйте следующее: 

tuple<int, int> splitHalves(int x, int power)
{
        int divisor = pow(10, power);
        return make_tuple(x / divisor, x % divisor);
}

Это даст вам «правильный» ответ на ваш ввод, но ... это не метод Карацубы.

Во-первых, имейте в виду, что вы не используете Не нужно «делить пополам». Рассмотрим 12 * 3456. разделение первого числа на половинки означает a = 0, b = 12, в то время как ваша реализация дает a = 1, b = 2.

В целом Karastuba работает с массивами, а не с целыми числами.

...