카라추바 알고리즘

카라추바 알고리즘

출처: 위키백과 카라추바  <- 링크

소련의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견하고 1962년에 공개한

큰 수에 대한 효과적인 곱셈 알고리즘이다.

x: B진법의 n자리 수 어떤 값

y: B진법의 n자리 수 어떤 값

기본적으로 x*y의 곱셈연산은 O(n²)이라는 연산횟수가 필요하다.

하지만 카라추바는 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해

연산횟수를 줄였다.

<Algorithm 설명>

x와 y는 아래와 같은 형태로 분할 할 수 있다. (단, m은 n-1보다 작은 양수이며 x₀ 는 B^m 보다 작은 양수)

이 알고리즘에서 봐야 할 것은 큰 수 x를 두 수로 분할하고 분할을 했을 때 4번의 곱셈연산을 해야 하는데

이를 3번으로 줄이는 방법인거 같다.

x = x₁B^m + x₀

y = y₁B^m + y₀

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀

라고 할 때, x와 y의 곱은

xy = (x₁B^m + x₀)(y₁B^m + y₀)

   = z₂ B^2m + z₁ B^m + z₀

이 식은 x₁y₁, x₁y_0,, x₀y₁, x₀y₀ 4번의 곱셈을 해야한다.

카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다.

여기서 z₁을 조금 수정하면 곱셈연산을 하나 줄일 수 있다.

<식 변환>

z₁ = (x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀) - x₁y₁ - x₀y₀ = x₁y₀ + x₀y₁

이므로

z₁ = (x₁ + x₀)(y₁ + y₀) − z₂ − z₀ 라 할 수 있다.

위와 같이 x₁y₀, x₀y₁ 2번의 곱셈을 (x₁ + x₀)(y₁ + y₀) 1번으로 줄일 수 있다.

카라추바 알고리즘은 모든 B와 m에 대해 작동하지만, m이 n/2일 때 가장 효율적이다.

카라추바 알고리즘 기본단계의 덧셈, 뺄셈, 시프트 연산(B의 거듭제곱으로 곱하는 것)은 n에 비례하는 시간이 걸리므로, 그 비용의 비중은 n이 증가함에 따라 무시할 정도로 줄어든다. 더 정확하게 t(n)이 두 n자리수의 곱셈에 필요한 기초연산의 총 횟수라고 할 때 다음과 같다.

t(n) = 3 t([n/2]) + cn + d

(c와 d는 적당한 상수) 이런 재귀적 관계를 마스터 정리를 통해 풀면

점근 표기법으로 t(n) = O(n^{log(3)/log(2)})이라는 것을 알 수 있다.

충분히 큰 n에 대해, 카라추바 알고리즘은 고전적인 곱셈법보다 적은 횟수의 시프트 연산과 한 자리 곱셈을 행한다. 하지만 작은 n에 대하여는 추가적인 덧셈과 시프트 연산 때문에 고전적인 곱셈법보다 속도가 느려진다. 그 경계는 컴퓨터의 플랫폼에 따라 달라진다. 대략적으로 곱하는 수가 2³²⁰ ≈ 2×10⁹⁶ 이상일 때 카라추바 알고리즘이 더 빠르다.