Усовершенствование умножения Карацубы

Question

Я реализовал алгоритм умножения Карацубы для моих образовательных целей. Теперь я ищу дальнейшие улучшения. Я реализовал какую-то длинную арифметику и хорошо работает, не использую ли я базу целочисленного представления более . с базой и компиляции с clang++ -O3 умножения двух случайных чисел в диапазоне [10^50000, 10^50001] принимает:

Naive algorithm took me 1967 cycles (1.967 seconds) 
Karatsuba algorithm took me 400 cycles (0.4 seconds) 

И те же номера с базой :

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 типа для вектора, но он также может быть переполнен для обширных чисел длины
• реализует представление переноса в длинной арифметике

После того как я видел некоторые комменты я решил расширить проблему. Предположим, что мы хотим представить наше длинное целое число как вектор ints. Для instanse:

ULLONG_MAX = 18446744073709551615 

И для ввода мы передаем число Фибоначчи 210-34507973060837282187130139035400899082304280, который не соответствует любому типу Stadard. Если мы представим его в виде вектора междунар с базой 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

Answer 1

Base 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.