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

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

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

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

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

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

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

Подробности

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

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

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

м	=	12	3456	7890	1234	5678	9012
н	=	9	8765	4321	9876	5432	1098.

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

Разделение

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

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

$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 :

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

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

$p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,$

$q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,$

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

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

$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 ^{в ты} когда x стремится к бесконечности. Следовательно, p (∞) всегда является значением своего коэффициента старшей степени (в приведенном выше примере коэффициента m ₂ ).

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

${\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 . В нашем примере мы получаем следующие значения:

р (0)	=	м 0	=	56789012	=	56789012
р (1)	=	м 0 + м 1 + м 2	=	56789012 + 78901234 + 123456	=	135813702
п (−1)	=	м 0 − м 1 + м 2	=	56789012 − 78901234 + 123456	=	−21988766
п (−2)	=	м 0 − 2 м 1 + 4 м 2	=	56789012 − 2 × 78901234 + 4 × 123456	=	−100519632
п (∞)	=	mм2	=	123456	=	123456
д (0)	=	п 0	=	54321098	=	54321098
д (1)	=	п 0 + п 1 + п 2	=	54321098 + 43219876 + 98765	=	97639739
q (−1)	=	п 0 - п 1 + п 2	=	54321098 − 43219876 + 98765	=	11199987
q (−2)	=	п 0 - 2 п 1 + 4 п 2	=	54321098 − 2 × 43219876 + 4 × 98765	=	−31723594
q (∞)	=	№ 2	=	98765	=	98765.

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

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

$\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 в последнем столбце.

Ускоренная оценка

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

п 0	←	м 0 + м 2	=	56789012 + 123456	=	56912468
р (0)	=	м 0	=	56789012	=	56789012
р (1)	=	р 0 + м 1	=	56912468 + 78901234	=	135813702
п (−1)	=	п 0 - м 1	=	56912468 − 78901234	=	−21988766
п (−2)	=	( п (−1) + м 2 ) × 2 - м 0	=	(− 21988766 + 123456 ) × 2 − 56789012	=	− 100519632
п (∞)	=	mм2	=	123456	=	123456.

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

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

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

р (0)	=	п (0) д (0)	=	56789012 × 54321098	=	3084841486175176
р (1)	=	п (1) д (1)	=	135813702 × 97639739	=	13260814415903778
р (−1)	=	п (−1) q (−1)	=	−21988766 × 11199987	=	−246273893346042
р (−2)	=	п (−2) q (−2)	=	−100519632 × −31723594	=	3188843994597408
р (∞)	=	п (∞) q (∞)	=	123456 × 98765	=	12193131840.

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

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

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

${\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 . Мы могли бы решить это уравнение с помощью метода исключения Гаусса , но это слишком дорого. Вместо этого мы используем тот факт, что при правильном выборе точек оценки эта матрица обратима (см. также матрицу Вандермонда ), и поэтому:

${\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}}$

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

р 0	←	р (0)	=	3084841486175176
р 4	←	р (∞)	=	12193131840
р 3	←	( р (−2) − р (1))/3	=	(3188843994597408 − 13260814415903778)/3
			=	−3357323473768790
р 1	←	( р (1) - р (-1))/2	=	(13260814415903778 − (−246273893346042))/2
			=	6753544154624910
год 2	←	р (−1) − р (0)	=	−246273893346042 − 3084841486175176
			=	−3331115379521218
р 3	←	( р 2 - р 3 )/2 + 2 р (∞)	=	(−3331115379521218 − (−3357323473768790))/2 + 2 × 12193131840
			=	13128433387466
год 2	←	р 2 + р 1 - р 4	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
р 1	←	р 1 - р 3	=	6753544154624910 − 13128433387466
			=	6740415721237444.

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

${\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 ⁴ и В = б ² = 10 ⁸ .

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840
	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

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

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

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

Тоом-1

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

$\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 и ∞. Его интерполяционная матрица тогда является единичной матрицей:

$\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 и ∞. Это то же самое, что и умножение Карацубы , с матрицей интерполяции:

$\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 и ∞. Затем он имеет матрицу интерполяции:

$\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).$

Ссылки

• Д. Кнут. Искусство компьютерного программирования , Том 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].