Algoritmo de Toom-Cook

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En matematiko, algoritmo de Toom-Cook estas multiplika algoritmo, maniero de multiplikado de du grandaj entjeroj.

Por donita du entjeroj a kaj b, la algoritmo fendas ĉiun el a kaj b je k pli malgrandajn partojn ĉiu de longo ne pli ol l ciferoj, kaj plenumas operaciojn sur la partoj. Dum ĉi tio, necesas fari plurajn multiplikajn sub-operaciojn de nombroj de l aŭ malmulte pli multaj ciferoj. La multiplikaj sub-operacioj povas esti faritaj rikure uzante algoritmon de Toom-Cook denove. En la plej profunda nivelo de la rikuro, necesas ebleco iel senpere multipliki sufiĉe malgrandajn nombrojn.

La algoritmo Toom-3 estas fendas la nombroj en 3 partojn, kaj por multipliko de la nombroj tiam necesas 5 sup-multiplikoj anstataŭ 9 en la kutima longa multipliko, kaj la asimptota tempa komputa komplikeco estas do Θ(nlog(5)/log(3))≈Θ(n1,465). La algoritmo de Karatsuba estas simpla speciala okazo de algoritmo de Toom-Cook, fakte Toom-2, kie la nombroj estas fendataj ĉiu en 2 partojn. kaj por multipliko de la nombroj tiam necesas 3 multiplikoj anstataŭ 4 en la kutima longa multipliko, kaj la asimptota komplikeco estas do Θ(nlog(3)/log(2))≈Θ(n1,585). Ordinara longa multipliko estas ekvivalento al Toom-1, kun komplikeco Θ(n2).

Ĝenerale, la algoritmo Toom-k havas la asimptotan komplikecon Θ(c(k) nf(k)), kie f(k) = log(2k-1) / log(k). En la formulo la ero nf(k) priskribas la elspezon de tempo pro rikuraj sub-multiplikoj, kaj c(k) priskribas la elspezon de tempo pro adicioj kaj multiplikoj je malgrandaj nombroj.

Kvankam la eksponento f povas esti farita arbitre proksima al 1 per pligrandiĝo de k, la funkcio c(k) bedaŭrinde kreskas tre rapide. La kreskada kurzo por miksito-nivela algoritmo de Toom-Cook estas ankoraŭ malfermita esplora problemo en 2005. Realigo priskribita de Donald Knuth atingas la polinoman tempon Θ(n 2√(2 log (n)) log (n)).


La algoritmo de Toom-Cook estas pli malrapida ol longa multipliko ĉe malgrandaj nombroj, kaj ĝi estas pro tio tipe uzita por mezo-ampleksaj nombroj. Por pli grandaj nombroj asimptote pli rapida algoritmo de Schönhage-Strassen kun komplikeco Θ(n log (n) log (log (n))) estas praktika.

La algoritmo estas nomita post Andrei Toom kaj Stephen Cook. Andrei Toom la unua priskribis ĉi tiun algoritmon en 1963, kaj Stephen Cook plibonigis la algoritmon kaj publikigis ĝin en sia PhD-tezo en 1966 [1].

Kvankam la "Toom-3" estas nur varianto de la algoritmo de Toom-Cook kun k = 3, iam la terminoj "Toom-3" kaj "Toom-Cook" estas malĝuste uzataj kvazaŭ signifantaj la samon.

Algoritmo kaj ekzemplo[redakti | redakti fonton]

En tipa praktika realigo de komputadoj kun grandaj entjeraj, ĉiu entjero estas prezentata kiel vico de ciferoj en pozicia nombrosistemo kun certa bazo b, tipe granda. Por ĉi tiu ekzemplo estas b=10000, tiel ke ĉiu cifero respektivas al grupo de kvar dekumaj ciferoj. En komputilaj realigoj, b devus tipe esti potenco de 2 anstataŭe.

Estu la du entjeroj por multiplikado

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

Ĉi tiuj nombroj estas multe pli malgrandaj ol tiuj kiuj kutime normale estas procezataj per algoritmo de Toom-Cook, ili estas nur por ilustri la algoritmon.

Disdivido de multiplikatoj[redakti | redakti fonton]

La unua paŝo estas elekti la bazon B = bi, tian ke la kvanto de ciferoj de ambaŭ m kaj n en bazo B estas maksimume k (ekzemple, k=3 en Toom-3). Tipa elekto por i estas donita per:

i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k{\rfloor}\}

En nia ekzemplo de Toom-3, B = b6/3 = 108. Oni tiam apartigu la nombrojn m kaj n en iliajn ciferoj en bazo B, mi kaj ni por i=0 ... k-1:

m2 = 123456
m1 = 78901234
m0 = 56789012
n2 = 98765
n1 = 43219876
n0 = 54321098

Oni tiam uzu ĉi tiujn ciferojn kiel koeficientoj de polinomoj p kaj q de grado (k-1), kun la propraĵo ke p(B) = m kaj q(B) = n:

p(x) = m2x2 + m1x + m0 = 123456x2 + 78901234x + 56789012
q(x) = n2x2 + n1x + n0 = 98765x2 + 43219876x + 54321098

La celo de difinado de ĉi tiuj polinomoj estas plisimpligo de rezonado pri komputado de ilia produto r(x) = p(x)q(x), kaj la r(x) estas interesa nur je kalkulado de r(B) = m×n, kio estas la rezulto de la algoritmo.

En la okazo se la multiplikataj nombroj estas de malsamaj ampleksoj, povas esti utile uzi malsamajn valorojn de k por m kaj n, la km kaj kn. Ekzemple, la algoritmo "Toom-2,5" estas tiu kun km=3 kaj kn=2. En ĉi tiu okazo la i en B = bi estas tipe elektata kiel

i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k_m{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k_n{\rfloor}\}

Pritakso[redakti | redakti fonton]

La maniero de komputado de la produto de polinomoj p(x)q(x) estas bazita je tio ke polinomo de grado d-1 estas unike difinita per ĝiaj valoroj en d punktoj (ekzemple, linio estas precizigita per du punktoj). La ideo estas komputi p(x) kaj q(x) je diversaj punktoj, multipliki iliajn valorojn je ĉi tiuj punktoj kaj uzi la rezultojn por trovi koeficientojn de p(x)q(x).

Pro tio ke grado(pq) = grado(p) + grado(q), oni bezonas

d=grado(p)+grado(q)+1=km+kn-1

punktojn. Ĉe Toom-3 estas d = 5. La algoritmo principe laboras sendepende de tio kiuj punktoj estas elektitaj, sed por plisimpligo estas pli bone elekti malgrandajn simplajn valorojn, simile al 0, 1/2, -1/2, 1, -1, 2, -2.

Unu nekutima punkto kiu estas ofte uzata estas malfinio ∞. Anstataŭ komputado de polinomo p je malfinio reale estas prenata valoro p, kiu estas la limeso de p(x)/(xgrado(p)) kiam x iras al malfinio. Ĝi ĉiam egalas al la konduka koeficiento de la polinomo.

En ĉi tiu ekzemplo de Toom-3, estos uzataj la punktoj 0, 1, -1, -2 kaj ∞. Ĉi tiu elekto plisimpligas la komputadon. La formuloj por la valoroj estas:

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

kaj la valoro m2 por ∞.

kaj analoge por q:

q(0) = n_0 + n_1(0) + n_2(0)^2 = n_0
q(1) = n_0 + n_1(1) + n_2(1)^2 = n_0 + n_1 + n_2
q(-1) = n_0 + n_1(-1) + n_2(-1)^2 = n_0 - n_1 + n_2
q(-2) = n_0 + n_1(-2) + n_2(-2)^2 = n_0 - 2n_1 + 4n_2

kaj la valoro n2 por ∞.

En la ekzemplo, la valoroj estas:

p(0) = m0 = 56789012
p(1) = m0 + m1 + m2 = 56789012 + 78901234 + 123456 = 135813702
p(-1) = m0 - m1 + m2 = 56789012 - 78901234 + 123456 = -21988766
p(-2) = m0 - 2m1 + 4m2 = 56789012 - 2×78901234 + 4×123456 = -100519632
p = m2 = 123456
q(0) = n0 = 54321098
q(1) = n0 + n1 + n2 = 54321098 + 43219876 + 98765 = 97639739
q(-1) = n0 - n1 + n2 = 54321098 - 43219876 + 98765 = 11199987
q(-2) = n0 - 2n1 + 4n2 = 54321098 - 2×43219876 + 4×98765 = -31723594
q = n2 = 98765

Kiel videblas, ĉi tiuj valoroj povas esti negativaj.

Por videbligi similecon de ĉi tiu komputo kun la rea komputo en unu el la sekvaj paŝoj, estas utile konsideri ĉi tiun komputon kiel matrico-vektora multipliko, kie ĉiu linio de la matrico enhavas potencojn de unu el la pritaksaj punktoj, kaj la vektoro enhavas la koeficientoj de la polinomo:


\begin{bmatrix}p(0) \\ p(1) \\ p(-1) \\ p(-2) \\ p_\infty \end{bmatrix} =
\begin{bmatrix}
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{bmatrix}
\begin{bmatrix}m_0 \\ m_1 \\ m_2\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
1 & -1 & 1 \\
1 & -2 & 4 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}m_0 \\ m_1 \\ m_2\end{bmatrix}

La dimensioj de la matrico estas d×km por p kaj d×kn por q. La linio por malfinio estas ĉiam kun nuloj ĉie krom 1 en la lasta kolumno.

Pli rapida pritakso[redakti | redakti fonton]

La kalkulado povas esti farita pli rapide ol senpere per la formuloj, se taŭge ordigi la operaciojn. La maniero donita de Bodrato por Toom-3 estas ĉi tie montrita, plenumata pot la unua multiplikato de la ekzemplo:

p0 = m0 + m2 = 56789012 + 123456 = 56912468
p(-1) = p0 - m1 = 56912468 - 78901234 = -21988766
p(1) = p0 + m1 = 56912468 + 78901234 = 135813702
p(-2) = (p(-1) + m2)×2 - m0 = (-21988766 + 123456)×2 - 56789012 = - 100519632
p(0) = m0 = 56789012
p = m2 = 123456

Ĉi tie p0 estas intera valoro dum la komputado.

Ĉi tiu vico postulas kvin adicion aŭ subtrahojn, kio estas je unu malpli ol en la simpla pritakso, ankaŭ la multipliko per 4 ne estas bezonata. Ĉi tiu plirapidigo ne influas asimptotan komplikecon de algortmo en okazo de konstanta k.

Multipliko je la punktoj[redakti | redakti fonton]

Malsimile al multiplikado la polinomoj p(x) kaj q(x), multiplikado de la komputitaj valoroj p(a) kaj q(a) estas nur multiplikado de entjeroj. Ĉi tio estas pli malgranda apero de la originala problemo. Oni rikure uzu la multiplikan proceduron pot multipliki valorojn je ĉiu pritaksa punkto, aŭ se la argumentoj iĝas sufiĉe pli malgranda, pli kompetenrtas uzi la longan multiplikon. La valoroj de la polinomo, respektiva al la produto, r(x)=p(x)q(x), estas en la ekzemplo:

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 = pq = 123456 × 98765 = 12193131840

Por sufiĉe grandaj nombroj, ĉi tio estas la plej multekosta paŝo de algoritmo, la nura paŝo kies komplikeco estas ne lineara de la amplekso de m kaj n.

Kalkulo de la polinomo respektiva al la produto[redakti | redakti fonton]

Ĉi tiu estas la paŝo la plej komplika je ideo, la rea al la pritaksa paŝo. Per donitaj d punktaj valoroj de r, oni bezonas komputi la koeficientojn de r. Por ĉi tio oni bezonas solvi ĉi tiun matrican ekvacion por la vektoro konsistanta el la koeficientoj de la polinomo r0... r4, kiu estas en la maldekstra flanko:


\begin{bmatrix}
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{bmatrix}
\begin{bmatrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{bmatrix} =
\begin{bmatrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r_\infty\end{bmatrix}

\begin{bmatrix}
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{bmatrix}
\begin{bmatrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{bmatrix} =
\begin{bmatrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r_\infty\end{bmatrix}

Ĉi tiu matrico estas konstruita la sama maniero kiel la tiu en la pritaksa paŝo, tamen ĝi estas de amplekso d×d. Oni povas solvi ĉi tiun ekvacion per gaŭsa eliminado, sed ĉi tio estas tro multekoste. Anstataŭe, oni inversigu la matricon. Se la pritaksaj punktoj estis elektitaj konvene, la inversa matrico enhavas nur sufiĉe simplajn erojn.


\begin{bmatrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{bmatrix} =
\begin{bmatrix}
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{bmatrix}^{-1}
\begin{bmatrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r_\infty\end{bmatrix} =
\begin{bmatrix}
 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{bmatrix}
\begin{bmatrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r_\infty\end{bmatrix}

Nun restas komputi ĉi tiu matrico-vektoran produton. Kvankam la matrico enhavas frakciojn, la rezultantaj koeficientoj estas entjeroj. La komputado povas esti farita per entjera aritmetiko, per adicioj kaj subtrahoj, kaj per multipliko kaj divido per malgrandaj konstantoj.

La kalkulado povas esti farita pli rapide ol senpere per la formuloj de matrica multipliko, se taŭge ordigi la operaciojn. La maniero donita de Bodrato por Toom-3 estas ĉi tie montrata, plenumata por la ekzemplo:

r0 = r(0) = 3084841486175176
r4 = r = 12193131840
r3 = (r(-2) - r(1))/3 = (3188843994597408 - 13260814415903778)/3
= -3357323473768790
r1a = (r(1) - r(-1))/2 = (13260814415903778 - (-246273893346042))/2
= 6753544154624910
r2a = r(-1) - r(0) = -246273893346042 - 3084841486175176
= -3331115379521218
r3 = (r2a - r3)/2 + 2r = (-3331115379521218 - (-3357323473768790))/2 + 2×12193131840
= 13128433387466
r2 = r2a + r1a - r = -3331115379521218 + 6753544154624910 - 12193131840
= 3422416581971852
r1 = r1a - r3 = 6753544154624910 - 13128433387466
= 6740415721237444

Ĉi tie r1a kaj r2a estas interaj valoroj dum la komputado.

La polinomo r estas do:

r(x) = 3084841486175176 + 6740415721237444x + 3422416581971852x2 + 13128433387466x3 + 12193131840x4

Se estus uzantaj malsamaj km, kn, aŭ pritaksaj punktoj, la matrico devus esti la alia; sed ĝi ne dependas de la multiplikatoj.

Komputado de la rezulto[redakti | redakti fonton]

Fine, necesas komputi r(B) kaj tiel ricevi la finan rezulton. Ĉi tio estas simpla pro tio ke B estas potenco de b kaj tiel la multiplikoj per potencoj de B estas ŝovoj de la ciferoj en bazo b:

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

La lasta nombro estas fakte produto de 1234567890123456789012 kaj 987654321987654321098.

Interpolaj matricoj por diversaj k[redakti | redakti fonton]

Ĉi tie estas priskribitaj komunaj interpolaj matricoj por kelkaj malsamaj komunaj malgrandaj valoroj de km kaj kn.

Toom-1[redakti | redakti fonton]

Toom-1 (km = kn = 1) postulas 1 pritaksan punkton, ĉi tie ĝi estas elektita al esti 0. Ĝi degeneriĝas al longa multipliko, kaj kiel la interpola matrico estas la identa matrico:

\begin{bmatrix}1\end{bmatrix}^{-1} =
\begin{bmatrix}1\end{bmatrix}

Toom-1.5[redakti | redakti fonton]

Toom-1.5 (km = 2, kn = 1) postulas 2 pritaksajn punktojn, ĉi tie ili estas elektitaj al esti 0 kaj ∞. Ĝi degeneriĝas al longa multipliko, kaj kiel la interpola matrico estas la identa matrico:

\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}^{-1} =
\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix}

Toom-2[redakti | redakti fonton]

Toom-2 (km = kn = 2) postulas 3 pritaksajn punktojn, ĉi tie ili estas elektitaj al esti 0, 1 kaj ∞. Ĝi estas la sama kiel multipliko de Karatsuba, kaj la interpola matrico estas

\begin{bmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}^{-1} =
\begin{bmatrix}
1 & 0 & 0 \\
-1 & 1 & -1 \\
0 & 0 & 1
\end{bmatrix}

Toom-2,5[redakti | redakti fonton]

Toom-2,5 (km = 3, kn = 2) postulas 4 pritaksajn punktojn, ĉi tie ili estas elektitaj al esti 0, 1, -1 kaj ∞. La interpola matrico estas

\begin{bmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 \\
0 & 0 & 0 & 1
\end{bmatrix}^{-1} =
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1/2 & -1/2 & -1 \\
-1 & 1/2 & 1/2 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]

  1. Tezo de Stephen Cook kun la algoritmo