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

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

Сорт	Алгоритм умножения

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

Алгоритм Карацубы — это быстрый алгоритм умножения . Он был открыт Анатолием Карацубой в 1960 году и опубликован в 1962 году. Это алгоритм «разделяй и властвуй» , который сводит умножение двух n -значных чисел к трем умножениям n /2-значных чисел и, повторяя это сокращение, не более чем к трем умножениям n/2-значных чисел. $n^{\log _{2}3}\approx n^{1.58}$ однозначное умножение. Следовательно, он асимптотически быстрее , чем традиционный алгоритм, который выполняет $n^{2}$ однозначные продукты.

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

История

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

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

Алгоритм

Основной шаг

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

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

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

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

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

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

где

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

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

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

Эти формулы требуют четырех умножений и были известны Чарльзу Бэббиджу . Карацуба заметил, что $xy$ можно вычислить всего за три умножения ценой нескольких дополнительных сложений. С $z_{0}$ и $z_{2}$ как раньше и $z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),$ можно наблюдать, что

${\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{aligned}}$

Таким образом, для вычисления требуется всего три умножения. $z_{0},z_{1}$ и $z_{2}.$

Пример

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

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

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

z ₂ = 12 × 6 = 72

г ₀ = 345 × 789 = 272205

z ₁ знак равно ( 12 + 345 ) × ( 6 + 789 ) - z ₂ - z ₀ знак равно 357 × 795 - 72 - 272205 = 283815 - 72 - 272205 = 11538

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

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

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

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

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

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

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

временной сложности Анализ

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

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

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

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

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

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

Выполнение

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

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

function karatsuba(num1, num2)
    if (num1 < 10 or num2 < 10)
        return num1 × num2 /* fall back to traditional multiplication */
    
    /* Calculates the size of the numbers. */
    m = max(size_base10(num1), size_base10(num2))
    m2 = floor(m / 2) 
    /* m2 = ceil (m / 2) will also work */
    
    /* Split the digit sequences in the middle. */
    high1, low1 = split_at(num1, m2)
    high2, low2 = split_at(num2, m2)
    
    /* 3 recursive calls made to numbers approximately half the size. */
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(low1 + high1, low2 + high2)
    z2 = karatsuba(high1, high2)
    
    return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

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

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

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

Внешние ссылки

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