카라추바 알고리즘

3. 알고리즘

카라추바 알고리즘은 분할 정복 방식을 사용하여 두 큰 수의 곱셈을 더 작은 수들의 곱셈으로 나누어 계산한다. 이 방법은 찰스 배비지가 알고 있던 공식^[4]을 이용해 곱셈 횟수를 줄일 수 있다는 아이디어에서 출발했다.

일반적인 곱셈 방식에서는 두 수를 곱할 때 여러 번의 곱셈이 필요하지만, 카라추바 알고리즘은 이 횟수를 줄인다. 예를 들어, 피승수 $X$와 승수 $Y$를 곱하여 $Z$를 구하는 경우($Z\; =\; X\; \backslash times\; Y$), $X$와 $Y$를 상위와 하위 부분으로 나누고, 분할 기준이 되는 기수 $b$(예: 3자리씩 분할하는 경우 $b:=1000$)를 정한다.

:$X\; :=\; x\_1\; \backslash cdot\; b\; +\; x\_0$

:$Y\; :=\; y\_1\; \backslash cdot\; b\; +\; y\_0$

:$Z\; :=\; z\_2\; \backslash cdot\; b^2\; +\; z\_1\; \backslash cdot\; b\; +\; z\_0$

카라추바 알고리즘은 다음 공식을 사용하여 $z\_1$을 계산하여 곱셈을 3번으로 줄인다.

:$z\_1\; :=\; z\_2\; +\; z\_0\; -\; (x\_1\; -\; x\_0)\; \backslash times\; (y\_1\; -\; y\_0)$

이 방식은 곱셈 횟수를 줄여 계산 효율성을 높인다.

3. 1. 기본 단계

3. 2. 예

4. 효율성 분석

카라추바 알고리즘의 기본 단계는 모든 B와 m에 대해 작동하지만, m이 n/2일 때 가장 효율적이다. 특히 양의 정수 k에 대해 n이 2^k이고, 재귀가 n이 1일 때 끝난다면, 한 자리 곱셈의 횟수는 3^k이 된다(''n''^''c''에서 ''c'' = log₂3이므로).^[7]

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

:t(n) = 3t($\backslash lceil$n/2$\backslash rceil$) + cn + d

(c와 d는 적당한 상수)

이런 재귀적 관계를 마스터 정리를 통해 풀면, 점근 표기법으로 t(n) = $\backslash Theta$(n^{log(3)/log(2)})이라는 것을 알 수 있다.^[6]

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

5. 구현

다음은 십진법으로 표현된 숫자를 사용하는 이 알고리즘의 의사 코드이다. 정수의 이진 표현의 경우, 10을 2로 바꾸면 된다.^[5]

`split_at` 함수의 두 번째 인수는 ''오른쪽''에서 추출할 자릿수를 지정한다. 예를 들어, `split_at("12345", 3)`은 마지막 3자리를 추출하여 high="12", low="345"를 반환한다.

```c

function karatsuba(num1, num2)

if (num1 < 10 or num2 < 10)

return num1 × num2 /* 기존 곱셈으로 돌아감 */

/* 숫자의 크기를 계산합니다. */

m = max(size_base10(num1), size_base10(num2))

m2 = floor(m / 2)

/* m2 = ceil (m / 2)도 작동합니다. */

/* 중간에서 숫자 시퀀스를 분할합니다. */

high1, low1 = split_at(num1, m2)

high2, low2 = split_at(num2, m2)

/* 크기가 대략 절반인 숫자에 대해 3번의 재귀 호출을 합니다. */

z0 = karatsuba(low1, low2)

z1 = karatsuba(low1 + high1, low2 + high2)

z2 = karatsuba(high1, high2)

return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

```

구현 시 발생하는 문제는 z₁에 대한 (x₁ + x₀)과 (y₁ + y₀)의 위 계산에서 오버플로가 발생할 수 있다는 것이다(B^m ≤ result < 2 B^m 범위의 결과가 생성됨). 이는 한 비트가 더 많은 승수를 필요로 한다. 이는 다음을 통해 피할 수 있다.

:z₁ = (x₀ - x₁)(y₁ - y₀) + z₂ + z₀.

(x₀ - x₁)과 (y₁ - y₀)의 이 계산은 -B^m < result < B^m 범위의 결과를 생성한다. 이 방법은 음수를 생성할 수 있으며, 이는 부호를 인코딩하기 위해 한 비트가 더 필요하며, 승수를 위해 여전히 한 비트가 더 필요하다. 그러나 이를 피하는 한 가지 방법은 부호를 기록한 다음 (x₀ - x₁) 및 (y₁ - y₀)의 절댓값을 사용하여 부호 없는 곱셈을 수행하는 것이다. 그런 다음 원래 두 부호가 다를 때 결과를 음수로 만들 수 있다. 또 다른 장점은 (x₀ - x₁)(y₁ - y₀)이 음수일 수 있지만, z₁의 최종 계산에는 덧셈만 포함된다는 것이다.

참조

_[1] 논문 Multiplication of Many-Digital Numbers by Automatic Computers https://www.mathnet.[...]
_[2] 논문 The Complexity of Computations http://www.ccas.ru/p[...]
_[3] 서적 The Art of Computer Programming Addison-Wesley Publ.Co.
_[4] 문서 Of the Analytical Engine, Larger Numbers Treated https://archive.org/[...] Longman Green, London 1864
_[5] 서적 Data Structures and Algorithm Analysis in C++ Addison-Wesley 2005
_[6] 저널 자동식 컴퓨터에 의핸 큰 수의 곱셈(Multiplication of Many-Digital Numbers by Automatic Computers)
_[7] 저널 계산 복잡도(The Complexity of Computations) http://www.ccas.ru/p[...]
_[8] 서적 컴퓨터 프로그래밍의 예술. 제 2권.