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

Longa multipliko

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.

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

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)

Kompleksa multipliko

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:

k₁ = c · (a + b)

k₂ = a · (d - c)

k₃ = b · (c + d)

x = k₁ - k₃

y = k₁ + k₂

Ĉ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

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.

• Algoritmo de Karacuba havas polinoman tempon Θ(n^{log(3)/log(2)})≈Θ(n^1,585)
• Algoritmo de Toom-Cook havas polinoman tempon O(n^1+ε) kie ε povas esti pozitiva arbitre malgranda. La relative simpla versio Toom-3 havas polinoman tempon Θ(n^{log(5)/log(3)})≈Θ(n^1,465).
• Algoritmoj bazitaj sur la rapida konverto de Fourier:

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:

${\displaystyle a=\sum _{i=0}^{m}{2^{wi}a_{i}}}$

${\displaystyle b=\sum _{j=0}^{m}{2^{wj}b_{j}}}$

Tiam

${\displaystyle 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 b_j=0 kaj a_i=0 por j>m, i>m, k=i+j kaj {c_k} estas la kunfaldaĵo de {a_i} kaj {b_j}. Laŭ la kunfaldaĵa teoremo ab povas esti komputita kiel

1. Komputado de la rapidaj konvertoj de Fourier de {a_i} kaj {b_j};
2. Intermultiplikado de la du rezultoj elemento per elemento;
3. Komputado de la inversa konverto de Fourier;
4. Adicio de la parto de ĉiu c_k kiu estas pli granda ol 2^w al c_k+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

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

• Glitkalkulilo
• Polinoma multipliko
• Matrica multipliko
• Polinoma divido
• Faktorigo de entjero - la rea tasko al multiplikado

Eksteraj ligiloj

• Baza aritmetiko
• Plibonigitaj algoritmoj
• Ŝovo kaj adicio de G. Reichborn-Kjennerud