Toom-Cook algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 februari 2022; kontroller kräver 7 redigeringar .

Toom-Cook- algoritmen , ibland kallad Toom-3 och uppkallad efter Andrey Leonovich Toom, som föreslog en ny algoritm med låg komplexitet, och Stephen Cook , som beskrev algoritmen tydligare, är en algoritm för att multiplicera stora tal .

Med tanke på två stora siffror a och b , enligt Toom-Cook-algoritmen, måste du dela upp a och b i k mindre delar var och en med längd l och utföra operationer på delarna. När k växer är det möjligt att kombinera några av operationerna för att multiplicera delar av partitionen, och därigenom minska den övergripande komplexiteten hos algoritmen. Produkten av partitionens delar kan sedan beräknas med samma Toom-Cook-algoritm rekursivt. Termerna "Toom-3-algoritmen" och "Toom-Cook-algoritmen" används ibland felaktigt omväxlande, även om Toom-3 bara är ett specialfall av Toom-Cook-algoritmen för k = 3.

Toom-3 minskar komplexiteten från 9 multiplikationer till 5 och fungerar i tid . I allmänhet fungerar Toom- k i tid , där , är tiden som spenderas på multiplikationer av underdelar, och c är tiden som spenderas på additioner och multiplikationer med små konstanter [1] . Karatsuba-algoritmen är ett specialfall av Toom-Cook-algoritmen, där numret är uppdelat i två delar. Det minskar komplexiteten från 4 multiplikationer till 3 och körs därför i tid . Normal multiplikation med en kolumn motsvarar Toom-1 med komplexitet . $\Theta (n^{\log(5)/\log(3)})\approx \Theta (n^{1{,}46})$ $\Theta (c(k)n^{e})$ ${\displaystyle e=\log {(2k-1)}/\log {(k)))$ ${\displaystyle n^{e))$ $\Theta (n^{\log(3)/\log(2)})\approx \Theta (n^{1{,}58})$ $\Theta (n^{2})$

Även om styrkan av e kan sättas så nära 1 som möjligt genom att öka k växer funktionen c tyvärr väldigt snabbt [1] [2] . Tillväxttakten för blandade Toom-Cook-program förblev ett öppet problem 2005 [3] . Implementeringen som beskrivs av Donald Knuth uppnår komplexitet [4] . $\Theta (n2^{\sqrt {2\log n}}\log n)$

På grund av overheaden är Toom-Cook-algoritmen för små tal långsammare än multiplikation med en kolumn och användes därför vanligtvis för faktorer av medelstor storlek, fram till den asymptotiskt snabbare Schönhage-Strassen-algoritmen (med komplexitet . $\Theta (n\log n\log {\log n))$

Toom beskrev sin algoritm 1963 , och Cook publicerade en förbättrad (asymptotiskt ekvivalent) algoritm i sin avhandling 1966 [ 5] .

Detaljer

Detta avsnitt diskuterar funktionen av Toom- k -algoritmen för ett givet värde på k och ger en förenklad beskrivning av Toom-Cook-multiplikation av polynom, som beskrivs av Marco Bodrato [6] . Algoritmen har fem huvudsteg:

splittring
Poängberäkning
Punktvis multiplikation
Interpolation
Omkomposition

I en typisk tolkning av stora tal representeras varje heltal som en sekvens av siffror i ett positionsnummersystem , där talbasen är något (vanligtvis stort) värde b . I vårt exempel använder vi , så att varje siffra motsvarar en grupp med fyra decimalsiffror (i en datorimplementation är b vanligtvis en potens av två). Låt oss säga att vi måste multiplicera två tal $b=10000$

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

De är mycket mindre än de som vanligtvis hanteras av Toom-Cook-algoritmen, men de illustrerar algoritmen här.

Uppdelning

Det första steget är att välja en bas så att antalet siffror för både m och n i bas B inte överstiger k (till exempel 3 i Toom-3). Vanligtvis ges jag av ${\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 vårt exempel kommer vi att använda Toom-3, så vi väljer . Nu delar vi m och n med deras radix B i siffror : $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 kommer att använda dessa tal som koefficienter i polynomen p och q av grad ( k − 1) , med egenskaperna och : $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 att ha introducerat dessa polynom får vi att om vi beräknar produkten , då blir svaret på problemet . $r(x)=p(x)q(x)$ $r(B)=m\ gånger n$

I fallet när de multiplicerade talen har olika storlekar är det användbart att använda olika värden på k för m och n , som vi kommer att beteckna och . Till exempel hänvisar "Toom-2.5"-algoritmen till Toom-Cook-algoritmen med och . I det här fallet väljs i in vanligtvis av uttrycket $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))}\höger\rgolv ,\left\ lgolv {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n))}\höger\rgolv \höger\}.

Beräkning i poäng

Toom-Cook-metoden för att beräkna produkten av polynom är vanlig. Observera att ett polynom av grad d är unikt definierat av punkter (till exempel är en linje ett polynom med grad 1 och definieras av två punkter). Tanken är att beräkna p (•) och q (•) vid olika punkter. Sedan utförs produkten av värdena vid dessa punkter för att erhålla värdena för produkten av polynomen. Slutligen interpolerar vi de erhållna värdena för att erhålla polynomets koefficienter. $p(x)q(x)$ $d+1$

Sedan behöver vi poäng för att få det slutliga resultatet. Låt oss kalla det d . I fallet med Toom-3 . Algoritmen fungerar oavsett vilka punkter som väljs (med några få mindre undantag - se kravet på att matrisen är inverterbar i Interpolationsavsnittet ), men för att förenkla algoritmen är det bättre att använda små värden som 0, 1, −1 och −2. $\deg(pq)=\deg(p)+\deg(q)$ $\deg(p)+\deg(q)+1=k_{m}+k_{n}-1$ $d=5$

En ovanlig punkt som ofta används är oändligheten, dvs. För att "beräkna" polynomet p vid oändlighet, ta gränsen eftersom x tenderar mot oändlighet. Därför är den alltid lika med värdet på den ledande koefficienten (i exemplet ovan, koefficienten ). $\infty$ ${\displaystyle p(x)/x^{\deg p))$ $p(\infty )$ $m_2$

I vårt Toom-3-exempel använder vi punkterna 0, 1, −1, −2 och . Detta val förenklar beräkningen i poäng och ger 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}}

Och på liknande sätt för q . I vårt exempel är de värden 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)$	=	${\displaystyle 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)$	=	${\displaystyle 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 dessa värden vara negativa.

För ytterligare förklaring är det användbart att tänka på denna process att beräkna i punkter som att multiplicera en matris med en vektor till höger, där varje rad i matrisen innehåller potenserna för en av de valda punkterna, och vektorn innehåller koefficienterna för polynomet:

\left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix))\ höger)=\left({\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}}\höger)\left({\begin{matrix}m_{0}\\m_{1 }\\m_{2}\end{matris}}\right).

Matrisernas dimensioner är lika för p och för q . Raden för oändlighet har nollvärden förutom den sista kolumnen, som har en 1. ${\displaystyle d\times k_{m))$ ${\displaystyle d\times k_{n))$

Snabbare beräkning av värden

Beräkna poängvärden kan göras snabbare än vad som anges i formlerna ovan. Antalet elementära operationer (addition/subtraktion) kan reduceras. Sekvensen av operationer som utformats av Bodrato [6] för Toom-3 visas här för den första operanden (polynom p ):

$p_{0}$	$\vänster 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})\ gånger 2-m_{0))$	=	$(-21988766+123456)\times 2-56789012$	=	− 100519632
$p(\infty )$	=	$m_2$	=	123456	=	123456.

Denna sekvens kräver fem additions-/subtraktionsoperationer, en mindre än den direkta beräkningen. Dessutom behöver vi inte multiplicera med 4 när vi beräknar p (−2).

Punktvis multiplikation

Till skillnad från multiplikationen av polynomen p (•) och q (•), reduceras multiplikationen av de beräknade värdena p ( a ) och q ( a ) helt enkelt till multiplikationen av heltal, en enklare version av det ursprungliga problemet. Vi använder rekursivt vår multiplikationsprocedur för att beräkna varje par av poängvärden. I praktiska implementeringar, när operanderna blir mindre, reduceras algoritmen till multiplikation i kolumnen . Om r är en produkt av polynom, har vi i vårt exempel:

$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 dessa värden vara negativa. För tillräckligt stora antal är detta det dyraste steget, det enda steget som inte är linjärt beroende av storlekarna m och n .

Interpolation

Detta är det svåraste steget, det omvända steget att beräkna i poäng - givet våra d- punkter av produkten av polynomen r (•), måste vi beräkna dess koefficienter. Med andra ord måste vi lösa en matrisekvation med en vektor på höger sida:

{\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)\\&{}=\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{aligned}}

Denna matris är konstruerad på samma sätt som i steget att beräkna polynomvärdena vid punkter, förutom att matrisen har storleken d × d . Vi kan lösa denna ekvation med Gauss- metoden (uteslutningsmetoden), men det blir väldigt dyrt. Istället använder vi det faktum att de punkter som används för att beräkna värdena är valda på ett speciellt sätt, vilket gör det enkelt att beräkna den inversa matrisen (se även Vandermonde-matrisen ), och sedan

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

Nu återstår bara att beräkna produkten av matrisen och vektorn. Även om matrisen innehåller bråk, kommer de resulterande koefficienterna att vara heltal, så beräkningar kan göras i heltalsaritmetik genom att addera, subtrahera och multiplicera/dividera med små konstanter. Här är huvuduppgiften att hitta en effektiv sekvens av operationer som gör att man kan beräkna produkten av en matris och en vektor. En sådan sekvens gavs av Bodrato [6] för Toom-3, och för vårt exempel är den följande:

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

Vi känner nu till produkten r av våra polynom:

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

Om vi använde andra eller valde andra punkter för att beräkna värdena, skulle matrisen, och sedan interpolationsstrategin, ändras, men detta beror inte på indata, och därför kan algoritmen kopplas fast för alla givna parametrar. ${\displaystyle k_{m},k_{n))$

Omkomposition

Slutligen beräknar vi r(B) för att få det slutliga resultatet. Detta görs direkt, eftersom B är en potens av b , och därför är multiplikation med potens av B en förskjutning av hela talet med ett heltal av siffror i basen b . I vårt exempel , och $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 är produkten av 1234567890123456789012 och 987654321987654321098.

Interpolationsmatriser för olika värden på k

Här presenterar vi interpolationsmatriserna för flera olika små värden på och . $k_m$ $k_n$

Toom −1

Toom-1 ( ) kräver beräkning vid en punkt, här väljs 0. Algoritmen degenererar till kolumnmultiplikation med en identitetsinterpolationsmatris: $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 två poäng, här 0 och väljs . Interpolationsmatrisen är då lika med identitetsmatrisen: $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}} \höger).

Algoritmen urartar också till multiplikation i en kolumn - båda koefficienterna för en faktor multipliceras med en koefficient för en annan faktor.

Toom-2

Toom-2 ( ) kräver tre poäng, 0, 1 och väljs här . Algoritmen är densamma som Karatsuba-algoritmen med interpolationsmatrisen $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 poäng, här 0, 1, −1 och väljs . Algoritmen har då en interpolationsmatris: $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{matris}}\höger).

Anteckningar

↑ 1 2 Knuth, 1997 , sid. 296.
↑ Crandall, Pomerance, 2005 , sid. 474.
↑ Crandall, Pomerance, 2005 , sid. 536.
↑ Knuth, 1997 , sid. 302.
↑ Positiva resultat Arkiverade 6 januari 2013 på Wayback Machine , kapitel III av Stephen A. Cook: Om den minsta beräkningstiden för funktioner .
↑ 1 2 3 Bodrato, 2007 , sid. 116–133.

Litteratur

D. Knuth. Avsnitt 4.3.3.A: Digitala metoder // Konsten att programmera datorer . - Tredje upplagan. - Addison-Wesley, 1997. - T. 2. - S. 294.
Knut D.E. Konsten att programmera. De resulterande algoritmerna. - 2019. - Vol. 2. - ISBN 978-5-907144-15-6 .
R. Crandall, C. Pomerance. Avsnitt 9.5.1: Karatsuba och Toom–Cook-metoder // Prime Numbers – A Computational Perspective . - Andra upplagan. - Springer, 2005. - S. 473 .
- Richard Crandall, Carl Pomerance. Enkla siffror. Kryptografiska och beräkningsaspekter. - Moskva: Librocom, 2011. - ISBN 978-5-397-02060-2 .
M. Bodrato. Mot optimal Toom-Cook-multiplikation för univariata och multivariata polynom i karaktäristik 2 och 0 // Aritmetik av ändliga fält . - Springer, 2007. - T. 4547. - (LNCS).

Länkar

Toom-Cook 3-vägs multiplikation från GMP-dokumentation

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm