로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''톰-쿡 곱셈법'''(Toom-Cook multiplication method)은 큰 정수의 곱을 바르게 셈하는 알고리즘이다. 1963년 안드레이 톰(Andrei Toom)이 처음 구상하고 1966년 스티븐 쿡(Stephen Cook)이 알고리즘을 발전 및 구체화하였다. 이 곱셈법은 n자리 수의 곱셈에 대해 시간복잡도가 <math>O(n^{\log_{3}5})\approx O(n^{1.465})</math>로 표현된다. 전통적인 곱셈법이 <math>O(n^{2})</math>에 비례하는 시간이 걸리는 걸 비교하면 시간을 상당히 단축할 수 있으며, 큰 수에서는 [[카라추바 곱셈법]]보다도 더 빨라진다. 물론 매우 큰 수에서는 [[쇤하게-슈트라센 곱셈법]]이 시간이 덜 걸린다. == 아이디어 == 어떤 큰 수 <math>M=m_2 B^2+m_1 B+m_0, N=n_2 B^2+n_1B+n_0</math>의 곱셈을 시행하려고 한다. 여기서 <math>B</math>는 자릿수를 끊기 위한 상수로, 십진법에서는 10의 거듭제곱이라 할 수 있다. 그리고 각 항의 계수는 <math>0 \leq m_0, m_1, \cdots , n_2 < B</math>이다. 이 다항식 모양을 유지하면서 곱하면 <math>MN=r_4 B^4 + r_3 B^3 + r_2 B^2 + r_1 B + r_0, 0 \leq r_0, r_1 \cdots r_4 < B^2 </math>형태로 쓸 수 있다. 그러면 각 항의 계수를 구할 차례인데, 계수는 <math>m_0, m_1, \cdots , n_2 \rightarrow r_0, r_1 \cdots r_4</math>로 대응하는 어떤 함수로 주어질 것이다. 여기서 두 수를 직접 곱하는 대신 '''수의 절댓값을 줄여서''' 곱셈이 쉬운 형태로 변형하고, 구하고 싶은 계수를 거꾸로 미정계수법으로 구하는 것이 이 곱셈법의 기본 흐름이다. 구체적으로는 아래와 같다. 먼저 두어진 두 수에 대응하는 다항식을 각각 세운다. 여기서는 이차식으로 설정한다. <math>f(x)=m_2 x^2+m_1 x+m_0, g(x)=n_2 x^2+n_1 x+n_0</math> 두 다항식의 계수는 우리가 알고 있는 값이다. 그 다음 구하고 싶은 다항식 <math>h(x)=f(x)g(x)=r_4 x^4+r_3 x^3+r_2 x^2+r_1 x+r_0</math>을 세우고, 이 다항식의 계수가 우리가 찾으려는 값이다. 그러면 <math>M=f(B), N=g(B), MN=h(B)</math>가 성립한다. 전통적인 곱셈법대로면 <math>\begin{cases} r_4=m_2 n_2, r_0=m_0 n_0 \\ r_3=m_1 n_2 + m_2 n_1, r_1=m_0 n_1 + m_1 n_0 \\ r_2= m_0 n_2 + m_1 n_1 + m_2 n_0 \end{cases}</math>을 각각 계산한다. 다시 말해 두 수의 자릿수를 세 블록으로 각각 쪼개서 곱하고자 한다면 부분 곱셈을 9회 시행해야 한다. 하지만 톰-쿡 방식에서는 부분 곱셈을 5회로 단축할 수 있다. === 부분 곱셈 === 먼저 절댓값이 작은 부분 곱셈을 다섯 개, 즉 <math>h(x)</math>의 미정계수의 개수만큼 상정한다. * <math>\begin{cases} h(0)=f(0)g(0)=m_2 n_2 \\ h(1)=f(1)g(1)=(m_2+m_1+m_0)(n_2+n_1+n_0) \\ h(-1)=f(-1)g(-1)=(m_2-m_1+m_0)(n_2-n_1+n_0) \\ h(-2)=f(-2)g(-2)=(4m_2-2m_1+m_0)(4n_2-2n_1+n_0) \\ h(\infty)=f(\infty)g(\infty)=m_2 n_2 \end{cases}</math> 여기서 무한대를 대입한 식은 엄밀히는 <math>\lim_{x \to \infty}\frac{h(x)}{x^4}=\lim_{x \to \infty}\frac{f(x)}{x^2} \cdot \lim_{x \to \infty}\frac{g(x)}{x^2}</math>로, 각 다항식의 '''최고차항의 계수'''를 의미한다. 여기서는 표기 편의상 무한대 표시로 적는다. === 다항식 구하기 === 그 다음 아래와 같이 미지수가 다섯 개인 연립일차방정식을 세울 수 있다. 좌변은 미지수의 일차 결합이고, 우변은 바로 위에서 구한 정보이다. * <math>\begin{cases} r_0=h(0) \\ r_0 + r_1 + r_2 + r_3 + r_4=h(1) \\ r_0 - r_1 + r_2 - r_3 + r_4=h(-1) \\ r_0 -2 r_1 +4 r_2 -8 r_3 +16 r_4=h(-2) \\ r_4=h(\infty) \end{cases}</math> 이 방정식을 직접 풀어서 <math>h(x)</math>를 도출할 수도 있지만, [[보간법]]을 이용하면 좀 더 편리하게 해를 도출할 수 있다. <math>\begin{align}h(x) &= \frac{h(1)}{6}x(x+1)(x+2) - \frac{h(0)}{2}(x-1)(x+1)(x+2) + \frac{h(-1)}{2}(x-1)x(x+2) \\ &- \frac{h(-2)}{6}(x-1)x(x+1) + h(\infty)(x-1)x(x+1)(x+2)\end{align}</math> 이 식을 전개해서 <math>h(x)=r_4 x^4+r_3 x^3+r_2 x^2+r_1 x+r_0</math>와 계수를 대조하면, 아래와 같이 행렬로 표현할 수 있다. <math>\begin{pmatrix}1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & -2 & 4 & -8 & 16 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4 \end{pmatrix} = \begin{pmatrix} h(0) \\ h(1) \\ h(-1) \\ h(-2) \\ h(\infty) \end{pmatrix} \Leftrightarrow \begin{pmatrix} r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4 \end{pmatrix} = \begin{pmatrix}1 & 0 & 0 & 0 & 0 \\ 1/2 & 1/3 & -1 & 1/6 & -2 \\ -1 & 1/2 & 1/2 & 0 & -1 \\ -1/2 & 1/6 & 1/2 & -1/6 & 2 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} h(0) \\ h(1) \\ h(-1) \\ h(-2) \\ h(\infty) \end{pmatrix}</math> 위 등식에 나온 두 5×5 행렬은 서로 역행렬 관계다. 오른쪽 식의 행렬은 이 알고리즘을 위해 사전에 지정해둔다. 행렬 내 성분 중 정수가 아닌 것도 있지만 실제로 해를 구하면 결과는 언제나 정수다. 해를 구하는 공식은 아래와 같이 쓸 수도 있다. <math>\begin{cases} \displaystyle r_0=h(0), r_4=h(\infty), s=\frac{h(-2)-h(1)}{3} \\ \displaystyle r_1=\frac{h(1)+r_0+s}{2}-h(-1)-2r_4, r_2=\frac{h(1)+h(-1)}{2}-r_0-r_4, r_3=\frac{h(-1)-r_0-s}{2}+2r_4\end{cases}</math> (★) 이렇게 계수들을 구하면 <math>h(x)</math>를 알게 되고, 여기에 <math>x=B</math>를 대입하면 원래 구하려던 곱셈 결과를 얻는다. ※ 참고: 여기서 말하는 부분 곱셈은 (큰 수)×(큰 수) 꼴의 곱셈만을 가리킨다. 위에서 추가로 행하는 (큰 수)×(2, 4, 1/2, 1/3)과 같이 작은 수를 곱하거나 나누는 행위는 컴퓨터 입장에서는 연산량이 많지 않으므로 실질적인 곱셈 횟수에 포함하지 않는다. == 알고리즘 == 이상의 접근 방법을 알고리즘으로 구성하면 아래와 같다. * 곱하고자 하는 두 수를 입력 받는다. <math>(M>N)</math> * 두 수의 자릿수를 비교하고, 큰 쪽의 자릿수를 3으로 나눈 값을 올림한다: <math>B=b^a, a=\left \lceil \frac{\log_{b}M}{3} \right \rceil, b: \text{ base}</math> * <math>m_2=M/B^2, m_1=(M/B)\%B, m_0=M\%B^2</math>의 값을 지정한다. 여기서 /는 몫을 구하는 나눗셈이고(나머지 제외), %는 나머지 연산이다. 마찬가지로 <math>n_2=N/B^2, n_1=(N/B)\%B, n_0=N\%B^2</math>의 값도 지정한다. * <math>\begin{cases} f(1)=m_2+m_1+m_0, f(-1)=m_2-m_1+m_0, f(-2)=2(2m_2-m_1)+m_0\\ g(1)=n_2+n_1+n_0, g(-1)=n_2-n_1+n_0, g(-2)=2(2n_2-n_1)+n_0 \end{cases}</math>을 셈한다. * <math>r_0=m_0 n_0, r_4=m_2 n_2, h(1)=f(1)g(1), h(-1)=f(-1)g(-1), h(-2)=f(-2)g(-2)</math>를 각각 셈한다. * 위 문단에 (★) 표시된 공식을 이용하여 <math>r_1, r_2, r_3</math>을 셈한다. * <math>r_4</math>를 <math>B</math>자리씩 왼쪽으로 민 다음 <math>r_3</math>를 더한다. 그리고 이렇게 '자리 밀고 항 더하기'를 <math>r_2, r_1, r_0</math> 순으로 이어서 시행하면 원하는 결과가 나온다. == 적용 예 == <math>M=21175008\ 6137468590\ 0115997983, N=166\ 6465230783\ 3393568241</math>의 곱을 십진법 상에서 구해보자. (편의상 열 자리씩 띄어씀) * 큰 쪽인 <math>M</math>은 28자리이므로 <math>B=10^{10}</math>으로 둔다. * 열 자리씩 블록을 나누면 <math>\begin{cases} m_2=21175008, m_1=6137468590, m_0=115997983 \\ n_2=166, n_1=6465230783, n_0=3393568241 \end{cases}</math> * <math>f(1)=6274641581, f(-1)=-6000295599, f(-2)=-1\ 2074239165</math> * <math>g(1)=9858799190, g(-1)=-3071662376, g(-2)=-9536892661</math> * 이제 부분 곱셈을 셈할 차례인데, 각 곱셈을 다시 톰-쿡 방식으로 시행할 수도 있다. 여기서는 부분 곱셈의 결과만을 적는다. ** <math>r_0=39364707\ 1128857903, r_4=3515051328</math> ** <math>h(1)=6186043133\ 6303119390, h(-1)=1843088223\ 6326683224, h(-2)=1\ 1515072287\ 9847268065</math> * 그 다음 (★) 표시된 공식을 적용하면 ** <math>s=1776343051\ 4514716225, r_1= 2157787221\ 7616560879, r_2=3975200971\ 1670992076, r_3=13690233\ 2371657204</math> * 구한 계수들을 바탕으로 자리 밀기와 덧셈을 시행한다. ** <math>r_4B=3515051328\ 0000000000</math> ** <math>r_4B+r_3=3528741561\ 2371657204</math> ** <math>r_4B^2+r_3B=3528741561\ 2371657204\ 0000000000</math> ** <math>r_4B^2+r_3B+r_2=3528741561\ 6346858175\ 1670992076</math> ** 같은 방법으로 시행하면 ** <math>r_4B^3+r_3B^2+r_2B+r_1=3528741561\ 6346858175\ 3828779297\ 7616560879</math> ** <math>r_4B^4+r_3B^3+r_2B^2+r_1B+r_0=3528741561\ 6346858175\ 3828779297\ 7655925586\ 1128857903</math> 따라서 마지막에 써진 값이 바로 구하고자 하던 최종 곱셈 결과이며, 전통적 방법으로 직접 곱한 결과와 일치함을 알 수 있다. == 알고리즘의 변형 == 위의 적용 예와 같이 두 수 중 큰 쪽이 대략 <math>3B</math>자리이고 작은 쪽은 <math>2B</math>자리 이상일 때, 자릿수를 세 블록으로 쪼개고 <math>f(x), g(x)</math>를 각각 이차식으로 표현하고 부분 곱셈을 합성하여 구할 수 있다. 그런데 만약 작은 쪽이 큰 쪽보다 한참 짧을 때, 즉 <math>n_2=0</math>이면 <math>h(x)</math>는 3차 이하 다항식으로, 미정계수는 4개 이하로 줄어든다. 이 경우 앞서 살펴본 풀이를 좀 더 간소화할 수 있다. 작은 쪽이 <math>B</math>자리 이하이면 큰 수와 작은 수는 각각 이차식과 상수항으로 표현된다. <math>f(x)=m_2 x^2+m_1 x+m_0, g(x)=n_0</math> 그러면 <math>h(x)</math>는 <math>f(x)</math>의 각 항의 계수에 <math>n_0</math>를 곱하기만 하면 된다. 사실상 <math>h(x)</math>의 미정계수를 구하는 과정은 따로 필요하지 않다. 만약 작은 쪽이 중간 크기, 즉 <math>2B</math> 자리 이하이면 <math>f(x)=m_2 x^2+m_1 x+m_0, g(x)=n_1x+n_0</math>와 같이 세우고, <math>h(x)=r_3 x^3+r_2 x^2+r_1 x+r_0</math>라 하면 구하려는 미지수는 4개가 된다. 그러면 조건식도 4개 구하면 되고, <math>\begin{cases} h(0)=f(0)g(0)=m_0 n_0, h(\infty)=f(\infty)g(\infty)=m_2 n_1\\ h(1)=f(1)g(1)=(m_2+m_1+m_0)(n_1+n_0)\\ h(-1)=f(-1)g(-1)=(m_2-m_1+m_0)(-n_1+n_0) \end{cases}</math>을 시행한다. 그 다음 보간법으로 <math>h(x)=\frac{h(1)}{2}x(x+1)-h(0)(x-1)(x+1)+\frac{h(-1)}{2}(x-1)x+h(\infty)(x-1)x(x+1)</math>을 유도하고 식을 전개하면 아래 관계식을 얻는다. <math>\begin{pmatrix}1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \\ r_2 \\ r_3 \end{pmatrix} = \begin{pmatrix} h(0) \\ h(1) \\ h(-1) \\ h(\infty) \end{pmatrix} \Leftrightarrow \begin{pmatrix} r_0 \\ r_1 \\ r_2 \\ r_3 \end{pmatrix} = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1/2 & -1/2 & -1 \\ -1 & 1/2 & 1/2 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} h(0) \\ h(1) \\ h(-1) \\ h(\infty) \end{pmatrix}</math> 만약 두 수에 대응하는 다항식을 각각 일차식으로 만들고, 같은 방법으로 <math>h(x)=r_2 x^2+r_1 x+r_0=f(x)g(x)=(m_1 x+m_0)(n_1 x+n_0)</math> 식을 세우면 [[카라추바 곱셈법]]이 된다. <math>\begin{pmatrix}1 & 0 & 0 \\ 1 & -1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \\ r_2 \end{pmatrix} = \begin{pmatrix} h(0) \\ h(-1) \\ h(\infty) \end{pmatrix} \Leftrightarrow \begin{pmatrix} r_0 \\ r_1 \\ r_2 \end{pmatrix} = \begin{pmatrix}1 & 0 & 0 \\ 1 & -1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} h(0) \\ h(-1) \\ h(\infty) \end{pmatrix}</math> 그렇다면 다항식의 차수를 올리고 블록을 더 잘게 쪼개면 곱셈 연산량을 더 줄일 수 있지 않을까? 가령 계수가 각각 4개인 [삼차식]×[삼차식] 꼴을 세우고 미정계수가 7개인 [육차식]을 상정하면, 두 수를 각각 네 블록으로 쪼개서 계수는 더 작아지고 부분 곱셈은 16회에서 7회로 단축한다. 물론 이렇게 접근해서 알고리즘을 새로 짤 수는 있지만, 곱셈 대상이 충분히 크지 않으면 미정계수 구하기를 비롯한 보조 연산량이 많아져서 효율은 오히려 떨어질 수 있다. 또한 아주 큰 수에 대해서는 [[쇤하겐-슈트라센 곱셈법]]과 같은 좀 더 효율적인 알고리즘이 있다. 즉 위에서 소개한 이차식 기준 알고리즘이 톰-쿡 곱셈법의 기본형이라 할 수 있다. {{각주}} {{수론 알고리즘}} [[분류:알고리즘]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 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 (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수론 알고리즘 (편집) 틀:틀바 (원본 보기) (준보호됨)