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

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

Алгоритм Карацуба является быстрым алгоритмом умножения . Он был открыт Анатолием Карацубой в 1960 году и опубликован в 1962 году. ^{[1] [2] [3]} Он сводит умножение двух n -значных чисел до не более чем однозначных умножений в целом (и именно тогда , когда n является степенью числа 2). Следовательно, он асимптотически быстрее, чем традиционный алгоритм, который требует однозначных произведений. Например, алгоритм Карацубы требует 3 ¹⁰ = 59 049 однозначных умножений для умножения двух 1024-значных чисел ( n${\ Displaystyle п ^ {\ журнал _ {2} 3} \ приблизительно п ^ {1.58}}$${\ Displaystyle п ^ {\ журнал _ {2} 3}}$${\ Displaystyle п ^ {2}}$= 1024 = 2 ¹⁰ ), тогда как традиционный алгоритм требует (2 ¹⁰ ) ² = 1048 576 (ускорение в 17,75 раза).

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

История [ править ]

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

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

Алгоритм [ править ]

Основной шаг [ править ]

Основным шагом алгоритма Карацубы является формула, которая позволяет вычислить произведение двух больших чисел и использовать три умножения меньших чисел, каждое из которых содержит примерно половину цифр, чем или , плюс некоторые сложения и сдвиги цифр. Этот базовый шаг, по сути, является обобщением аналогичного алгоритма комплексного умножения , где мнимая единица i заменяется степенью основания .${\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 {\begin{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 {\text{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}<{\text{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, выберите m = 3. Мы используем m сдвигов вправо для разложения входных операндов с использованием полученной базы ( B ^m = 1000 ), как:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

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

г ₂ = 12 × 6 = 72

г ₀ = 345 × 789 = 272205

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

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

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

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

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

Рекурсивное приложение [ править ]

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

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

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

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

${\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 умножениями в , где - поле Галуа с двумя элементами 0 и 1.${\displaystyle {\text{GF}}(2)[x]}$${\displaystyle {\text{GF}}(2)}$

${\displaystyle {\begin{aligned}\left\{{\begin{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}}\right.\end{aligned}}}$

где и . Заметим, что сложение и вычитание одинаковы в полях характеристики 2.${\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})}$

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

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

${\displaystyle {\begin{aligned}\left\{{\begin{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}}\right.\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 {\begin{aligned}\left\{{\begin{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}}\right.\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 и любого m , но рекурсивный алгоритм наиболее эффективен, когда m равно n / 2 с округлением в большую сторону . В частности, если n равно 2 ^k для некоторого целого числа k , и рекурсия останавливается только тогда, когда n равно 1, то количество однозначных умножений равно 3 ^k , то есть n ^c, где c = log ₂ 3.

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

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

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

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

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

Псевдокод [ править ]

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

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

Процедура  Карацуба ( num1 ,  пит2 ) ,  если  ( num1  <  10 )  или  ( пит2  <  10 )  возврата  num1  ×  пит2  / * Вычисляет размер чисел. * /  М  =  мин ( size_base10 ( num1 ),  size_base10 ( пит2 ))  м2  =  пол ( м  /  2 )  / * м2 = CEIL (м / 2) также будет работать * /  / * Разделить последовательность цифр посередине. * /  HIGH1 ,  LOW1  =  split_at ( num1 ,  м2 )  HIGH2 ,  Low2  =  split_at ( пит2 ,  м2 )  / * 3 вызова на номера примерно в два раза меньше. * /  z0  =  карацуба ( low1 ,  low2 )  z1  =  karatsuba (( low1  +  high1 ),  ( low2  +  high2 ))  z2  =  karatsuba ( high1 ,  high2 )  return  ( z2  ×  10  ^  ( m2  ×  2 ))  +  (( z1  -  z2  -  z0 )  ×  10  ^  m2 )  +  z0

Ссылки [ править ]

Внешние ссылки [ править ]

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