Toom-Cook algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. februar 2022; checks kræver 7 redigeringer .

Toom-Cook- algoritmen , nogle gange omtalt som Toom-3 og opkaldt efter Andrey Leonovich Toom, der foreslog en ny algoritme med lav kompleksitet, og Stephen Cook , der beskrev algoritmen mere tydeligt, er en algoritme til at multiplicere store tal .

Givet to store tal a og b skal du ifølge Toom-Cook-algoritmen opdele a og b i k mindre dele hver med længden l og udføre operationer på delene. Efterhånden som k vokser , er det muligt at kombinere nogle af operationerne ved at multiplicere dele af partitionen og derved reducere algoritmens overordnede kompleksitet. Produktet af partitionens dele kan derefter beregnes ved hjælp af den samme Toom-Cook-algoritme rekursivt. Udtrykkene "Toom-3-algoritme" og "Toom-Cook-algoritme" bruges nogle gange fejlagtigt i flæng, selvom Toom-3 kun er et specialtilfælde af Toom-Cook-algoritmen for k = 3.

Toom-3 reducerer kompleksiteten fra 9 gange til 5 og arbejder i tide . Generelt virker Toom- k i tid , hvor , er den tid brugt på multiplikationer af underdele, og c er den tid der bruges på addition og multiplikation med små konstanter [1] . Karatsuba-algoritmen er et specialtilfælde af Toom-Cook-algoritmen, hvor tallet er opdelt i to dele. Det reducerer kompleksiteten fra 4 gange til 3 og kører derfor i tid . Normal multiplikation med en kolonne svarer til Toom-1 med kompleksitet . $\Theta (n^{\log(5)/\log(3)})\ca. \Theta (n^{1{,}46})$ $\Theta (c(k)n^{e})$ ${\displaystyle e=\log {(2k-1)}/\log {(k)))$ $n^{e}$ $\Theta (n^{\log(3)/\log(2)})\ca. \Theta (n^{1{,}58})$ $\Theta (n^{2})$

Selvom styrken af e kan sættes så tæt på 1 som muligt ved at øge k , vokser funktionen c desværre meget hurtigt [1] [2] . Vækstraten for blandede Toom-Cook-ordninger forblev et åbent problem i 2005 [3] . Implementeringen beskrevet af Donald Knuth opnår kompleksitet [4] . $\Theta (n2^{\sqrt {2\log n))\log n)$

På grund af overhead er Toom-Cook-algoritmen for små tal langsommere end multiplikation med en kolonne og blev derfor normalt brugt til faktorer af mellemstørrelse, indtil den asymptotisk hurtigere Schönhage-Strassen-algoritme (med kompleksitet . $\Theta (n\log n\log {\log n))$

Toom beskrev sin algoritme i 1963 , og Cook udgav en forbedret (asymptotisk ækvivalent) algoritme i sit speciale i 1966 [ 5] .

Detaljer

Dette afsnit diskuterer driften af Toom - k -algoritmen for enhver given værdi af k og giver en forenklet beskrivelse af Toom-Cook-multiplikation af polynomier, som beskrevet af Marco Bodrato [6] . Algoritmen har fem hovedtrin:

opsplitning
Pointberegning
Punktvis multiplikation
Interpolation
Gensammensætning

I en typisk fortolkning af store tal er hvert heltal repræsenteret som en sekvens af cifre i et positionelt talsystem , hvor talgrundlaget er en eller anden (normalt stor) værdi b . I vores eksempel bruger vi , så hvert ciffer svarer til en gruppe med fire decimalcifre (i en computerimplementering er b normalt en potens af to). Lad os sige, at vi skal gange to tal $b=10000$

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

De er meget mindre end dem, der normalt håndteres af Toom-Cook-algoritmen, men de illustrerer algoritmen her.

Opdeling

Det første trin er at vælge en base , så antallet af cifre for både m og n i basis B ikke overstiger k (f.eks. 3 i Toom-3). Normalt er jeg givet af ${\displaystyle B=b^{i))$

i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k))\right\rfloor ,\left\lfloor {\ frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.

I vores eksempel vil vi bruge Toom-3, så vi vælger . Nu opdeler vi m og n med deres radix B i cifre : $B=b^{2}=10^{8}$ $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}}

Vi vil bruge disse tal som koefficienter i polynomier p og q af grad ( k − 1) , med egenskaberne og : $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\,

Efter at have introduceret disse polynomier, får vi, at hvis vi beregner produktet , så vil svaret på problemet være . $r(x)=p(x)q(x)$ $r(B)=m\ gange n$

I det tilfælde, hvor de multiplicerede tal har forskellige størrelser, er det nyttigt at bruge forskellige værdier af k for m og n , som vi vil betegne og . For eksempel refererer "Toom-2.5"-algoritmen til Toom-Cook-algoritmen med og . I dette tilfælde er i in normalt valgt af udtrykket $k_m$ $k_n$ $k_{m}=3$ $k_{n}=2$ $B=b^{'}i$

i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil}{k_{m))}\right\rfloor ,\left\ lgulv {\frac {\left\lceil \log _{b}n\right\rceil}{k_{n))}\højre\rgulv \right\}.

Beregning i point

Toom-Cook-tilgangen til at beregne produktet af polynomier er almindelig. Bemærk, at et polynomium af grad d er entydigt defineret af punkter (for eksempel er en linje et polynomium af grad 1 og er defineret af to punkter). Ideen er at beregne p (•) og q (•) på forskellige punkter. Derefter udføres produktet af værdierne på disse punkter for at opnå værdierne af produktet af polynomierne. Til sidst interpolerer vi de opnåede værdier for at opnå koefficienterne for polynomiet. $p(x)q(x)$ $d+1$

Siden har vi brug for point for at få det endelige resultat. Lad os kalde det d . I tilfældet med Toom-3 . Algoritmen fungerer uanset hvilke punkter der vælges (med få mindre undtagelser - se kravet om, at matrixen er inverterbar i Interpolation -afsnittet ), men for at forenkle algoritmen er det bedre at bruge små værdier som 0, 1, −1 og −2. $\deg(pq)=\deg(p)+\deg(q)$ $\deg(p)+\deg(q)+1=k_{m}+k_{n}-1$ $d=5$

Et usædvanligt punkt, der ofte bruges, er uendelighed, dvs. For at "beregne" polynomiet p ved uendelig, tag grænsen, da x har en tendens til uendelig. Derfor er den altid lig med værdien af den førende koefficient (i eksemplet ovenfor koefficienten ). $\infty$ ${\displaystyle p(x)/x^{\deg p))$ $p(\infty )$ $m_2$

I vores Toom-3 eksempel bruger vi punkterne 0, 1, −1, −2 og . Dette valg forenkler beregningen i point og giver formler: $\infty$

{\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}}

Og tilsvarende for q . I vores eksempel er de værdier, vi får:

$p(0)$	=	$m_{0}$	=	56789012	=	56789012
$p(1)$	=	${\displaystyle m_{0}+m_{1}+m_{2))$	=	$56789012+78901234+123456$	=	135813702
$p(-1)$	=	${\displaystyle m_{0}-m_{1}+m_{2))$	=	$56789012-78901234+123456$	=	−21988766
$p(-2)$	=	${\displaystyle m_{0}-2m_{1}+4m_{2))$	=	$56789012-2\times 78901234+4\times 123456$	=	−100519632
$p(\infty )$	=	$m_2$	=	123456	=	123456
$q(0)$	=	$n_{0}$	=	54321098	=	54321098
$q(1)$	=	$n_{0}+n_{1}+n_{2}$	=	$54321098+43219876+98765$	=	97639739
$q(-1)$	=	${\displaystyle n_{0}-n_{1}+n_{2))$	=	$54321098-43219876+98765$	=	11199987
$q(-2)$	=	$n_{0}-2n_{1}+4n_{2}$	=	$54321098-2\times 43219876+4\times 98765$	=	−31723594
$q(\infty )$	=	$n_{2}$	=	98765	=	98765.

Som du kan se, kan disse værdier være negative.

For yderligere forklaring er det nyttigt at tænke på denne proces med beregning af punkter som at gange en matrix med en vektor til højre, hvor hver række i matrixen indeholder potenserne af et af de valgte punkter, og vektoren indeholder koefficienterne for polynomiet:

\left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix))\ højre)=\venstre({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1) ^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2} \\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left( {\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1 }\\m_{2}\end{matrix}}\right).

Dimensionerne af matricerne er ens for p og for q . Rækken for uendelighed har nul værdier bortset fra den sidste kolonne, som har en 1. ${\displaystyle d\ gange k_{m))$ ${\displaystyle d\times k_{n))$

Hurtigere beregning af værdier

Beregning af punktværdier kan gøres hurtigere end angivet i ovenstående formler. Antallet af elementære operationer (addition/subtraktion) kan reduceres. Sekvensen af operationer udtænkt af Bodrato [6] for Toom-3 er vist her for den første operand (polynomium p ):

$p_{0}$	$\venstre pil$	${\displaystyle m_{0}+m_{2))$	=	56789012 + 123456	=	56912468
$p(0)$	=	$m_{0}$	=	56789012	=	56789012
$p(1)$	=	$p_{0}+m_{1}$	=	56912468 + 78901234	=	135813702
$p(-1)$	=	${\displaystyle p_{0}-m_{1))$	=	56912468 - 78901234	=	−21988766
$p(-2)$	=	${\displaystyle (p(-1)+m_{2})\ gange 2-m_{0))$	=	$(-21988766+123456)\times 2-56789012$	=	− 100519632
$p(\infty )$	=	$m_2$	=	123456	=	123456.

Denne sekvens kræver fem additions-/subtraktionsoperationer, en mindre end den direkte beregning. Desuden behøver vi ikke at gange med 4, når vi beregner p (−2).

Punktvis multiplikation

I modsætning til multiplikationen af polynomierne p (•) og q (•), reducerer multiplikationen af de beregnede værdier p ( a ) og q ( a ) simpelthen til multiplikationen af heltal, en enklere version af det oprindelige problem. Vi bruger rekursivt vores multiplikationsprocedure til at beregne hvert par af punktværdier. I praktiske implementeringer, når operanderne bliver mindre, reduceres algoritmen til multiplikation i kolonnen . Hvis r er et produkt af polynomier, har vi i vores eksempel:

$r(0)$	=	$p(0)q(0)$	=	$56789012\times 54321098$	=	3084841486175176
$r(1)$	=	$p(1)q(1)$	=	$135813702\times 97639739$	=	13260814415903778
$r(-1)$	=	$p(-1)q(-1)$	=	$-21988766\times 11199987$	=	−246273893346042
$r(-2$ )	=	$p(-2)q(-2)$	=	$-100519632\times -31723594$	=	3188843994597408
$r(\infty )$	=	$p(\infty )q(\infty )$	=	$123456\times 98765$	=	12193131840.

Som du kan se, kan disse værdier være negative. For tilstrækkeligt store tal er dette det dyreste trin, det eneste trin, der ikke afhænger lineært af størrelserne m og n .

Interpolation

Dette er det sværeste trin, det omvendte trin med beregning af point - givet vores d - punkter af produktet af polynomier r (•), må vi beregne dets koefficienter. Med andre ord skal vi løse en matrixligning med en vektor på højre side:

{\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\ end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^ {0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2 }&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(- 2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{ 2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\venstre({\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)\venstre({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\ \r_{4}\end{matrix}}\right).\end{aligned}}

Denne matrix er konstrueret på samme måde som i trinnet med at beregne polynomieværdierne ved punkter, bortset fra at matrixen har en størrelse på d × d . Vi kan løse denne ligning ved hjælp af Gauss- metoden (udelukkelsesmetode), men det vil være meget dyrt. I stedet bruger vi det faktum, at de punkter, der bruges til at beregne værdierne, er valgt på en særlig måde, hvilket gør det nemt at beregne den inverse matrix (se også Vandermonde matrix ), og så

{\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix }}\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}\venstre({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix))\ højre)\\&{}=\venstre({\begin{matrix}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{matrix}}\right)\venstre({\ start{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned} }

Nu er det kun tilbage at beregne produktet af matrixen og vektoren. Selvom matricen indeholder brøker, vil de resulterende koefficienter være heltal, så udregninger kan udføres i heltalsaritmetik ved at addere, subtrahere og gange/dividere med små konstanter. Her er hovedopgaven at finde en effektiv sekvens af operationer, der gør det muligt at beregne produktet af en matrix og en vektor. En sådan sekvens blev givet af Bodrato [6] for Toom-3, og for vores eksempel er den som følger:

$r_{0}$	$\venstre pil$	$r(0)$	=	3084841486175176
$r_4$	$\venstre pil$	$r(\infty )$	=	12193131840
$r_3$	$\venstre pil$	$(r(-2)-r(1))/3$	=	(3188843994597408 − 13260814415903778)/3
			=	−3357323473768790
$r_{1}$	$\venstre pil$	$(r(1)-r(-1))/2$	=	$(13260814415903778-(-246273893346042))/2$
			=	6753544154624910
$r_{2}$	$\venstre pil$	$r(-1)-r(0)$	=	$-246273893346042-3084841486175176$
			=	−3331115379521218
$r_3$	$\venstre pil$	$(r_{2}-r_{3})/2+2r(\infty )$	=	$(-3331115379521218-(-3357323473768790))/2+2\ gange 12193131840$
			=	13128433387466
$r_{2}$	$\venstre pil$	${\displaystyle r_{2}+r_{1}-r_{4))$	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
$r_{1}$	$\venstre pil$	${\displaystyle r_{1}-r_{3))$	=	6753544154624910 − 13128433387466
			=	6740415721237444.

Vi kender nu produktet r af vores polynomier:

{\begin{array}{rrr}r(x)=&{}&3084841486175176\\&+&6740415721237444x\\&+&3422416581971852x^{2}\71852x^{2}\71841486175176\\&+&6740415721237444x\\&+&3422416581971852x^{2}\71852x^{2}\75176&331\331\31^&331 4}\end{array}}

Hvis vi brugte andre eller valgte andre punkter til at beregne værdierne, ville matricen og derefter interpolationsstrategien ændre sig, men dette afhænger ikke af inputdataene, og derfor kan algoritmen fastkobles for alle givne parametre. ${\displaystyle k_{m},k_{n))$

Omkomposition

Til sidst beregner vi r(B) for at få det endelige resultat. Dette gøres direkte, fordi B er en potens af b , og derfor er multiplikation med potenser af B en forskydning af hele tallet med et helt tal af cifre i grundtallet b . I vores eksempel , og $b=10^{4}$ $B=b^{2}=10^{8}$

								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

Resultatet er produktet af 1234567890123456789012 og 987654321987654321098.

Interpolationsmatricer for forskellige værdier af k

Her præsenterer vi interpolationsmatricerne for flere forskellige små værdier af og . $k_m$ $k_n$

Toom −1

Toom-1 ( ) kræver beregning på et tidspunkt, her vælges 0. Algoritmen degenererer til kolonnemultiplikation med en identitetsinterpolationsmatrix: $k_{m}=k_{n}=1$

\left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).

Toom-1.5

Toom-1.5 ( ) kræver to point, her 0 og er valgt . Interpolationsmatricen er da lig med identitetsmatrixen: $k_{m}=2,k_{n}=1$ $\infty$

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

Algoritmen degenererer også til multiplikation i en kolonne - begge koefficienter for en faktor multipliceres med en koefficient for en anden faktor.

Toom-2

Toom-2 ( ) kræver tre point, 0, 1 og vælges her . Algoritmen er den samme som Karatsuba-algoritmen med interpolationsmatricen $k_{m}=2,k_{n}=2$ $\infty$

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

Toom-2.5

Toom-2.5 ( kræver 4 point, her 0, 1, −1 og er valgt . Algoritmen har så en interpolationsmatrix: $k_{m}=3,k_{n}=2)$ $\infty$

\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).

Noter

↑ 1 2 Knuth, 1997 , s. 296.
↑ Crandall, Pomerance, 2005 , s. 474.
↑ Crandall, Pomerance, 2005 , s. 536.
↑ Knuth, 1997 , s. 302.
↑ Positive resultater arkiveret 6. januar 2013 på Wayback Machine , kapitel III af Stephen A. Cook: On the Minimum Computation Time of Functions .
↑ 1 2 3 Bodrato, 2007 , s. 116-133.

Litteratur

D. Knuth. Afsnit 4.3.3.A: Digitale metoder // The Art of Computer Programming . — Tredie Udgave. - Addison-Wesley, 1997. - T. 2. - S. 294.
Knut D.E. Kunsten at programmere. De resulterende algoritmer. - 2019. - Vol. 2. - ISBN 978-5-907144-15-6 .
R. Crandall, C. Pomerance. Afsnit 9.5.1: Karatsuba og Toom-Cook metoder // Prime Numbers – A Computational Perspective . - Anden version. - Springer, 2005. - S. 473 .
- Richard Crandall, Carl Pomerance. Simple tal. Kryptografiske og beregningsmæssige aspekter. - Moskva: Librocom, 2011. - ISBN 978-5-397-02060-2 .
M. Bodrato. Mod Optimal Toom-Cook-multiplikation for univariate og multivariate polynomier i karakteristik 2 og 0 // Aritmetik af endelige felter . - Springer, 2007. - T. 4547. - (LNCS).

Links

Toom-Cook 3-vejs multiplikation fra GMP dokumentation

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme