Есть ли хороший способ оптимизировать умножение двух BigNums?

Question

У меня есть класс BigNum:

struct BigNum{
    vector <int> digits;
    
    BigNum(vector <int> data){
        for(int item : data){d.push_back(item);}
    }
    
    int get_digit(size_t index){
        return (index >= d.size() ? 0 : d[index]);
    }
};

, и я пытаюсь написать код для умножения двух BigNum s. В настоящее время я использую традиционный метод умножения, при котором первое число умножается на каждое di git другого и прибавляется к промежуточной сумме. Вот мой код:

BigNum add(BigNum a, BigNum b){ // traditional adding: goes digit by digit and keeps a "carry" variable
    vector <int> ret;

    int carry = 0;
    for(size_t i = 0; i < max(a.digits.size(), b.digits.size()); ++i){
        int curr = a.get_digit(i) + b.get_digit(i) + carry;

        ret.push_back(curr%10);
        carry = curr/10;
    }

    // leftover from carrying values
    while(carry != 0){
        ret.push_back(carry%10);
        carry /= 10;
    }

    return BigNum(ret);
}

BigNum mult(BigNum a, BigNum b){
    BigNum ret({0});

    for(size_t i = 0; i < a.d.size(); ++i){
        vector <int> row(i, 0); // account for the zeroes at the end of each row

        int carry = 0;
        for(size_t j = 0; j < b.d.size(); ++j){
            int curr = a.d[i] * b.d[j] + carry;

            row.push_back(curr%10);
            carry = curr/10;
        }

        while(carry != 0){ // leftover from carrying
            row.push_back(carry%10);
            carry /= 10;
        }

        ret = add(ret, BigNum(row)); // add the current row to our running sum
    }

    return ret;
}

Этот код все еще работает довольно медленно; вычисление факториала 1000 занимает около минуты. Есть ли лучший способ умножить два BigNum? Если нет, есть ли лучший способ представления больших чисел, который ускорит этот код?

Answer 1

Если вы используете другое основание, скажем 2 ^ 16 вместо 10, умножение будет намного быстрее.

Но добираться до печати в десятичном формате будет дольше.

Answer 2

Получите готовую библиотеку bignum. Они, как правило, оптимизированы до смерти, вплоть до конкретных моделей c ЦП, со сборкой, где это необходимо.

GMP и MPIR - два популярных. . Последний более Windows дружелюбен.

Answer 3

Один из способов - использовать основание больше десяти. Это огромная трата времени и пространства - взять int, способный хранить значения до четырех миллиардов (беззнаковый вариант), и использовать его для хранения одиночных цифр.

Что вы можете сделать, так это используйте unsigned int/long значений для начала, затем выберите основание так, чтобы его квадрат соответствовал значению. Так, например, квадрат root самого большого 32-битного unsigned int - это всего лишь 65 000, поэтому вы выбираете 10 000 в качестве основы.

Итак, «bigdi git» (я используйте этот термин для di git в схеме base-10,000, он фактически равен четырем десятичным цифрам (отсюда только цифры), и это имеет несколько эффектов:

• гораздо меньше места вверх (примерно 1/1000 пространства);
• по-прежнему нет шансов на переполнение при умножении групп на четыре ди git.
• более быстрое умножение, выполняя четыре цифры за раз, а чем один; и
• по-прежнему легко печатать, так как он в формате «основание десять в степени чего-то».

Эти последние два пункта требуют некоторых пояснений.

На втором последнем, это должно быть примерно в шестнадцать раз быстрее, так как для умножения 1234 и 5678 каждое di git в первом должно быть умножено на каждый di git в секунду. Для обычного di git это шестнадцать умножений, а это o только один для bigdi git.

Поскольку большие цифры - это ровно четыре цифры, вывод все еще относительно прост, примерно так:

printf("%d", node[0]);
for (int i = 1; i < node_count; ++i) {
    printf("%04d", node[0]);
}

---

Кроме того, и обычные оптимизации C ++, такие как передача const ссылок вместо копирования всех объектов, вы можете изучить те же приемы, которые используются в MPIR и GMP. Я сам стараюсь избегать их, поскольку у них была (или была в какой-то момент) довольно неприятная привычка просто насильственно закрывать программы, когда им не хватало памяти, что я считаю непростительным в библиотеке общего назначения. В любом случае, у меня есть процедуры, созданные с течением времени, которые работают, хотя и далеко не намного как GMP, определенно больше, чем мне нужно (и которые во многих случаях используют те же алгоритмы).

---

Одним из приемов умножения является алгоритм Карацубы (честно говоря, я не уверен , если GMP / MPIR использует его, но, если у них нет чего-то намного лучшего, я подозреваю, что они будет).

Это в основном включает в себя разделение чисел на части, так что a = a<sub>1</sub>a<sub>0</sub> является первым, а b = b<sub>1</sub>b<sub>0</sub>. Другими словами:

• a = a<sub>1</sub> x B<sup>p</sup> + a<sub>0</sub>
• b = b<sub>1</sub> x B<sup>p</sup> + b<sub>0</sub>

B<sup>p</sup> - это просто некоторая интегральная мощность фактического основания, которое вы используя, и обычно может быть ближайшим значением к квадрату root большего числа (примерно вдвое меньше цифр).

Затем вы вычислите:

• c<sub>2</sub> = a<sub>1</sub> x b<sub>1</sub>
• c<sub>0</sub> = a<sub>0</sub> x b<sub>0</sub>
• c<sub>1</sub> = (a<sub>1</sub> + a<sub>0</sub>) x (b<sub>1</sub> + b<sub>0</sub>) - c<sub>2</sub> - c<sub>0</sub>

Последний пункт сложен, но он имеет математическое доказательство. Я предлагаю, если вы хотите достичь такого уровня глубины go, я не лучший человек для этой работы. В какой-то момент, даже я, законченный тип «не верю ничему, что не можешь доказать», принимаю мнения экспертов как факт: -)

Затем вы работаете с магами добавления / сдвига * (умножение выглядит как , но, поскольку это умножение на степень основания, на самом деле это просто вопрос сдвига значений влево).

• c = c<sub>2</sub> x B<sup>2p</sup> + c<sub>1</sub> x B<sup>p</sup> + c<sub>0</sub>

Теперь вы можете задаться вопросом, почему три умножения лучше, чем одно, но вы должны принять во внимание, что в этих умножениях используется гораздо меньше цифр, чем в исходном. Если вы вспомните комментарий, который я сделал выше о выполнении одного умножения вместо шестнадцати при переключении с base-10 на base-10000, вы поймете, что количество умножений di git пропорционально квадрату чисел цифр.

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

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

И, как мои более продвинутые математики скажут мне (довольно часто), что если вы не хотите, чтобы ваша голова взорвалась, вам, вероятно, не стоит заниматься математикой: -)