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

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

В Алгоритм Карацубы быстро алгоритм умножения. Это было обнаружено Анатолий Карацуба в 1960 г. и опубликовано в 1962 г.^[1][2][3] Это уменьшает умножение двух п-значные числа не более ${displaystyle n ^ {log _ {2} 3} приблизительно 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 (п ^ {журнал _ {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 {align} xy & = (x_ {1} B ^ {m} + x_ {0}) (y_ {1} B ^ {m} + y_ {0}) & = z_ {2} B ^ {2m} + z_ {1} B ^ {m} + z_ {0}, end {align}}}$

куда

${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}}$. Этот метод может выдавать отрицательные числа, для которых требуется один дополнительный бит для кодирования подписи, а также один дополнительный бит для множителя. Однако один из способов избежать этого - записать знак, а затем использовать абсолютное значение ${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 {align} 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}, конец {массив}} ight.end {выровнен}}}$

куда ${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 {align} 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}, конец {массив}} ight.end {выровнено}}}$

куда ${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 {align} 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}, конец {массив}} ight.end {выровнено}}}$

куда ${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})}$.

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

процедура Карацуба(число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