Vidi fonton por Algoritmo de multiplikado

En [[matematiko]], '''multiplika algoritmo''' estas [[algoritmo]] (aŭ maniero) por [[multipliko|multipliki]] du nombroj.

== Longa multipliko ==

Se [[cifereca sistemo|pozicia cifereca sistemo]] estas uzata, natura vojo de multiplikado de nombroj estas instruata en lernejoj
kiel '''longa multipliko''': multipliki la unuan [[multiplikato]]n 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 [[entjero]]j. En la aliaj okazoj, la [[signumo]]jn kaj la poziciojn de la [[dekuma komo|dekumaj komoj]] estas konsideri aparte, kaj post la longa multipliko apliki al la rezulto.

=== Ekzemplo ===

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

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 spaco|logaritma spaca]] algoritmo; kio estas, algoritmo kiu nur bezonas por laboro spacon proporcian al la logaritmo de la kvanto de ciferoj en la enigo ''[[granda O|Θ]](log n)''. Ĉi tiu estas la duopa logaritmo de la multiplikitaj nombroj (''log log N''). Oni ne inkluzivas la enigajn aŭ eligajn bitojn 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 [[porto]]n 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 ''a<sub>i</sub>'' kaj ''b<sub>i</sub>'' respektive, kaj estu ''r<sub>i</sub>'' la ''i''-a bito de la rezulto, ĉiuj startante je ''i=0''. Tiam:

: <math>r_i = c + \sum_{j+k=i} a_j b_k</math>

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 ''r''<sub>''i''</sub> 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 ===

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

Multipliko de [[kompleksa nombro|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<sub>1</sub> = c · (a + b)''
: ''k<sub>2</sub> = a · (d - c)''
: ''k<sub>3</sub> = b · (c + d)''
: ''x = k<sub>1</sub> - k<sub>3</sub>''
: ''y = k<sub>1</sub> + k<sub>2</sub>''

Ĉ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 ''[[Granda O|Θ]](n<sup>log(3)/log(2)</sup>)≈Θ(n<sup>1,585</sup>)''
* [[Algoritmo de Toom-Cook]] havas polinoman tempon ''O(n<sup>1+ε</sup>)'' kie ''ε'' povas esti pozitiva arbitre malgranda. La relative simpla versio Toom-3 havas polinoman tempon ''Θ(n<sup>log(5)/log(3)</sup>)≈Θ(n<sup>1,465</sup>)''.
* 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 [[entjera troo|entjeran troon]] dum la procezo konturita pli sube. Tiam oni fendu la du nombroj en ''m'' grupojn po ''w'' bitoj:

: <math>a=\sum_{i=0}^m {2^{wi}a_i}</math>

: <math>b=\sum_{j=0}^m {2^{wj}b_j}</math>

Tiam

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

per meto ''b<sub>j</sub>=0'' kaj ''a<sub>i</sub>=0'' por ''j>m'', ''i>m'', ''k=i+j'' kaj ''{c<sub>k</sub>}'' estas la [[kunfaldaĵo]] de ''{a<sub>i</sub>}'' kaj ''{b<sub>j</sub>}''. Laŭ la [[kunfaldaĵa teoremo]] ''ab'' povas esti komputita kiel

# Komputado de la [[rapida konverto de Fourier|rapidaj konvertoj de Fourier]] de ''{a<sub>i</sub>}'' kaj ''{b<sub>j</sub>}'';
# Intermultiplikado de la du rezultoj elemento per elemento;
# Komputado de la inversa konverto de Fourier;
# Adicio de la parto de ĉiu ''c<sub>k</sub>'' kiu estas pli granda ol ''2<sup>w</sup>'' al ''c<sub>k+1</sub>''.

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<sup>Θ(log<sup>*</sup>(n))</sup>'' uzante konvertoj de Fourier super kompleksaj nombroj. Anindya De, Chandan Saha, Piyush Kurur kaj Ramprasad Saptharishi donis similan algoritmon uzantan [[modula aritmetiko|modulan aritmetikon]] en 2008, atingantan la saman rulan tempon.

Uzo de [[nombro-teoria konverto|nombro-teoriaj konvertoj]] anstataŭ [[diskreta konverto de Fourier|diskretaj konvertoj de Fourier]] evitas [[ondiga eraro|rondigajn erarajn]] problemojn per uzo de [[modula aritmetiko]] anstataŭ [[kompleksa nombro|kompleksaj nombroj]].

== Kvadrata multiplikado ==

: <math>
\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
</math>

Kvadrataj multiplikiloj estis unuaj uzataj por faro de produto de du analogaj enigaj signaloj en [[analoga komputilo|analogaj komputiloj]]. En ĉi tiu apliko, la sumo kaj diferenco de du enigaj [[elektra tensio|elektraj tensioj]] estas formataj per [[operacia amplifilo|operaciaj amplifiloj]]. La ĉiu kvadrato estas aproksimata per [[popeca lineara funkcio|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 ==

* [http://www.nychold.com/em-arith.html Baza aritmetiko]
* [http://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication%20Algorithms Plibonigitaj algoritmoj]
* [http://techref.massmind.org/techref/method/math/muldiv.htm Ŝovo kaj adicio] de G. Reichborn-Kjennerud

[[Kategorio:Nombraj teoriaj algoritmoj]]