Умножение Тума – Кука

Алгоритм умножения больших чисел

Toom–Cook , иногда известный как Toom-3 , названный в честь Андрея Тоома , представившего новый алгоритм с его низкой сложностью, и Стивена Кука , подчистившего его описание, представляет собой алгоритм умножения больших целых чисел.

Учитывая два больших целых числа, a и b , Тум-Кук разбивает a и b на k меньших частей, каждая длиной l , и выполняет операции над частями. По мере роста k можно объединить многие подоперации умножения, тем самым уменьшая общую вычислительную сложность алгоритма. Подоперации умножения затем можно вычислить рекурсивно, снова используя умножение Тума – Кука, и так далее. Хотя термины «Тум-3» и «Тум-Кук» иногда неправильно используются как взаимозаменяемые, Тоом-3 представляет собой лишь один экземпляр алгоритма Тум-Кука, где k = 3.

Toom-3 сокращает девять умножений до пяти и работает за Θ( n ^{log(5)/log(3)} ) ≈ Θ( n ^1,46 ). В общем, Toom- k работает в Θ( c ( k ) n ^e ) , где e = log(2 k − 1) / log( k ) , n ^e — время, затраченное на частичное умножение, а c — время тратится на сложение и умножение на небольшие константы. ^[1] Алгоритм Карацубы эквивалентен Тоом-2, где число разбивается на два меньших. Он сокращает четыре умножения до трех и поэтому работает при Θ( n ^{log(3)/log(2)} ) ≈ Θ( n ^1,58 ).

Хотя показатель степени e можно установить сколь угодно близким к 1, увеличивая k , постоянный член функции растет очень быстро. ^{[1] [2]} Скорость роста для схем Тума – Кука смешанного уровня все еще оставалась открытой исследовательской проблемой в 2005 году. ^[3] Реализация, описанная Дональдом Кнутом, достигает временной сложности Θ( n 2 ^{√ 2 log n} log n ) . ^[4]

Из-за накладных расходов алгоритм Тума-Кука медленнее, чем длинное умножение с небольшими числами, и поэтому он обычно используется для умножений промежуточного размера перед асимптотически более быстрым алгоритмом Шенхаге-Штрассена (со сложностью Θ( n log n log log n ) ). становится практичным.

Тум впервые описал этот алгоритм в 1963 году, а Кук опубликовал улучшенный (асимптотически эквивалентный) алгоритм в своей докторской диссертации в 1966 году. ^[5]

Подробности

В этом разделе обсуждается, как именно выполнить Toom- k для любого заданного значения k , и он представляет собой упрощенное описание умножения полиномов Тума – Кука, описанное Марко Бодрато. ^[6] Алгоритм состоит из пяти основных шагов:

1. Разделение
2. Оценка
3. Поточечное умножение
4. Интерполяция
5. Рекомпозиция

В типичной реализации большого целого числа каждое целое число представляется как последовательность цифр в позиционной записи с основанием или основанием системы счисления, установленным на некоторое (обычно большое) значение b ; в этом примере мы используем b  = 10000, так что каждая цифра соответствует группе из четырех десятичных цифр (в компьютерной реализации вместо этого b обычно будет степенью 2). Предположим, что умножаются два целых числа:

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

Разделение

В Toom- k мы хотим разделить факторы на k частей.

Первый шаг — выбрать базу B  =  b ⁱ так, чтобы количество цифр m и n в базе B было не более k (например, 3 в Toom-3). Типичный выбор для i определяется следующим образом:

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}$

В нашем примере мы будем использовать Toom-3, поэтому выбираем B = b ² = 10 ⁸ . Затем мы разделяем m и n на их базовые B- цифры m _i , n _i :

${\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}$

Затем мы используем эти цифры в качестве коэффициентов в полиномах p и q степени ( k − 1) со свойством, что p ( B ) =  m и q ( B ) =  n :

${\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}[phone]x+56789012\,}$

${\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}[phone]x+54321098\,}$

Целью определения этих многочленов является то, что если мы сможем вычислить их произведение r ( x ) = p ( x ) q ( x ) , наш ответ будет r ( B ) = m × n .

_{В случае ,} когда умножаемые числа имеют разные размеры, полезно использовать разные значения k для m и n , которые мы будем называть km и k _n . Например, алгоритм «Toom-2.5» относится к Туму-Куку с k _m  = 3 и k _n  = 2. В этом случае i в B  =  b ⁱ обычно выбирается по формуле:

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}$

Оценка

Подход Тума – Кука для вычисления полиномиального произведения p ( x ) q ( x ) является широко используемым. Заметим, что многочлен степени d однозначно определяется d  + 1 точкой (например, линия-полином первой степени задается двумя точками). Идея состоит в том, чтобы оценить p (·) и q (·) в различных точках. Затем умножьте их значения в этих точках, чтобы получить баллы на полиноме произведения. Наконец, интерполируйте, чтобы найти его коэффициенты.

Поскольку deg( pq ) = deg( p ) + deg( q ) , нам понадобится deg( p ) + deg( q ) + 1 = k _m + k _n − 1 очков для определения окончательного результата. Назовите это д . В случае Тоом-3 d  = 5. Алгоритм будет работать независимо от того, какие точки выбраны (за некоторыми небольшими исключениями, см. требование обратимости матрицы в разделе «Интерполяция»), но в интересах упрощения алгоритма лучше выбирать небольшие целочисленные значения, такие как 0, 1, -1 и -2.

Одно необычное значение точки, которое часто используется, — это бесконечность, обозначаемая ∞ или 1/0. «Оценить» полином p на бесконечности на самом деле означает взять предел p ( x )/ x ^{deg p} , когда x стремится к бесконечности. Следовательно, p (∞) всегда является значением своего коэффициента старшей степени (в приведенном выше примере коэффициента m ₂ ).

В нашем примере Toom-3 мы будем использовать точки 0, 1, −1, −2 и ∞. Этот выбор упрощает оценку, создавая формулы:

${\displaystyle {\begin{array}{lrlrl}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}$

и аналогично для q . В нашем примере мы получаем следующие значения:

Как показано, эти значения могут быть отрицательными.

В целях дальнейшего объяснения будет полезно рассматривать этот процесс оценки как умножение матрицы на вектор, где каждая строка матрицы содержит степени одной из точек оценки, а вектор содержит коэффициенты полинома:

${\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}$

Размеры матрицы _равны d на km для p и d на k _n для q . Строка для бесконечности всегда равна нулю, за исключением 1 в последнем столбце.

Более быстрая оценка

Многоточечную оценку можно получить быстрее, чем с помощью приведенных выше формул. Количество элементарных операций (сложение/вычитание) можно сократить. Последовательность, заданная Бодрато ^[6] для Toom-3, выполняемая здесь над первым операндом (многочленом p ) текущего примера, следующая:

Эта последовательность требует пяти операций сложения/вычитания, что на одну меньше, чем при прямом вычислении. При этом умножение на 4 при вычислении p (−2) было сохранено.

Поточечное умножение

В отличие от умножения полиномов p (·) и q (·), умножение вычисленных значений p ( a ) и q ( a ) включает в себя просто умножение целых чисел — меньший экземпляр исходной проблемы. Мы рекурсивно вызываем нашу процедуру умножения для умножения каждой пары оцененных точек. В практических реализациях, когда операнды становятся меньше, алгоритм переключается на умножение в длину, как в школьном учебнике . Полагая r полиномом произведения, в нашем примере мы имеем:

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

Интерполяция

Это самый сложный шаг, обратный шагу оценки: учитывая наши d точек на полиноме произведения r (·), нам нужно определить его коэффициенты. Другими словами, мы хотим решить это матричное уравнение для вектора в правой части:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}$

Эта матрица строится так же, как и на этапе оценки, за исключением того, что она имеет размер d × d . Мы могли бы решить это уравнение с помощью метода исключения Гаусса , но это слишком дорого. Вместо этого мы используем тот факт, что при правильном выборе точек оценки эта матрица обратима (см. также матрицу Вандермонда ), и поэтому:

${\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}$

Остается только вычислить это произведение матрицы на вектор. Хотя матрица содержит дроби, результирующие коэффициенты будут целыми числами — так что все это можно сделать с помощью целочисленной арифметики, просто сложения, вычитания и умножения / деления на небольшие константы. Сложная задача проектирования в Туме – Куке состоит в том, чтобы найти эффективную последовательность операций для вычисления этого продукта; одна последовательность, данная Бодрато ^[6] для Тоом-3, следующая: она выполняется здесь на примере текущего примера:

Теперь мы знаем наш полином произведения r :

${\displaystyle {\begin{array}{rrr}r(x)=&{}&3084841486175176\\&+&6740415721237444x\\&+&3422416581971852x^{2}\\&+&13128433387466x^{3}\\&+&12193131840x^{4}\end{array}}}$

Если бы мы использовали разные km , k _n или точки оценки, матрица и, следовательно, наша стратегия интерполяции изменились бы _; но это не зависит от входных данных и поэтому может быть жестко запрограммировано для любого заданного набора параметров.

Рекомпозиция

Наконец, мы оцениваем r(B), чтобы получить окончательный ответ. Это просто, поскольку B является степенью b , и поэтому все умножения на степени B представляют собой сдвиги на целое число цифр по базе b . В текущем примере b = 10 ⁴ и B = b ² = 10 ⁸ .

А это на самом деле произведение 1234567890123456789012 и 987654321987654321098.

Интерполяционные матрицы для различных k

Здесь мы приводим общие матрицы интерполяции для нескольких различных общих малых _{значений} km и k _n .

Тоом-1

Применяя формально определение, мы можем рассмотреть Toom-1 ( k _m = k _n = 1). Это дает не алгоритм умножения, а рекурсивный алгоритм, который никогда не останавливается, поскольку он тривиально сводит каждый входной экземпляр к рекурсивному вызову одного и того же экземпляра. Алгоритму требуется 1 точка оценки, значение которой не имеет значения, поскольку оно используется только для «оценки» постоянных полиномов. Таким образом, матрица интерполяции является единичной матрицей:

${\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}$

Тоом-1,5

Toom-1.5 ( k _m = 2, k _n = 1) все еще является вырожденным: он рекурсивно уменьшает один вход, уменьшая его размер вдвое, но оставляет другой вход неизменным, следовательно, мы можем превратить его в алгоритм умножения, только если мы предоставим 1 Алгоритм умножения × n как базовый вариант (тогда как истинный алгоритм Тума – Кука сводится к базовым случаям постоянного размера). Для этого требуется 2 оценочных балла, здесь выбраны значения 0 и ∞. Его интерполяционная матрица тогда является единичной матрицей:

${\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}$

Алгоритм по существу эквивалентен форме длинного умножения: оба коэффициента одного фактора умножаются на единственный коэффициент другого фактора.

Тоом-2

Toom-2 ( k _m = 2, k _n = 2) требует 3 оценочных балла, здесь выбраны значения 0, 1 и ∞. Это то же самое, что и умножение Карацубы , с матрицей интерполяции:

${\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}$

Тоом-2,5

Toom-2.5 ( k _m = 3, k _n = 2) требует 4 оценочных балла, здесь выбраны значения 0, 1, −1 и ∞. Затем он имеет матрицу интерполяции:

${\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}$

Примечания

1. Кнут, с. 296
2. Крэндалл и Померанс, с. 474
3. Крэндалл и Померанс, с. 536
4. Кнут, с. 302
5. Положительные результаты, глава III книги Стивена А. Кука: О минимальном времени вычисления функций .
6. Марко Бодрато. К оптимальному умножению Тума – Кука для одномерных и многомерных полиномов с характеристикой 2 и 0. В материалах WAIFI'07 , том 4547 LNCS, страницы 116–133. 21–22 июня 2007 г. сайт автора

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

• Д. Кнут. Искусство компьютерного программирования , Том 2. Третье издание, Addison-Wesley, 1997. Раздел 4.3.3.A: Цифровые методы, стр. 294.
• Р. Крэндалл и К. Померанс. Простые числа – вычислительная перспектива . Второе издание, Springer, 2005. Раздел 9.5.1: Методы Карацубы и Тума – Кука, стр. 473.
• Бодрато, Марко (2007). «К оптимальному умножению Тума – Кука для одномерных и многомерных полиномов в характеристике 2 и 0». В Карле, Клод; Сунар, Берк (ред.). Арифметика конечных полей, Первый международный семинар, WAIFI 2007, Мадрид, Испания, 21–22 июня 2007 г., Труды . Конспекты лекций по информатике. Том. 4547. Спрингер. стр. 116–133. дои : 10.1007/978-3-540-73074-3_10.
• Бодрато, Марко (8 августа 2011 г.). «Оптимальное умножение полиномов Тума-Кука / свертка Тума Кука, реализация для полиномов» . Проверено 22 сентября 2023 г.

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

• Трехстороннее умножение Тума – Кука из документации GMP: «Трёхстороннее умножение Тума». Руководство по библиотеке арифметики множественной точности GNU MP (версия 6.3.0) . Free Software Foundation, Inc., 30 июля 2023 г. [Авторские права 1991, 1993–2016, 2018–2020].