Просмотр кода страницы Алгоритм Тоома — Кука

Алгоритм '''Тоома — Кука''', иногда упоминаемый как '''Тоом-3''' — это {{нп5|алгоритм умножения|||multiplication algorithm}} больших чисел, названный именами {{iw|Тоом, Андрей Леонович|Андрея Леоновича Тоома|en|Andrei Toom}}, предложившего новый алгоритм с [[Вычислительная сложность|низкой сложностью]], и [[Кук, Стивен Артур|Стивена Кука]], более ясно его описавшего.

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

Тоом-3 сокращает сложность с 9 умножений до 5 и работает за время <math>\Theta(n^{\log(5)/\log(3)}) \approx \Theta(n^{1{,}46})</math>. В общем случае Тоом-''k'' работает за время <math>\Theta(c(k)n^e)</math>, где <math>e = \log{(2k - 1)} / \log{(k)}</math>, <math>n^e</math> является временем, затрачиваемым на умножения подчастей, а ''c'' — время, затрачиваемое на сложения и умножение на малые константы {{sfn|Knuth|1997|с=296}}. [[Алгоритм Карацубы]] является частным случаем алгоритма Тоома — Кука, где число разбивается на две части. Он сокращает сложность с 4 умножений до 3, а потому работает за время <math>\Theta(n^{\log(3)/\log(2)}) \approx \Theta(n^{1{,}58})</math>. Обычное умножение в столбик эквивалентно Тоом-1 со сложностью <math>\Theta(n^2)</math>.

Хотя степень ''e'' может быть установлена как можно близкой к 1 путём увеличения ''k'', функция ''c'' растёт очень быстро{{sfn|Knuth|1997|с=296}}{{sfn|Crandall, Pomerance|2005|с=474}}. Скорость роста для смешанных схем Тоома — Кука оставалась открытой проблемой к 2005-му году{{sfn|Crandall, Pomerance|2005|с=536}}. Реализация, описанная [[Кнут, Дональд Эрвин|Дональдом Кнутом,]] добивается сложности <math>\Theta(n2^{\sqrt{2\log n}}\log n)</math>{{sfn|Knuth|1997|с=302}}.

За счёт накладных расходов алгоритм Тоома-Кука для малых чисел медленнее умножения в столбик и потому обычно использовался для множителей среднего размера, пока не был обнаружен асимптотически более быстрый [[алгоритм Шёнхаге — Штрассена]] (со сложностью <math>\Theta(n \log n \log {\log n}))</math>.

Тоом описал свой алгоритм в [[1963 год|1963]] году, а Кук опубликовал улучшенный ([[Асимптотическое равенство|асимптотически эквивалентный]]) алгоритм в тезисах своей диссертации в [[1966 год|1966-м]] году{{r|COOK}}.

== Детали ==
<blockquote>В этой секции обсуждается работа алгоритма Тоома-''k'' для любого заданного значения ''k'' и даётся упрощённое описание умножения Тоома — Кука [[Многочлен|многочленов]], которое описал Марко Бодрато{{sfn|Bodrato|2007|с=116–133}}. Алгоритм имеет пять основных шагов:</blockquote>
# [[#Разбиение|Разбиение]]
# [[#Вычисление в точках|Вычисление в точках]]
# [[#Поточечное умножение|Поточечное умножение]]
# [[#Интерполяция|Интерполяция]]
# [[#Рекомпозиция|Рекомпозиция]]

В типичной интерпретации больших чисел каждое целое представляется как последовательность цифр в [[Позиционная система счисления|позиционной системе счисления]], где основанием счисления берётся некоторое (обычно большое) значение ''b''. В нашем примере мы используем <math>b=10000</math>, так что каждая цифра соответствует группе из четырёх десятичных цифр (в реализации в компьютере в качестве ''b'' обычно берётся степень двойки). Скажем, нужно перемножить два числа:

:{|
|''m'' || = ||12||3456||7890||1234||5678||9012
|-
|''n'' || =
|align=right|9||8765||4321||9876||5432||1098.
|}

Они много меньше, чем обычно обрабатываются алгоритмом Тоома — Кука, но они здесь иллюстрируют алгоритм.

=== Разбиение ===
Первым шагом является выбор основания счисления <math>B=b^i</math>, так что число цифр как у числа ''m'', так и у числа ''n'' по основанию ''B'' не превосходит ''k'' (например, 3 в Тоом-3). Обычно ''i'' задаётся выражением:

: <math>i = \max\left\{\left\lfloor\frac{\left\lfloor\log_b m\right\rfloor}{k}\right\rfloor, \left\lfloor\frac{\left\lfloor\log_b n\right\rfloor}{k}\right\rfloor\right\} + 1.</math>

В нашем примере мы будем использовать Тоом-3, так что мы выбираем <math>B = b^2 = 10^8</math>. Теперь мы разбиваем ''m'' и ''n'' по их основанию счисления ''B'' на цифры <math>m_i, n_i</math>:

: <math>
\begin{align}
m_2 & {} = 123456 \\
m_1 & {} = 78901234 \\
m_0 & {} = 56789012 \\
n_2 & {} = 98765 \\
n_1 & {} = 43219876 \\
n_0 & {} = 54321098
\end{align}
</math>

Мы будем использовать эти цифры как коэффициенты в многочленах ''p'' и ''q'' степени {{nowrap|(''k'' − 1)}}, со свойствами <math>p(B)=m</math> и <math>q(B)=n</math>:

: <math>p(x) = m_2x^2 + m_1x + m_0 = 123456x^2 + 78901234x + 56789012 \, </math>
: <math>q(x) = n_2x^2 + n_1x + n_0 = 98765x^2 + 43219876x + 54321098 \, </math>

После введения этих многочленов получаем, что если мы вычислим произведение <math>r(x) = p(x)q(x)</math>, то ответом задачи будет <math>r(B) = m \times n</math>.

В случае, когда перемножаемые числа имеют разные размеры, полезно использовать разные значения ''k'' для ''m'' и ''n'', которые мы будем обозначать <math>k_m</math> и <math>k_n</math>. Например, алгоритм «Тоом-2.5» относится к алгоритму Тоома-Кука с <math>k_m=3</math> и <math>k_n=2</math>. В этом случае ''i'' в <math>B=b^'i</math> обычно выбирается по выражению

: <math>i = \max\left\{\left\lfloor\frac{\left\lceil\log_b m\right\rceil}{k_m}\right\rfloor, \left\lfloor\frac{\left\lceil\log_b n\right\rceil}{k_n}\right\rfloor\right\}.</math>

=== Вычисление в точках ===
Подход Тоома — Кука вычисления произведения многочленов <math>p(x)q(x)</math> обычен. Заметим, что многочлен степени ''d'' единственным образом определяется <math>d+1</math> [[Точка (геометрия)|точками]] (например, [[прямая]] — это многочлен степени 1 и определяется двумя точками). Идеей является вычисление ''p''(•) и ''q''(•) в различных точках. Затем осуществляется произведение значений в этих точках, чтобы получить значения произведения многочленов. Наконец, [[Интерполяция|интерполируем]] полученные значения для получения коэффициентов многочлена.

Поскольку <math>\deg(pq) = \deg(p) + \deg(q)</math>, нам нужно <math>\deg(p) + \deg(q) + 1 = k_m + k_n - 1</math> точек для получения конечного результата. Назовём его ''d''. В случае Тоом-3 <math>d=5</math>. Алгоритм будет работать независимо от того, какие точки были выбраны (с несколькими небольшими исключениями — см. требование обратимости матрицы в разделе [[#Интерполяция|Интерполяция]]), но для упрощения алгоритма лучше использовать небольшие значения типа 0, 1, −1 и −2.

Одна необычная точка, которая часто используется, это [[бесконечность]], то есть <math>\infty</math>. Чтобы «вычислить» многочлен ''p'' на бесконечности, берут предел <math>p(x)/x^{\deg p}</math> при стремлении ''x'' к бесконечности. Следовательно, <math>p(\infty)</math> всегда равно значению старшего коэффициента (в примере выше — коэффициента <math>m_2</math>).

В нашем примере Тоом-3 мы используем точки 0, 1, −1, −2 и <math>\infty</math>. Этот выбор упрощает вычисление в точках и даёт формулы:

: <math>
\begin{array}{lrlrl}
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) & = & m_0 + m_1(-2) + m_2(-2)^2 & = & m_0 - 2m_1 + 4m_2 \\
p(\infty) & = & m_2 & &
\end{array}
</math>

И аналогично для ''q''. В нашем примере, значения, которые мы получаем, равны:

:{|
|-
|<math>p(0)</math> || = || <math>m_0</math> || = || 56789012 || = ||align="right"| 56789012
|-
|<math>p(1)</math> || = || <math>m_0 + m_1 + m_2</math> || = || <math>56789012 + 78901234 + 123456</math> || = ||align="right"| 135813702
|-
|<math>p(-1)</math> || = || <math>m_0 - m_1 + m_2</math> || = || <math>56789012 - 78901234 + 123456</math> || = ||align="right"| −21988766
|-
|<math>p(-2)</math> || = || <math>m_0 - 2m_1 + 4m_2</math> || = || <math>56789012 - 2 \times 78901234 + 4 \times 123456</math> || = ||align="right"| −100519632
|-
|<math>p(\infty)</math> || = || <math>m_2</math> || = || 123456 || = ||align="right"| 123456
|-
|<math>q(0)</math> || = || <math>n_0</math> || = || 54321098 || = ||align="right"| 54321098
|-
|<math>q(1)</math> || = || <math>n_0 + n_1 + n_2</math> || = || <math>54321098 + 43219876 + 98765</math> || = ||align="right"| 97639739
|-
|<math>q(-1)</math> || = || <math>n_0 - n_1 + n_2</math> || = || <math>54321098 - 43219876 + 98765</math> || = ||align="right"| 11199987
|-
|<math>q(-2)</math> || = || <math>n_0 - 2n_1 + 4n_2</math> || = || <math>54321098 - 2 \times 43219876 + 4 \times 98765</math> || = ||align="right"| −31723594
|-
|<math>q(\infty)</math> || = || <math>n_2</math> || = || 98765 || = ||align="right"| 98765.
|}

Как видно, эти значения могут быть [[Отрицательное число|отрицательными]].

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

: <math>
\left(\begin{matrix}p(0) \\ p(1) \\ p(-1) \\ p(-2) \\ p(\infty)\end{matrix}\right) =
\left(\begin{matrix}
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
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right) =
\left(\begin{matrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
1 & -1 & 1 \\
1 & -2 & 4 \\
0 & 0 & 1
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right).
</math>

Размерности матриц равны <math>d \times k_m</math> для ''p'' и <math>d \times k_n</math> для ''q''. Строка для значения бесконечность имеет нулевые значения за исключением последнего столбца, в котором стоит 1.

==== Более быстрое вычисление значений ====
Вычисление значений в точках может быть выполнено быстрее, чем указано в приведённых выше формулах. Число элементарных операций (сложение/вычитание) может быть сокращено. Последовательность операций, придуманная Бодрато{{sfn|Bodrato|2007|с=116–133}} для Тоом-3, показана здесь для первого [[Операнд|операнда]] (многочлена ''p''):

:{|
|-
|<math>p_0</math> || <math>\leftarrow</math> || <math>m_0 + m_2</math> || = || 56789012 + 123456 || = ||align="right"| 56912468
|-
|<math>p(0)</math> || = || <math>m_0</math> || = || 56789012 || = ||align="right"| 56789012
|-
|<math>p(1)</math> || = || <math>p_0 + m_1</math> || = || 56912468 + 78901234 || = ||align="right"| 135813702
|-
|<math>p(-1)</math> || = || <math>p_0 - m_1</math> || = || 56912468 − 78901234 || = ||align="right"| −21988766
|-
|<math>p(-2)</math> || = || <math> (p(-1)+m_2) \times 2 - m_0</math> || = ||align="right"|<math>(-21988766 + 123456) \times 2 - 56789012</math> || = || − 100519632
|-
|<math>p(\infty)</math> || = || <math>m_2</math> || = || 123456 || = ||align="right"| 123456.
|}

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

=== Поточечное умножение ===
В отличие от умножения многочленов ''p''(•) и ''q''(•), умножение вычисленных значений ''p''(''a'') и ''q''(''a'') просто сводится к умножению целых — более простого варианта исходной задачи. Мы рекурсивно используем нашу процедуру умножения для вычисления каждой пары значений в точках. В практических реализациях, когда операнды становятся меньше, алгоритм сводится к {{нп5|Алгоритм умножения|умножению в столбик||Multiplication algorithm}}. Если ''r'' — произведение многочленов, в нашем примере мы имеем:

:{|
|-
|<math>r(0)</math> || = || <math>p(0)q(0)</math> || = || <math>56789012 \times 54321098</math> || = ||align="right"| 3084841486175176
|-
|<math>r(1)</math> || = || <math>p(1)q(1)</math> || = || <math>135813702 \times 97639739</math> || = ||align="right"| 13260814415903778
|-
|<math>r(-1)</math> || = || <math>p(-1)q(-1)</math> || = || <math>-21988766 \times 11199987</math> || = ||align="right"| −246273893346042
|-
|<math>r(-2</math>) || = || <math>p(-2)q(-2)</math> || = || <math>-100519632 \times -31723594</math> || = ||align="right"| 3188843994597408
|-
|<math>r(\infty)</math> || = || <math>p(\infty)q(\infty)</math> || = || <math>123456 \times 98765</math> || = ||align="right"| 12193131840.
|}

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

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

: <math>
\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}
</math>

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

: <math>
\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}\right) \\
& {} =
\left(\begin{matrix}
 1 & 0 & 0 & 0 & 0 \\
 \tfrac12 & \tfrac13 & -1 & \tfrac16 & -2 \\
 -1 & \tfrac12 & \tfrac12 & 0 & -1 \\
-\tfrac12 & \tfrac16 & \tfrac12 & -\tfrac16 & 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{align}
</math>

Теперь остаётся лишь вычислить произведение матрицы на вектор. Хотя матрица содержит [[Дробь (математика)|дроби]], результирующие коэффициенты будут целыми числами, так что вычисления можно вести в целочисленной арифметике путём сложения, вычитания и умножения/деления на маленькие [[Постоянная|константы]]. Здесь основной задачей является поиск эффективной последовательности операций, позволяющей вычислить произведение матрицы на вектор. Одну такую последовательность дал Бодрато{{sfn|Bodrato|2007|с=116–133}} для Тоом-3 и она для нашего примера следующая:

:{|
|-
|<math>r_0</math> || <math>\leftarrow</math> || <math>r(0)</math> || = || 3084841486175176
|-
|<math>r_4</math> || <math>\leftarrow</math> || <math>r(\infty)</math> || = || 12193131840
|-
|<math>r_3</math> || <math>\leftarrow</math> || <math>(r(-2) - r(1))/3</math> || = || (3188843994597408 − 13260814415903778)/3
|-
| || || || = || −3357323473768790
|-
|<math>r_1</math> || <math>\leftarrow</math> || <math>(r(1) - r(-1))/2</math> || = || <math>(13260814415903778 - (-246273893346042))/2</math>
|-
| || || || = || 6753544154624910
|-
|<math>r_2</math> || <math>\leftarrow</math> || <math>r(-1) - r(0)</math> || = || <math>-246273893346042 - 3084841486175176</math>
|-
| || || || = || −3331115379521218
|-
|<math>r_3</math> || <math>\leftarrow</math> || <math>(r_2 - r_3)/2 + 2r(\infty)</math> || = || <math>(-3331115379521218 - (-3357323473768790))/2 + 2 \times 12193131840</math>
|-
| || || || = || 13128433387466
|-
|<math>r_2</math> || <math>\leftarrow</math> || <math>r_2 + r_1 - r_4</math> || = || −3331115379521218 + 6753544154624910 − 12193131840
|-
| || || || = || 3422416581971852
|-
|<math>r_1</math> || <math>\leftarrow</math> || <math>r_1 - r_3</math> || = || 6753544154624910 − 13128433387466
|-
| || || || = || 6740415721237444.
|}

Мы теперь знаем произведение ''r'' наших многочленов:

: <math>
\begin{array}{rrr}
r(x) = & {} & 3084841486175176 \\
 & + & 6740415721237444x \\
 & + & 3422416581971852x^2 \\
 & + & 13128433387466x^3 \\
 & + & 12193131840x^4
\end{array}
</math>

Если бы мы использовали другие <math>k_m, k_n</math> или выбрали другие точки для вычисления значений, матрица, а тогда и стратегия [[Интерполяция|интерполяции]], изменилась бы, но это не зависит от входных данных, а потому алгоритм может быть зашит «в железе» для любых данных параметров.

=== Рекомпозиция ===
Наконец, мы вычисляем r(B) для получения конечного результата. Это выполняется напрямую, поскольку B является степенью ''b'', а потому умножение на степени B является сдвигом всего числа на целое число знаков основания ''b''. В нашем примере <math>b = 10^4</math> и <math>B = b^2 = 10^8</math>.

:{|
|-
| || || || || || || || ||3084||8414||8617||5176
|-
| || || || || || ||6740||4157||2123||7444|| ||
|-
| || || || ||3422||4165||8197||1852|| || || ||
|-
| ||
|align=right| 13||1284||3338||7466|| || || || || ||
|-
| + ||121||9313||1840|| || || || || || || ||
|-
|colspan=100|<hr>
|-
| ||121||9326||3124||6761||1632||4937||6009||5208||5858||8617||5176
|}

Результатом является произведение 1234567890123456789012 и 987654321987654321098.

== Матрицы интерполяции для различных значений ''k'' ==
Здесь мы приведём матрицы интерполяции для нескольких различных малых значений <math>k_m</math> и <math>k_n</math>.

=== Тоом −1 ===
Тоом-1 (<math>k_m = k_n = 1</math>) требует вычисления в одной точке, здесь выбирается 0. Алгоритм вырождается в умножение в столбик с единичной матрицей интерполяции:

: <math>\left(\begin{matrix}1\end{matrix}\right)^{-1} = 
\left(\begin{matrix}1\end{matrix}\right).</math>

=== Тоом-1.5 ===
Тоом-1.5 (<math>k_m = 2, k_n = 1</math>) требует две точки, здесь выбраны 0 и <math>\infty</math>. Матрица интерполяции тогда равна единичной матрице:

: <math>\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right)^{-1} =
\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right).</math>

Алгоритм также вырождается в умножение в столбик — оба коэффициента одного множителя умножается на один коэффициент другого множителя.

=== Тоом-2 ===
Тоом-2 (<math>k_m = 2, k_n = 2</math>) требует трёх точек, здесь выбраны 0, 1 и <math>\infty</math>. Алгоритм получается тем же, что и [[алгоритм Карацубы]] с матрицей интерполяции:

: <math>\left(\begin{matrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 \\
-1 & 1 & -1 \\
0 & 0 & 1
\end{matrix}\right).</math>

=== Тоом-2.5 ===
Тоом-2.5 (<math>k_m=3, k_n=2)</math> требует 4 точки, здесь выбраны 0, 1, −1 и <math>\infty</math>. Алгоритм тогда имеет матрицу интерполяции:

: <math>\left(\begin{matrix}
1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
0 & 0 & 0 & 1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 & 0 \\
0 & \tfrac12 & -\tfrac12 & -1 \\
-1 & \tfrac12 & \tfrac12 & 0 \\
0 & 0 & 0 & 1
\end{matrix}\right).</math>

== Примечания ==
{{примечания|2|refs=
<ref name=COOK>[http://cr.yp.to/bib/1966/cook.html Positive Results] {{Wayback|url=http://cr.yp.to/bib/1966/cook.html |date=20130106174428 }}, chapter III of Stephen A. Cook: ''On the Minimum Computation Time of Functions''.</ref>
}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{книга
|автор=D. Knuth
|ref=Knuth
|заглавие=[[Искусство программирования|The Art of Computer Programming]]
|том=2
|издание=Third Edition
|издательство=Addison-Wesley
|год=1997
|часть=Section 4.3.3.A: Digital methods
|страницы=294
}}
* {{книга
|автор=Кнут Д.Э.
|заглавие=Искусство программирования. Получисленные алгоритмы
|том=2
|год=2019
|isbn=978-5-907144-15-6
}}
* {{книга
|автор=R. Crandall, C. Pomerance
|ref= Crandall, Pomerance
|заглавие=Prime Numbers – A Computational Perspective
|ссылка=https://archive.org/details/primenumberscomp00cran
|издание=Second Edition
|издательство=Springer
|год=2005
|часть=Section 9.5.1: Karatsuba and Toom–Cook methods
|страницы=[https://archive.org/details/primenumberscomp00cran/page/n481 473]
}}
** {{книга
|автор=Ричард Крэндалл, Карл Померанс
|заглавие=Простые числа. Криптографические и вычислительные аспекты
|место=Москва
|издательство=Либроком
|год=2011
|isbn=978-5-397-02060-2
}}
* {{книга
|автор=M. Bodrato
|ref=Bodrato
|ссылка=http://bodrato.it/toom-cook/ 
|часть=Toward Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0
|заглавие=Arithmetic of Finite Fields
|том=4547
|серия=LNCS
|издательство=Springer
|год=2007
}}
{{refend}}

== Ссылки ==
* [http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html Toom-Cook 3-way multiplication from GMP documentation]

{{ Теоретико-числовые алгоритмы|state=collapsed }}

[[Категория:Длинная арифметика]]
[[Категория:Умножение]]

{{rq|checktranslate|style|grammar}}