Умножение Тума – Кука
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 — время, затрачиваемое на сложение и умножение на малые константы. [1] Алгоритм Карацубы эквивалентен Тоом-2, где число разбивается на два меньших. Он уменьшает четыре умножения до трех и, таким образом, работает при Θ( n журнал(3)/журнал(2) ) ≈ Θ( n 1.58 ).
Хотя показатель степени e можно установить сколь угодно близким к 1, увеличивая k , постоянный член функции растет очень быстро. [1] [2] В 2005 году темпы роста смешанных схем Тума – Кука все еще оставались открытой исследовательской проблемой. [3] Реализация, описанная Дональдом Кнутом, достигает временной сложности Θ( n 2 √ 2 лог н войти н ) . [4]
Из-за накладных расходов алгоритм Тума – Кука медленнее, чем длинное умножение с небольшими числами, и поэтому он обычно используется для умножений промежуточного размера перед асимптотически более быстрым алгоритмом Шёнхаге – Штрассена (со сложностью Θ( 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.
Они намного меньше, чем обычно обрабатываются с помощью Тума-Кука (умножение в начальной школе будет быстрее), но они послужат для иллюстрации алгоритма.
Разделение [ править ]
В Toom- k мы хотим разделить факторы на k частей.
Первым шагом является выбор базы B = b. я , такой, что количество цифр m и n в базе B не превышает k (например, 3 в Toom-3). Типичный выбор для i определяется следующим образом:
В нашем примере мы будем использовать Toom-3, поэтому выбираем B = b. 2 = 10 8 . Затем мы разделяем m и n на их базовые B- цифры m i , n i :
Затем мы используем эти цифры в качестве коэффициентов в степени ( k − 1 ) полиномах p и q со свойством p ( B ) = m и q ( B ) = n :
Целью определения этих многочленов является то, что если мы сможем вычислить их произведение 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 я обычно выбирают:
Оценка [ править ]
Подход Тума – Кука к вычислению полиномиального произведения 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 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 п (∞) = 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.
Как показано, эти значения могут быть отрицательными.
В целях дальнейшего объяснения будет полезно рассматривать этот процесс оценки как умножение матрицы на вектор, где каждая строка матрицы содержит степени одной из точек оценки, а вектор содержит коэффициенты полинома:
матрицы равны d на km Размеры для p и d на k n для q . Строка для бесконечности всегда равна нулю, за исключением 1 в последнем столбце.
Ускоренная оценка [ править ]
Многоточечную оценку можно получить быстрее, чем с помощью приведенных выше формул. Количество элементарных операций (сложение/вычитание) можно сократить. Последовательность, данная Бодрато [6] для 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 (·), нам нужно определить его коэффициенты. Другими словами, мы хотим решить это матричное уравнение для вектора в правой части:
Эта матрица строится так же, как и на этапе оценки, за исключением того, что она имеет размер d × d . Мы могли бы решить это уравнение с помощью метода исключения Гаусса , но это слишком дорого. Вместо этого мы используем тот факт, что при правильном выборе точек оценки эта матрица обратима (см. также матрицу Вандермонда ), и поэтому:
Остается только вычислить это произведение матрицы на вектор. Хотя матрица содержит дроби, результирующие коэффициенты будут целыми числами — так что все это можно сделать с помощью целочисленной арифметики, просто сложения, вычитания и умножения/деление на небольшие константы. Сложная задача проектирования в Туме – Куке состоит в том, чтобы найти эффективную последовательность операций для вычисления этого продукта; одна последовательность, данная Бодрато [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.
Теперь мы знаем наш полином произведения r :
Если бы мы использовали разные km ; , k n или точки оценки, матрица и, следовательно, наша стратегия интерполяции изменились бы но это не зависит от входных данных и поэтому может быть жестко запрограммировано для любого заданного набора параметров.
Рекомпозиция [ править ]
Наконец, мы оцениваем r(B), чтобы получить окончательный ответ. Это просто, поскольку B является степенью b , и поэтому все умножения на степени B представляют собой сдвиги на целое число цифр по базе b . В текущем примере b = 10 4 и В = б 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 [ править ]
для нескольких различных общих малых значений km Здесь мы приводим общие матрицы интерполяции и k n .
Тоом-1 [ править ]
Применяя формально определение, мы можем рассмотреть Toom-1 ( k m = k n = 1). Это дает не алгоритм умножения, а рекурсивный алгоритм, который никогда не останавливается, поскольку он тривиально сводит каждый входной экземпляр к рекурсивному вызову с одним и тем же экземпляром. Алгоритму требуется 1 точка оценки, значение которой не имеет значения, поскольку оно используется только для «оценки» постоянных полиномов. Таким образом, матрица интерполяции является единичной матрицей:
Тоом-1.5 [ править ]
Toom-1.5 ( k m = 2, k n = 1) все еще является вырожденным: он рекурсивно уменьшает один вход, уменьшая его размер вдвое, но оставляет другой вход неизменным, следовательно, мы можем превратить его в алгоритм умножения, только если мы предоставим 1 Алгоритм умножения × n как базовый вариант (тогда как истинный алгоритм Тума – Кука сводится к базовым случаям постоянного размера). Для этого требуется 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 и ∞. Затем он имеет матрицу интерполяции:
Примечания [ править ]
- ^ Jump up to: Перейти обратно: а б Кнут, с. 296
- ^ Крэндалл и Померанс, с. 474
- ^ Крэндалл и Померанс, с. 536
- ^ Кнут, с. 302
- ^ Положительные результаты , глава III Стивена А. Кука: О минимальном времени вычисления функций .
- ^ Jump up to: Перейти обратно: а б с Марко Бодрато. К оптимальному умножению Тума – Кука для одномерных и многомерных полиномов с характеристикой 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].