Алгоритм Карацубы - Karatsuba algorithm

Умножение по Карацубе на az + b и cz + d (в рамке), а также 1234 и 567. Пурпурные стрелки обозначают умножение, янтарный обозначает сложение, серебристый обозначает вычитание, а светло-голубой обозначает сдвиг влево. (A), (B) и (C) показывают рекурсию, используемую для получения промежуточных значений.

В Алгоритм Карацубы быстро алгоритм умножения. Это было обнаружено Анатолий Карацуба в 1960 г. и опубликовано в 1962 г.^[1][2][3] Это уменьшает умножение двух п-значные числа не более ${displaystyle n^{log _{2}3}approx n^{1.58}}$ однозначные умножения вообще (а именно ${displaystyle n^{log _{2}3}}$ когда п это степень 2). Поэтому он быстрее, чем традиционный алгоритм, который требует ${displaystyle n^{2}}$ однозначные продукты. Например, алгоритм Карацубы требует 3¹⁰ = 59 049 однозначных умножений для умножения двух 1024-значных чисел (п = 1024 = 2¹⁰), тогда как традиционный алгоритм требует (2¹⁰)² = 1 048 576 (ускорение в 17,75 раза).

Алгоритм Карацубы был первым алгоритмом умножения, асимптотически более быстрым, чем квадратичный алгоритм «начальной школы». Алгоритм Тоома – Кука (1963) является более быстрым обобщением метода Карацубы, а Алгоритм Шёнхаге – Штрассена (1971) даже быстрее при достаточно больших п.

История

Стандартная процедура умножения двух п-значные числа требуют ряда элементарных операций, пропорциональных ${displaystyle n^{2},!}$, или же ${displaystyle O(n^{2}),!}$ в нотация big-O. Андрей Колмогоров предположил, что традиционный алгоритм асимптотически оптимальный, это означает, что любой алгоритм для этой задачи потребует ${displaystyle Omega (n^{2}),!}$ элементарные операции.

В 1960 году Колмогоров организовал семинар по математическим проблемам в кибернетика на Московский Государственный Университет, где он заявил ${displaystyle Omega (n^{2}),!}$ предположение и другие проблемы в сложность вычислений. Через неделю Карацуба, тогда еще 23-летний студент, нашел алгоритм (позже он был назван «разделяй и властвуй»), который умножает два п-значные числа в ${displaystyle O(n^{log _{2}3})}$ элементарные шаги, тем самым опровергая гипотезу. Колмогоров был очень взволнован этим открытием; он сообщил об этом на следующем заседании семинара, которое затем было прекращено. Колмогоров прочитал несколько лекций по результату Карацубы на конференциях по всему миру (см., Например, «Труды Международного конгресса математиков 1962 г.», стр. 351–356, а также «6 лекций, прочитанных на Международном конгрессе математиков в г. Стокгольм, 1962 ») и опубликовал метод в 1962 г. в Известия АН СССР.. Статья была написана Колмогоровым и содержала два результата по умножению, алгоритм Карацубы и отдельный результат автора. Юрий Офман; в нем указаны «А. Карацуба и Ю. Офман». Карацуба узнал об этой газете только после того, как получил от издателя оттиски.^[2]

Алгоритм

Основной шаг

Основным шагом алгоритма Карацубы является формула, которая позволяет вычислить произведение двух больших чисел. ${displaystyle x}$ и ${displaystyle y}$ используя три умножения меньших чисел, каждое из которых примерно вдвое меньше, чем ${displaystyle x}$ или же ${displaystyle y}$, плюс некоторые дополнения и сдвиги цифр. Этот основной шаг, по сути, является обобщением аналогичный сложный алгоритм умножения, где мнимая единица я заменяется силой основание.

Позволять ${displaystyle x}$ и ${displaystyle y}$ быть представленным как ${displaystyle n}$-цифровые строки в некоторой базе ${displaystyle B}$. Для любого положительного целого числа ${displaystyle m}$ меньше, чем ${displaystyle n}$, можно записать два заданных числа как

${displaystyle x=x_{1}B^{m}+x_{0},}$

${displaystyle y=y_{1}B^{m}+y_{0},}$

куда ${displaystyle x_{0}}$ и ${displaystyle y_{0}}$ меньше чем ${displaystyle B^{m}}$. Затем продукт

${displaystyle {egin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},end{aligned}}}$

куда

${displaystyle z_{2}=x_{1}y_{1},}$

${displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${displaystyle z_{0}=x_{0}y_{0}.}$

Эти формулы требуют четырех умножений и были известны Чарльз Бэббидж.^[4] Карацуба заметил, что ${displaystyle xy}$ можно вычислить всего за три умножения за счет нескольких дополнительных сложений. С ${displaystyle z_{0}}$ и ${displaystyle z_{2}}$ как и раньше можно заметить, что

${displaystyle z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.}$

Однако проблема, возникающая при вычислении ${displaystyle z_{1}}$ заключается в том, что приведенное выше вычисление ${displaystyle (x_{1}+x_{0})}$ и ${displaystyle (y_{1}+y_{0})}$ может привести к переполнению (даст результат в диапазоне ${displaystyle B^{m}leq { ext{result}}<2B^{m}}$), для которых требуется множитель с одним дополнительным битом. Этого можно избежать, отметив, что

${displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}$

Это вычисление ${displaystyle (x_{0}-x_{1})}$ и ${displaystyle (y_{1}-y_{0})}$ даст результат в диапазоне ${displaystyle -B^{m}<{ ext{result}}<B^{m}}$. Этот метод может выдавать отрицательные числа, для которых требуется один дополнительный бит для кодирования подписи, а также один дополнительный бит для множителя. Однако один из способов избежать этого - записать знак, а затем использовать абсолютное значение ${displaystyle (x_{0}-x_{1})}$ и ${displaystyle (y_{1}-y_{0})}$ для выполнения беззнакового умножения, после которого результат может быть отменен, если оба знака изначально различались. Еще одно преимущество в том, что даже если ${displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}$ может быть отрицательным, окончательное вычисление ${displaystyle z_{1}}$ включает только дополнения.

Пример

Чтобы вычислить произведение 12345 и 6789, где B = 10, выберите м = 3. Мы используем м сдвиги вправо для разложения входных операндов с использованием полученной базы (B^м = 1000), в качестве:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Только три умножения, которые работают с меньшими целыми числами, используются для вычисления трех частичных результатов:

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

Мы получаем результат, просто добавляя эти три частичных результата, сдвинутых соответствующим образом (и затем принимая во внимание, разлагая эти три входных параметра в базовую 1000 как для входных операндов):

результат = z₂ · (B^м)² + z₁ · (B^м)¹ + z₀ · (B^м)⁰, т.е.

результат = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

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

Рекурсивное приложение

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

В компьютере с полной 32-битной на 32-битной множитель, например, можно выбрать B = 2³¹ = 2147483648и сохраните каждую цифру как отдельное 32-битное двоичное слово. Тогда суммы Икс₁ + Икс₀ и у₁ + у₀ не потребуется дополнительное двоичное слово для хранения переходящей цифры (как в переносной сумматор ), и рекурсия Карацубы может применяться до тех пор, пока числа для умножения не станут только однозначными.

Асимметричные формулы типа Карацубы

Исходная формула Карацубы и другие обобщения сами по себе симметричны. Например, следующая формула вычисляет

${displaystyle c(x)=c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}=a(x)b(x)=(a_{2}x^{2}+a_{1}x+a_{0})(b_{2}x^{2}+b_{1}x+b_{0})}$

с 6 умножениями в ${displaystyle { ext{GF}}(2)[x]}$, куда ${displaystyle { ext{GF}}(2)}$ - поле Галуа с двумя элементами 0 и 1.

${displaystyle {egin{aligned}left{{egin{array}{l}c_{0}=p_{0},c_{1}=p_{012}+p_{02}+p_{12}+p_{2},c_{2}=p_{012}+p_{01}+p_{12},c_{3}=p_{012}+p_{01}+p_{02}+p_{0},c_{4}=p_{2},end{array}}ight.end{aligned}}}$

куда ${displaystyle p_{i}=a_{i}b_{i}, p_{ij}=(a_{i}+a_{j})(b_{i}+b_{j})}$ и ${displaystyle p_{ijk}=(a_{i}+a_{j}+a_{k})(b_{i}+b_{j}+b_{k})}$Заметим, что сложение и вычитание одинаковы в полях характеристики 2.

Эта формула симметрична, а именно, она не меняется при замене ${displaystyle a}$ и ${displaystyle b}$ в ${displaystyle p_{i}, p_{ij}}$ и ${displaystyle p_{ijk}}$.

На основании второго Обобщенные алгоритмы деления,^[5] Fan et al. нашел следующую асимметричную формулу:

${displaystyle {egin{aligned}left{{egin{array}{l}c_{0}=p_{0}c_{1}=p_{012}+p_{2}+m_{4}+m_{5}c_{2}=p_{012}+m_{3}+m_{5}c_{3}=p_{012}+p_{0}+m_{3}+m_{4}c_{4}=p_{2},end{array}}ight.end{aligned}}}$

куда ${displaystyle m_{3}=(a_{1}+a_{2})(b_{0}+b_{2}), m_{4}=(a_{0}+a_{1})(b_{1}+b_{2})}$ и ${displaystyle m_{5}=(a_{0}+a_{2})(b_{0}+b_{1})}$.

Он асимметричен, потому что мы можем получить следующую новую формулу, заменив ${displaystyle a}$ и ${displaystyle b}$ в ${displaystyle m_{3}, m_{4}}$ и ${displaystyle m_{5}}$.

${displaystyle {egin{aligned}left{{egin{array}{l}c_{0}=p_{0}c_{1}=p_{012}+p_{2}+m_{4}+m_{5}c_{2}=p_{012}+m_{3}+m_{5}c_{3}=p_{012}+p_{0}+m_{3}+m_{4}c_{4}=p_{2},end{array}}ight.end{aligned}}}$

куда ${displaystyle m_{3}=(a_{0}+a_{2})(b_{1}+b_{2}), m_{4}=(a_{1}+a_{2})(b_{0}+b_{1})}$ и ${displaystyle m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})}$.

Анализ эффективности

Базовый шаг Карацубы работает для любой базы B и любой м, но рекурсивный алгоритм наиболее эффективен, когда м равно п/ 2 с округлением в большую сторону. В частности, если п 2^k, для некоторого целого числа k, и рекурсия прекращается только тогда, когда п равно 1, то количество однозначных умножений равно 3^k, который п^c куда c = журнал₂3.

Поскольку можно расширить любые входные данные нулевыми цифрами до тех пор, пока их длина не станет степенью двойки, отсюда следует, что количество элементарных умножений для любого п, не более ${displaystyle 3^{lceil log _{2}nceil }leq 3n^{log _{2}3},!}$.

Поскольку сложение, вычитание и сдвиг цифр (умножение на степени B) в основном шаге Карацубы занимайте время, пропорциональное п, их стоимость становится незначительной, поскольку п увеличивается. Точнее, если т(п) обозначает общее количество элементарных операций, которые алгоритм выполняет при умножении двух п-значные числа, затем

${displaystyle T(n)=3T(lceil n/2ceil )+cn+d}$

для некоторых констант c и d. За это отношение повторения, то основная теорема для повторений "разделяй и властвуй" дает асимптотический граница ${displaystyle T(n)=Theta (n^{log _{2}3}),!}$.

Отсюда следует, что при достаточно больших п, Алгоритм Карацубы будет выполнять меньше сдвигов и однозначных сложений, чем обычное умножение, даже несмотря на то, что его основной шаг использует больше сложений и сдвигов, чем простая формула. Для малых значений поднако дополнительные операции сдвига и добавления могут сделать его медленнее, чем стандартный метод. Точка положительного возврата зависит от компьютерная платформа и контекст. Как показывает опыт, метод Карацубы обычно быстрее, когда множимые длиннее 320–640 бит.^[6]

Псевдокод

Вот псевдокод этого алгоритма с использованием чисел, представленных в десятичной системе координат. Для двоичного представления целых чисел достаточно заменить всюду 10 на 2.^[7]

Второй аргумент функции split_at указывает количество цифр, извлекаемых из верно: например, split_at ("12345", 3) извлечет 3 последние цифры, давая: high = "12", low = "345".

процедура Карацуба(число1, число2)    если (число1 < 10) или же (число2 < 10)        возвращаться число1 × число2        / * Вычисляет размер чисел. * /    м = мин(size_base10(число1), size_base10(число2))    m2 = этаж(м / 2)     / * m2 = ceil (m / 2) также будет работать * /        / * Разделить последовательность цифр посередине. * /    высокий1, низкий1 = split_at(число1, m2)    высокий2, низкий2 = split_at(число2, m2)        / * 3 вызова на номера примерно в два раза меньше. * /    z0 = Карацуба(низкий1, низкий2)    z1 = Карацуба((низкий1 + высокий1), (низкий2 + высокий2))    z2 = Карацуба(высокий1, высокий2)        возвращаться (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

Рекомендации

1. А. Карацуба, Ю. Офман (1962). «Умножение многоцифровых чисел автоматами». Известия АН СССР.. 145: 293–294. Перевод в академическом журнале Физика-Доклады, 7 (1963), стр. 595–596
2. Карацуба А.А. (1995). «Сложность вычислений» (PDF). Труды Математического института им. В. А. Стеклова.. 211: 169–183. Перевод из Труды Матем. Inst. МИАН, 211, 186–202 (1995)
3. Кнут Д.Э. (1969) Искусство программирования. v.2. Addison-Wesley Publ.Co., 724 стр.
4. Чарльз Бэббидж, Глава VIII - Об аналитической машине, рассматриваются большие числа, Отрывки из жизни философа, Longman Green, Лондон, 1864 г .; стр.125.
5. Хайнинг Фан, Мин Гу, Цзягуанг Сун, Квок-Ян Лам, «Получение большего количества формул типа Карацуба над двоичным полем», IET Information security Vol. 6 No 1 с. 14-19, 2012.
6. "Умножение Карацубы". www.cburch.com.
7. Вайс, Марк А. (2005). Структуры данных и анализ алгоритмов в C ++. Эддисон-Уэсли. п. 480. ISBN  0321375319.

внешняя ссылка

• Алгоритм Карацубы умножения многочленов
• Вайсштейн, Эрик В. "Умножение Карацубы". MathWorld.
• Бернштейн, Д. Дж. "Многозначное умножение для математиков ". Охватывает Карацубу и многие другие алгоритмы умножения.