'''톰–쿡 알고리즘'''()은 안드레이 톰과 스테픈 쿡이 제안한 곱셈 알고리즘으로 정수를 곱할 사용된다. 톰-쿡 알고리즘에서는 정수 ''a''와 ''b''를 곱하기 위해, 수를 작은 조각으로 나눈다. 조각의 수를 ''k''라고 할때, ''k''가 커질수록 곱셈의 내부 연산법은 복잡해지지만, 전체 시간 복잡도는 낮아진다. 곱셈 방법은 나눠진 각각의 조각에 대해서도 다시 적용할 있기 때문에, 조각이 작아질때까지 재귀적으로 사용할 있다. 톰-3 알고리즘은 ''k''가 3일 경우를 가리키며, 9번의 곱셈을 5번으로 단축시켜, Θ(''n''1.465) 시간 안에 곱셈을 완료한다. 일반적으로 톰-''k'' 알고리즘은 Θ(''c''(''k'') ''ne'') 시간에 수행될 있다. 여기서 ''e'' log(2''k'' 1) log(''k''), ''ne''은 조각들 간의 곱셈에 걸리는 시간, ''c''는 덧셈이나 뺄셈, 혹은 작은 상수와의 곱셈에 걸리는 시간을 뜻한다. 카라슈바 알고리즘은 톰-쿡 알고리즘에서 ''k''가 2인 특별한 경우로, 4번의 곱셈을 3번으로 줄여 시간 안에 수행된다. ''k''가 1인 경우는 일반적인 곱셈 알고리즘과 동일해지며 시간 복잡도는 Θ(''n''2)가 된다. ''k''값을 증가시켜서 ''e''값을 거의 1에 가깝게 낮출수 있지만, 경우 ''c''의 값이 급속하게 커져 소용이 없다. 이런 부가적인 연산 때문에 톰-쿡 알고리즘은 작은 정수의 곱셈에 적용하면 일반 곱셈법보다 느려지기에 알고리즘은 적당히 정수에 사용되며, 정수 크기가 훨씬 커질 경우는 시간복잡도가 Θ(''n'' log ''n'' log log ''n'')인 쇤하게-슈트라센 알고리즘이더빠 르게 된다. 톰은 1963년에 처음 알고리즘을 제시하였고, 쿡은 1966년에 그의 박사 논문에서 알고리즘을 개량시켰다. == 상세 == 단락은 톰-''k'' 알고리즘이 어떻게 작동하는지를 간략하게 설명한다. 알고리즘은 크게 5단계를 거쳐 완료된다. 분할 평가 점별 곱셈 보간 합성 정수를 구현하는데 있어서, 대개 위치 기수법으로 자리의 정수를 표현하는 방법이 자주 사용된다. 때의 밑을 ''b''라고 하자. 예시에서는 ''b'' 10000을 사용할 것이므로, 자리에는 4개의 10진 정수가 들어가게 된다. (실제 컴퓨터 구현에서는 연산의 효율성을 위해 ''b''값으로 2의 거듭제곱이 사용된다.) 정수를 다음과 같다고 하자. ''m'' 12 3456 7890 1234 5678 9012 ''n'' 8765 4321 9876 5432 1098. 물론 정수들은 톰-쿡 알고리즘을 사용하기엔 작아서, 그냥 일반 곱셈법이 훨씬 빠르다. 하지만 설명을 위해 값을 사용하도록 한다. === 분할 === 첫번째 단계는 정수를 ''k''개의 조각으로 자르기 위한 적절한 단위인 ''B'' ''b''''i''를 찾는 것이다. 일반적으로 ''i''는 다음과 같이 구할 있다. 예제에서는 톰-3 알고리즘을 사용할 것이므로, ''B'' ''b''2 108가 된다. B값을 단위로 ''m''과 ''n''을 자르면 ''m''''i'', ''n''''i''는 다음과 같이 것이다. 우리는 수를 계수로 하는 ''k''−1차 다항식을 만들것이다. 다항식을 이렇게 정의하면 ''p''(''B'') ''m'', ''q''(''B'') ''n''이 된다. 이렇게 정의한 목적은 다항식의 곱인 ''r''(''x'') 구하기 위해서이다. 우리가 구하고자 하는 결과는 다항식에 ''B''를 대입함으로써 얻을 있다. ''r''(''B'') ''m''×''n'' ''m''과 ''n''을 일반적인 곱셈법으로 곱하면 (여기서는 조각으로 나누었으므로), 조각 간의 곱셈이 9번 필요하다. 하지만, ''r''(''x'')는 2(''k''−1)차 다항식(''k''가 3이므로 4차 다항식)이므로, 2''k''−1개의 미지 계수를 구하기 위해서는 2''k''-1개의 방정식만 있으면 된다. 방정식은 선형 대수를 이용하여 간단한 방법으로 풀어낼 있으므로, 결과적으로 일반 곱셈법보다 적은 수의 곱셈을 사용하여 결과를 얻을 있게 된다. 만약 곱하는 수의 자리수가 다를 경우 ''k''값을 ''m''과 ''n''에 따라 다르게 주는 것이 유용하다. ''톰-2.5'' 알고리즘에서는 ''k''''m'' and ''k''''n'' 같은 값을 사용한다. 때의 ''i''는 다음과 같이 구할 있다. === 평가 === 앞서 언급했듯, 톰-쿡 알고리즘에서는 ''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, ∞을 넣어 계산해볼 것이다: ''q''에 대해서도 마찬가지. 예시의 값을 실제로 대입하면 다음과 같다: ''p''(0) ''m''0 56789012 56789012 ''p''(1) ''m''0 ''m''1 ''m''2 56789012 78901234 123456 135813702 ''p''(−1) ''m''0 ''m''1 ''m''2 56789012 78901234 123456 −21988766 ''p''(−2) ''m''0 2''m''1 4''m''2 56789012 2×78901234 4×123456 −100519632 ''p''(∞) ''m''2 123456 123456 ''q''(0) ''n''0 54321098 54321098 ''q''(1) ''n''0 ''n''1 ''n''2 54321098 43219876 98765 97639739 ''q''(−1) ''n''0 ''n''1 ''n''2 54321098 43219876 98765 11199987 ''q''(−2) ''n''0 2''n''1 4''n''2 54321098 2×43219876 4×98765 −31723594 ''q''(∞) ''n''2 98765 98765. 위에 보이는대로 결과값이 음수가 수도 있다. 다음과 같이 행렬로 간단하게 표현할 있다. 표현은 보간 과정에서도 유용하게 있다. ==== 빠른 평가 ==== 평가 지점에서 중복되는 연산을 줄여 빠르게 계산하는 방법이 있다. 방법을 사용할 경우 덧셈/뺄셈의 수를 줄일 있다. 여기에서는 톰-3의 경우만 제시한다. ''p''0 ''m''0 ''m''2 56789012 123456 56912468 ''p''(0) ''m''0 56789012 56789012 ''p''(1) ''p''0 ''m''1 56912468 78901234 135813702 ''p''(−1) ''p''0 ''m''1 56912468 78901234 −21988766 ''p''(−2) (''p''(−1) ''m''2)×2 ''m''0 (− 21988766 123456 )×2 56789012 100519632 ''p''(∞) ''m''2 123456 123456. 과정은 오직 5번의 덧셈/뺄셈이 필요하다. 이는 단순 계산보다 1회 적은 것이다. === 점별 곱셈 === 다항식 ''p''(''x'')와 ''q''(''x'')를 통째로 곱하는 대신, 앞에서 구한 여러 개의 지점에 대해서 구한다. 이는 원래 목표였던 정수끼리의 곱셈보다 훨씬 작은 수끼리의 연산이 된다. 게다가 점별 곱셈 과정에 톰-쿡 알고리즘을 재귀적으로 사용하여 실제로 곱하게 되는 수를 일반 곱셈법으로도 충분히 빠르게 곱할 있는 크기로 줄일 있다. 예시의 결과물은 다음과 같을 것이다. ''r''(0) 56789012 54321098 ''r''(1) 135813702 97639739 ''r''(−1) −21988766 11199987 ''r''(−2) −100519632 −31723594 ''r''(∞) 123456 98765 12193131840. 과정이 가장 시간을 오래 잡아먹는 부분이다. 나머지 과정은 ''m''과 ''n''의 크기와 선형의 시간복잡도를 갖기만, 오직 과정만 그보다 시간복잡도를 갖는다. === 보간 === 과정은 전체 과정 가장 복잡한 과정으로, 위에서 구한 점별 곱셈 결과를 이용하여 다항식 ''r''(''x'')의 미지계수를 구하는 과정이다. 행렬은 평가 과정에서 만들었던 행렬과 같은 방식으로 만들어진 것이다. 가우스 소거법을 통해 행렬의 역행렬을 구할수도 있지만, 이는 너무 느리다. 하지만 우리가 앞서 고른 지점이 0, 1, &minus1, 2, &minus2 등으로 단순하므로 복잡한 계산과정 없이 행렬을 풀어낼 있다. 이제 남은 과정들은 모두 행렬-벡터 간의 곱셈이다. 행렬에 분수가 들어있지만, 결과는 정수로 나온다. 그렇기에 과정은 정수 간의 덧셈/뺄셈과 작은 상수를 곱하고 나누는 연산만 가지고 수행할 있다. 하지만 과정을 효율적으로 짜는 것은 쉽지 않은 일이다. 여기에서는 톰-3 알고리즘의 효율적인 방법을 소개한다. ''r''0 ''r''(0) ''r''4 ''r''(∞) 12193131840 ''r''3 (''r''(−2) ''r''(1))/3 ''r''1 (''r''(1) ''r''(−1))/2 ''r''2 ''r''(−1) ''r''(0) ''r''3 (''r''2 ''r''3)/2 2''r''(∞) 2×12193131840 13128433387466 ''r''2 ''r''2 ''r''1 ''r''4 12193131840 ''r''1 ''r''1 ''r''3 13128433387466 이제 다항식 ''r''(''x'')의 모든 계수를 알게 되었다: 만약 정수의 크기가 다르거나, 평가 지점이 다르다면 행렬 계산식 역시 달라질 것이다. 하지만 이는 사전에 계산될 있는 부분이므로 미리 효율적으로 작성해 있다. === 합성 === 최종적으로 다항식 ''r''(''x'')에 ''B''를 대입하여 결과를 얻어낼 있다. 여기서 104였으므로, b2 108이다. 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 결과가 곱이다. == ''k''값에 따른 보간 행렬 == ''k''값에 따른 보간 행렬을 가지 정리해두었다. === 톰-1 === 톰-1 (''k''''m'' ''k''''n'' 1)은 1개의 지점만을 필요로 한다. 여기서는 0을 잡았다. 사실 이는 일반 곱셈알고리즘과 동일하다: === 톰-1.5 === 톰-1.5 (''k''''m'' 2, ''k''''n'' 1)는 2개의 지점을 필요로 한다. 여기서는 0과 ∞를 잡았다. 보간 행렬은 단위행렬과 동일하다: === 톰-2 === 톰-2 (''k''''m'' 2, ''k''''n'' 2)은 3개의 지점을 필요로 하고, 대개 0, 1, ∞를 잡는다. 이는 카라슈바 알고리즘과 동일하다: === 톰-2.5 === 톰-2.5 (''k''''m'' 3, ''k''''n'' 2)는 4개의 평가지점을 필요로 한다. 여기에서는 0, 1, -1, ∞를 잡았다: == 각주 == == 참고문헌 == 커누스. ''컴퓨터 프로그래밍의 예술'', 2권. 1997. 섹션 4.3.3.A: Digital methods, 294쪽. R. Crandall C. Pomerance. ''Prime Numbers Computational Perspective''. Second Edition, Springer, 2005. Section 9.5.1: Karatsuba and Toom–Cook methods, 473쪽. M. Bodrato. '' Toward Optimal Toom–Cook In WAIFI'07, Springer, 2007. == 외부 링크 == 톰-쿡 알고리즘에 관한 GMP의 문서 톰-쿡 알고리즘에 대한 간략한 설명 분류:컴퓨터 산술 알고리즘 분류:곱셈