카라추바 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''카라추바 알고리즘'''은 소련의 수학자 [[아나톨리 알렉세예비치 카라추바]]가 1960년에 발견하고 1962년에 공개한, 큰 수에 대한 효과적인 [[곱셈 알고리즘]]이다.
<ref name="kara1962">
  {{저널 인용
  | author = A. Karatsuba and Yu. Ofman
  | 제목 = 자동식 컴퓨터에 의핸 큰 수의 곱셈(Multiplication of Many-Digital Numbers by Automatic Computers)
  | journal = Proceedings of the USSR Academy of Sciences
  | volume = 145
  | year = 1962
  | pages = 293–294
  | note = Translation in Physics-Doklady, 7 (1963), pp. 595–596}}
</ref><ref name="kara1995">
  {{저널 인용
  | author = A. A. Karatsuba
  | 제목 = 계산 복잡도(The Complexity of Computations)
  | journal = Proceedings of the Steklov Institute of Mathematics
  | volume = 211
  | pages 169-183
  | year = 1995
  | url = http://www.ccas.ru/personal/karatsuba/divcen.pdf
  | note = translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995)}}
</ref><ref name="knuthV2">
  커누스 (1969) ''컴퓨터 프로그래밍의 예술. 제 2권.'', 724 pp..
</ref>
이 방법은 두 ''n''자리 수의 곱셈을 최대 <math>3 n^{\log_23}\approx 3 n^{1.585}</math>(''n''이 [[2의 거듭제곱]]일 때는 정확하게 <math>n^{\log_23}</math>와 일치한다)개의 한 자리 곱셈으로 줄인다. 그러므로 이 방법은 ''n''<sup>2</sup>개의 한 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 ''n'' = 2<sup>10</sup> = 1024 라면, 고전적인 방법에서는 (2<sup>10</sup>)<sup>2</sup> = 1,048,576 회의 한 자리 곱셈이 필요하지만, 이 방법으로는 3<sup>10</sup> = 59,049 회의 한 자리 곱셈만이 필요하다.

[[톰-쿡 곱셈법]]은 카라추바 알고리즘의 일반적인 형태이다. 충분히 큰 ''n''에 대해 카라추바 알고리즘의 복잡도는 [[쇤하게-슈트라센 알고리즘]]보다 크다.

카라추바 알고리즘은 [[분할 정복 알고리즘]]의 좋은 예이다.

== 역사 ==
기본적으로 두 ''n''자리 수의 곱셈은 ''n''<sup>2</sup>에 비례하는 ([[점근 표기법]]으로는 <math>\Theta(n^2)</math>)횟수의 기초 연산이 필요하다. 1952년 [[안드레이 콜모고로프]]는 고전적인 알고리즘이 <math>\Omega(n^2)</math>의 연산 횟수로 점근적으로 최적화 될 수 있을 것이라고 추측했다.

1960년 가을, 콜모고로프는 [[모스크바 대학교]]에서 [[사이버네틱스]]에 관한 수학 문제들에 대한 세미나를 열었다. 그곳에서 <math>\Omega(n^2)</math> 추측과 다른 [[계산 복잡도 이론]]에 대한 문제들을 언급했다. 그 후 1주 만에 23살 학생 카라추바가 두 ''n''자리수의 곱셈을 <math>\Theta(n^{\log_2 3})</math>회의 기초 연산을 통해 행할 수 있는 분할 정복 알고리즘을 발견함으로써, 그 추측을 반증하였다. 콜모고로프는 그 발견에 매우 당황했다. 그는 마지막이 될 다음 세미나에서 이것을 알렸다<ref name="kara1995"/>.

이 방법은 1962년 ''소비에트 연방 과학 학회(Доклады Академии наук СССР)''에 발표되었다<ref name="kara1962"/>. 그 논문은 콜모고로프가 유리 오프만과 협력하여 썼지만, 카라추바와 오프만이 저자로 올라갔다. 카라추바는 발표자로부터 사본을 받고 그 사실을 알게 되었다<ref name="kara1995"/>.

== 알고리즘 ==
=== 기본 단계 ===
카라추바 알고리즘의 기본 단계는 큰 두 수 ''x''와 ''y''의 곱을 자릿수가 ''x'', ''y''의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다.

''x''와 ''y''를 ''B''진법의 ''n''자리수라고 하자. ''n''보다 작은 양수 ''m''에 대해 다음과 같이 ''x'', ''y''를 쪼갤 수 있다.

:''x'' = ''x''<sub>1</sub>''B''<sup>''m''</sup> + ''x''<sub>0</sub>
:''y'' = ''y''<sub>1</sub>''B''<sup>''m''</sup> + ''y''<sub>0</sub>

(단, ''x''<sub>0</sub>과 ''y''<sub>0</sub>는 ''B''<sup>''m''</sup>보다 작다.)

:''z''<sub>2</sub> = ''x''<sub>1</sub>''y''<sub>1</sub>
:''z''<sub>1</sub> = ''x''<sub>1</sub>''y''<sub>0</sub> + ''x''<sub>0</sub>''y''<sub>1</sub>
:''z''<sub>0</sub> = ''x''<sub>0</sub>''y''<sub>0</sub>

라고 할 때, ''x''와 ''y''의 곱은
:''xy'' = (''x''<sub>1</sub>''B''<sup>''m''</sup> + ''x''<sub>0</sub>)(''y''<sub>1</sub>''B''<sup>''m''</sup> + ''y''<sub>0</sub>)
::= ''z''<sub>2</sub> ''B''<sup>2''m''</sup> + ''z''<sub>1</sub> ''B''<sup>''m''</sup> + ''z''<sub>0</sub>

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

:''z''<sub>2</sub> = ''x''<sub>1</sub>''y''<sub>1</sub> 라 하자.
:''z''<sub>0</sub> = ''x''<sub>0</sub>''y''<sub>0</sub> 라 하자.

:''z''<sub>1</sub> = (''x''<sub>1</sub>''y''<sub>1</sub> + ''x''<sub>1</sub>''y''<sub>0</sub> + ''x''<sub>0</sub>''y''<sub>1</sub> + ''x''<sub>0</sub>''y''<sub>0</sub>) - ''x''<sub>1</sub>''y''<sub>1</sub> - ''x''<sub>0</sub>''y''<sub>0</sub> = ''x''<sub>1</sub>''y''<sub>0</sub> + ''x''<sub>0</sub>''y''<sub>1</sub>
이므로

:''z''<sub>1</sub> = (''x''<sub>1</sub> + ''x''<sub>0</sub>)(''y''<sub>1</sub> + ''y''<sub>0</sub>) − ''z<sub>2</sub>'' − ''z<sub>0</sub>'' 라 할 수 있다.

=== 예 ===
''B'' = 10 이라하고, ''m'' = 2 라 하자. 1234와 5678의 곱을 구하고 싶으면,

:12 34 = 12 × 10<sup>2</sup> + 34
:56 78 = 56 × 10<sup>2</sup> + 78
:''z''<sub>2</sub> = 12 × 56 = 672
:''z''<sub>0</sub> = 34 × 78 = 2652
:''z''<sub>1</sub> = (12 + 34)(56 + 78) − ''z''<sub>2</sub> − ''z''<sub>0</sub> = 46 × 134 − 672 − 2652 = 2840
:결과 = ''z''<sub>2</sub> × 10<sup>2×2</sup> + ''z''<sub>1</sub> × 10<sup>2</sup> + ''z''<sub>0</sub> = 672 × 10000 + 2840 × 100 + 2652 = '''7006652'''

=== 재귀적 활용 ===
만약 ''n''이 4 이상이면, 카라추바 알고리즘 기본 단계를 통해 ''n''보다 작은 자리의 수에 대한 곱셈 3번을 하게 된다. 그러므로 [[재귀 호출]]을 통해 그 곱을 계산할 수 있다. 재귀 호출은 곱하는 수가 단번에 계산될 정도로 작아질 때까지 적용할 수 있다.

예를 들어 32비트끼리 곱하는 [[곱셈기]]에서 ''B'' = 2<sup>31</sup> = 2,147,483,648 or ''B'' = 10<sup>9</sup> = 1,000,000,000를 선택하고 각 자리를 독립된 32비트 단위로 저장할 수 있다. 그러면 ''x''<sub>1</sub> + ''x''<sub>0</sub>와 ''y''<sub>1</sub> + ''y''<sub>0</sub>에 여분의 자리올림 비트가 필요없고, 카라추바 재귀는 숫자가 한 자리가 될 때까지 반복가능하다.

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

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

:''t''(''n'') = 3 ''t''(<math>\lceil</math>''n''/2<math>\rceil</math>) + ''cn'' + ''d''

(''c''와 ''d''는 적당한 상수)
이런 재귀적 관계를 [[마스터 정리]]를 통해 풀면, [[점근 표기법]]으로 ''t''(''n'') = <math>\Theta</math>(''n''<sup>log(3)/log(2)</sup>)이라는 것을 알 수 있다.

충분히 큰 ''n''에 대해, 카라추바 알고리즘은 고전적인 곱셈법보다 적은 횟수의 시프트 연산과 한 자리 곱셈을 행한다. 하지만 작은 ''n''에 대하여는 추가적인 덧셈과 시프트 연산 때문에 고전적인 곱셈법보다 속도가 느려진다. 그 경계는 컴퓨터의 플랫폼에 따라 달라진다. 대략적으로 곱하는 수가 2<sup>320</sup> ≈ 2{{e|96}} 이상일 때 카라추바 알고리즘이 더 빠르다.[http://gmplib.org/manual/Karatsuba-Multiplication.html][https://web.archive.org/web/20160313095537/http://ozark.hendrix.edu/~burch/proj/karat/comment1.html]

== 각주 ==
{{각주}}
* Karacuba A. A. ''Berechnungen und die Kompliziertheit von Beziehungen (German).'' Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).

== 외부 링크 ==
{{포털|수학}}
* [https://web.archive.org/web/20090527213340/http://utilitymill.com/utility/Karatsuba_Multiplication 카라추바 곱셈 알고리즘 - 웹 기반 계산기 (GPL)]
* [http://mathworld.wolfram.com/KaratsubaMultiplication.html MathWorld의 카라추바 알고리즘]
* Bernstein, D. J., "[http://cr.yp.to/papers/m3.pdf 수학자를 위한 여러 자리 수의 곱셈법]". 카라추바 알고리즘을 비롯한 여러 곱셈 알고리즘.
* [https://www.youtube.com/watch?v=8iIU9EDC2GQ "중국식 곱셈법"] - 카라추바 알고리즘의 실용적인 활용 사례.

{{수론 알고리즘}}

[[분류:컴퓨터 산술 알고리즘]]
[[분류:곱셈]]