로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''카라추바 곱셈법'''(Karatsuba multiplication algorithm)은 큰 수의 곱셈을 빠르게 계산하는 방법으로, [[소련]]의 수학자인 아나톨리 카라추바(Anatoly Karatsuba/Анатолий Алексеевич Карацуба)가 1960년에 고안하고 1962년에 발표하였다. 자세한 소개는 [https://www.youtube.com/watch?v=cCKOl5li6YM 이 영상에서 볼 수 있다.] 전통적인 방법으로는 n자리 수의 곱셈에 대해 <math>O(n^{2})</math> 만큼의 시간 복잡도를 가지는 반면 이 문서에서 소개하는 방법은 <math>O(n^{\log_{2}3}) \approx O(n^{1.585})</math>으로 단축할 수 있다. 다시 말해 곱하고자 하는 두 수의 자릿수가 각각 2배씩 늘어난다면 한 자리 곱셈(구구단)의 시행 횟수는 4배가 되지만 카라추바 곱셈법에서는 3배 늘어난다. 이 알고리즘을 확장하여 좀 더 빠르게 개량한 방법으로 [[톰-쿡 곱셈법]], 이보다 더 빠른 방법으로 [[쇤하게-슈트라센 곱셈법]]이 있다. == 아이디어 == 곱하고자 하는 두 수 <math>x, y</math>가 있다. 이를 <math>B</math>진법으로 쓰고, 두 수가 <math>m</math>자리수보다 길다고 가정하자. (즉 <math>x, y \geq B^{m}</math>) 그러면 <math>x=aB^{m}+b, y=cB^{m}+d</math> 꼴로 쓸 수 있고, 두 수를 곱하면 <math>xy=acB^{2m}+(ad+bc)B^{m}+bd</math>가 된다. 이때 양 끝 항의 계수는 직접 곱하고(각 곱셈 2회), 가운데 항의 계수는 전통적 방법으로는 '곱셈 2회+덧셈 1회'를 시행한다. 가령 <math>x=62,y=73</math>일 때 우리는 보통 <math>xy =(6\cdot7)10^2+(6\cdot3+2\cdot7)10+2\cdot3 = 4200+320+6 = 4526</math>과 같은 풀이를 떠올리며 여기서 시행한 구구단 곱셈은 총 4회이다. 그런데 가운데 항의 계수에 대해 곱셈을 1회로 단축하는 방법이 존재한다. 사람이나 컴퓨터나 기본적으로 곱셈보다는 덧셈이 쉬우므로, 덧셈이 좀 늘더라도 곱셈 횟수가 준다면 전체적으로는 시간 상 이득이다. 관계식 <math>(a+c)(b+d) = (ad+bc)+ac+bd</math>을 변형하면 <math>ad+bc = (a+c)(b+d)-(ac+bd)</math>가 된다. 여기서 <math>ac, bd</math>는 앞서 언급했던 "양 끝 항의 계수"와 정확히 같으므로 다시 한 번 셈할 필요는 없고, 실질적으로 추가 곱셈이 필요한 항은 <math>(a+c)(b+d)</math>하나뿐이다. 위의 예시를 다시 들자면, 가장 큰 항과 가장 작은 항의 계수인 42, 6을 먼저 셈하고, 그 다음 <math>6\cdot3+2\cdot7 = (6+2)\cdot(3+7) - (42+6) = 80-48 = 32</math>를 도출하는 것이다. 이렇게 하면 필요한 부분 곱셈은 총 3회가 된다. 물론 여기서 <math>8 \cdot 10</math>은 후자가 다시 두 자리 수가 되지만, 핵심은 부분 곱셈으로 들어갈 때 곱하려는 수의 크기가 줄어든다는 데 있다. 어차피 한 자리 수의 덧셈 결과는 18을 넘지 않는다. <s>혹은 십구십구단 곱셈을 바로 적용하면 된다</s> 전체적인 맥락은 곱할 대상의 자리수를 절반씩 끊고, 각 끊어진 부분을 곱해서 부분 결과를 다시 합하는 것이다. 여기서 부분 곱셈의 크기가 여전히 크다 싶으면 다시 자리수 끊기를 시행하면 된다. == 알고리즘 == *아래는 알고리즘 <math>f(x, y)=xy</math>를 시행하는 방법을 설명한 것이다. #전통적 곱셈을 시행할 기준 크기 <math>A</math>를 정한다. 두 수 중 한 쪽이라도 <math>A</math>보다 작으면, 전통적 방법으로 곱한 값을 반환한다. #곱하고자 하는 두 수를 <math>B</math>진법으로 쓰고, 중 큰 쪽의 자리수를 가늠하고, <math>n</math>자리수임을 확인한다. #두 수를 앞의 <math>\lfloor n/2 \rfloor</math>자리와 뒤의 <math>\lceil n/2 \rceil</math> 자리 꼴로 끊는다. #*즉 <math>x=aX+c, y=bX+d, X=B^{\lceil n/2 \rceil}</math> 꼴의 식으로부터 변수 <math>X, (a, c), (b, d)</math>를 새로 지정한다. #<math>p=f(a, b), r=f(c, d)</math>를 계산한다. #<math>q=f(a+c, b+d)-p-r</math>를 계산한다. #<math>f(x, y)=pX^{2}+qX+r</math>를 반환한다. === 변형 알고리즘 === 항등식 <math>(c-a)(d-b)=ac+bd-(ad+bc)</math>를 이용하면 <math>ad+bc=ac+bd-(c-a)(d-b)</math>와 같이 쓸 수 있다. 이 경우도 마찬가지로 부분곱셈을 3회 시행한다. 상술한 알고리즘의 마지막 세 줄은 아래와 같이 고칠 수 있다. <math>x=aX+c, y=bX+d, X=B^{\lceil n/2 \rceil}</math>임을 참고. #<math>p=f(a, b), r=f(c, d)</math>를 계산한다. #<math>q=p+r-f(c-a, d-b)</math>를 계산한다. #<math>f(x, y)=pX^{2}+qX+r</math>를 반환한다. == 적용 예 == 알고리즘을 적용할 때 [[기수법|몇 진법]]을 기준으로 하느냐에 따라 셈법이 달라진다. 물론 맥락은 모두 동일하다. 아래 예시에서는 사람에게 친숙한 [[십진법]]에서 구구단 곱셈의 시행 횟수를 알아본다. 자릿수를 쪼개다가 특정 항이 10보다 작아질 때 구구단 곱셈을 적용한다. (변형 알고리즘을 기준으로 계산) * 예시: <math>x=3984, y=6752</math> * 두 수의 자릿수를 반으로 각각 쪼갠다: <math>x_1=39, x_2=84, y_1=67, y_2=52, X=10^2</math> * 앞쪽 두 항인 <math>x_1=39, y_1=67</math>의 곱셈을 먼저 셈한다. <ref>물론 이 단계에서 39×67을 직접 셈하는 것이 편할 수 있지만 여기서는 카라추바 곱셈법을 이용한다.</ref> 아래 과정에 따르면 구구단 곱셈 3회, 덧셈·뺄셈 6회 시행한다. 결과는 2613으로, 전통적 곱셈법과 일치한다. ** 두 수를 다시 두 부분으로 각각 쪼갠다: <math>x_{11}=3, x_{12}=9, y_{11}=6, y_{12}=7, X_1=10</math> ** <math>p_1=x_{11}y_{11} =3\cdot6 =18</math> … 구구단 곱셈 1회 ** <math>r_1=x_{12}y_{12} =9\cdot7 =63</math> … 구구단 곱셈 1회 ** <math>(x_{12}-x_{11})(y_{12}-y_{11}) =6\cdot1 =6</math> … 구구단 곱셈 1회, 뺄셈 2회 ** <math>q_1=p_1+r_1-(x_{12}-x_{11})(y_{12}-y_{11}) =18+63-6 =75</math> … 덧셈·뺄셈 2회 ** 따라서 <math>p =x_1y_1 =p_1 X_1^2+q_1 X_1+r_1 =1800+750+63 =2613</math> … 덧셈 2회<ref>여기서 18에 100을 곱하고, 75에 10을 곱하는 단계는 숫자 뒤에 0을 붙이는 것 뿐이므로 실질적 곱셈 횟수에 포함하지 않는다.</ref> * 다음으로 뒤의 두 항인 <math>x_2=84, y_2=52</math>의 곱셈을 시행한다. 바로 위와 같은 방법으로 셈하면 <math>r=4368</math>이 나오고, 마찬가지로 구구단 곱셈 3회, 덧셈·뺄셈 6회를 시행한다. * 그 다음 <math>x_2-x_1=45, y_2-y_1=-15</math> (… 뺄셈 2회)의 곱을 셈한다. 결과는 <math>(x_2-x_1)(y_2-y_1)=-675</math>가 나오고, 여기서 또 구구단 곱셈 3회, 덧셈·뺄셈 6회를 시행한다. * <math>q =p+r-(x_2-x_1)(y_2-y_1) =2613+4368-(-675) =7656</math> … 여기서 덧셈 2회를 추가한다. * 따라서 최종 결과는 <math>xy =pX^2+qX+r =26130000+765600+4368 =26899968</math> … 마지막 덧셈 2회가 더해진다. * 이렇게 해서 우리는 구구단 곱셈 9회, 자리 합성을 위한 덧셈·뺄셈을 24회 시행했다. 물론 중간 과정에서 덧셈이나 뺄셈은 자리수에 따라 계산량이 달라진다. === 전통적 곱셈과 비교 === 앞서 예시로 든 3984×6752를 통상 방법으로 계산한다면 구구단 곱셈을 총 16회 시행해야 한다. 카라추바 곱셈법에서는 9회로 단축되었는데, 계산 과정을 빙빙 돌아서 간 것 치고는 단축 효과가 그리 커 보이지 않을 수 있다. 하지만 수가 커질수록 계산 과정의 길이는 눈에 띄게 차이가 난다. 만약 곱하려는 두 수가 여덟 자리라면 전통적 곱셈법에서는 구구단 곱셈을 64회 써야 하지만 카라추바 곱셈법에서는 27회 쓴다. 그리고 이 횟수의 비는 자릿수가 더 늘어남에 따라 더욱 벌어진다. {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)