Введение
Алгоритм умножения больших чисел Toom–Cook, иногда известный как Toom 3, названный в честь Андрея Тума, который представил новый алгоритм с низкой вычислительной сложностью, и Стивена Кука, который уточнил его описание, является алгоритмом умножения для больших целых чисел. Для двух больших целых чисел, a и b, алгоритм Toom–Cook разбивает a и b на k меньших частей длиной l каждая и выполняет операции над этими частями. С ростом k можно объединять множество операций подмножения, тем самым снижая общую вычислительную сложность алгоритма. Операции подмножения затем могут быть вычислены рекурсивно, снова используя умножение Toom–Cook, и так далее. Хотя термины "Toom 3" и "Toom–Cook" иногда некорректно используются как взаимозаменяемые, Toom 3 является лишь частным случаем алгоритма Toom–Cook, при k = 3. Toom 3 сокращает девять умножений до пяти и выполняется за время Θ(n log(5) / log(3)) ≈ Θ(n1.46). В общем случае, Toom k выполняется за время Θ(c(k) n^e), где e = log(2k − 1) / log(k), n^e – время, затрачиваемое на подмножения, а c – время, затрачиваемое на сложение и умножение на небольшие константы. Алгоритм Карацубы эквивалентен Toom 2, где число разбивается на две меньшие части. Он сокращает четыре умножения до трех и работает за время Θ(n log(3) / log(2)) ≈ Θ(n1.58). Обычное умножение в столбик эквивалентно Toom 1 и имеет сложность Θ(n2). Хотя показатель e можно установить произвольно близким к 1, увеличивая k, постоянный член в функции растет очень быстро. В 2005 году скорость роста для смешанных схем Toom–Cook оставалась открытой исследовательской проблемой. Реализация, описанная Дональдом Кнутом, достигает временной сложности. Из-за накладных расходов Toom–Cook медленнее, чем умножение в столбик для небольших чисел, и поэтому обычно используется для умножения чисел среднего размера, прежде чем асимптотически более быстрый алгоритм Шёнхаге–Штрассена (со сложностью Θ(n log n log log n)) станет практичным. Тум впервые описал этот алгоритм в 1963 году, а Кук опубликовал улучшенный (асимптотически эквивалентный) алгоритм в своей докторской диссертации в 1966 году.
Toom–Cook, sometimes known as Toom 3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers. Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub operations, thus reducing the overall computational complexity of the algorithm. The multiplication sub operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom 3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom 3 is only a single instance of the Toom–Cook algorithm, where k = 3. Toom 3 reduces nine multiplications to five, and runs in Θ(nlog(5)/log(3)) ≈ Θ(n1.46). In general, Toom k runs in Θ(c(k) ne), where 1=e = log(2k − 1) / log(k), ne is the time spent on sub multiplications, and c is the time spent on additions and multiplication by small constants. The Karatsuba algorithm is equivalent to Toom 2, where the number is split into two smaller ones. It reduces four multiplications to three and so operates at Θ(nlog(3)/log(2)) ≈ Θ(n1.58). Ordinary long multiplication is equivalent to Toom 1, with complexity Θ(n2). Although the exponent e can be set arbitrarily close to 1 by increasing k, the constant term in the function grows very rapidly. The growth rate for mixed level Toom–Cook schemes was still an open research problem in 2005. An implementation described by Donald Knuth achieves the time complexity
Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical. Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.
Интерполяционные матрицы для различных k
Здесь мы приводим типичные матрицы интерполяции для нескольких часто встречающихся малых значений km и kn.
Тоом-1
Для тома 1 (км = кн = 1) требуется одна точка вычисления, выбранная здесь как 0. Он вырождается в умножение в столбик, с интерполяционной матрицей, являющейся единичной матрицей.
Тоом-1.5
Для тома 1.5 (км = 2, kn = 1) требуются 2 точки оценки, в данном случае выбранные как 0 и ∞. Его интерполяционная матрица является матрицей единиц.
Это также сводится к умножению в столбик: оба коэффициента одного множителя умножаются на единственный коэффициент другого множителя.
Тум-2
Для вычисления Toom 2 (км = 2, кн = 2) требуется 3 точки оценки, выбранные как 0, 1 и ∞. Это эквивалентно умножению Каратсубы, с интерполяционной матрицей:
Тоом-2.5
Тому 2.5 (км = 3, kn = 2) требуется 4 точки оценки, выбранные как 0, 1, −1 и ∞. Соответствующая матрица интерполяции: