Algoritmo de multiplikado

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.

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 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 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 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 a_i kaj b_i respektive, kaj estu r_i la i-a bito 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 r_i 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 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:

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

Komputado de la rapidaj konvertoj de Fourier de {a_i} kaj {b_j};
Intermultiplikado de la du rezultoj elemento per elemento;
Komputado de la inversa konverto de Fourier;
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

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