Улучшение умножения Карацубы
Я реализовал алгоритм умножения Карацубы для своих образовательных целей. Сейчас я ищу дальнейшие улучшения. Я реализовал некоторую длинную арифметику, и она хорошо работает, не использую ли я базу целочисленного представления больше, чем 100.
С базой 10 и составление с clang++ -O3 умножение двух случайных чисел в диапазоне [10^50000, 10^50001] принимает:
Naive algorithm took me 1967 cycles (1.967 seconds)
Karatsuba algorithm took me 400 cycles (0.4 seconds)
И те же цифры с базой 100:
Naive algorithm took me 409 cycles (0.409 seconds)
Karatsuba algorithm took me 140 cycles (0.14 seconds)
Есть ли способ улучшить этот результат?
Теперь я использую такую функцию, чтобы завершить мой результат:
void finalize(vector<int>& res) {
for (int i = 0; i < res.size(); ++i) {
res[i + 1] += res[i] / base;
res[i] %= base;
}
}
Как вы можете видеть каждый шаг, он рассчитывает перенос и нажимает на следующую цифру. И если я возьму базу >=1000 результат будет переполнен.
Если вы видите в моем коде, я использую векторы int для представления длинного целого числа. По моей базе число будет делиться на отдельные части вектора.
Теперь я вижу несколько вариантов:
- использовать
long longтип для вектора, но он также может быть переполнен для целых чисел большой длины - реализовать представление переноса в длинной арифметике
После того, как я увидел некоторые комментарии, я решил расширить этот вопрос. Предположим, что мы хотим представить наше длинное целое как вектор целых чисел. Для примера:
ULLONG_MAX = 18446744073709551615
И для ввода мы передаем 210-е число Фибоначчи 34507973060837282187130139035400899082304280 который не подходит для любого стандартного типа. Если мы представим его в векторе int с базой 10000000, это будет выглядеть так:
v[0]: 2304280
v[1]: 89908
v[2]: 1390354
v[3]: 2187130
v[4]: 6083728
v[5]: 5079730
v[6]: 34
И когда мы делаем умножение, мы можем получить (для простоты пусть это будут два одинаковых числа)
(34507973060837282187130139035400899082304280)^2:
v[0] * v[0] = 5309706318400
...
v[0] * v[4] = 14018612755840
...
Это был только первый ряд, и мы должны сделать шесть таких шагов. Конечно, какой-то шаг вызовет переполнение во время умножения или после вычисления переноса.
Если я что-то пропустил, пожалуйста, дайте мне знать, и я это поменяю.
Если вы хотите увидеть полную версию, это на моем GitHub
Решение
База 2^64 и база 2^32 являются наиболее популярными основами для арифметики высокой точности. Обычно цифры хранятся в неподписанный целочисленный тип, потому что они хорошо ведут себя семантику в отношении переполнения.
Например, можно определить перенос из дополнения следующим образом:
uint64_t x, y; // initialize somehow
uint64_t sum = x + y;
uint64_t carry = sum < x; // 1 if true, 0 if false
Кроме того, языки ассемблера обычно содержат несколько инструкций «добавить с переносом»; если вы можете написать встроенную сборку (или иметь доступ к встроенным функциям), вы можете воспользоваться этим.
Для умножения большинство компьютеров имеют машинные инструкции, которые могут вычислить одно машинное слово -> произведение двух машинных слов; иногда инструкции для получения двух половинок называются «умножить привет» и «умножить низкий». Вам нужно написать ассемблер, чтобы получить их, хотя многие компиляторы предлагают большие целочисленные типы, использование которых позволит вам получить доступ к следующим инструкциям: например, в gcc Вы можете реализовать умножение привет как
uint64_t mulhi(uint64_t x, uint64_t y)
{
return ((__uint128_t) x * y) >> 64;
}
Когда люди не могут использовать это, они делают умножение в 2^32 вместо этого, чтобы они могли использовать один и тот же подход для реализации переносимой команды Mulhi, используя uint64_t как двузначный тип.
Если вы хотите написать эффективный код, вам действительно нужно воспользоваться этими большими инструкциями умножения. Умножение цифр в базе 2^32 более чем в девяносто раз мощнее, чем умножение цифр в базе 10, Умножение цифр в базе 2^64 в четыре раза мощнее, чем это. И ваш компьютер, вероятно, может сделать это быстрее, чем вы используете для умножения на базовые 10.
Другие решения
detector