톰-쿡 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''톰–쿡 알고리즘'''({{lang|en|Toom–Cook algorithm}})은 안드레이 톰과 스테픈 쿡이 제안한 곱셈 [[알고리즘]]으로 큰 두 정수를 곱할 때 사용된다.

톰-쿡 알고리즘에서는 큰 정수 ''a''와 ''b''를 곱하기 위해, 두 수를 작은 조각으로 나눈다. 조각의 수를 ''k''라고 할때, ''k''가 커질수록 곱셈의 내부 연산법은 복잡해지지만, 전체 시간 복잡도는 낮아진다. 이 곱셈 방법은 나눠진 각각의 조각에 대해서도 다시 적용할 수 있기 때문에, 조각이 작아질때까지 재귀적으로 사용할 수 있다.

톰-3 알고리즘은 ''k''가 3일 경우를 가리키며, 9번의 곱셈을 5번으로 단축시켜, Θ(''n''<sup>log(5)/log(3)</sup>), 즉 Θ(''n''<sup>1.465</sup>) 시간 안에 곱셈을 완료한다. 일반적으로 톰-''k'' 알고리즘은 Θ(''c''(''k'')&nbsp;''n<sup>e</sup>'') 시간에 수행될 수 있다. 여기서 ''e'' = log(2''k''&nbsp;−&nbsp;1) / log(''k''), ''n<sup>e</sup>''은 조각들 간의 곱셈에 걸리는 시간, ''c''는 덧셈이나 뺄셈, 혹은 작은 상수와의 곱셈에 걸리는 시간을 뜻한다.<ref name="Knuth, p. 296">커누스, p. 296</ref> [[카라슈바 알고리즘]]은 톰-쿡 알고리즘에서 ''k''가 2인 특별한 경우로, 4번의 곱셈을 3번으로 줄여 Θ(''n''<sup>log(3)/log(2)</sup>) 시간 안에 수행된다. ''k''가 1인 경우는 일반적인 곱셈 알고리즘과 동일해지며 시간 복잡도는 Θ(''n''<sup>2</sup>)가 된다.

''k''값을 증가시켜서 ''e''값을 거의 1에 가깝게 낮출수 있지만, 이 경우 ''c''의 값이 급속하게 커져 소용이 없다.<ref name="Knuth, p. 296"/><ref>Crandall & Pomerance, p. 474</ref> 이런 부가적인 연산 때문에 톰-쿡 알고리즘은 작은 정수의 곱셈에 적용하면 일반 곱셈법보다 느려지기에 이 알고리즘은 적당히 큰 정수에 사용되며, 정수 크기가 훨씬 더 커질 경우는 시간복잡도가 Θ(''n''&nbsp;log&nbsp;''n''&nbsp;log&nbsp;log&nbsp;''n'')인 [[쇤하게-슈트라센 알고리즘]]이더빠 르게 된다.

톰은 1963년에 처음 이 알고리즘을 제시하였고, 쿡은 1966년에 그의 박사 논문에서 이 알고리즘을 개량시켰다.<ref>[http://cr.yp.to/bib/1966/cook.html Positive Results], chapter III of Stephen A. Cook: ''On the Minimum Computation Time of Functions''.</ref>

== 상세 ==

이 단락은 톰-''k'' 알고리즘이 어떻게 작동하는지를 간략하게 설명한다.<ref name="Bodrato2007">Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In ''WAIFI'07 proceedings'', LNCS 4547권, 116 쪽–133. 2007년 6월 21–22일. [http://bodrato.it/papers/#WAIFI2007 저자의 웹 사이트]</ref> 알고리즘은 크게 5단계를 거쳐 완료된다.

# [[톰-쿡 알고리즘#분할|분할]]
# [[톰-쿡 알고리즘#평가|평가]]
# [[톰-쿡 알고리즘#점별 곱셈|점별 곱셈]]
# [[톰-쿡 알고리즘#보간|보간]]
# [[톰-쿡 알고리즘#합성|합성]]

큰 정수를 구현하는데 있어서, 대개 [[위치 기수법]]으로 각 자리의 정수를 표현하는 방법이 자주 사용된다. 이 때의 밑을 ''b''라고 하자. 이 예시에서는 ''b'' = 10000을 사용할 것이므로, 한 자리에는 4개의 10진 정수가 들어가게 된다. (실제 컴퓨터 구현에서는 연산의 효율성을 위해 ''b''값으로 2의 거듭제곱이 사용된다.) 두 큰 정수를 다음과 같다고 하자.

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

물론 이 정수들은 톰-쿡 알고리즘을 사용하기엔 작아서, 그냥 일반 곱셈법이 훨씬 빠르다. 하지만 설명을 위해 이 값을 사용하도록 한다.

=== 분할 ===
첫번째 단계는 정수를 ''k''개의 조각으로 자르기 위한 적절한 단위인 ''B'' = ''b''<sup>''i''</sup>를 찾는 것이다. 일반적으로 ''i''는 다음과 같이 구할 수 있다.

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

이 예제에서는 톰-3 알고리즘을 사용할 것이므로, ''B'' = ''b''<sup>2</sup> = 10<sup>8</sup>가 된다. 이 B값을 단위로 ''m''과 ''n''을 자르면 ''m''<sub>''i''</sub>, ''n''<sub>''i''</sub>는 다음과 같이 될 것이다.

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

우리는 이 수를 계수로 하는 ''k''−1차 다항식을 만들것이다.

:<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>

다항식을 이렇게 정의하면 ''p''(''B'')&nbsp;=&nbsp;''m'', ''q''(''B'')&nbsp;=&nbsp;''n''이 된다. 이렇게 정의한 목적은 두 다항식의 곱인 ''r''(''x'')&nbsp;=&nbsp;''p''(''x'')''q''(''x'')를 구하기 위해서이다. 즉 우리가 구하고자 하는 결과는 이 다항식에 ''B''를 대입함으로써 얻을 수 있다. ''r''(''B'')&nbsp;=&nbsp;''m''×''n''

''m''과 ''n''을 일반적인 곱셈법으로 곱하면 (여기서는 3 조각으로 나누었으므로), 조각 간의 곱셈이 9번 필요하다. 하지만, ''r''(''x'')는 2(''k''−1)차 다항식(''k''가 3이므로 4차 다항식)이므로, 2''k''−1개의 미지 계수를 구하기 위해서는 2''k''-1개의 방정식만 있으면 된다. 이 방정식은 선형 대수를 이용하여 간단한 방법으로 풀어낼 수 있으므로, 결과적으로 일반 곱셈법보다 적은 수의 곱셈을 사용하여 결과를 얻을 수 있게 된다.

만약 곱하는 두 수의 자리수가 다를 경우 ''k''값을 ''m''과 ''n''에 따라 다르게 주는 것이 유용하다. ''톰-2.5'' 알고리즘에서는 ''k''<sub>''m''</sub> = 3 and ''k''<sub>''n''</sub> = 2 와 같은 값을 사용한다. 이 때의 ''i''는 다음과 같이 구할 수 있다.

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

=== 평가 ===

앞서 언급했듯, 톰-쿡 알고리즘에서는 ''r''(''B'')를 구하기 위해 ''r''(''x'')의 각 계수를 구한다. 이 계수를 구하기 위해 적당한 ''x''를 선정하여 ''p''(''x'')와 ''q''(''x'')의 값을 구한다. (''k''가 3인 경우 ''r''(''x'')는 4차식이 되고, 미지계수는 5개이므로 총 5개의 지점을 구해야한다.) 간단한 계산을 위해 대개 ''x''는 0이나 1, 2, &minus1, &minus2 등의 값을 넣는다.
특별한 지점으로 흔히 무한대로 표기하는 값이 있는데, 이는 극한 표기를 간단하게 적은 것으로 최고 차항의 계수를 뜻한다.

이 예제에서는 ''x''에 0, 1, −1, −2, ∞을 넣어 계산해볼 것이다:

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

''q''에 대해서도 마찬가지. 예시의 값을 실제로 대입하면 다음과 같다:

{|
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = || 56789012
|-
|''p''(1) || = || ''m''<sub>0</sub> + ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 + 78901234 + 123456 || = || 135813702
|-
|''p''(−1) || = || ''m''<sub>0</sub> − ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 − 78901234 + 123456 || = || −21988766
|-
|''p''(−2) || = || ''m''<sub>0</sub> − 2''m''<sub>1</sub> + 4''m''<sub>2</sub> || = || 56789012 − 2×78901234 + 4×123456 || = || −100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = || 123456
|-
|''q''(0) || = || ''n''<sub>0</sub> || = || 54321098 || = || 54321098
|-
|''q''(1) || = || ''n''<sub>0</sub> + ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 + 43219876 + 98765 || = || 97639739
|-
|''q''(−1) || = || ''n''<sub>0</sub> − ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 − 43219876 + 98765 || = || 11199987
|-
|''q''(−2) || = || ''n''<sub>0</sub> − 2''n''<sub>1</sub> + 4''n''<sub>2</sub> || = || 54321098 − 2×43219876 + 4×98765 || = || −31723594
|-
|''q''(∞) || = || ''n''<sub>2</sub> || = || 98765 || = || 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>


==== 빠른 평가 ====
평가 시 각 지점에서 중복되는 연산을 줄여 더 빠르게 계산하는 방법이 있다. 이 방법을 사용할 경우 덧셈/뺄셈의 수를 줄일 수 있다. 여기에서는 톰-3의 경우만 제시한다.

{|
|''p''<sub>0</sub> || ← || ''m''<sub>0</sub> + ''m''<sub>2</sub> || = || 56789012 + 123456 || = || 56912468
|-
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = || 56789012
|-
|''p''(1) || = || ''p''<sub>0</sub> + ''m''<sub>1</sub> || = || 56912468 + 78901234 || = || 135813702
|-
|''p''(−1) || = || ''p''<sub>0</sub> − ''m''<sub>1</sub> || = || 56912468 − 78901234 || = || −21988766
|-
|''p''(−2) || = || (''p''(−1) + ''m''<sub>2</sub>)×2 − ''m''<sub>0</sub> || = || (− 21988766 + 123456 )×2 − 56789012 || = || − 100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = || 123456.
|}

이 과정은 오직 5번의 덧셈/뺄셈이 필요하다. 이는 단순 계산보다 1회 적은 것이다.

=== 점별 곱셈 ===

두 다항식 ''p''(''x'')와 ''q''(''x'')를 통째로 곱하는 대신, 앞에서 구한 여러 개의 지점에 대해서 ''p''(''a'')''q''(''a'')를 구한다. 이는 원래 목표였던 큰 정수끼리의 곱셈보다 훨씬 작은 수끼리의 연산이 된다. 게다가 점별 곱셈 과정에 톰-쿡 알고리즘을 재귀적으로 사용하여 실제로 곱하게 되는 수를 일반 곱셈법으로도 충분히 빠르게 곱할 수 있는 크기로 줄일 수 있다. 이 예시의 결과물은 다음과 같을 것이다.

{|
|''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''의 크기와 선형의 시간복잡도를 갖기만, 오직 이 과정만 그보다 큰 시간복잡도를 갖는다.

=== 보간 ===
이 과정은 전체 과정 중 가장 복잡한 과정으로, 위에서 구한 점별 곱셈 결과를 이용하여 다항식 ''r''(''x'')의 미지계수를 구하는 과정이다.

: <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>

이 행렬은 평가 과정에서 만들었던 행렬과 같은 방식으로 만들어진 것이다. [[가우스 소거법]]을 통해 이 행렬의 역행렬을 구할수도 있지만, 이는 너무 느리다. 하지만 우리가 앞서 고른 지점이 0, 1, &minus1, 2, &minus2 등으로 단순하므로 복잡한 계산과정 없이 행렬을 풀어낼 수 있다.

: <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 \\
 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
\end{matrix}\right)
\left(\begin{matrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r(\infty)\end{matrix}\right).
\end{align}
</math>

이제 남은 과정들은 모두 행렬-벡터 간의 곱셈이다. 행렬에 분수가 들어있지만, 그 결과는 정수로 나온다. 그렇기에 이 과정은 정수 간의 덧셈/뺄셈과 작은 상수를 곱하고 나누는 연산만 가지고 수행할 수 있다. 하지만 이 과정을 효율적으로 짜는 것은 쉽지 않은 일이다. 여기에서는 톰-3 알고리즘의 효율적인 방법을 소개한다.<ref name="Bodrato2007" />
{|
|''r''<sub>0</sub> || ← || ''r''(0) || = || 3084841486175176
|-
|''r''<sub>4</sub> || ← || ''r''(∞) || = || 12193131840
|-
|''r''<sub>3</sub>  || ← ||  (''r''(−2) − ''r''(1))/3 || = || (3188843994597408 − 13260814415903778)/3
|-
| || || || = || −3357323473768790
|-
|''r''<sub>1</sub>  || ← ||  (''r''(1) − ''r''(−1))/2 || = || (13260814415903778 − (−246273893346042))/2
|-
| || || || = || 6753544154624910
|-
|''r''<sub>2</sub>  || ← ||  ''r''(−1) − ''r''(0) || = || −246273893346042 − 3084841486175176
|-
| || || || = || −3331115379521218
|-
|''r''<sub>3</sub>  || ← ||  (''r''<sub>2</sub> − ''r''<sub>3</sub>)/2&nbsp;+ 2''r''(∞) || = || (−3331115379521218 − (−3357323473768790))/2&nbsp;+ 2×12193131840
|-
| || || || = || 13128433387466
|-
|''r''<sub>2</sub>  || ← ||  ''r''<sub>2</sub> + ''r''<sub>1</sub> − ''r''<sub>4</sub> || = || −3331115379521218 + 6753544154624910 − 12193131840
|-
| || || || = || 3422416581971852
|-
|''r''<sub>1</sub>  || ← ||  ''r''<sub>1</sub> − ''r''<sub>3</sub> || = || 6753544154624910 − 13128433387466
|-
| || || || = || 6740415721237444.
|}

이제 다항식 ''r''(''x'')의 모든 계수를 알게 되었다:

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

만약 두 정수의 크기가 다르거나, 평가 지점이 다르다면 이 행렬 계산식 역시 달라질 것이다. 하지만 이는 사전에 계산될 수 있는 부분이므로 미리 효율적으로 작성해 둘 수 있다.

=== 합성 ===

최종적으로 다항식 ''r''(''x'')에 ''B''를 대입하여 결과를 얻어낼 수 있다. 여기서 b = 10<sup>4</sup>였으므로, B = b<sup>2</sup> = 10<sup>8</sup>이다.

{|
|   ||   ||    ||    ||    ||    ||    ||    ||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''값에 따른 보간 행렬 ==

''k''값에 따른 보간 행렬을 몇 가지 정리해두었다.

=== 톰-1 ===
톰-1 (''k''<sub>''m''</sub> = ''k''<sub>''n''</sub> = 1)은 1개의 지점만을 필요로 한다. 여기서는 0을 잡았다. 사실 이는 일반 곱셈알고리즘과 동일하다:

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

=== 톰-1.5 ===
톰-1.5 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 1)는 2개의 지점을 필요로 한다. 여기서는 0과 ∞를 잡았다. 보간 행렬은 단위행렬과 동일하다:

: <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 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 2)은 3개의 지점을 필요로 하고, 대개 0, 1, ∞를 잡는다. 이는 [[카라슈바 알고리즘]]과 동일하다:

: <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 (''k''<sub>''m''</sub> = 3, ''k''<sub>''n''</sub> = 2)는 4개의 평가지점을 필요로 한다. 여기에서는 0, 1, -1, ∞를 잡았다:

: <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 & 1/2 & -1/2 & -1 \\
-1 & 1/2 & 1/2 & 0 \\
0 & 0 & 0 & 1
\end{matrix}\right).</math>

== 각주 ==
<references/>

== 참고 문헌 ==
* 커누스. ''[[컴퓨터 프로그래밍의 예술]]'', 제 2권. 1997. 섹션 4.3.3.A: Digital methods, 294쪽.
* R. Crandall & C. Pomerance. ''Prime Numbers – A Computational Perspective''. Second Edition, Springer, 2005. Section 9.5.1: Karatsuba and Toom–Cook methods, 473쪽.
* M. Bodrato. ''[http://bodrato.it/toom-cook/ Toward Optimal Toom–Cook Multiplication...]''. In WAIFI'07, Springer, 2007.

== 외부 링크 ==
{{포털|수학}}
* {{언어링크|en}} [http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html 톰-쿡 알고리즘에 관한 GMP의 문서]
* {{언어링크|ko}} [http://bab2min.tistory.com/428 톰-쿡 알고리즘에 대한 간략한 설명]

{{수론 알고리즘}}

[[분류:컴퓨터 산술 알고리즘]]
[[분류:곱셈]]