Jump to content

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

(Перенаправлено из алгоритма Тума-Кука )

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] Алгоритм состоит из пяти основных шагов:

  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 определяется следующим образом:

В нашем примере мы будем использовать 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 и ∞. Затем он имеет матрицу интерполяции:

Примечания [ править ]

  1. ^ Jump up to: Перейти обратно: а б Кнут, с. 296
  2. ^ Крэндалл и Померанс, с. 474
  3. ^ Крэндалл и Померанс, с. 536
  4. ^ Кнут, с. 302
  5. ^ Положительные результаты , глава III Стивена А. Кука: О минимальном времени вычисления функций .
  6. ^ 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].
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ae3bbfe67b75f2ee6bd0c78a83e19799__1718342700
URL1:https://arc.ask3.ru/arc/aa/ae/99/ae3bbfe67b75f2ee6bd0c78a83e19799.html
Заголовок, (Title) документа по адресу, URL1:
Toom–Cook multiplication - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)