Disdivido de multiplikatoj

La unua paŝo estas elekti la bazon B = bⁱ, 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:

${\displaystyle 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 = b^6/3 = 10⁸. Oni tiam apartigu la nombrojn m kaj n en iliajn ciferoj en bazo B, m_i kaj n_i por i=0 ... k-1:

m₂ = 123456

m₁ = 78901234

m₀ = 56789012

n₂ = 98765

n₁ = 43219876

n₀ = 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) = m₂x² + m₁x + m₀ = 123456x² + 78901234x + 56789012

q(x) = n₂x² + n₁x + n₀ = 98765x² + 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 k_m kaj k_n. Ekzemple, la algoritmo "Toom-2,5" estas tiu kun k_m=3 kaj k_n=2. En ĉi tiu okazo la i en B = bⁱ estas tipe elektata kiel

${\displaystyle 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=k_m+k_n-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)/(x^grado(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:

${\displaystyle p(0)=m_{0}+m_{1}(0)+m_{2}(0)^{2}=m_{0}}$

${\displaystyle p(1)=m_{0}+m_{1}(1)+m_{2}(1)^{2}=m_{0}+m_{1}+m_{2}}$

${\displaystyle p(-1)=m_{0}+m_{1}(-1)+m_{2}(-1)^{2}=m_{0}-m_{1}+m_{2}}$

${\displaystyle p(-2)=m_{0}+m_{1}(-2)+m_{2}(-2)^{2}=m_{0}-2m_{1}+4m_{2}}$

kaj la valoro m₂ por ∞.

kaj analoge por q:

${\displaystyle q(0)=n_{0}+n_{1}(0)+n_{2}(0)^{2}=n_{0}}$

${\displaystyle q(1)=n_{0}+n_{1}(1)+n_{2}(1)^{2}=n_{0}+n_{1}+n_{2}}$

${\displaystyle q(-1)=n_{0}+n_{1}(-1)+n_{2}(-1)^{2}=n_{0}-n_{1}+n_{2}}$

${\displaystyle q(-2)=n_{0}+n_{1}(-2)+n_{2}(-2)^{2}=n_{0}-2n_{1}+4n_{2}}$

kaj la valoro n₂ 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:

${\displaystyle {\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×k_m por p kaj d×k_n por q. La linio por malfinio estas ĉiam kun nuloj ĉie krom 1 en la lasta kolumno.

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 kompetenrtas 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 r₀... r₄, kiu estas en la maldekstra flanko:

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

${\displaystyle {\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.

${\displaystyle {\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 r_1a kaj r_2a estas interaj valoroj dum la komputado.

La polinomo r estas do:

r(x) = 3084841486175176 + 6740415721237444x + 3422416581971852x² + 13128433387466x³ + 12193131840x⁴

Se estus uzantaj malsamaj k_m, k_n, 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.

Toom-1

Toom-1 (k_m = k_n = 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:

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

Toom-1.5

Toom-1.5 (k_m = 2, k_n = 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:

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

Toom-2

Toom-2 (k_m = k_n = 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

${\displaystyle {\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 (k_m = 3, k_n = 2) postulas 4 pritaksajn punktojn, ĉi tie ili estas elektitaj al esti 0, 1, -1 kaj ∞. La interpola matrico estas

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