톰-쿡 알고리즘
From Wikipedia, the free encyclopedia
톰–쿡 알고리즘(Toom–Cook algorithm)은 안드레이 톰과 스테픈 쿡이 제안한 곱셈 알고리즘으로 큰 두 정수를 곱할 때 사용된다.
톰-쿡 알고리즘에서는 큰 정수 a와 b를 곱하기 위해, 두 수를 작은 조각으로 나눈다. 조각의 수를 k라고 할때, k가 커질수록 곱셈의 내부 연산법은 복잡해지지만, 전체 시간 복잡도는 낮아진다. 이 곱셈 방법은 나눠진 각각의 조각에 대해서도 다시 적용할 수 있기 때문에, 조각이 작아질때까지 재귀적으로 사용할 수 있다.
톰-3 알고리즘은 k가 3일 경우를 가리키며, 9번의 곱셈을 5번으로 단축시켜, Θ(nlog(5)/log(3)), 즉 Θ(n1.465) 시간 안에 곱셈을 완료한다. 일반적으로 톰-k 알고리즘은 Θ(c(k) ne) 시간에 수행될 수 있다. 여기서 e = log(2k − 1) / log(k), ne은 조각들 간의 곱셈에 걸리는 시간, c는 덧셈이나 뺄셈, 혹은 작은 상수와의 곱셈에 걸리는 시간을 뜻한다.[1] 카라슈바 알고리즘은 톰-쿡 알고리즘에서 k가 2인 특별한 경우로, 4번의 곱셈을 3번으로 줄여 Θ(nlog(3)/log(2)) 시간 안에 수행된다. k가 1인 경우는 일반적인 곱셈 알고리즘과 동일해지며 시간 복잡도는 Θ(n2)가 된다.
k값을 증가시켜서 e값을 거의 1에 가깝게 낮출수 있지만, 이 경우 c의 값이 급속하게 커져 소용이 없다.[1][2] 이런 부가적인 연산 때문에 톰-쿡 알고리즘은 작은 정수의 곱셈에 적용하면 일반 곱셈법보다 느려지기에 이 알고리즘은 적당히 큰 정수에 사용되며, 정수 크기가 훨씬 더 커질 경우는 시간복잡도가 Θ(n log n log log n)인 쇤하게-슈트라센 알고리즘이더빠 르게 된다.
톰은 1963년에 처음 이 알고리즘을 제시하였고, 쿡은 1966년에 그의 박사 논문에서 이 알고리즘을 개량시켰다.[3]