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

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

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

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

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

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

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

Подробности

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

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

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

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

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

Расщепление

Первым делом нужно выбрать базу B = б^я, так что количество цифр обоих м и п в базе B самое большее k (например, 3 в Toom-3). Типичный выбор для я дан кем-то:

${ 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 = б² = 10⁸. Затем мы отделяем м и п в их базу B цифры м_я, п_я:

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

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

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

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

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

В случае, когда умножаемые числа имеют разный размер, полезно использовать разные значения k за м и п, который мы назовем k_м и k_п. Например, алгоритм «Тоом-2.5» относится к Тоом-Куку с k_м = 3 и k_п = 2. В этом случае я в 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 }.}$

Оценка

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

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

Одно необычное значение точки, которое часто используется, - это бесконечность, обозначаемая как ∞ или 1/0. Чтобы «вычислить» полином п на бесконечности на самом деле означает взять предел п(Икс)/Икс^{град п} в качестве Икс уходит в бесконечность. Как следствие, п(∞) всегда является значением его коэффициента наивысшей степени (в приведенном выше примере коэффициент 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 {массив}}}$

и аналогично для 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
п(∞)	=	м2	=	123456	=	123456
q(0)	=	п0	=	54321098	=	54321098
q(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.

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

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

${ 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 к k_м за п и d к k_п за q. Строка для бесконечности всегда равна нулю, за исключением 1 в последнем столбце.

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

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

п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
п(∞)	=	м2	=	123456	=	123456.

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

Точечное умножение

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

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

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

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

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

${ Displaystyle { begin {align} 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 {выравнивается}}}$

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

${ displaystyle { begin {align} 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}} справа) & {} = 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 {выравнивается} }}$

Осталось только вычислить это произведение матрицы на вектор. Хотя матрица содержит дроби, результирующие коэффициенты будут целыми числами - так что все это можно сделать с помощью целочисленной арифметики, просто сложения, вычитания и умножения / деления на небольшие константы. В Toom – Cook сложная задача проектирования состоит в том, чтобы найти эффективную последовательность операций для вычисления этого продукта; одна последовательность, данная Бодрато^[6] для 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.

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

${ displaystyle { begin {array} {rrr} r (x) = & {} & 3084841486175176 & + & 6740415721237444x & + & 3422416581971852x ^ {2} & + & 13128433387466x ^ {3} & + & ^ 121931318 {4} end {массив}}}$

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

Перекомпозиция

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

Здесь мы даем общие матрицы интерполяции для нескольких различных общих малых значений k_м и k_п.

Тоом-1

Тоом-1 (k_м = k_п = 1) требуется 1 оценочная точка, здесь она выбрана равной 0. Она вырождается в длинное умножение с матрицей интерполяции единичной матрицы:

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

Тоом-1.5

Тум-1.5 (k_м = 2, k_п = 1) требует 2 оценочных баллов, здесь выбираются 0 и ∞. Его матрица интерполяции тогда является единичной матрицей:

${ displaystyle left ({ begin {matrix} 1 & 0 0 & 1 end {matrix}} right) ^ {- 1} = left ({ begin {matrix} 1 & 0 0 & 1 end {matrix}} верно).}$

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

Тоом-2

Тум-2 (k_м = 2, k_п = 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

Тум-2.5 (k_м = 3, k_п = 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).}$

Примечания

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

• Д. Кнут. Искусство программирования, Том 2. Третье издание, Addison-Wesley, 1997. Раздел 4.3.3.A: Цифровые методы, стр.294.
• Р. Крэндалл и К. Померанс. Простые числа - вычислительная перспектива. Второе издание, Springer, 2005. Раздел 9.5.1: Методы Карацубы и Тоома – Кука, стр. 473.
• М. Бодрато. К оптимальному умножению Тоома – Кука .... В WAIFI'07, Springer, 2007.

внешняя ссылка

• Трехстороннее умножение Тоома – Кука из документации GMP