Тоом-Кук , иногда известный как Тоом-3 , названный в честь Андрея Тоома , который представил новый алгоритм с его низкой сложностью, и Стивена Кука , который очистил его описание, представляет собой алгоритм умножения для больших целых чисел.
Имея два больших целых числа, a и b , Тоом-Кук разбивает a и b на k меньших частей длиной l каждая и выполняет над ними операции. По мере роста k можно комбинировать множество подопераций умножения, тем самым уменьшая общую сложность алгоритма. Затем подоперации умножения могут быть вычислены рекурсивно, снова используя умножение Тоома – Кука, и так далее. Хотя термины «Тоом-3» и «Тоом-Кук» иногда неправильно используются как взаимозаменяемые, «Тоом-3» - это всего лишь единичный пример алгоритма Тоома-Кука, где k = 3.
Toom-3 уменьшает 9 умножений до 5 и выполняется в Θ ( 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] Карацуб алгоритм является частным случаем Toom-Кук, где число делится на две меньшие. Он уменьшает 4 умножения до 3 и, таким образом, работает при Θ ( n log (3) / log (2) ) ≈ 1.5 ( n 1,58 ). Обычное длинное умножение эквивалентно Toom-1 со сложностью Θ ( n 2 ).
Хотя показатель e можно установить произвольно близким к 1, увеличивая k , функция c, к сожалению, растет очень быстро. [1] [2] Скорость роста для смешанных схем Тоома – Кука все еще оставалась открытой проблемой исследования в 2005 году. [3] Реализация, описанная Дональдом Кнутом, достигает временной сложности Θ ( n 2 √ 2 log n log n ) . [4]
Из-за накладных расходов Toom – Cook работает медленнее, чем длинное умножение с маленькими числами, и поэтому обычно используется для умножений промежуточного размера перед асимптотически более быстрым алгоритмом Шёнхаге – Штрассена (со сложностью Θ ( n log n log log n ) ) становится практичным.
Тоом впервые описал этот алгоритм в 1963 году, а Кук опубликовал улучшенный (асимптотически эквивалентный) алгоритм в своей докторской диссертации в 1966 году [5].
Подробности
В этом разделе обсуждается, как именно выполнить Toom- k для любого заданного значения k , и это упрощение описания умножения полиномов Тоома – Кука, описанного Марко Бодрато. [6] Алгоритм состоит из пяти основных шагов:
В типичной реализации большого целого числа каждое целое число представлено как последовательность цифр в позиционной системе счисления , с основанием или основанием системы счисления, установленным на некоторое (обычно большое) значение b ; в этом примере мы используем b = 10000, так что каждая цифра соответствует группе из четырех десятичных цифр (в компьютерной реализации вместо b обычно будет степень 2). Скажем, умножаются два целых числа:
м знак равно 12 3456 7890 1234 5678 9012 п знак равно 9 8765 4321 9876 5432 1098.
Они намного меньше, чем обычно обрабатываются с помощью Тоома – Кука (умножение в начальной школе будет быстрее), но они служат для иллюстрации алгоритма.
Расщепление
Первый шаг - выбрать основание B = b i , такое, чтобы количество цифр как m, так и n в базе B не превышало k (например, 3 в Toom-3). Типичный выбор для i дается:
В нашем примере мы будем делать Toom-3, поэтому мы выбираем B = b 2 = 10 8 . Затем мы разделяем m и n на их базовые B- цифры m i , n i :
Затем мы используем эти цифры в качестве коэффициентов в градусов- ( к - 1) многочленов р и д , со свойством , что р ( В ) = т и д ( В ) = п :
Цель определения этих многочленов состоит в том, что если мы можем вычислить их произведение r ( x ) = p ( x ) q ( x ) , наш ответ будет r ( B ) = m × n .
В случае, когда умножаемые числа имеют разный размер, полезно использовать разные значения k для m и n , которые мы назовем k m и k n . Например, алгоритм «Тоом-2.5» относится к Тоом-Куку с k m = 3 и k n = 2. В этом случае i в B = b i обычно выбирается следующим образом:
Оценка
Подход Тоома – Кука к вычислению полиномиального произведения 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 балл, чтобы определить окончательный результат. Назовите это d . В случае Toom-3, d = 5. Алгоритм будет работать независимо от того, какие точки выбраны (за некоторыми небольшими исключениями, см. Требование обратимости матрицы в Интерполяции ), но в интересах упрощения алгоритма лучше выбрать маленькие целочисленные значения, такие как 0, 1, -1 и -2.
Одно необычное значение точки, которое часто используется, - это бесконечность, обозначаемая как ∞ или 1/0. «Оценить» полином p на бесконечности на самом деле означает взять предел p ( x ) / x deg p, когда x стремится к бесконечности. Следовательно, p (∞) всегда является значением своего коэффициента наивысшей степени (в приведенном выше примере коэффициент m 2 ).
В нашем примере Toom-3 мы будем использовать точки 0, 1, −1, −2 и ∞. Эти варианты упрощают оценку, создавая формулы:
и аналогично для 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 p (∞) знак равно м 2 знак равно 123456 знак равно 123456 д (0) знак равно п 0 знак равно 54321098 знак равно 54321098 д (1) знак равно п 0 + п 1 + п 2 знак равно 54321098 + 43219876 + 98765 знак равно 97639739 д (-1) знак равно п 0 - п 1 + п 2 знак равно 54321098 - 43219876 + 98765 знак равно 11199987 д (-2) знак равно п 0 - 2 л 1 + 4 н 2 знак равно 54321098 - 2 × 43219876 + 4 × 98765 знак равно −31723594 q (∞) знак равно п 2 знак равно 98765 знак равно 98765.
Как показано, эти значения могут быть отрицательными.
В целях дальнейшего объяснения будет полезно рассматривать этот процесс оценки как умножение матрицы на вектор, где каждая строка матрицы содержит степени одной из точек оценки, а вектор содержит коэффициенты полинома:
Размеры матрицы: d на k m для p и d на k n для q . Строка для бесконечности всегда равна нулю, за исключением 1 в последнем столбце.
Быстрая оценка
Многоточечную оценку можно получить быстрее, чем с помощью приведенных выше формул. Количество элементарных операций (сложение / вычитание) можно уменьшить. Последовательность, данная Бодрато [6] для Toom-3, выполняемая здесь над первым операндом (полиномом p ) работающего примера, следующая:
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 p (∞) знак равно м 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) д (-1) знак равно −21988766 × 11199987 знак равно −246273893346042 г (-2) знак равно p (−2) q (−2) знак равно −100519632 × −31723594 знак равно 3188843994597408 г (∞) знак равно p (∞) q (∞) знак равно 123456 × 98765 знак равно 12193131840.
Как показано, они также могут быть отрицательными. Для достаточно больших чисел это самый дорогой шаг, единственный шаг, который не является линейным по размерам m и n .
Интерполяция
Это наиболее сложный этап, обратный этапу оценки: учитывая наши d точек на полиноме произведения r (·), нам нужно определить его коэффициенты. Другими словами, мы хотим решить это матричное уравнение для вектора в правой части:
Эта матрица строится так же, как и на этапе оценки, за исключением того, что это d × d . Мы могли бы решить это уравнение с помощью метода исключения Гаусса , но это слишком дорого. Вместо этого мы используем тот факт, что при условии, что точки оценки были выбраны подходящим образом, эта матрица является обратимой (см. Также матрицу Вандермонда ), и поэтому:
Остается только вычислить это произведение матрицы на вектор. Хотя матрица содержит дроби, результирующие коэффициенты будут целыми числами, поэтому все это можно сделать с помощью целочисленной арифметики, просто сложения, вычитания и умножения / деления на небольшие константы. Сложная задача проектирования в Тоом-Куке - найти эффективную последовательность операций для вычисления этого продукта; одна последовательность, данная Бодрато [6] для Toom-3, следующая, выполняемая здесь в текущем примере:
г 0 ← г (0) знак равно 3084841486175176 r 4 ← г (∞) знак равно 12193131840 r 3 ← ( г (−2) - г (1)) / 3 знак равно (3188843994597408 - 13260814415903778) / 3 знак равно −3357323473768790 r 1 ← ( г (1) - г (−1)) / 2 знак равно (13260814415903778 - (−246273893346042)) / 2 знак равно 6753544154624910 r 2 ← г (-1) - г (0) знак равно −246273893346042 - 3084841486175176 знак равно −3331115379521218 r 3 ← ( г 2 - г 3 ) / 2 + 2 г (∞) знак равно (−3331115379521218 - (−3357323473768790)) / 2 + 2 × 12193131840 знак равно 13128433387466 r 2 ← г 2 + г 1 - г 4 знак равно −3331115379521218 + 6753544154624910 - 12193131840 знак равно 3422416581971852 r 1 ← г 1 - г 3 знак равно 6753544154624910–13128433387466 знак равно 6740415721237444.
Теперь мы знаем наш полином-произведение r :
Если бы мы использовали разные k m , k n или точки оценки, матрица и наша стратегия интерполяции изменились бы; но он не зависит от входных данных и поэтому может быть жестко запрограммирован для любого заданного набора параметров.
Перекомпоновка
Наконец, мы оцениваем r (B), чтобы получить окончательный ответ. Это просто, поскольку B является степенью b, и поэтому все умножения на степени B представляют собой сдвиги на целое число цифр в базе b . В текущем примере b = 10 4 и B = b 2 = 10 8 .
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 m и k n .
Тоом-1
Toom-1 ( k m = k n = 1) требует 1 оценочную точку, здесь выбирается равной 0. Он вырождается в длинное умножение с матрицей интерполяции единичной матрицы:
Тоом-1.5
Toom-1.5 ( k m = 2, k n = 1) требует 2 оценочных баллов, здесь выбраны 0 и ∞. Тогда его матрица интерполяции является единичной матрицей:
Это также вырождается к длинному умножению: оба коэффициента одного множителя умножаются на единственный коэффициент другого множителя.
Тоом-2
Toom-2 ( k m = 2, k n = 2) требует 3 оценочных баллов, которые здесь выбираются равными 0, 1 и ∞. Это то же самое, что и умножение Карацубы , с матрицей интерполяции:
Тум-2,5
Toom-2.5 ( k m = 3, k n = 2) требует 4 оценочных баллов, которые здесь выбраны равными 0, 1, −1 и ∞. Затем он имеет матрицу интерполяции:
Заметки
- ^ а б Кнут, стр. 296
- ^ Crandall & Pomerance, стр. 474
- ^ Crandall & Pomerance, стр. 536
- ^ Кнут, стр. 302
- ^ Положительные результаты , глава III Стивена А. Кука: О минимальном времени вычисления функций .
- ^ a b c Марко Бодрато. На пути к оптимальному умножению Тоома – Кука для одномерных и многомерных многочленов от характеристик 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.
- М. Бодрато. К Optimal Тоом-Кук Умножение ... . В WAIFI'07, Springer, 2007.