31. 12. 2007

Násobenie v assembleri

(Mikezt, 2004/12/02)

Zdá se, že nadešel čas zaplácnout nicnedění na našem webu sérií starších článků z předchozí verze webu. Něco zmizelo v propadlišti dějin, něco se opět objeví.
Určite ste sa niekedy trápili nad otázkou násobenia čísiel v assembleri. V prvom rade človeka napadne použitie definície násobenia: A*B je A-násobný súčet čísla B. Čísla A a B voláme činitele súčinu a výsledok operácie násobenie súčin. A hľa, padne do oka programátorovi inštrukcia djnz a stvorí niečo podobné:


ld b,A
ld e,B
ld d,0
ld l,d
ld h,d
MULTIPLY add hl,de
djnz MULTIPLY

Program je na prvý pohľad správny, ale čo ak chceme násobiť nulou v premennej A? Túto situáciu budeme musieť ošetriť. Taktiež sa náš programátor zamyslí a porozmýšľa, či by nebolo výhodnejšie testovať, ktorá premenná je menšia a podľa nej riadiť cyklus. Program sa nám začne komplikovať a teda sa skúsime vrátiť na začiatok a znovu popremýšľať (pozn. koho by to snáď bolelo, premýšľať nemusí, ale čítať ďalej mu odporúčam).

Definície sú síce pekné, ale v praxi sa im snažíme oblúkom vyhýbať (hlavne preto, že definície tvoria tí hlúpi inžinieri, ktorí nevedia, aké je to ťažké pracovať vlastnými rukami). Pozrime sa, ako nás pani učiteľka učila násobiť na prvom stupni základnej školy.

Oba činitele si napíšeme pod seba. Zo spodného činiteľa zoberieme poslednú číslicu a vynásobíme ju poslednou číslicou horného činiteľa. Dostaneme zväčša dvojciferný výsledok. Číslo na menej významnom mieste podpíšeme pod oba činitele a číslo na významnejšom mieste si zapamätáme. Ak dostaneme len jednociferné číslo, zapamätáme si číslo nula. Ďalej pokračujeme tak, že poslednou číslicou zo spodného činiteľa násobíme všetky ostatné číslice horného činiteľa a k výsledku pripočítame naše zapamätané číslo. Ak sme vynásobili poslednou číslicou spodného činiteľa všetky číslice horného činiteľa, presunieme sa na ďaľšiu číslicu a postup opakujeme pre túto číslicu, s tým rozdielom, že výsledok zapisujeme už pod vypočítaný výsledok o jeden rád posunutý. Nakoniec sčítame všetky riadky, ktoré vypočítame pod oboma činiteľmi a dostaneme výsledok násobenia.

Verím, že ste predchádzajúci odstavec vôbec nepochopili a to viete aj ručne násobiť (priznávam, odflákol som to). Preto si to ukážeme v praxi:

     89
53
--
267
445
----
4717

K čomu je to ale dobré pri násobení v assembleri? Nuž, počítač je tvor zaujímavý a ľudskému slovu a písmu nerozumie. Skúsme uvedený spôsob násobenia preložiť do počítačových núl a jednotiek:

         1011001 x 110101 = 1001001101101
-------
1011001
0000000
1011001
0000000
1011001
1011001
-------------
1001001101101

Náš bystrý programátor si určite všimol krásy takéhoto spôsobu násobenia, pretože k násobeniu nám bude stačiť rotácia a súčet. Skúsme si teda napísať rutinku:

vstup: e,a
vystup: hl
nici: hl, de, a

     ld hl,0
ld d,l
rra
jr nc, N1
add hl,de
or a
N1 rl e
rl d
rra
...

V rutinke sa opakuje 8x to isté, blok začína rra, končí rl d.

Niečo podobné si náš programátor ale všimol niekde na internete. Určite to nebola žiadna poznamka, ani porno stránka. Určite to boli Bazeho z80 bits a rutinka Classic 8-bit * 8-bit Unsigned Multiplication. Tu ju máte:

Vstup: H, E = činitele súčinu, L = 0, D = 0
Výstup: HL = súčin

   sla   h         ; optimalizovaná prvá iterácia
jr nc,$+3
ld l,e
add hl,hl ; opíąte 7 krát
jr nc,$+3
add hl,de

Ak by Vás napadol ďaľší zaujímavý spôsob násobenia (a vôbec nemusí byť rýchlejší, alebo kratší), ozvite sa niektorému členovi MB Maniax, alebo mne (kontakt na mňa nájdete na http://zeroteam.sk/). Veľa šťastných súčinov Vám praje Mike/ZT

Žádné komentáře: