Тоом – Кука

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

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

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

Хотя показатель степени e можно установить произвольно близким к 1 путем увеличения k, функция c, к сожалению, растет очень быстро. Скорость роста для смешанных схем Тоома – Кука все еще оставалась открытой проблемой исследования в 2005 году. Реализация, описанная Дональдом Кнутом, достигает временной сложности Θ (n 2 log n).

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

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

• 1 Детали
  • 1.1 Разделение
  • 1.2 Оценка
    • 1.2.1 Более быстрая оценка
  • 1.3 Точечное умножение
  • 1.4 Интерполяция
  • 1.5 Перекомпозиция
• 2 Матрицы интерполяции для различных k
  • 2.1 Toom-1
  • 2.2 Toom-1.5
  • 2.3 Toom-2
  • 2.4 Toom-2.5
• 3 Примечания
• 4 Ссылки
• 5 Внешние ссылки

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

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

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

m	=	12	3456	7890	1234	5678	9012
n	=	9	8765	4321	9876	5432	1098.

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

Разделение

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

$i\; =\; max\; \{\lfloor \; \lfloor \; log\; b\; \; m\; \rfloor \; k\; \rfloor ,\; \lfloor \; \lfloor \; log\; b\; \; n\; \rfloor \; k\; \rfloor \}\; +\; 1.\; \{\backslash \; displaystyle\; i\; =\; \backslash \; max\; \backslash \; left\; \backslash \; \{\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{\backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{b\}\; m\; \backslash \; right\; \backslash \; rfloor\}\; \{k\}\}\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{\backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{b\; \}\; n\; \backslash \; right\; \backslash \; rfloor\}\; \{k\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right\; \backslash \}\; +\; 1.\}$

В нашем примере мы будем делать Toom-3, поэтому выбираем B = b = 10. Затем мы разделяем m и n в свои базовые цифры B m i, n i:

$m\; 2\; =\; 123456\; m\; 1\; =\; 78901234\; m\; 0\; =\; 56789012\; n\; 2\; =\; 98765\; n\; 1\; =\; 43219876\; n\; 0\; =\; 54321098\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; m\_\; \{2\}\; \{\}\; =\; 123456\; \backslash \backslash \; m\_\; \{1\}\; \{\}\; =\; 78901234\; \backslash \backslash \; m\_\; \{0\}\; \{\}\; =\; 56789012\; \backslash \backslash \; n\_\; \{2\}\; \{\}\; =\; 98765\; \backslash \backslash \; n\_\; \{\; 1\}\; \{\}\; =\; 43219876\; \backslash \backslash \; n\_\; \{0\}\; \{\}\; =\; 54321098\; \backslash \; end\; \{align\}\}\}$

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

$p\; (x)\; =\; m\; 2\; x\; 2\; +\; m\; 1\; x\; +\; m\; 0\; =\; 123456\; x\; 2\; +\; 78901234\; x\; +\; 56789012\; \{\backslash \; displaystyle\; p\; (x)\; =\; m\_\; \{2\}\; x\; ^\; \{2\}\; +\; m\_\; \{1\}\; x\; +\; m\_\; \{0\}\; =\; 123456x\; ^\; \{2\}\; +\; 78901234x\; +\; 56789012\; \backslash ,\}$

$q\; (x)\; =\; n\; 2\; x\; 2\; +\; n\; 1\; х\; +\; п\; 0\; =\; 98765\; x\; 2\; +\; 43219876\; x\; +\; 54321098\; \{\backslash \; displaystyle\; q\; (x)\; =\; n\_\; \{2\}\; x\; ^\; \{2\}\; +\; n\_\; \{1\}\; x\; +\; n\_\; \{0\}\; =\; 98765x\; ^\; \{2\}\; +\; 43219876x\; +\; 54321098\; \backslash ,\}$

Цель определения этих многочленов состоит в том, что если мы можем вычислить их произведение 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\; =\; max\; \{\lfloor \; \lceil \; log\; b\; \; m\; \rceil \; km\; \rfloor ,\; \lfloor \; \lceil \; log\; b\; \; n\; \rceil \; kn\; \rfloor \}.\; \{\backslash \; displaystyle\; i\; =\; \backslash \; max\; \backslash \; left\; \backslash \; \{\backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{\backslash \; left\; \backslash \; lceil\; \backslash \; log\; \_\; \{b\}\; m\; \backslash \; right\; \backslash \; rceil\}\; \{k\_\; \{m\}\}\}\; \backslash \; right\; \backslash \; rfloor,\; \backslash \; left\; \backslash \; lfloor\; \{\backslash \; frac\; \{\backslash \; left\; \backslash \; lceil\; \backslash \; log\; \_\; \{b\}\; n\; \backslash \; right\; \backslash \; rceil\}\; \{k\_\; \{n\}\}\}\; \backslash \; right\; \backslash \; rfloor\; \backslash \; right\; \backslash \}.\}$

Оценка

The Toom Подход «Кука» к вычислению полиномиального произведения 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, когда x стремится к бесконечности. Следовательно, p (∞) всегда является значением своего коэффициента наивысшей степени (в приведенном выше примере коэффициент m 2).

В нашем примере Toom-3 мы будем использовать точки 0, 1, −1, −2 и ∞. Эти варианты упрощают оценку, создавая формулы:

$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)\; знак\; равно\; м\; 0\; +\; м\; 1\; (-\; 2)\; +\; м\; 2\; (-\; 2)\; 2\; =\; м\; 0\; -\; 2\; м\; 1\; +\; 4\; м\; 2\; п\; (\infty )\; =\; м\; 2\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{lrlrl\}\; p\; (0)\; =\; m\_\; \{0\}\; +\; m\_\; \{1\}\; (0)\; +\; m\_\; \{2\}\; (0)\; ^\; \{2\}\; =\; m\_\; \{0\}\; \backslash \backslash \; p\; (1)\; =\; m\_\; \{0\}\; +\; m\_\; \{\; 1\}\; (1)\; +\; m\_\; \{2\}\; (1)\; ^\; \{2\}\; =\; m\_\; \{0\}\; +\; m\_\; \{1\}\; +\; m\_\; \{2\}\; \backslash \backslash \; p\; (-1)\; =\; m\_\; \{0\}\; +\; m\_\; \{1\; \}\; (-\; 1)\; +\; m\_\; \{2\}\; (-\; 1)\; ^\; \{2\}\; =\; m\_\; \{0\}\; -m\_\; \{1\}\; +\; m\_\; \{2\}\; \backslash \backslash \; p\; (-2)\; =\; m\_\; \{0\}\; +\; m\_\; \{\; 1\}\; (-\; 2)\; +\; m\_\; \{2\}\; (-\; 2)\; ^\; \{2\}\; =\; m\_\; \{0\}\; -2m\_\; \{1\}\; +\; 4m\_\; \{2\}\; \backslash \backslash \; p\; (\backslash \; infty)\; =\; m\_\; \{2\}\; \backslash \; end\; \{array\}\}\}$

и аналогично для q. В нашем примере мы получаем следующие значения:

p (0)	=	m0	=	56789012	=	56789012
p (1)	=	m0+ m 1 + m 2	=	56789012 + 78901234 + 123456	=	135813702
p (−1)	=	m0- m 1 + m 2	=	56789012 - 78901234 + 123456	=	−21988766
p (−2)	=	m0- 2m 1 + 4m 2	=	56789012 - 2 × 78901234 + 4 × 123456	=	−100519632
p (∞)	=	m2	=	123456	=	123456
q (0)	=	n0	=	54321098	=	54321098
q (1)	=	n0+ n 1 + n 2	=	54321098 + 43219876 + 98765	=	97639739
q ( −1)	=	n0- n 1 + n 2	=	54321098 - 43219876 + 98765	=	11199987
q (−2)	=	n0- 2n 1 + 4n 2	=	54321098 - 2 × 43219876 + 4 × 98765	=	−31723594
q (∞)	=	n2	=	98765	=	98765.

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

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

$(p\; (0)\; p\; (1)\; p\; (-\; 1)\; p\; (-\; 2)\; p\; (\infty ))\; =\; (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)\; (м\; 0\; м\; 1\; м\; 2)\; =\; (1\; 0\; 0\; 1\; 1\; 1\; 1\; -\; 1\; 1\; 1\; -\; 2\; 4\; 0\; 0\; 1)\; (м\; 0\; м\; 1\; м\; 2).\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; п\; (0)\; \backslash \backslash \; p\; (1)\; \backslash \backslash \; p\; (-1)\; \backslash \backslash \; p\; (-2)\; \backslash \backslash \; p\; (\backslash \; infty)\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; =\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; 0\; ^\; \{0\}\; 0\; ^\; \{1\}\; 0\; ^\; \{2\}\; \backslash \backslash \; 1\; ^\; \{0\}\; 1\; ^\; \{1\}\; 1\; ^\; \{2\}\; \backslash \backslash \; (-\; 1)\; ^\; \{0\}\; (-\; 1)\; ^\; \{1\}\; (-\; 1)\; ^\; \{2\}\; \backslash \backslash \; (-\; 2)\; ^\; \{0\}\; (-\; 2)\; ^\; \{1\}\; (-\; 2)\; ^\; \{2\}\; \backslash \backslash \; 0\; 0\; 1\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; m\_\; \{0\}\; \backslash \backslash \; m\_\; \{1\}\; \backslash \backslash \; m\_\; \{2\}\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; =\; \backslash \; left\; (\; \{\backslash \; begin\; \{matrix\}\; 1\; 0\; 0\; \backslash \backslash \; 1\; 1\; 1\; \backslash \backslash \; 1\; -1\; 1\; \backslash \backslash \; 1\; -2\; 4\; \backslash \backslash \; 0\; 0\; 1\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; m\_\; \{0\}\; \backslash \backslash \; m\_\; \{1\; \}\; \backslash \backslash \; m\_\; \{2\}\; \backslash \; end\; \{matrix\}\}\; \backslash \; right).\}$

Размеры матрицы: d на k m для p и d на k n для q. Строка для бесконечности всегда равна нулю, за исключением 1 в последнем столбце.

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

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

p0	←	m0+ m 2	=	56789012 + 123456	=	56912468
p (0)	=	m0	=	56789012	=	56789012
p (1)	=	p0+ m 1	=	56912468 + 78901234	=	135813702
p (-1)	=	p0- m 1	=	56912468 - 78901234	=	−21988766
p (−2)	=	(p (−1) + m 2) × 2 - m 0	=	(- 21988766 + 123456) × 2 - 56789012	=	- 100519632
p (∞)	=	m2	=	123456	=	123456.

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

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

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

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

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

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

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

$(r (0) r (1) r (- 1) r (- 2) r (∞)) = ( 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) (r 0 r 1 r 2 r 3 r 4) = (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) (r 0 r 1 r 2 r 3 r 4). {\ 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 {align}}}$

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

$(r 0 r 1 r 2 r 3 r 4) = (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) - 1 (r (0) r (1) r (- 1) r (- 2) r (∞)) = (1 0 0 0 0 1 2 1 3 - 1 1 6 - 2 - 1 1 2 1 2 0 - 1 - 1 2 1 6 1 2 - 1 6 2 0 0 0 0 1) (r (0) r (1) r (- 1) г (- 2) г (∞)). {\ 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-3, выглядит следующим образом:

r0	←	r (0)	=	3084841486175176
r4	←	r (∞)	=	12193131840
r3	←	(r (−2) - r (1)) / 3	=	(3188843994597408 - 13260814415903778) / 3
			=	−3357323473768790
r1	←	(r (1) - r (−1)) / 2	=	(13260814415903778 - (−246273893346042)) / 2
			=	6753544154624910
r2	←	r (-1) - r (0)	=	-246273893346042-3084841486175176
			=	-3331115379521218
r3	←	(r2- r 3) / 2 + 2r (∞)	=	(−3331115379521218 - (−3357323473768790)) / 2 + 2 × 12193131840
			=	13128433387466
r2	←	r2+ r 1 - r 4	=	−3331115379521218 + 6753544153461324910 - 675354415461324910 ->3422416581971852
r1	←	r1- r 3	=	6753544154624910 - 13128433387466
			=	6740415721237444.

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

$r\; (x)\; =\; 3084841486175176\; +\; 6740415721237444\; x\; +\; 3422416581971852\; x\; 2\; +\; 13128433387466\; x\; 3\; +\; 12193131840\; x\; 4\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{\}\}\; \{rrr\}\; r\; (x)\; =\; \{\}\; 3084841486175176\; \backslash \backslash \; +\; 6740415721237444x\; \backslash \backslash \; +\; 3422416581971852x\; ^\; \{2\}\; \backslash \backslash \; +\; 13128433387466x\; ^\; \{3\}\; \backslash \backslash \; +\; 12193131840x\; ^\; \{4\}\; \backslash \; end\; \{array\}\}\}$

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

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

Наконец, мы оцениваем r (B), чтобы получить окончательный ответ. Это просто, поскольку B является степенью 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 m и k n.

Toom-1

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

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

Toom-1.5

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

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

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

Тоом-2

Тоом-2 (k m = 2, k n = 2) требует 3 оценочных баллов, здесь выбранных 0, 1 и ∞. Это то же самое, что и умножение Карацубы, с матрицей интерполяции:

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

Toom-2.5

Toom-2.5 (k m = 3, k n = 2) требует 4 оценочных баллов, выбранных здесь равными 0, 1, −1 и ∞. Затем он имеет матрицу интерполяции:

$(1\; 0\; 0\; 0\; 1\; 1\; 1\; 1\; 1\; -\; 1\; 1\; -\; 1\; 0\; 0\; 0\; 1)\; -\; 1\; =\; (1\; 0\; 0\; 0\; 0\; 1\; 2\; -\; 1\; 2\; -\; 1\; -\; 1\; 1\; 2\; 1\; 2\; 0\; 0\; 0\; 0\; 1).\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; 1\; 0\; 0\; 0\; \backslash \backslash \; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; -1\; 1\; -1\; \backslash \backslash \; 0\; 0\; 0\; 1\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; ^\; \{-\; 1\}\; =\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; 1\; 0\; 0\; 0\; \backslash \backslash \; 0\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; -\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; -\; 1\; \backslash \backslash \; -\; 1\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\; 0\; \backslash \backslash \; 0\; 0\; 0\; 1\; \backslash \; end\; \{matrix\}\}\; \backslash \; right).\}$

1. ^ Knuth, p. 296
2. ^Crandall Pomerance, стр. 474
3. ^Crandall Pomerance, стр. 536
4. ^Кнут, стр. 302
5. ^Положительные результаты, глава III Стивена А. Кука: О минимальном времени вычисления функций.
6. ^ Марко Бодрато. На пути к оптимальному умножению Тоома – Кука для одномерных и многомерных многочленов от характеристик 2 и 0. В протоколах WAIFI'07, том 4547 LNCS, страницы 116–133. 21–22 июня 2007 г. сайт автора

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

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