Algoritmo de multiplikado

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

En matematiko, multiplika algoritmo estas algoritmo (aŭ maniero) por multipliki du nombroj.

Longa multipliko[redakti | redakti fonton]

Se pozicia cifereca sistemo estas uzata, natura vojo de multiplikado de nombroj estas instruata en lernejoj kiel longa multipliko: multipliki la unuan multiplikaton per ĉiu cifero de la alia multiplikanto kaj tiam adicii ĉiujn propre ŝovitajn rezultojn. Ĝi postulas memorigon de la multiplika tabelo por solaj ciferoj.

Ĉi tiu estas la kutima algoritmo por multiplikante permane en bazo 10. Komputiloj normale uzi tre similan ŝovan kaj adician algoritmon en bazo 2.

La algoritmo funkciaj kun nenegativaj entjeroj. En la aliaj okazoj, la signumojn kaj la poziciojn de la dekumaj komoj estas konsideri aparte, kaj post la longa multipliko apliki al la rezulto.

Ekzemplo[redakti | redakti fonton]

Ĉi tiu ekzemplo uzas la longan multiplikon al multipliki 23958233 kaj 5830.

    23958233
        5830 ×
------------
    00000000 (= 23958233 × 0)
   71874699 (= 23958233 × 30)
 191665864 (= 23958233 × 800)
119791165 (= 23958233 × 5000)
------------
139676498390

kaj do la produto estas 139676498390.


Oni deziru multipliki 239582,33 kaj -5,830.

La signumo de la rezulto estos (+1)×(-1)=(-1)

La dekuma komo estas en la 2-a pozicio en unua multiplikato kaj en 3-a pozicio en la dua multiplikato; do ĝi estos en pozicio 2+3=5 en la produto.

Multipliku la nombrojn sen signumoj kaj komoj (vidu la antaŭan ekzemplon) 23958233×5830=139676498390.

Apliku la signumon kaj komon, kaj do la rezulto estas -1396764,98390

Spaca komplikeco[redakti | redakti fonton]

Estu n tuteca kvanto de bitoj en la du enigaj nombroj. Longa multipliko havas la avantaĝon ke ĝi povas facile esti formulita kiel logaritma spaca algoritmo; kio estas, algoritmo kiu nur bezonas por laboro spacon proporcian al la logaritmo de la kvanto de ciferoj en la enigo Θ(log n). Ĉi tiu estas la duopa logaritmo de la multiplikitaj nombroj (log log N). Oni ne inkluzivas la enigajn aŭ eligajn bitojm en ĉi tiu mezuro, pro tio ke ili devus bagatele fari la spacan bezonon linearan; anstataŭe oni faras la enigajn bitoj nur-legajn kaj la eligajn bitojn nur-skribajn.

La maniero estas simpla: oni adiciu la kolumnojn de dekstro al maldekstro, konservanta la porton kiel la kalkulado ruliĝas. Oni ne devas konservi la kolumnojn por fari ĉi tion. Estu la i-a bito de la dekstro de la unua kaj dua argumentoj signifitaj ai kaj bi respektive, kaj estu ri la i-a bito de la de la rezulto, ĉiuj startante je i=0. Tiam:

r_i = c + \sum_{j+k=i} a_j b_k

kie c estas la porti de la antaŭa kolumno. Pro tio ke nek c nek la tuteca sumo superas logaritman spaco, oni povas realigi ĉi tiun formulon en logaritma spaco, pro tio ke ankaŭ ĉiu el la indeksoj j kaj k havi O(log n) bitoj.

Indukto montras ke la porto ne povas superi n kaj la tuteca sumo por ri ne povas superi 2n: la porto enen la unua kolumno estas nulo, kaj por ĉiuj aliaj kolumnoj, estas maksimume n bitoj en la kolumno, kaj porto de maksimume n venanta al la antaŭa kolumno (per la indukta hipotezo). Ilia sumo estas maksimume 2n, kaj la porto al la venonta kolumno estas maksimume duono de ĉi tiu, aŭ n. Tial ambaŭ ĉi tiuj valoroj povas esti konservitaj en O(log n) bitoj.

En pseŭdokodo, la logaritmo-spaca algoritmo estas:

multipliki (a[0..n-1], b[0..n-1]) // Tabeloj prezentantaj la duumajn prezentojn
  x ← 0 // porto
  por i ekde 0 al 2n-1
   por j ekde 0 al i
     k ← i - j
     x ← x + (a[j] × b[k])
   rezulto[i] ← x mod 2
   x ← planko(x/2)

Ŝovo kaj adicio[redakti | redakti fonton]

Komputiloj uzas ŝovan kaj adician algoritmon por multiplikado de malgrandaj entjeroj, kio estas la longa multipliko kun bazo 2.

En bazo 2, multipliko per la sola cifero de la multiplikanto malpligrandiĝas al la logika KAJ operacio. Ĉiu parta produto estas adiciata al parta sumo tuj kiam ĉiu parta produto estas komputata.

Ekzemple, estas kelkaj manieroj al multipliki per 10 uzante nur bitajn ŝovojn kaj adiciojn.

((x << 2) + x) << 1
(x << 3) + (x << 1)

Kompleksa multipliko[redakti | redakti fonton]

Multipliko de kompleksaj nombroj (x + iy) = (a + ib) · (c + id) normale engaĝas kvar multiplikojn:

x = ac - bd
y = ad + bc

En 1805 Carl Friedrich Gauss esploris manieron de malpligrandigo de la kvanto de multiplikoj al tri. Per la gaŭsa kompleksa multiplika algoritmo la produto povas esti kalkulita jene:

k1 = c · (a + b)
k2 = a · (d - c)
k3 = b · (c + d)
x = k1 - k3
y = k1 + k2

Ĉi tiu algoritmo uzas nur tri multiplikojn, anstataŭ kvar, kaj kvin adiciojn aŭ subtrahoj anstataŭ du. Se multipliko estas pli multekosta ol tri adicioj aŭ subtrahoj, kiel estas en kalkulado permane, tiam estas gajno en rapido. Sur modernaj komputiloj multiplikoj kaj adicioj povas preni proksimume la saman tempon, tiel tie povas ne esti gajno en rapido. En la maniero povas esti iu malprofito ĉe precizeco se estas uzata flosanta punkto.

Aliaj algoritmoj[redakti | redakti fonton]

Ekzistas algoritmoj de multiplikado de grandaj nombroj, asimptote pli rapidaj ol la longa multipliko, kvankam la pliaj rapideco estas atingata je kosto de komplikeco de algoritmo.

La ideo, de Volker Strassen (1968), estas jena: oni elektu la plej grandan entjeron w kiu ne kaŭzas entjeran troon dum la procezo konturita pli sube. Tiam oni fendu la du nombroj en m grupojn po w bitoj:

a=\sum_{i=0}^m {2^{wi}a_i}
b=\sum_{j=0}^m {2^{wj}b_j}

Tiam

ab=\sum_{i=0}^m \sum_{j=0}^m 2^{w(i+j)}a_i b_j = \sum_{k=0}^{2m} 2^{wk} \sum_{i=0}^k a_i b_{k-i} = \sum_{k=0}^{2m} 2^{wk} c_k

per meto bj=0 kaj ai=0 por j>m, i>m, k=i+j kaj {ck} estas la kunfaldaĵo de {ai} kaj {bj}. Laŭ la kunfaldaĵa teoremo ab povas esti komputita kiel

  1. Komputado de la rapidaj konvertoj de Fourier de {ai} kaj {bj};
  2. Intermultiplikado de la du rezultoj elemento per elemento;
  3. Komputado de la inversa konverto de Fourier;
  4. Adicio de la parto de ĉiu ck kiu estas pli granda ol 2w al ck+1.

Por multaj jaroj, la plej rapida sciata maniero bazita sur ĉi tiu ideo estis priskribita en 1971 de Arnold Schönhage kaj Volker Strassen (algoritmo de Schönhage-Strassen) kaj havas polinoman tempon de Θ(n log(n) log(log(n))). En 2007 ĉi tio estis plibonigita de Martin Fürer (algoritmo de Fürer) kaj havas polinoman tempon n log(n) 2Θ(log*(n)) uzante konvertoj de Fourier super kompleksaj nombroj. Anindya De, Chandan Saha, Piyush Kurur kaj Ramprasad Saptharishi donis similan algoritmon uzantan modulan aritmetikon en 2008, atingantan la saman rulan tempon.

Uzo de nombro-teoriaj konvertoj anstataŭ diskretaj konvertoj de Fourier evitas rondigajn erarajn problemojn per uzo de modula aritmetiko anstataŭ kompleksaj nombroj.

Kvadrata multiplikado[redakti | redakti fonton]


\frac{1}{4}\left(\left(x+y\right)^2 - \left(x-y\right)^2\right) =
\frac{1}{4}\left(\left(x^2+2xy+y^2\right) - \left(x^2-2xy+y^2\right)\right) =
\frac{1}{4}\left(4xy\right) = xy

Kvadrataj multiplikiloj estis unuaj uzataj por faro de produto de du analogaj enigaj signaloj en analogaj komputiloj. En ĉi tiu apliko, la sumo kaj diferenco de du enigaj elektraj tensioj estas formataj per operaciaj amplifiloj. La ĉiu kvadrato estas aproksimata per popecaj linearaj cirkvitoj. Fine la diferenco de la du kvadratoj estas formata kaj skalata per faktoro ankaŭ per operacia amplifilo.

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]