Блог

Сначала немного предыстории:
— Я новичок, студент университета (не в программировании).
— Это не вопрос домашнего задания, я делаю это только для развлечения.
— Мой опыт программирования состоит из одного семестра (3 месяца) C и некоторого QBasic в средней школе.
— Да, я просмотрел библиотеки GMP и Bignum; очень сложно изучать материал из необработанных кодов, особенно без понимания намерений программистов. Кроме того, я хочу научиться делать это для себя.

Я кодирую функцию умножения для произвольно больших целых чисел. Я использую массивы символов для представления этих чисел, с или — в конце, чтобы служить в качестве часового (например. «12345 «, «31415-«).

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

 char* dam(char* one, char* two){            // Karatsuba method

    char* zero = intochar(0, 0);
    int size_a = char_size(one) - 1;
    int size_b = char_size(two) - 1;

    if(compare(one, zero) == 0 || compare(two, zero) == 0)
        return zero;                        // if either array is zero, product is zero
    delete[] zero;

    if(size_a < 4 amp;amp; size_b < 4)            // if both numbers are 3 digits or less, just return their product
        return multiplication(one, two);
                                            // is the product negative?
    bool negative = one[size_a] == two[size_b]? false : true;
    int digits = size_a > size_b ? size_a : size_b;
    digits  = digits amp; 1;                   // add one if digits is odd
    int size = digits / 2   1;              // half the digits plus sentinel

    char* a, *b;                            // a and b represent one and two but with even digits
    if(size_a != digits)
        a = pad_char(one, digits - size_a); // pad the numbers with leading zeros so they have even digits
    else
        a = copy_char(one);
    if(size_b != digits)
        b = pad_char(two, digits - size_b);
    else
        b = copy_char(two);

    char* a_left = new char[size];          // left half of number a
    char* a_rite = new char[size];          // right half of number a
    char* b_left = new char[size];
    char* b_rite = new char[size];
    memcpy(a_left, a, size - 1);
    a_left[size - 1] = a[digits];
    memcpy(a_rite, a   size - 1, size);
    memcpy(b_left, b, size - 1);
    b_left[size - 1] = b[digits];
    memcpy(b_rite, b   size - 1, size);
    delete[] a;
    delete[] b;

    char* p0 = dam(a_left, b_left);         // Karatsuba product = p1*10^n   (p0 p2-p1)*10^(n/2)   p2
    char* p2 = dam(a_rite, b_rite);
    deduct(a_left, a_rite);
    deduct(b_left, b_rite);
    char* p1 = dam(a_left, b_left);
    char* p3 = intochar(0, digits - 1);     // p3 = p0   p2 - p1
    append(p3, p0);                         // append does naive addition
    append(p3, p2);
    deduct(p3, p1);
    delete[] a_left;
    delete[] a_rite;
    delete[] b_left;
    delete[] b_rite;

    int sum_size = 2 * digits;              // product of two numbers can have a maximum of n1   n2 digits
    char* sum = new char[sum_size   1];
    memset(sum, 0, sum_size);
    if(negative)
        sum[sum_size] = '-';
    else
        sum[sum_size] = ' ';

    char* left = extend_char(p0, digits, false);        // extend returns a new array with trailing zeros
    char* mid = extend_char(p3, size - 1, false);
    append(sum, left);
    append(sum, mid);
    append(sum, p2);
    delete[] p0;
    delete[] p1;
    delete[] p2;
    delete[] p3;
    delete[] left;
    delete[] mid;

    return sum;}
  

Карацуба — хороший алгоритм, и его не так сложно программировать. Если вы делаете это только для развлечения, даже неплохо поработать с базой 10 — это ужасно замедляет вас, но также замедляет и наивную реализацию, так что у вас все еще есть основа для сравнения двух методов.

Однако вы абсолютно должны отказаться от идеи динамического выделения и освобождения вашего рабочего пространства в каждом узле дерева рекурсии. Вы просто не можете себе этого позволить. Вы должны выделить требуемое рабочее пространство в начале вычисления и разумно обрабатывать свои указатели, чтобы каждый уровень дерева получал необходимое рабочее пространство без необходимости его выделения.

Кроме того, нет смысла проверять отрицательные продукты на каждом уровне. Просто сделайте это на верхнем уровне и работайте исключительно с положительными числами во время вычисления.

Не то, чтобы это имело отношение к вашему вопросу, но всякий раз, когда я вижу что-то вроде

 bool negative = one[size_a] == two[size_b]? false : true;
  

мое сердце немного сжимается. Подумайте обо всех этих потраченных впустую пикселях! Я с уважением предлагаю:

 bool negative = one[size_a] != two[size_b] ;
  

Использование прописанных десятичных значений приводит к большим накладным расходам. Умножение Карацубы превзойдет длинное умножение только для чисел, которые огромны по сравнению с размером машинного регистра, и вы действительно хотите, чтобы каждое примитивное умножение выполняло как можно больше работы. насколько это возможно.

Я рекомендую вам перепроектировать свою структуру данных таким образом, чтобы это:

 if(size_a < 4 amp;amp; size_b < 4)
    return multiplication(one, two);
  

может стать чем-то вроде этого:

 if(size_a == 1 amp;amp; size_b == 1)
    return box(int64_t(one[0]) * two[0]);
  

возможно one[0] int32_t , это тип. Это то, что GMP делает со своими mp_limb_t массивами.

Я бы предположил, что замедление может быть связано с распределением. Замените их локальными буферами фиксированного размера, и я бы предположил, что вы увидите приличное увеличение скорости. Или с помощью пользовательского распределителя пула. Но я думаю, что если вы хитры, многое из этого можно сделать на месте.

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

(также пишется «правильно»).

Что вы имеете в виду, написав «функция в 5 раз медленнее»? Карацуба асимптотически быстрее, а не просто быстрее. Это означает, что даже игрушечная реализация Карацубы в конечном итоге будет быстрее, чем наивное умножение. Вы тестировали скорость с 10000-значными числами?

Я знаю, что код GMP нелегко читать … но посмотрите на эту таблицу, извлеченную из кода. Он дает (для разных процессоров) пороговое значение для Toom-2,2 (Карацуба). Вкратце, реализация Karatsuba в GMP НЕ быстрее, чем наивная реализация для операндов размером менее 320 бит (10 x 32-разрядных регистров).

Некоторые вопросы о вашем коде:

• вам действительно нужны символы * a, * b ? Вы удаляете их перед началом вычисления! 😉
• вы уверены, что вам нужно скопировать знак в {a,b}_{left,rite} ? Вы проверили, верен ли результат с отрицательными операндами?
• рассмотрим очень несбалансированные операнды… что вам делать, если size_a * 2 < size_b (или наоборот)?

Следующим шагом будет Toom, верно?