카라츠바 알고리즘

카라츠바는 아즈+b와 cz+d(상자)의 곱셈과 1234와 567을 곱한다. 마젠타 화살표는 곱셈을, 황색은 덧셈을, 은색은 뺄셈을, 연청색은 왼쪽 시프트를 나타낸다. (A), (B) 및 (C)는 중간 값을 구하는 데 사용되는 재귀성을 나타낸다.

카라츠바 알고리즘은 빠른 곱셈 알고리즘이다. 1960년 아나톨리 가라쓰바에 의해 발견되어 1962년에 출판되었다.^[1][2][3] 두 개의 n자리 숫자의 곱셈을 최대 $n{\displaystyle {}^{}}$ ${\displaystyle {{\log }_{}}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ ${\displaystyle {}^{\mathrm{}}{}^{}}$ n 1.$[\$ n$^{$2}$3$$}\clog$ $_{1$$.58$}\ 약 n$^1$.58$}$의 한자리 곱셈$$(n이 2의 검정력일 때 정확히$$ n ${\displaystyle {{\log }_{}}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ ${\$ n$^{\}}}$ 따라서 n ${\displaystyle {2\mathrm{}}^{}}$ ${\$개의 한자리$$ 제품을 필요로 하는 기존 알고리즘보다 증상이 없을 정도로 빠르다. 예를 들어 카라츠바 알고리즘은 2개의 1024자리 숫자(n = 1024 = 2¹⁰)를 곱하기 위해 3¹⁰ = 59,049개의 한자리 승수가 필요한 반면, 기존 알고리즘은 (2¹⁰) ²= 1048,576 (속도 17.75배)를 요구한다.

카라추바 알고리즘은 2차 "학년" 알고리즘보다 점증적으로 더 빠른 첫 번째 곱셈 알고리즘이었다. 톰-쿡 알고리즘(1963년)은 카라츠바 방법의 일반화 속도가 더 빠르고, 쇤네-스트라센 알고리즘(1971)은 충분히 큰 n을 위해 더욱 빠르다.

역사

두 개의 n자리 숫자를 곱하기 위한 표준 절차는 큰 O 표기법으로 n$$ $2{\displaystyle {}^{}}$ $displaystyle n^{2}\,\!}$또는 $O{\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) $displaystyle O(n^{2}\,\!})$에 비례하는 다수의 초등 연산을 요구한다. 안드레이 콜모고로프는 전통적인 알고리즘이 무증상 최적이었다고 추측했는데, 이는 그 작업에 대한 알고리즘에는 $\Omega {\displaystyle \mathrm{}}$ (${\displaystyle {}^{}{2\mathrm{}}^{}}$) $displaystyle \Oomega (n^{2}\,\!})$의 초등$$ 연산이 필요하다는 것을 의미한다.

1960년, 콜모고로프는 모스크바 주립대학에서 사이버네틱스의 수학 문제에 관한 세미나를 조직하였는데, 거기서 $그$는${\displaystyle {}^{}}$ (${\displaystyle {n\mathrm{}}^{}}$ 2 ${\displaystyle {}^{}}$ $디스플레이스타일 \Oomega (n$^{2$}\,\!}}$ 추측과$$ 기타 계산 복잡성의 문제를 기술하였다. 1주일 만에 당시 23세의 학생이었던 가라쓰바는 $O{\displaystyle ({\mathrm{n}}^{}}$ ${\displaystyle {{\log }_{}}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ 3$){\displaystyle O(n^{\log _{2}3})$의 초등 스텝에서 두 개의 n자리 숫자를 곱한 알고리즘(이하 "divide and concer"라 함)을 발견해 추측을 반증했다. 콜모고로프는 이 발견에 매우 흥분했다. 그는 그 다음 회의 때 그것을 전달했고, 그 후 종료되었다. 콜모고로프는 전 세계 학회에서 카라츠바 결과에 대해 일부 강의(예: "1962년 국제 수학자 대회 진행", 페이지 351–356 참조), 또한 "1962년 스톡홀름 국제 수학자 대회에서 행한 6개 강의"를 실시하여 1962년 미국 학술회의에 그 방법을 발표하였다.SSR 과학 아카데미. 이 기사는 콜모고로프가 썼으며, 카라츠바의 알고리즘과 유리 오브만의 별도 결과라는 두 가지 곱셈 결과를 담고 있었다. 가라쓰바와 유. 작가로서 "Ofman"이다. 카라츠바는 출판사로부터 재인쇄를 받았을 때 비로소 그 논문을 알게 되었다.^[2]

알고리즘.

기본 단계

카라츠바 알고리즘의 기본 단계는 두 개의 큰 $숫자{\displaystyle }$ x$[\displaystyle x$$}$와 y$[\displaystyle y}$의 곱셈을 사용하여$$ 산출물을 계산할 수 있는 공식으로, 각각 $x{\displaystyle }${\$displaystyle$x} $또는{\displaystyle }$y {\$displaysty y$의 약 절반의 숫자와 약간의 추가 및 자릿수를 가진다. 교대. 이 기본 단계는 사실 이와 유사한 복잡한 곱셈 알고리즘의 일반화인데, 여기서 상상 단위 I는 기지의 힘으로 대체된다.

$x{\displaystyle }$ {\$displaystyle$ x}$$$및$ y ${\$$displaystyle y$$}$을(를) 일부 $기본{\displaystyle }$ B$${\$displaystyle$B}에서$$n ${\$displaystyle n}$$-자리$$ 문자열로 표시하십시오$.$ n ${\displaystyle n}$보다 작은$$ 양의 정수 $m{\displaystyle }$ ${\displaysty$ m$\}$의 경우, 주어진 두 숫자를 다음과 같이 쓸 수 있다.

${\displaystyle x=x_{1}}B^{m}+x_{0}}}$

${\displaystyle y=y_{1}B^{m}+y_{0}}$

여기서 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 및 y$$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은(는) ${\displaystyle {Bm}^{}}$ ${\$ B$^{m}$보다 작다$$$.$ 그 제품은 그 때 입니다.

${\displaystyle {\begin}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{1}B^{m}+y_{0}\&=z_{2}B^{2m}+z_{1)}}B^{m}+z_{0},\\\end{arged}}}$

어디에

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

이 공식은 4개의 승수를 필요로 하며 찰스 배비지에게 알려져 있다.^[4] 카라츠바는 x ${\displaystyle y}$ ${\displaystyle xy}$을(를) 몇 번의 추가 비용을 들여 세 번의 곱으로만 계산할 수 있다고$$ 관찰했다. $z{\displaystyle {}_{}}$ ${\$과(${\displaystyle {와\mathrm{}}_{}}$)$$z 2 {\$displaystyle$ z_${2}}:$ 사전 관찰할 수 있는 것과 같이$$ 사용

${\displaystyle z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.}$

발생하는 문제 그러나}z1{\displaystyle z_{1}컴퓨팅은(x1+x0){\displaystyle(x_{1}+x_{0})}과(y1+y0){\displaystyle(y_{1}+y_{0})}위의 계산 플로가 발생할 수 있는 범위에서 B인류≤ 결과<>2Bm{\displays 결과 만들 것입니다.tyl$e B^{m}\leq {\text{result}<2B^{m}}$ )). 이는 다음과 같은 점에 유의함으로써 피할 수 있다.

${\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}$

$({\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (x_{0}-x_{1}}$ 및${\displaystyle }$(${\displaystyle {y\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$- ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (y_{1}-y_{0}}}$의 계산은 - < < ${\$의 결과를 산출한다$$. 이 방법은 부호를 인코딩하는 데 1개의 추가 비트가 필요한 음수를 생성할 수 있으며, 여전히 승수를 위해 1개의 추가 비트가 필요하다. 그러나 이를 피하는 한 가지 방법은 부호를 기록한 다음 $({\displaystyle {x\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (x_{0}-x_{1}}}$ 및$$${\displaystyle }$( ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$- ${\displaystyle {y\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$) ${\displaystyle (y_{1}-y_{0})$의 절대값을 사용하여$$ 서명되지 않은 곱을 수행하고, 이후 두 부호가 원래 다를 때 결과가 부정될 수 있다. 또 다른 장점은${\displaystyle }$(${\displaystyle {x\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$- ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle ({y\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$- ${\displaystyle {y\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle (x_{0}-x_{1}(y_{1}-y_{0})$이 음수일 수 있지만$$, $z{\displaystyle {}_{}}$ 1 ${\$1}}{$0}}$의 최종 계산은 추가 사항만$$ 포함한다는 것이다.

예

12345와 6789의 곱(여기서 B = 10)을 계산하려면 m = 3을 선택하십시오. 다음과 같이 결과 베이스(B^m = 1000)를 사용하여 입력 피연산자를 분해하는 데 m 오른쪽 교대조(m right shift)를 사용한다.

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

세 가지 부분 결과를 계산하는 데 사용되는 세 가지 배율만 더 작은 정수에 작용한다.

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) - z₂₀ = 357 × 795 - 72 - 272205 = 283815 - 72 - 272205 = 11538

우리는 단지 이 세 가지 부분적인 결과를 추가하고 그에 따라 이동함으로써 결과를 얻는다. (그리고 나서 이 세 가지 입력을 입력 피연산자와 마찬가지로 베이스 1000으로 분해함으로써 이행을 고려한다.)

결과 = z₂ · (B^m)² + z₁ · (B^m)¹ + z · (B₀^m),⁰ 즉,

결과 = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

중간 세 번째 곱셈은 두 개의 첫 번째 곱셈보다 두 배 작은 입력 영역에서 작동하며, 그 출력 영역은 네 배 미만이며, 처음 두 곱셈에서 계산된 베이스-1000 운반은 이 두 가지 오차를 계산할 때 반드시 고려되어야 한다.

재귀적용

n이 4개 이상이면 카라츠바의 기본 단계에서 3개의 승수는 0자리 미만의 피연산자를 포함한다. 따라서 이러한 제품은 카라츠바 알고리즘의 재귀적 호출을 통해 계산할 수 있다. 재귀는 숫자가 너무 작아서 직접 계산할 수 있을 때까지(또는 반드시) 적용할 수 있다.

예를 들어 32비트 곱하기 32비트인 컴퓨터에서는 B = 2³¹ = 2147483648을 선택하고 각 숫자를 별도의 32비트 이진 워드로 저장할 수 있다. 그러면 합계 x₁ + x₀ 및 y + y는₁₀ 이월 숫자를 저장하는 데 별도의 이진 단어가 필요하지 않으며(이월 저장 추가에서와 같음), 카라츠바 재귀성은 곱할 숫자가 한 자릿수 길이에 불과할 때까지 적용할 수 있다.

비대칭 카라츠바 유사공식

카라추바의 원래 공식과 다른 일반화들은 그 자체로 대칭적이다. 예를 들어, 다음 공식은 계산한다.

${\displaystyle c(x)=c_{4}x^{4}+c_{3}x^{3}+c_{2}x^{2}+c_{1}x+c_{0}=a(x)b(x)=(a_{2}x^{2}+a_{1)}x+a_{0})(b_{2}x^{2}+b_{1)}x+b_{0}}}$

${\displaystyle \text{GF}}$( ${\displaystyle 2}$)${\displaystyle }$[ ${\displaystyle x}$ ${\displaystyle ]}$ ${\displaystyle {\text{$$GF}(2)[$${\displaystyle \mathrm{x}}$$]\},$ 여기서 ${\displaystyle \text{GF}}$( 2${\displaystyle }$) ${\displaystyle {\text{$$GF}}(2)$은 0과 1의 두 원소를 가진 갈루아 필드다.

${\displaystyle {\begin{aligned}\left\{{\begin{array}{l}c_{0}=p_{0},\\c_{1}=p_{012}+p_{02}+p_{12}+p_{2},\\c_{2}=p_{012}+p_{01}+p_{12},\\c_{3}=p_{012}+p_{01}+p_{02}+p_{0},\\c_{4}=p_{2},\end{array}}\right.\end{정렬}}}$

where ${\displaystyle p_{i}=a_{i}b_{i},\ \ p_{ij}=(a_{i}+a_{j})(b_{i}+b_{j})}$ and ${\displaystyle p_{ijk}=(a_{i}+a_{j}+a_{k})(b_{i}+b_{j}+b_{k})}$. We note that addition and 뺄셈은 특성 2의 분야에서 동일하다.

$이{\displaystyle }$ 공식은 대칭적이다$.$ $즉{\displaystyle }$$,$ ${\displaystyle p_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle p{}_{}}$ ${\displaystyle i_{}}$ {\$displaystyle$ $p_{i},$ p$i$ j {\$displaystyle$ $p_${$ij},$ p$$ ${\displaystyle i_{}}$ j {\displaystyle $p_{ij$}, p $ij$ k {\displaystystyle p_${$ijk$\}.$

제2차 일반화 분할 알고리즘에 기초하여 팬 등은 다음과 같은 비대칭 공식을 찾아냈다.^[5]

${\displaystyle {\pregated}\왼쪽\{\\nfg{array}{l}c_{0}=p_{0}\c_{1}=p_{012}+p_{2}+m_{4}+m_{5}}\\c_{2}=p_{012}+m_{3}+m_{5}\\c_{3}=p_{012}+p_{0}+m_{3}+m_{4}\\c_{4}=p_{2},\end{array}\오른쪽.\end{정렬}}}$

where ${\displaystyle m_{3}=(a_{1}+a_{2})(b_{0}+b_{2}),\ \ m_{4}=(a_{0}+a_{1})(b_{1}+b_{2})}$ and ${\displaystyle m_{5}=(a_{0}+a_{2})(b_{0}+b_{1})}$.

m ${\displaystyle {3\mathrm{}}_{}}$,${\displaystyle {}_{}m{}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$},$\m_{4},$ m$$ ${\displaystyle {5\mathrm{}}_{}}$ ${\$에 $있는{\displaystyle }${\displaystyle $a}$ 및 $b$ {\$displaystytle b}$를 교환하면 다음과 같은 새로운 공식을 얻을 수 있기 때문에 비대칭이다$.$

${\displaystyle {\pregated}\왼쪽\{\\nfg{array}{l}c_{0}=p_{0}\c_{1}=p_{012}+p_{2}+m_{4}+m_{5}}\\c_{2}=p_{012}+m_{3}+m_{5}\\c_{3}=p_{012}+p_{0}+m_{3}+m_{4}\\c_{4}=p_{2},\end{array}\오른쪽.\end{정렬}}}$

where ${\displaystyle m_{3}=(a_{0}+a_{2})(b_{1}+b_{2}),\ \ m_{4}=(a_{1}+a_{2})(b_{0}+b_{1})}$ and ${\displaystyle m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})}$.

시간 복잡도 분석

카라추바의 기본 단계는 어떤 베이스 B와 어떤 m에도 효과가 있지만, 재귀 알고리즘은 m이 반올림된 n/2와 같을 때 가장 효율적이다. 특히, 일부 정수 k에 대해 n이 2이고^k, n이 1일 때만 재귀가 멈춘다면, 한 자릿수 승수의 수는^k 3으로, 여기서^c c = log3이다₂.

길이가 2의 검정력이 될 때까지 숫자가 0인 입력을 확장할 수 있기 때문에, n에 대한 기본 승수의 수는 최대 $3{\displaystyle {\mathrm{}}^{}}$⌈ ${\displaystyle {{\mathrm{로그}}_{}}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ 3 ${\displaystyle {}^{}}$ ${\displaystyle {{\mathrm{로그}}_{}}^{}}$ ${\displaystyle 2^{}}$ ${\displaystyle {{}_{}}^{}}$ 3 ⁡ 3${\displaystyle {}^{}}$⁡ 3 {\$displaystyle 3^{$2}n$\rceil ^}}}\leq 3n^{log _{2}3$

카라츠바의 기본 단계에서 추가, 축소, 자릿수 이동(B의 힘에 의한 다중통신)은 n에 비례하여 시간이 걸리기 때문에 n이 증가하면 그 비용은 무시할 수 있다. 더 정확히 말하면, t(n)가 두 개의 n자리 숫자를 곱할 때 알고리즘이 수행하는 총 기본 연산 수를 나타낸다면,

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

일부 상수 c와 d에 대해. 이러한 재발관계의 경우, 분할과 재무 재발을 위한 마스터 정리는 점근성 결합 $T{\displaystyle }$( n${\displaystyle }$)${\displaystyle }$= ${\displaystyle \mathrm{\theta }}$(${\displaystyle {}^{}}$ ${\displaystyle {{\log }_{}}^{}}$ ${\displaystyle {{2\mathrm{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{}}$ $displaystyle T(n)=$를 부여한다.$\theta (n^{\log _{2}3}\,\!}$.

그것은 카라츠바의 알고리즘이 충분히 큰 n에 대해, 비록 그것의 기본 단계가 단순한 공식보다 더 많은 추가와 이동을 사용하지만, 긴 손 곱셈보다 적은 수의 교대조 및 한 자리 수의 추가 작업을 수행할 것이라는 것을 따른다. 그러나 n의 작은 값에 대해서는 추가 이동 및 추가 작업을 수행하면 장기 방법보다 실행 속도가 느려질 수 있다. 플러스 수익의 포인트는 컴퓨터 플랫폼과 맥락에 따라 달라진다. 경험에 비추어 볼 때, 카라츠바의 방법은 일반적으로 승수가 320-640비트보다 길면 더 빠르다.^[6]

가성음

여기 이 알고리즘에 대한 유사코드가 있는데, 베이스 10에 표시된 숫자를 사용한다. 정수의 이진 표현에 대해서는, 10의 어느 곳이나 2로 교체하는 것으로 충분하다.^[7]

split_at 함수의 두 번째 인수는 오른쪽에서 추출할 자릿수를 지정한다. 예를 들어, split_at("12345", 3)는 세 개의 최종 숫자를 추출하여 high="12", low="345"를 부여한다.

기능을 하다 가라쓰바 (num1, num2)     만일 (num1 < 10) 또는 (num2 < 10)         돌아오다 num1 × num2 /* 전통적인 곱셈으로 돌아가기 */          /* 숫자의 크기를 계산한다. */     m = 분 (size_base10(num1), size_base10(num2))     m2 = 마루를 깔다 (m / 2)      /* m2 = ceil (m / 2)도 효과가 있을 것이다 */          /* 숫자 시퀀스를 가운데로 분할한다. */     하이원, low1 = split_at (num1, m2)     하이투, low2 = split_at (num2, m2)          /* 크기의 대략 절반에 해당하는 숫자에 대해 3번의 재귀 호출이 이루어졌다. */     z0 = 가라쓰바 (low1, low2)     z1 = 가라쓰바 (low1 + 하이원, low2 + 하이투)     z2 = 가라쓰바 (하이원, 하이투)          돌아오다 (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0 

참조

외부 링크

• 가라쓰바의 다항식 곱셈 알고리즘
• Weisstein, Eric W. "Karatsuba Multiplication". MathWorld.
• Bernstein, D. J. "수학자들을 위한 멀티디깃 곱하기" 카라츠바와 많은 다른 곱셈 알고리즘을 다룬다.