카라추바 곱셈법

카라추바 곱셈법(Karatsuba multiplication algorithm)은 큰 수의 곱셈을 빠르게 계산하는 방법으로, 소련의 수학자인 아나톨리 카라추바(Anatoly Karatsuba/Анатолий Алексеевич Карацуба)가 1960년에 고안하고 1962년에 발표하였다. 자세한 소개는 이 영상에서 볼 수 있다.

전통적인 방법으로는 n자리 수의 곱셈에 대해 [math]\displaystyle{ O(n^{2}) }[/math] 만큼의 시간 복잡도를 가지는 반면 이 문서에서 소개하는 방법은 [math]\displaystyle{ O(n^{\log_{2}3}) \approx O(n^{1.585}) }[/math]으로 단축할 수 있다. 다시 말해 곱하고자 하는 두 수의 자릿수가 각각 2배씩 늘어난다면 한 자리 곱셈(구구단)의 시행 횟수는 4배가 되지만 카라추바 곱셈법에서는 3배 늘어난다.

이 알고리즘을 확장하여 좀 더 빠르게 개량한 방법으로 톰-쿡 곱셈법, 이보다 더 빠른 방법으로 쇤하게-슈트라센 곱셈법이 있다.

아이디어

곱하고자 하는 두 수 [math]\displaystyle{ x, y }[/math]가 있다. 이를 [math]\displaystyle{ B }[/math]진법으로 쓰고, 두 수가 [math]\displaystyle{ m }[/math]자리수보다 길다고 가정하자. (즉 [math]\displaystyle{ x, y \geq B^{m} }[/math])

그러면 [math]\displaystyle{ x=aB^{m}+b, y=cB^{m}+d }[/math] 꼴로 쓸 수 있고, 두 수를 곱하면 [math]\displaystyle{ xy=acB^{2m}+(ad+bc)B^{m}+bd }[/math]가 된다. 이때 양 끝 항의 계수는 직접 곱하고(각 곱셈 2회), 가운데 항의 계수는 전통적 방법으로는 '곱셈 2회+덧셈 1회'를 시행한다. 가령 [math]\displaystyle{ x=62,y=73 }[/math]일 때 우리는 보통 [math]\displaystyle{ xy =(6\cdot7)10^2+(6\cdot3+2\cdot7)10+2\cdot3 = 4200+320+6 = 4526 }[/math]과 같은 풀이를 떠올리며 여기서 시행한 구구단 곱셈은 총 4회이다.

그런데 가운데 항의 계수에 대해 곱셈을 1회로 단축하는 방법이 존재한다. 사람이나 컴퓨터나 기본적으로 곱셈보다는 덧셈이 쉬우므로, 덧셈이 좀 늘더라도 곱셈 횟수가 준다면 전체적으로는 시간 상 이득이다.

관계식 [math]\displaystyle{ (a+c)(b+d) = (ad+bc)+ac+bd }[/math]을 변형하면 [math]\displaystyle{ ad+bc = (a+c)(b+d)-(ac+bd) }[/math]가 된다. 여기서 [math]\displaystyle{ ac, bd }[/math]는 앞서 언급했던 "양 끝 항의 계수"와 정확히 같으므로 다시 한 번 셈할 필요는 없고, 실질적으로 추가 곱셈이 필요한 항은 [math]\displaystyle{ (a+c)(b+d) }[/math]하나뿐이다.

위의 예시를 다시 들자면, 가장 큰 항과 가장 작은 항의 계수인 42, 6을 먼저 셈하고, 그 다음 [math]\displaystyle{ 6\cdot3+2\cdot7 = (6+2)\cdot(3+7) - (42+6) = 80-48 = 32 }[/math]를 도출하는 것이다. 이렇게 하면 필요한 부분 곱셈은 총 3회가 된다. 물론 여기서 [math]\displaystyle{ 8 \cdot 10 }[/math]은 후자가 다시 두 자리 수가 되지만, 핵심은 부분 곱셈으로 들어갈 때 곱하려는 수의 크기가 줄어든다는 데 있다. 어차피 한 자리 수의 덧셈 결과는 18을 넘지 않는다. 혹은 십구십구단 곱셈을 바로 적용하면 된다

전체적인 맥락은 곱할 대상의 자리수를 절반씩 끊고, 각 끊어진 부분을 곱해서 부분 결과를 다시 합하는 것이다. 여기서 부분 곱셈의 크기가 여전히 크다 싶으면 다시 자리수 끊기를 시행하면 된다.

알고리즘

• 아래는 알고리즘 [math]\displaystyle{ f(x, y)=xy }[/math]를 시행하는 방법을 설명한 것이다.

1. 전통적 곱셈을 시행할 기준 크기 [math]\displaystyle{ A }[/math]를 정한다. 두 수 중 한 쪽이라도 [math]\displaystyle{ A }[/math]보다 작으면, 전통적 방법으로 곱한 값을 반환한다.
2. 곱하고자 하는 두 수를 [math]\displaystyle{ B }[/math]진법으로 쓰고, 중 큰 쪽의 자리수를 가늠하고, [math]\displaystyle{ n }[/math]자리수임을 확인한다.
3. 두 수를 앞의 [math]\displaystyle{ \lfloor n/2 \rfloor }[/math]자리와 뒤의 [math]\displaystyle{ \lceil n/2 \rceil }[/math] 자리 꼴로 끊는다.
   • 즉 [math]\displaystyle{ x=aX+c, y=bX+d, X=B^{\lceil n/2 \rceil} }[/math] 꼴의 식으로부터 변수 [math]\displaystyle{ X, (a, c), (b, d) }[/math]를 새로 지정한다.
4. [math]\displaystyle{ p=f(a, b), r=f(c, d) }[/math]를 계산한다.
5. [math]\displaystyle{ q=f(a+c, b+d)-p-r }[/math]를 계산한다.
6. [math]\displaystyle{ f(x, y)=pX^{2}+qX+r }[/math]를 반환한다.

변형 알고리즘

항등식 [math]\displaystyle{ (c-a)(d-b)=ac+bd-(ad+bc) }[/math]를 이용하면 [math]\displaystyle{ ad+bc=ac+bd-(c-a)(d-b) }[/math]와 같이 쓸 수 있다. 이 경우도 마찬가지로 부분곱셈을 3회 시행한다. 상술한 알고리즘의 마지막 세 줄은 아래와 같이 고칠 수 있다. [math]\displaystyle{ x=aX+c, y=bX+d, X=B^{\lceil n/2 \rceil} }[/math]임을 참고.

1. [math]\displaystyle{ p=f(a, b), r=f(c, d) }[/math]를 계산한다.
2. [math]\displaystyle{ q=p+r-f(c-a, d-b) }[/math]를 계산한다.
3. [math]\displaystyle{ f(x, y)=pX^{2}+qX+r }[/math]를 반환한다.

적용 예

알고리즘을 적용할 때 몇 진법을 기준으로 하느냐에 따라 셈법이 달라진다. 물론 맥락은 모두 동일하다. 아래 예시에서는 사람에게 친숙한 십진법에서 구구단 곱셈의 시행 횟수를 알아본다. 자릿수를 쪼개다가 특정 항이 10보다 작아질 때 구구단 곱셈을 적용한다. (변형 알고리즘을 기준으로 계산)

• 예시: [math]\displaystyle{ x=3984, y=6752 }[/math]
• 두 수의 자릿수를 반으로 각각 쪼갠다: [math]\displaystyle{ x_1=39, x_2=84, y_1=67, y_2=52, X=10^2 }[/math]
• 앞쪽 두 항인 [math]\displaystyle{ x_1=39, y_1=67 }[/math]의 곱셈을 먼저 셈한다. 아래 과정에 따르면 구구단 곱셈 3회, 덧셈·뺄셈 6회 시행한다. 결과는 2613으로, 전통적 곱셈법과 일치한다.
  • 두 수를 다시 두 부분으로 각각 쪼갠다: [math]\displaystyle{ x_{11}=3, x_{12}=9, y_{11}=6, y_{12}=7, X_1=10 }[/math]
  • [math]\displaystyle{ p_1=x_{11}y_{11} =3\cdot6 =18 }[/math] … 구구단 곱셈 1회
  • [math]\displaystyle{ r_1=x_{12}y_{12} =9\cdot7 =63 }[/math] … 구구단 곱셈 1회
  • [math]\displaystyle{ (x_{12}-x_{11})(y_{12}-y_{11}) =6\cdot1 =6 }[/math] … 구구단 곱셈 1회, 뺄셈 2회
  • [math]\displaystyle{ q_1=p_1+r_1-(x_{12}-x_{11})(y_{12}-y_{11}) =18+63-6 =75 }[/math] … 덧셈·뺄셈 2회
  • 따라서 [math]\displaystyle{ p =x_1y_1 =p_1 X_1^2+q_1 X_1+r_1 =1800+750+63 =2613 }[/math] … 덧셈 2회
• 다음으로 뒤의 두 항인 [math]\displaystyle{ x_2=84, y_2=52 }[/math]의 곱셈을 시행한다. 바로 위와 같은 방법으로 셈하면 [math]\displaystyle{ r=4368 }[/math]이 나오고, 마찬가지로 구구단 곱셈 3회, 덧셈·뺄셈 6회를 시행한다.
• 그 다음 [math]\displaystyle{ x_2-x_1=45, y_2-y_1=-15 }[/math] (… 뺄셈 2회)의 곱을 셈한다. 결과는 [math]\displaystyle{ (x_2-x_1)(y_2-y_1)=-675 }[/math]가 나오고, 여기서 또 구구단 곱셈 3회, 덧셈·뺄셈 6회를 시행한다.
• [math]\displaystyle{ q =p+r-(x_2-x_1)(y_2-y_1) =2613+4368-(-675) =7656 }[/math] … 여기서 덧셈 2회를 추가한다.
• 따라서 최종 결과는 [math]\displaystyle{ xy =pX^2+qX+r =26130000+765600+4368 =26899968 }[/math] … 마지막 덧셈 2회가 더해진다.
• 이렇게 해서 우리는 구구단 곱셈 9회, 자리 합성을 위한 덧셈·뺄셈을 24회 시행했다. 물론 중간 과정에서 덧셈이나 뺄셈은 자리수에 따라 계산량이 달라진다.

전통적 곱셈과 비교

앞서 예시로 든 3984×6752를 통상 방법으로 계산한다면 구구단 곱셈을 총 16회 시행해야 한다. 카라추바 곱셈법에서는 9회로 단축되었는데, 계산 과정을 빙빙 돌아서 간 것 치고는 단축 효과가 그리 커 보이지 않을 수 있다. 하지만 수가 커질수록 계산 과정의 길이는 눈에 띄게 차이가 난다.

만약 곱하려는 두 수가 여덟 자리라면 전통적 곱셈법에서는 구구단 곱셈을 64회 써야 하지만 카라추바 곱셈법에서는 27회 쓴다. 그리고 이 횟수의 비는 자릿수가 더 늘어남에 따라 더욱 벌어진다.