'''카라추바 알고리즘'''은 소련의 수학자 아나톨리 알렉세예비치 카라추바가 1960년에 발견하고 1962년에 공개한, 수에 대한 효과적인 곱셈 알고리즘이다. 방법은 ''n''자리 수의 곱셈을 최대 (''n''이 2의 거듭제곱일 때는 정확하게 일치한다)개의 자리 곱셈으로 줄인다. 그러므로 방법은 ''n''2개의 자리 곱셈을 해야하는 고전적인 곱셈 방법보다 빠르다. 만약 ''n'' 210 1024 라면, 고전적인 방법에서는 (210)2 1,048,576 회의 자리 곱셈이 필요하지만, 방법으로는 310 59,049 회의 자리 곱셈만이 필요하다. 톰-쿡 곱셈법은 카라추바 알고리즘의 일반적인 형태이다. 충분히 ''n''에 대해 카라추바 알고리즘의 복잡도는 쇤하게-슈트라센 알고리즘보다 크다. 카라추바 알고리즘은 분할 정복 알고리즘의 좋은 예이다. == 역사 == 기본적으로 ''n''자리 수의 곱셈은 ''n''2에 비례하는 (점근 표기법으로는 )횟수의 기초 연산이 필요하다. 1952년 안드레이 콜모고로프는 고전적인 알고리즘이 연산 횟수로 점근적으로 최적화 있을 것이라고 추측했다. 1960년 가을, 콜모고로프는 모스크바 대학교에서 사이버네틱스에 관한 수학 문제들에 대한 세미나를 열었다. 그곳에서 추측과 다른 계산 복잡도 이론에 대한 문제들을 언급했다. 1주 만에 23살 학생 카라추바가 ''n''자리수의 곱셈을 회의 기초 연산을 통해 행할 있는 분할 정복 알고리즘을 발견함으로써, 추측을 반증하였다. 콜모고로프는 발견에 매우 당황했다. 그는 마지막이 다음 세미나에서 이것을 알렸다. 방법은 1962년 ''소비에트 연방 과학 학회(Доклады Академии наук СССР)''에 발표되었다. 논문은 콜모고로프가 유리 오프만과 협력하여 썼지만, 카라추바와 오프만이 저자로 올라갔다. 카라추바는 발표자로부터 사본을 받고 사실을 알게 되었다. == 알고리즘 == === 기본 단계 === 카라추바 알고리즘의 기본 단계는 ''x''와 ''y''의 곱을 자릿수가 ''x'', ''y''의 절반인 수들의 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다. ''x''와 ''y''를 ''B''진법의 ''n''자리수라고 하자. ''n''보다 작은 양수 ''m''에 대해 다음과 같이 ''x'', ''y''를 쪼갤 있다. :''x'' ''x''0 :''y'' ''y''0 (단, ''x''0과 ''y''0는 ''B''''m''보다 작다.) :''z''2 ''x''1''y''1 :''z''1 ''x''1''y''0 ''x''0''y''1 :''z''0 ''x''0''y''0 라고 때, ''x''와 ''y''의 곱은 :''xy'' ''y''0) ::= ''z''2 ''B''2''m'' ''z''1 ''B''''m'' ''z''0 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 함으로써, ''xy''를 3번의 곱셈을 통해 구할 있다는 알았다. :''z''2 ''x''1''y''1 하자. :''z''0 ''x''0''y''0 하자. :''z''1 (''x''1''y''1 ''x''1''y''0 ''x''0''y''1 ''x''0''y''0) ''x''1''y''1 ''x''0''y''0 ''x''1''y''0 ''x''0''y''1 이므로 :''z''1 (''x''1 ''x''0)(''y''1 ''y''0) ''z2'' ''z0'' 있다. === === ''B'' 10 이라하고, ''m'' 하자. 1234와 5678의 곱을 구하고 싶으면, :12 34 12 102 34 :56 78 56 102 78 :''z''2 12 56 672 :''z''0 34 78 2652 :''z''1 (12 34)(56 78) ''z''2 ''z''0 46 134 672 2652 2840 :결과 ''z''2 102×2 ''z''1 102 ''z''0 672 10000 2840 100 2652 '''7006652''' === 재귀적 활용 === 만약 ''n''이 이상이면, 카라추바 알고리즘 기본 단계를 통해 ''n''보다 작은 자리의 수에 대한 곱셈 3번을 하게 된다. 그러므로 재귀 호출을 통해 곱을 계산할 있다. 재귀 호출은 곱하는 수가 단번에 계산될 정도로 작아질 때까지 적용할 있다. 예를 들어 32비트끼리 곱하는 곱셈기에서 ''B'' 231 2,147,483,648 or ''B'' 109 1,000,000,000를 선택하고 자리를 독립된 32비트 단위로 저장할 있다. 그러면 ''x''1 ''x''0와 ''y''1 ''y''0에 여분의 자리올림 비트가 필요없고, 카라추바 재귀는 숫자가 자리가 때까지 반복가능하다. == 효율성 분석 == 카라추바 알고리즘 기본단계는 모든 ''B''와 ''m''에 대해 작동하지만, ''m''이 ''n''/2일 가장 효율적이다. 특히 양의 정수 ''k''에 대해 ''n''이 2''k''이고, 재귀가 ''n''이 1일 끝난다면, 자리 곱셈의 횟수는 3''k''이 된다(''n''''c''에서 ''c'' log23가 되므로). 카라추바 알고리즘 기본단계의 덧셈, 뺄셈, 시프트 연산(''B''의 거듭제곱으로 곱하는 것)은 ''n''에 비례하는 시간이 걸리므로, 비용의 비중은 ''n''이 증가함에 따라 무시할 정도로 줄어든다. 정확하게 ''t''(''n'')이 ''n''자리수의 곱셈에 필요한 기초연산의 횟수라고 다음과 같다. :''t''(''n'') ''t''(''n''/2) ''cn'' ''d'' (''c''와 ''d''는 적당한 상수) 이런 재귀적 관계를 마스터 정리를 통해 풀면, 점근 표기법으로 ''t''(''n'') 것을 있다. 충분히 ''n''에 대해, 카라추바 알고리즘은 고전적인 곱셈법보다 적은 횟수의 시프트 연산과 자리 곱셈을 행한다. 하지만 작은 ''n''에 대하여는 추가적인 덧셈과 시프트 연산 때문에 고전적인 곱셈법보다 속도가 느려진다. 경계는 컴퓨터의 플랫폼에 따라 달라진다. 대략적으로 곱하는 수가 2320 이상일 카라추바 알고리즘이 빠르다. == 참조 == Karacuba A. A. ''Berechnungen und die Kompliziertheit von Beziehungen (German).'' Elektron. Kybernetik, 11, 603–606 (1975). == 외부 링크 == 카라추바 곱셈 알고리즘 기반 계산기 (GPL) MathWorld의 카라추바 알고리즘 Bernstein, D. J., 수학자를 위한 여러 자리 수의 곱셈법". 카라추바 알고리즘을 비롯한 여러 곱셈 알고리즘. "중국식 곱셈법" 카라추바 알고리즘의 실용적인 활용 사례. 분류:컴퓨터 산술 알고리즘 분류:곱셈