Dělení INP 2008 FIT VUT v Brně
Dělení čísel s pevnou řádovou čárkou Nejdříve se budeme zabývat dělením čísel s pevnou řádovou čárkou bez znaménka. Pro jednotlivé činitele operace dělení zavedeme symboly D
dělenec
d
dělitel
Q
podíl
qi
i-tý bit podílu
Ri
i-tý (průběžný) zbytek
Máme tedy vypočítat Q, R tak, aby byla splněna rovnice D = Q .d + R,
0 ≤ |R| < d.
Pro d, Q, R máme k dispozici n bitů, pro D vyhradíme 2n bitů. Nejdříve si ukážeme dělení čísel bez znamének, resp. dělení jejich absolutních hodnot.
2
Příklad 38:5
V kroku i se pokoušíme odečíst od průběžného zbytku Ri posunutý dělitel 2-i d D=100110 d=101 (n=3, 2n=6) Q= qn … q0 = q3 q2 q1 q0 = 0111 i=0 i=1 i=2 i=3
1. 100110 -000000 100110 -010100 010010 -001010 001000 -000101 011
2. R0=D q320d R1 q22-1d R2 q12-2d R3 q02-3d R=R4
Ri+1= Ri - qn-i2-id
3. 2-id > Ri (5.) 2-id < Ri
4. => qn-i= q3 =0
2-id < Ri
=> qn-i = q1 =1
2-id < Ri
=> qn-i = q0 =1
=> qn-i = q2 =1
3
Postup rozhodování při dělení Při rozhodování o hodnotě bitu podílu q n-i jsme postupovali podle vztahů: je-li 2-i d menší než Ri, pak qn-i = 1, je-li 2-i d větší než Ri, pak qn-i = 0 ------------------------------------------------------------------------------------------------------Tedy Q = q3q2q1q0 = 0111. Nový zbytek se vypočte: Ri+1 := Ri - qn-i 2-i d V praxi se posouvá dílčí/průběžný zbytek vlevo, d je v pevné poloze, takže Ri+1 := 2Ri - qn-i d
4
Dělení – modifikovaný postup (Praxe: posuv Ri vlevo, d v pevné poloze)
D=100110 d=101 (n=3, 2n=6) Q= qn … q0 = q3 q2 q1 q0 = 0111 i=0 i=1
i=2
i=3
100110 -000 100110 100110x -101000 10010x 10010xx -101000 1000xxx 1000xxxx -101000 011xxxx
2R0=D q3 d R1 2R1 q2 d R2 2R2 q1 d R3 2R3 q0 d R4 =24R
Ri+1= 2Ri - qn-id
d > 2R0
=>
Q=0
d < 2R1
=>
Q=01
d < 2R2
=>
Q=011
d < 2R3
=>
Q=0111
=> R = 2-4R4 5
Pravidlo pro určení q n-i Pravidlo pro určení q n-i : když d je větší než 2Ri, pak qn-i = 0 jinak qn-i = 1 ---------------------------------------------------V praxi se porovnávání čísel založené na použití komparátorů nepoužívá. Odečtení se provede (zkusmo), tedy když 2Ri - d je menší než 0, pak qn-i = 0 jinak qn-i = 1 -----------------------------------------------------------
6
Dva postupy dělení Máme k dispozici dva hlavní algoritmy dělení: a) Je-li qn-i = 0, je výsledek "zkušebního" odečtení Ri+1’ = 2Ri - d, správný zbytek má být Ri+1 = 2Ri. Správný zbytek dostaneme opravou přičtením +d, což nazýváme restaurací nezáporného zbytku (návrat k nezápornému zbytku), tedy Ri+1 := Ri+1’ + d. Je-li pravděpodobnost výskytu jedničky v podílu Q rovna p(qn-i = 1) = 1/2, potřebujeme pro n odečtení v průměru ještě n/2 krát přičítat. Grafické znázornění dělení s restaurací nezáporného zbytku je na následujícím obrázku. b) Postup bez restaurace nezáporného zbytku (bez návratu k nezápornému zbytku). Restaurací provádíme operaci Ri := Ri’ + d. V dalším kroku po odečtení d dostaneme Ri+1 := 2Ri - d (1) nebo po přičtení d Ri+1 := 2Ri + 2d - d = 2Ri + d (2) Vidíme, že můžeme postupovat podle rovnic (1), (2): když qn-i = 1 (Ri větší než 0), použijeme vztah (1), když qn-i = 0, použijeme vztah (2). Postup je úspornější, protože v každém kroku pak jen přičítáme d, nebo odčítáme d, nikdy neprovádíme obě operace. Při dělení bez restaurace tedy provedeme n aritmetických operací (+ nebo -), pro dělení s restaurací 3/2 n operací. 7
Grafické znázornění dělení s restaurací 0
D -d +d
0 r1
r 2
x2 2r 1 -d
1
x2 2r 2
-d +d
0 r3
r 4
r 5
x2
2r3 -d
x2 2r 4 -d
1
1 konverguje k nezápornému zbytku
t
8
Příklad: Dělení bez návratu k nezápornému zbytku D = 1100001 = (97)10, d = 1010 = (10)10, v bitu S se zaznamenává znaménko průběžného zbytku a to pak rozhoduje o následující operaci (+ -). krok S A Q ---------------------------------------------------------------------------0 0 1100 001x = D 1 -1010 -d --------0 0 0010 001x q3 = 1 Pos. vl. 0100 01xx 2 -1010 -d --------1 1 1010 01xx q2 = 0 Pos. vl. 0100 1xxx 3 +1010 +d --------1 0 1110 1xxx q1 = 0 Pos. vl. 1101 xxxx 4 +1010 +d --------0 1 0111 xxxx q0 = 1 R Q = 1001 9
30=00011110, 7=0111, -7=1001 00011110 +1001 -d 10101110 <0 => c4 = 0 0101110x posuv <+0111 +d 1100110x <0 => c3 = 0 100110xx posuv +0111 +d 000010xx >0 => c2 = 1 00010xxx posuv +1001 -d 10100xxx <0 => c1 = 0 0100xxxx posuv +0111 +d 1011xxxx <0 => c0 = 0 +0111 +d (korekce na kladný zbytek) 0010xxxx zbytek 2
Příklad: 30:7=4, zb 2 bez návratu k nezápornému zbytku
10
Dělení bez restaurace – poslední zbytek je kladný Vyjde-li poslední zbytek záporný, musí se upravit na nezáporné číslo korekcí, tedy přičtením dělitele. Grafické znázornění dělení bez restaurace nezáporného zbytku pro případ kladného a záporného posledního zbytku: 0 D -d x2 2r 1
+d r2 -d
1 x2 2r 2 0
r3
x2 2r 3
0
r1
+d r4
1 kladný zbytek
t 11
Dělení bez restaurace – poslední zbytek je záporný 0
D
-d 2r 1
0
r1
+d
1 r2
x2
2r3
2r 2
-d r3
0
+d záporný zbytek!
0
r4 +d
korekce
korekce
r4kor t 12
Dělení SRT - tabulka odhadů podle tří bitů R i Dělení čísel se znaménkem se po dlouhou dobu převádělo na dělení absolutních hodnot a dodatečné určení znaménka výsledku. Tuto nedokonalost odstranil algoritmus SRT autorů Sweeneyho, Robertsona a Tochera (1958). Prováděné operace se pro každý krok určují například (je to školní příklad) podle nejvyšších tří bitů průběžného zbytku Ri.
Ri
d>0 bit podílu
d>0 operace
d<0 bit podílu
d<0 operace
000 111
0
posuv vlevo
0
posuv vlevo
001 010 011
1
-d, posuv vlevo
-1
+d, posuv vlevo
101 110 100
-1
+d, posuv vlevo
1
-d, posuv vlevo
13
49=00110001, 7=0111, -7=1001 -49=11001111 (d>0) -1
+1
0 +1
-1
11001111 0111 00111111 0111111x 1001 0000111x 000111xx 00111xxx 1001 11001xxx 1001xxxx 0111 0000xxxx zbytek 0
Příklad: -49:7=-7, zb. 0 SRT
+d <-d <<-d <+d
Ri
d>0 bit podílu
d>0 operace
d<0 bit podílu
d<0 operace
000 111
0
posuv vlevo
0
posuv vlevo
001 010 011
1
-d, posuv vlevo
-1
+d, posuv vlevo
101 110 100
-1
+d, posuv vlevo
1
-d, posuv vlevo
Q = -1 1 0 1 –1 = = -16+8+0+2-1 = -7 14
Zdokonalený algoritmus dělení SRT Odhad podle tří bitů průběžného zbytku je nedostatečný a způsobuje časté chybování postupu SRT. Praktické realizace postupu (např. Pentium) odhadují hodnotu číslice podílu více bitů průběžného (okamžitého) zbytku, a podle více bitů dělitele. Je to aplikace principu zobecněného ukazatele do tabulky odhadů. Například v Pentiu se odhaduje číslice podílu podle 7 bitů průběžného zbytku a podle 5 bitů hodnoty dělitele. Jinou modifikací algoritmu dělení je postup „2 bity najednou“, tedy s radixem 4. Obecný vzorec:
r – radix Ri+1 = rRi – qn-i d
15
Chyba dělení u Pentia (listopad 1994) $475M
16
Obvodová realizace dělení - sekvenční dělička SRT posuv P
Dělenec D
A B
0 n-1
n n-1n-2
10
n bitů n bitů
n bitů
operace +/-/ prázdná řízení operací
n-1
0
BA dělitel d 17
Postup sekvenčního dělení 0. Má-li dělenec D i dělitel d k levostranných nul, posunou se obsahy registrů PA i B o k bitů vlevo. V této fázi lze v zájmu zrychlení operace dělení odstranit levostranné nuly dělence nebo dělitele posuvem obsahu příslušného registru vlevo. To se však na závěr musí kompenzovat odpovídajícím posuvem výsledku. 1. Je-li pn = pn-1 = pn-2, pak qn-i = 0 posuv registru PA o 1 bit vlevo Je-li pn = 0 pak qn-i = 1, odečtení PA - B, posuv registru PA o 1 bit vlevo Je-li pn = 1 pak qn-i = -1, přičtení PA + B, posuv registru PA o 1 bit vlevo Krok 1 provedeme celkem (n - k) krát. 2. Je-li koncový zbytek menší než nula, přičti P + B a odečti Q-1.
18
Kombinační dělička s restaurací – odečítačka x - bit dělence y - bit dělitele u - výstup výpůjčky t - vstup výpůjčky D a - řídicí signál
a - řídicí signál
y - bit dělitele z - výstup rozdílu
kde x je vstup jednoho bitu dělence, y je vstup jednoho bitu dělitele, t je vstup výpůjčky, a je řídící vstup (0 odčítej, 1 neodčítej), který vede i do sousední buňky vpravo, z je výstup rozdílu, u výstup výpůjčky. Rovněž bit dělitele y je veden do sousední buňky dole. Pro a = 0 se odečítá, tedy z = x - (y + t), pro a = 1 se neodečítá, tedy z = x. Funkci odečítačky definuje pravdivostní tabulka.
19
Pravdivostní tabulka odečítačky
Dostáváme tak rovnice z = x ⊕ a‘ ( y ⊕ t )
(a je řídicí vstup: 0 odčítej, 1 neodčítej),
u = x’ y + x‘ t + yt 20
Obvodová dělička s restaurací D D5
D6 d2
d1
D4 d0
x - bit dělence y - bit dělitele
=d
u - výstup výpůjčky t - vstup výpůjčky D
q4
q3
q2 q1 q0
D
D
a - řídicí signál
D D3
D
D
D
D
D
D
D
a - řídicí signál
y - bit dělitele z - výstup rozdílu
D2 D D1
D
D
D
D D0
D
D r2
D
D
r1
r0
R 21
Obvodová dělička s restaurací - komentář Shora vstupují do kaskády odečítaček jednotlivé bity dělence D, bity 6 až 0, a tříbitový dělitel d. Na levé straně vystupují jednotlivé bity kvocientu Q. Počet řádků kaskády je dán potřebným počtem operací odečítání, oby se poloha tříbitového dělitele dostala do nejnižšího řádu dělence. V této poloze vznikne poslední průběžný rozdíl, tedy konečný zbytek. Jde o kombinatorické dělení podle postupu „s návratem k nezápornému zbytku“, protože v každé operační úrovni vzniká nezáporný výsledek – pokud by vznikl po odečtení záporný mezivýsledek, neodečítá se, tedy „nejde odečíst“.
22
