Algoritmo de Toom-Cook

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 .

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 
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

Ĉ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 
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 ciferojn 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 
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:

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 
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:

Ĉ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 
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 kompetentas uzi la longan multiplikon. La valoroj de la polinomo, respektiva al la produto, *r(x)=p(x)q(x)*, estas en la ekzemplo:

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 
Ĉ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:

Ĉ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 
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*:

La lasta nombro estas fakte produto de 1234567890123456789012 kaj 987654321987654321098.

## Interpolaj matricoj por diversaj *k* 
Ĉi tie estas priskribitaj komunaj interpolaj matricoj por kelkaj malsamaj komunaj malgrandaj valoroj de *km* kaj *kn*.

### Toom-1 
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 
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 
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 
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ŭ 
* Longa multipliko
* Algoritmo de Karacuba

## Eksteraj ligiloj 
* M. Bodrato. *Al optimala multipliko de Toom-Cook...''. En WAIFI'07, Springer, 2007.
* Toom-3 en dokumentaroj de GMP
* Toom-4 en dokumentaroj de GMP

Kategorio:Nombraj teoriaj algoritmoj