텀-쿡 곱하기

때로는 톰-3로 알려져 있는 톰-쿡은 복잡성이 낮은 새로운 알고리즘을 도입한 안드레이 톰과 그에 대한 설명을 청소한 스티븐 쿡의 이름을 따서 이름이 붙여진 것으로, 큰 정수를 위한 곱셈 알고리즘이다.

toom-Cook은 a와 b라는 두 개의 큰 정수를 주어 a와 b를 각각 길이 l의 작은 부분으로 나누고 부품에 대한 연산을 수행한다.k가 커지면 많은 곱셈 하위 연산들을 결합하여 알고리즘의 전체적인 복잡성을 줄일 수 있다.그런 다음 Toom-Cook 곱하기 등을 사용하여 곱하기 하위 연산들을 반복적으로 계산할 수 있다."Toom-3"와 "Toom-Cook"이라는 용어는 때때로 잘못 사용되지만, Toom-3는 Toom-Cook 알고리즘의 단일 인스턴스일 뿐이다. 여기서 k = 3.

Toom-3은 9배의 승수를 5로 줄이고, ((n^{log(5)/log(3)}) ≈(n)에서 운행한다^1.46.일반적으로 Toom-k는 θ(c(k) n에서^e 실행되는데, 여기서 e = log(2k - 1) / log(k)는 하위^e 곱셈에 소비되는 시간이며, c는 작은 상수에 의한 덧셈과 곱셈에 소비되는 시간이다.^[1]가라쓰바 알고리즘은 툼-쿡의 특수한 경우로, 숫자가 두 개의 작은 것으로 나누어진다.4배수를 3배로 줄여 θ(n^{log(3)/log(2)}) ≈(n) n(n^1.58)에서 동작)한다.일반적인 긴 곱셈은 Toom-1과 동일하며 복잡성은 complexity(n²)이다.

지수 e는 k를 증가시켜 임의로 1에 가깝게 설정할 수 있지만 c함수는 불행히도 매우 빠르게 성장한다.^[1]^[2]텀-쿡 혼합형 계획의 성장률은 2005년의 공개 연구 문제였다.^[3]Donald Knuth가 설명한 구현은 시간 복잡성 $complexity(n \sqrt 2 log n$ 2 $log$ $n)$ 을 달성한다 $.$ ^[4]

Toom-Cook은 오버헤드 때문에 숫자가 작은 긴 곱셈보다 속도가 느리며, 따라서 점증적으로 빠른 Schönhage-Strassen 알고리즘(복잡성 θ(n log n log n)이 실용화되기 전에 일반적으로 중간 크기의 곱셈에 사용된다.

톰은 1963년 이 알고리즘을 처음 설명했고, 쿡은 1966년 박사학위 논문에서 개선된 (비수학적으로 동등한) 알고리즘을 발표했다.^[5]

세부 사항

이 절에서는 주어진 k 값에 대해 Toom-k를 수행하는 방법을 정확하게 논의하고, Marco Bodrato가 설명한 Toom-Cook 다항식 곱셈에 대한 설명을 단순화한 것이다.^[6]알고리즘에는 다음과 같은 5가지 주요 단계가 있다.

일반적인 큰 정수 구현에서, 각 정수는 위치 표기법에서 자릿수 순서에 따라 표시되며, 기본 또는 라디스는 일부 (일반적으로 큰) 값 b로 설정된다. 이 예에서 우리는 b = 10000을 사용하므로 각 자릿수는 4개의 소수 자릿수 집단에 해당된다(컴퓨터 구현에서 b는 일반적으로 2 instant의 검정력이 된다).ead). 곱하는 두 정수는 다음과 같다.

m	=	12	3456	7890	1234	5678	9012
n	=	9	8765	4321	9876	5432	1098.

이것들은 보통 톰-쿡으로 처리되는 것보다 훨씬 작지만, 알고리즘을 설명하는 역할을 할 것이다.

쪼개기

첫 번째 단계는 기준 B = b를ⁱ 선택하는 것으로, 기준 B의 m과 n 모두 자릿수가 최대 k(예: Toom-3의 3개)가 되도록 한다.i에 대한 일반적인 선택은 다음과 같다.

i=\max \왼쪽\{\floor \floor \frac \\floor \{b}m\right\loor }\floor }{b}n\right\loor }{k\ploor \loor \loor \loor \loor \loor \loor \loor \{k\loor \loor \loor \loor \lo

이 예에서는 Toom-3를 할 예정이므로 B = b = 10을²⁸ 선택한다.그런 다음 m과 n을 기본 B 자리 m_i, n_i:

{\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}

그런 다음 p(B) = m 및 q(B) = n:

p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,

q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,

이러한 다항식을 정의하는 목적은 만약 우리가 그들의 제품 r(x) = p(x)q(x)를 계산할 수 있다면 우리의 대답은 r(B) = m × n이 될 것이다.

곱하는 숫자의 크기가 다른 경우에는 m과 n에 대해 k의 다른 값을 사용하는 것이 유용하며, 이를 k와_m k라고_n 한다.예를 들어, "Toom-2" 알고리즘을 참조하십시오.5"는 toom-Cook을 k_m = 3과 k = 2로_n 지칭한다. 이 경우 일반적으로 b = b의ⁱ i는 다음과 같이 선택된다.

i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.

평가하기

다항식 제품 p(x)q(x)를 계산하는 Toom-Cook 접근법은 흔히 사용된다.도 d의 다항식은 d + 1 점(예: 도 1의 선 다항식은 두 점으로 지정됨)에 의해 고유하게 결정된다는 점에 유의한다.p(·)와 q(·)를 여러 점에서 평가하는 것이 발상이다.그런 다음 이 지점에서 값을 곱하여 제품 다항식의 포인트를 얻으십시오.마지막으로 보간하여 계수를 찾는다.

deg(pq) = deg(p) + deg(q)이기 때문에 deg(p) + deg(q) + 1_m = k_n + k - 1 포인트가 있어야 최종 결과를 결정할 수 있다.이것을 d라고 불러라.Toom-3의 경우 d = 5.알고리즘은 어떤 점을 선택하든 작동하지만(소규모 예외는 몇 개, 보간에서 매트릭스 반전성 요건 참조), 알고리즘을 단순화하기 위해서는 0, 1, -1, -2와 같은 작은 정수 값을 선택하는 것이 좋다.

자주 사용되는 특이한 점 값은 무한대, ∞ 또는 1/0이다.무한대에서 다항식 p를 "평가"한다는 것은 실제로 x가 무한대로 가면서 p(x)/x의^{deg p} 한도를 취하는 것을 의미한다.따라서 p(∞)는 항상 최고도 계수의 값이다(위의 계수₂ m 예에서).

Toom-3 예에서는 0, 1, -1, -2, ∞을 사용할 것이다.이러한 선택은 평가를 단순화하여 다음과 같은 공식을 산출한다.

{\begin{array}{lrlrl}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}

Q와 유사하게이 예에서 얻을 수 있는 가치는 다음과 같다.

p(0)	=	m₀	=	56789012	=	56789012
p(1)	=	m₀ + m₁ + m₂	=	56789012 + 78901234 + 123456	=	135813702
p(−1)	=	m₀ − m₁ + m₂	=	56789012 − 78901234 + 123456	=	−21988766
p(−2)	=	m₀ − 2m₁ + 4m₂	=	56789012 − 2 × 78901234 + 4 × 123456	=	−100519632
p(∞)	=	m₂	=	123456	=	123456
q(0)	=	n₀	=	54321098	=	54321098
q(1)	=	n₀ + n + n₁₂ + n	=	54321098 + 43219876 + 98765	=	97639739
q(−1)	=	n₀ − n₁ + n₂	=	54321098 − 43219876 + 98765	=	11199987
q(−2)	=	n₀ − 2n₁ + 4n₂	=	54321098 − 2 × 43219876 + 4 × 98765	=	−31723594
q(수치)	=	n₂	=	98765	=	98765.

표시된 것처럼 이러한 값은 음수일 수 있다.

나중에 설명하기 위해 이 평가 과정을 매트릭스 벡터 곱셈으로 보는 것이 유용할 것이다. 매트릭스의 각 행은 평가 지점 중 하나의 힘을 포함하고 벡터는 다항식의 계수를 포함한다.

\left({\begin{매트릭스}p(0)\\p(1)\\p())\\p(-2)\\p(\infty)\end{행렬}}\right)=\left({\begin{매트릭스}0^{0}일 경우&0^{1}&0^{2}\\1^{0}일 경우&1^{1}&1^{2}\\())^{0}&,())^{1}&,())^ᆷ\\(-2)^{0}&,(-2)^{1}&,(-2)^{2}\\0&, 0&, 1\end{매트릭스}}\right)\left({\begin{매트릭스}m_{0}일 경우 \\m_{1}\\m_{2}\end{매트릭스}}\right)=\left({\begin{엄마trix}1&, 0&, 0\\1&, 1&, 1\\1&, -1&, 1\\1&, -2&, 4\\0&, 0& 1\end{{n1}\오른쪽)\left}m_{0}\\m_{1}\m_{2}\end{nd}}\right).

행렬의 치수는 p의 경우 d by k이고_m q의 경우 d by k이다_n.무한대의 행은 마지막 열의 1을 제외하고 항상 모두 0이다.

평가 속도 향상

다점 평가는 위의 공식보다 더 빨리 얻을 수 있다.기본 운영(추가/감산) 횟수를 줄일 수 있다.실행 예제의 첫 번째 피연산자(폴리놈 p)에 대해 여기서 실행되는 Toom-3에 대해 Bodrato가^[6] 제공한 순서는 다음과 같다.

p₀	←	m₀ + m₂	=	56789012 + 123456	=	56912468
p(0)	=	m₀	=	56789012	=	56789012
p(1)	=	p₀ + m₁	=	56912468 + 78901234	=	135813702
p(−1)	=	p₀ − m₁	=	56912468 − 78901234	=	−21988766
p(−2)	=	(p(−1) + m₂) × 2 − m₀	=	(− 21988766 + 123456 ) × 2 − 56789012	=	− 100519632
p(∞)	=	m₂	=	123456	=	123456.

이 시퀀스는 직접적인 평가보다 1회 적은 5회의 추가/감속 연산이 필요하다.게다가 p(-2)의 계산에서 곱하기 4가 절약되었다.

점 곱하기

다항식 p(·)와 q(··)를 곱하는 것과 달리, 평가된 값 p(a)와 q(a)를 곱하는 것은 단지 정수를 곱하는 것만을 포함한다. 즉, 원래 문제의 작은 예다.우리는 각각의 평가된 점 쌍을 곱하기 위해 반복적으로 곱하기 절차를 실행한다.실제 구현에서, 피연산자가 작아질수록 알고리즘은 학교책의 긴 곱셈으로 전환될 것이다.r을 제품 다항식(product polynormal)으로 간주해 보십시오.

r(0)	=	p(0)q(0)	=	56789012 × 54321098	=	3084841486175176
r(1)	=	p(1)q(1)	=	135813702 × 97639739	=	13260814415903778
r(−1)	=	p(−1)q(−1)	=	−21988766 × 11199987	=	−246273893346042
r(−2)	=	p(−2)q(−2)	=	−100519632 × −31723594	=	3188843994597408
r(∞)	=	p(수치)q(수치)	=	123456 × 98765	=	12193131840.

표시된 것처럼, 이것들도 음성이 될 수 있다.충분한 숫자의 경우, 이것은 가장 비싼 단계로서, m과 n의 크기로 선형적이지 않은 유일한 단계다.

보간법

이것은 평가 단계의 가장 복잡한 단계, 즉 평가 단계의 역순으로, 제품 다항식 r(·)에 대한 우리의 d 포인트를 감안할 때, 우리는 그 계수를 결정해야 한다.즉, 오른쪽 벡터에 대한 행렬 방정식을 해결하고자 한다.

{\justice}\왼쪽 사진\put}r(0)\r(1)\r)\r(\inflict )\end{nd}\오른쪽)&{}({\begin{매트릭스}0^{0}일 경우&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}일 경우&1^{1}&1^{2}&1^{3}&1^{4}\\())^{0}&,())^{1}&,())^{2}&,())^{3}&,())^ᆷ\\(-2)^{0}&,(-2)^{1}&,(-2)^{2}&,(-2)^{3}&,(-2)^{4}\\0&, 0&, 0&, 0&, 1\end{매트릭스}}\right)\left({\begin{행렬}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{매트릭스}}\right))\&{}=\left({\begin{matrix}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{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{정렬}}

이 매트릭스는 d × d라는 점을 제외하고 평가 단계의 매트릭스와 동일한 방식으로 구성된다.우리는 가우스 제거와 같은 기술로 이 방정식을 풀 수 있지만, 이것은 너무 비싸다.대신 평가 점수를 적절하게 선택했다면 이 매트릭스는 변환할 수 없다는 사실을 사용한다(Vandermonde 매트릭스 참조).

{\required}\left\put}r_{0}\\r_{1}\r_{1}\r_{2}\r_{3}\r_{4}\end}\right)&{}=\left({\begin{matrix}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{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&,{}({\begin{매트릭스}1&, 0&, 0&, 0&, 0\\{\tfrac{1}{2}}&,{\tfrac{1}{3}}&-1&,{\tfrac{1}{6}}&-2\\-1&,{\tfrac{1}{2}}&,{\tfrac{1}{2}}&0&, -1\\-{\tfrac{1}{2}}&,{\tfrac{1}{6}}&,{\tfrac{1}{2}}&-{\tfrac{1}{6}}&2\\0&, 0&, 0&, 0&, 1\end{매트릭스}}\right)\left({\begin{매트릭스}r(0)\\r(1)\\r(.-1)\\r(-2)\\r(\infty)\end{매트릭스}}\right cm이다.\end{정렬}}

남은 것은 이 매트릭스 벡터 제품을 계산하는 것뿐이다.비록 행렬이 분수를 포함하지만, 결과 계수는 정수가 될 것이다. 따라서 이 모든 것은 정수 산술, 추가, 소량 산술, 그리고 작은 상수에 의한 곱하기/분할로 할 수 있다.Toom-Cook에서 어려운 설계 당면 과제는 이 제품을 계산하기 위한 효율적인 작업 순서를 찾는 것이다. Bodrato가^[6] Toom-3에 대해 제공한 한 가지 순서는 실행 예에서 여기에서 실행한 것이다.

r₀	←	r(0)	=	3084841486175176
r₄	←	r(∞)	=	12193131840
r₃	←	(r(-2) - r(1)/3	=	(3188843994597408 − 13260814415903778)/3
			=	−3357323473768790
r₁	←	(r(1) - r(-1)/2	=	(13260814415903778 − (−246273893346042))/2
			=	6753544154624910
r₂	←	r(−1) − r(0)	=	−246273893346042 − 3084841486175176
			=	−3331115379521218
r₃	←	(r₂₃ - r)/2 + 2r(iiii)	=	(−3331115379521218 − (−3357323473768790))/2 + 2 × 12193131840
			=	13128433387466
r₂	←	r₂ + r₁ − r₄	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
r₁	←	r₁ − r₃	=	6753544154624910 − 13128433387466
			=	6740415721237444.

이제 제품 다항식 r:

{\cHB{array}{rrr(x)=&#{}&3084841486175176\\\&#6740415721237444x\\&#342241651971852x^{2}\}\&#13233484387466x^{3134x^}\&#8224x4x^}}\end{array}}

만약 우리가 다른_m k_n, k 또는 평가 지점을 사용한다면, 매트릭스와 우리의 보간 전략은 바뀔 것이다; 그러나 그것은 입력에 의존하지 않고 따라서 주어진 매개변수 집합에 대해 하드 코딩될 수 있다.

재조합

마지막으로, 우리는 최종 답을 얻기 위해 r(B)를 평가한다.이는 B가 b의 힘이기 때문에 B의 힘에 의한 승수는 base b에서 모두 자릿수 이동이기 때문에 간단하다.실행 예제에서 b = 10⁴ 및 B = b = 10²⁸.

								3084	8414	8617	5176
						6740	4157	2123	7444
				3422	4165	8197	1852
		13	1284	3338	7466
+	121	9313	1840

	121	9326	3124	6761	1632	4937	6009	5208	5858	8617	5176

그리고 이것은 사실 1234567890123456789012와 987654321987654321098의 제품이다.

다양한 k에 대한 보간 행렬

여기서는 k와_m k의_n 몇 가지 다른 공통의 작은 값에 대한 공통 보간 행렬을 제공한다.

톰-1

Toom-1(k_m = k_n = 1)에는 1개의 평가점이 필요하며 여기서 0으로 선택된다.이는 ID 매트릭스의 보간 행렬과 함께 긴 곱으로 변한다.

\left \put}\nd{put}}{{put}}\right)^{-1=\prettend{put}{put}}\right.

톰-1.5

Toom-1.5(k_m = 2, k_n = 1)에는 2개의 평가 포인트가 필요하며 여기서 0과 ∞으로 선택된다.보간 행렬은 다음과 같은 ID 행렬이 된다.

\lefts\{ft}{ft}1&0\\0&1\end{ft}\right)^{-1=\left\ft}1&0\#0&1\end{ft}\right).

이것은 또한 긴 곱셈으로 변한다: 한 요인의 두 계수는 다른 요인의 유일한 계수에 의해 곱된다.

톰-2

Toom-2(k_m = 2, k_n = 2)는 3개의 평가점이 필요하며, 여기서 0, 1, ∞으로 선택된다.카라츠바 곱셈과 동일하며, 보간 행렬은 다음과 같다.

\left \ft&0\1&1&1\\\0&1&1\end{ft}^{-1}=\ft&1&0\nd{ft}}{ft}@1&#1&#1&#1\end{ft}\rig}\rig}\right}.

톰-2.5

Toom-2.5(k_m_n = 3, k = 2)에는 4개의 평가점이 필요하며, 여기서 0, 1, -1, ∞으로 선택된다.그 다음 보간 행렬이 다음과 같다.

\left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).

메모들

^ ^a ^b 크누스, 페이지 296
^ 크랜달 & 포머런스, 페이지 474
^ 크랜달 & 포머런스, 536 페이지
^ 크누스, 302페이지
^ 긍정적인 결과, Stephen A의 제3장.요리사: 함수의 최소 계산 시간에.
^ ^a ^b ^c 마르코 보드라토특성 2와 0의 일변량 다항식 및 다변량 다항식의 최적 텀-쿡 곱셈에 대하여.WAIFI'07 절차서, LNCS 제4547권, 116-133페이지.2007년 6월 21일-22일 작성자 웹사이트

참조

D. 크누스.컴퓨터 프로그래밍의 기술 제2권.1997년 애디슨 웨슬리 제3판섹션 4.3.3.A: 디지털 방법, 페이지 294.
R. 크랜달 & C. 포머런스.Prime Numbers – 계산적 관점.2005년 Springer, Second Edition.제9.5.1절: 카라츠바와 톰-쿡 방법, 페이지 473.
보드라토 M.Toom-Cook 곱하기...WAIFI07, Springer, 2007.

외부 링크

Toom-GMP 문서에서 3방향 곱하기 요리

[Knuth,_p._296-1] 크누스, 페이지 296

[2] 크랜달 & 포머런스, 페이지 474

[3] 크랜달 & 포머런스, 536 페이지

[4] 크누스, 302페이지

[5] 긍정적인 결과, Stephen A의 제3장.요리사: 함수의 최소 계산 시간에.

[Bodrato2007-6] 마르코 보드라토특성 2와 0의 일변량 다항식 및 다변량 다항식의 최적 텀-쿡 곱셈에 대하여.WAIFI'07 절차서, LNCS 제4547권, 116-133페이지.2007년 6월 21일-22일 작성자 웹사이트

[1]

[2]

[3]

[4]

[5]

[6]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search