카라추바 알고리즘
From Wikipedia, the free encyclopedia
카라추바 알고리즘은 소련의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 곱셈 알고리즘이다. [1][2][3] 이 방법은 두 n자리 수의 곱셈을 최대 (n이 2의 거듭제곱일 때는 정확하게 와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 n2개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 n = 210 = 1024 라면, 고전적인 방법에서는 (210)2 = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 310 = 59,049 회의 한 자리 곱셈만이 필요하다.
톰-쿡 곱셈법은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 n에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다.
카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다.