Dělení

INP 2008FIT VUT v Brně

2

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.

3

Příklad 38:5V 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 Ri+1= Ri - qn-i2-id

1. 2. 3. 4.

i=0 100110 R0=D 2-id > Ri => qn-i= q3 =0-000000 q320d (5.)

i=1 100110 R1 2-id < Ri => qn-i = q2 =1-010100 q22-1d

i=2 010010 R2 2-id < Ri => qn-i = q1 =1-001010 q12-2d

i=3 001000 R3 2-id < Ri => qn-i = q0 =1-000101 q02-3d

011 R=R4

= 0111

4

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

5

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 Ri+1= 2Ri - qn-id

i=0 100110 2R0=D d > 2R0 => Q=0-000 q3d

i=1 100110 R1

100110x 2R1 d < 2R1 => Q=01-101000 q2d

i=2 10010x R2

10010xx 2R2 d < 2R2 => Q=011-101000 q1d

i=3 1000xxx R3

1000xxxx 2R3 d < 2R3 => Q=0111-101000 q0d011xxxx R4 =24R => R = 2-4R4

= 0111

6

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

7

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 z bytku), 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 ne zápornému zbytku) .

Restaurací provádíme operaci Ri := Ri’ + d. V dalším kroku po odečtení ddostaneme

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 naritmetických operací (+ nebo -), pro dělení s restaurací 3/2 n operací.

8

Grafické znázornění dělení s restaurací 0 D

x2

-d +d

r

-d r

x2

2r

2r

-d +d

r 2r

-d r

x2 2r

-d r 5

4

3

2

1

1

x2 2

3

4

0

1

0

1

1

t

konverguje k nezápornému zbytku

9

Příklad: Dělení bez návratu k nezápornému zbytkuD = 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 = D1 -1010 -d

---------0 0 0010 001x q3 = 1

Pos. vl. 0100 01xx2 -1010 -d

---------1 1 1010 01xx q2 = 0

Pos. vl. 0100 1xxx3 +1010 +d

---------1 0 1110 1xxx q1 = 0

Pos. vl. 1101 xxxx4 +1010 +d

---------0 1 0111 xxxx q0 = 1

R Q = 1001

10

Příklad: 30:7=4, zb 2 bez návratu k nezápornému zbytku

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

11

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

x2

D

-d

+d

-d

x2

+d r 4

r 3

r 2

r 1

2r 1

x2 2r 2

2r 3

0

1

0

1

t kladný zbytek

12

Dělení bez restaurace – poslední zbytek je záporný

+d

r 2

0

1

t

D

-d r 1

x2

0 2r 1

+d

2r 2 -d 0 r 3

korekce

2r 3

r 4 0

záporný zbytek! korekce

r 4 kor

+d

13

Dělení SRT - tabulka odhadů podle tří bitů R iDě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, Robertsonaa 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.

-d, posuv vlevo

1+d, posuv vlevo

-1101110100

+d, posuv vlevo

-1-d, posuv vlevo

1001010011

posuv vlevo0posuv vlevo0000111

d<0operace

d<0bit podílu

d>0operace

d>0bit podílu

Ri

14

Příklad:-49:7=-7, zb. 0SRT

49=00110001, 7=0111, -7=1001

-49=11001111 (d>0)

-1 11001111

0111 +d

00111111 <-

+1 0111111x

1001 -d

0000111x

0 000111xx <-

+1 00111xxx <-

1001 -d

11001xxx <-

-1 1001xxxx

0111 +d

0000xxxx

zbytek 0

Q = -1 1 0 1 –1 =

= -16+8+0+2-1 = -7

-d, posuv vlevo

1+d, posuv vlevo

-1101110100

+d, posuv vlevo

-1-d, posuv vlevo

1001010011

posuv vlevo

0posuv vlevo

0000111

d<0operace

d<0bit podílu

d>0operace

d>0bit podílu

Ri

15

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 = rR i – qn-i d

16

Chyba dělení u Pentia

(listopad 1994) $475M

17

Obvodová realizace dělení - sekvenční dělička SRT

A

B

0 1

P

n

n bitů

n bitů

0 n-1

operace +/-/

n bitů

0 n-1

n-1

posuv

dělitel d

Dělenec D

n-2

řízení operací

prázdná

B

A

18

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

19

Kombinační dělička s restaurací – odečítačka

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.

D - vstup výpůjčky

- řídicí signál - řídicí signál

- bit dělence - bit dělitele

- výstup výpůjčky

- výstup rozdílu - bit dělitele

x y

u

a a

t

y z

20

Pravdivostní tabulka odečítačky

Dostáváme tak rovnicez = x ⊕ a‘ ( y ⊕ t ) (a je řídicí vstup: 0 odčítej, 1 neodčítej),

u = x’ y + x‘ t + yt

21

Obvodová dělička s restaurací

D D D

D D D D

D D D D

D D D D

D D D D

D D D

D

D

D

D

6 5 4

3

2 1

0

q

q

q

q

q

4

3

2

1

2

0

d d d 1 0

r r r 2 1 0

R

D

= d

D - vstup výpůjčky

- řídicí signál - řídicí signál

- bit dělence - bit dělitele

- výstup výpůjčky

- výstup rozdílu - bit dělitele

x y

u

a a

t

y z

22

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