Dělení. MI-AAK(Aritmetika a kódy)

MI-AAK (Aritmetika a kódy)

Dělení c doc. Ing. Alois Pluháček, CSc., 2011

Katedra číslicového návrhu Fakulta informačních technologií České vysoké učení technické v Praze

Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti

A4. dělení • úvod • dělení nezáporných čísel menších než 1 – dělení s návratem přes nulu – dělení bez návratu přes nulu • dělení nezáporných celých čísel (bez návratu přes nulu) • dělení čísel se znaménkem – přímý kód – inverzní kód – doplňkový kód • přeskakování nul • přeskakování jedniček • metody SRT • použití rychlých násobiček – rozšiřování zlomku – použití iterací MI-AAK

c A. Pluháček 2011

úvod

dělení — značně problematická operace

• jeden operand (dělitel) nikdy nesmí být 0 (! • obecně je výsledek „praktickyÿ nezobrazitelný A/B = ?

! !)

B 6= 0 !!!

nezáporná čísla — dvojková soustava

➊ ➋

Z = 1 =⇒ A < 1, B < 1 a A/B < 1 ε = 1 =⇒ celá čísla • A÷B = ? celočíselný podíl • A%B = ? zbytek po dělení

➊ příklad:

MI-AAK

A = 0,1012 B = 0,1102 . 0,101 / 0,110 = 0,110 A4 – 1

zbytek: 0,000 100 c A. Pluháček 2011

dělení s návratem přes nulu 0 ,101

101

: ↓

0 ,110

: 110 = 0 ,110

podíl

110 −1 → 0 , + 110 návrat 101 0 − 110 100 0 → 1 − 110 10 0 → 1 − 110 −1 0 → 0 + 110 návrat 100 zbytek návrat — pomocná operace obnovující původní dílčí zbytek pro následující odčítání −

MI-AAK

A4 – 2


dělení bez návratu přes nulu návrat = přičtení jistého čísla X → + X následuje odečtení čísla X ⊲ 1 → −X/2 +X/2

101 − + − − +

:

110 −1 0 110 100 0 110 10 11 −1 11 10

110 = 0 , 110 →

0, 1

→ 0

0 0 0 0

podíl

1

→

0

→

návrat

zbytek

návrat — pouze v posledním kroku, je-li zbytek záporný, a to jenom v případě, že třeba získat také správný zbytek. MI-AAK

A4 – 3


dělení bez návratu přes nulu

1. takt další takty návrat MI-AAK

α 0 1 0

ψ 1 0 0 A4 – 4

ii

l+1 (popř. l+2) taktů podíl . . . C zbytek . . . A c A. Pluháček 2011

dělení bez návratu přes nulu

iii

vstup sčítačky

Uvědomíme si, že obě schémata jsou ekvivalentní.

MI-AAK

A4 – 5


dělení nezáporných celých čísel 111 : 011 0 0 0 1 − 1 1 0 0 1 0 1 1 1 0 ↓ ↓ ↓ 1 1 0 + 0 0 1 1 0 0 0 ↓ ↓ 0 0 − 1 1 N

MI-AAK

1 1 :

:

:

:

:

:

↓ 1 1 0 ↓ 0 0

:

0 1 1 1 0 0 1 1 0 0 0 0 0

: 0 0 1 1 negace horká 1 − ⇒ 0

: :

1 + ⇒ 1 ↓ 1 0 1 0 − ⇒ 0 1 návrat 1 1 — zbytek 0 1 0 — pod í l A4 – 6


dělení nezáporných celých čísel

ii

0 0 0 1 1 1 : 0 0 1 1 − 1 1 0 0 : : negace 1 : : horká 1 0 1 1 1 0 : : − ⇒ 0 ււււււ 1 1 0 1 1 ? + 0 0 1 1 : : 1 0 0 0 0 1 : + ⇒ 1 ււււււ 0 0 0 1 ? ? − 1 1 0 0 : : 1 : : 0 1 1 1 0 : : − ⇒ 0 ււււււ 1 1 0 ? ? ? N 0 1 1 0 : : návrat 1 0 0 1 ? : : ↓ ↓ ↓ ↓ ↓ ↓ 0 0 1 ? ? ? 0 0 1 — zbytek 0 1 0 — pod í l MI-AAK

A4 – 7


dělení nezáporných celých čísel

α 1. takt 1 další takty 1 návrat 0 MI-AAK

β 0 0 1

ψ 1 0 0 A4 – 8

iii

l (popř. l+1) taktů podíl . . . nižší řády A zbytek . . . vyšší řády A c A. Pluháček 2011

dělení čísel se znaménkem ➊

přímý kód znaménko:

+ + − −

+ − + −

+ − ⇒ − +

0 0 1 1

0 1 0 1

0 1 1 0

⇒ XOR

absolutní hodnota — nezáporné číslo ⇒ dělení čísel bez znaménka ➋

inverzní kód — možná metodika návrhu: Pro různé kombinace znamének dělence A a dělitele B se modiﬁkuje známý postup pro dělení nezáporných čísel |A| a |B| tak, aby • byly zachovány stejné absolutní hodnoty mezivýsledků a • bity podílu byly invertovány (anebo neinvertovány) podle toho, zda A/B = |A|/|B| (anebo A/B = −|A|/|B|).

MI-AAK

A4 – 9


dělení čísel se znaménkem — ➋ inverzní kód

A ... B ... Y ...

dělenec dělitel výsledek dílčí operace

A≥0

B>0 B<0 Y ≥0 Y <0 Y ≥0 Y <0 bit výsledku 1 0 0 1 násl. operace – + + – A<0 bit výsledku násl. operace

B>0 B<0 Y ≤0 Y >0 Y ≤0 Y >0 0 +

1 –

1 –

souhlas znamének ⇒ bit podílu = 1 Uvažte případ: znaménko a nula! MI-AAK

A4 – 10

0 + a

příště odečítat


dělení čísel se znaménkem — ➌ doplňkový kód

➌

doplňkový kód

Postup pro dělení v inverzním kódu lze použíti v případě, že dělenec, děliteli a zbytek jsou v jakémkoliv kódu, pokud má být podíl v inverzním kódu. dělení v doplňkovém kódu

modiﬁkace dělení v inverzním kódu

• určit obraz I(C) podílu C v inverzním kódu, ale všechny operace a jejich vyhodnocení provádět v doplňkovém kódu • obraz I(C) převést do doplňkového kódu: I(C), pro C > 0, D(C) = I(C) + ε, pro C < 0. • zbytek bude v doplňkovém kódu MI-AAK

A4 – 11


Dále se budeme zabývat pouze dělením čísel bez znaménka a budeme předpokládat, že dělitel B splňuje podmínku 1 2

≤B<1 ,

tzn. že je tzv. normalizován.

pozn.: Naprosto analogicky lze postupovat v případě, že 1 ≤ B < 2.

MI-AAK

A4 – 12


přeskakování nul příklad dělení: 0 , 1000

:

0,1111 = 0,1000

1000 0001 0 10010 1111 1 00010 0001 0 0011 0100 0001 0 0101 1000 0001 0 1001 1000 MI-AAK

−0,1111 ⊲ 0 0, +0,1111 ⊲ 1 1 −0,1111 ⊲ 2 0

návrat −0,1111 ⊲ 3 0

návrat −0,1111 ⊲ 4 0

A4 – 13

návrat c A. Pluháček 2011

přeskakování nul

3 nuly

=⇒

0 , 1000

:

ii

zapsat 2 nuly do podílu a dílčí zbytek posunout o tři místa 0,1111 = 0,1000

1000 0001 0 10010 1111 1 0001000 0001 0 1001 1000

−0,1111 ⊲ 0 0, +0,1111 ⊲ 1 100 −0,1111 ⊲ 4 0

návrat

lze zobecnit: k nul

MI-AAK

=⇒

zapsat k−1 nul do podílu a dílčí zbytek posunout o k míst A4 – 14


přeskakování jedniček příklad dělení: 0 , 1110 : 0,1111 = 0,1110 1110 0001 −0,1111 ⊲ 0 0 11110 0, 01111 +0,1111 ⊲ 1 1 1101 1 „protinávratÿ ?! 11100 1111 +0,1111 ⊲ 2 1 1011 1 „protinávratÿ ?! 11000 1111 +0,1111 ⊲ 3 1 0111 1 „protinávratÿ ?! 10000 1111 −0,1111 ⊲ 4 0 1111 0 1111 návrat 1110 MI-AAK

A4 – 15


přeskakování jedniček

4 jedničky 0,1110

=⇒ :

ii

zapsat 3 jedničky do podílu a dílčí zbytek posunout o čtyři místa

0,1111 = 0,1110

1110 0001 0 11110000 1111 0 1111 1111 1110

−0,1111 ⊲ 0 0,111 +0,1111 ⊲ 4 0

návrat

lze zobecnit: k jedniček

MI-AAK

=⇒

zapsat k−1 jedniček do podílu a dílčí zbytek posunout o k míst

A4 – 16


metody SRT

metody SRT (Sweeney - Robertson - Tocher) • Podíl se nejprve určí v soustavě s relativními číslicemi. Pak se převede do standardní soustavy. • Zbytek se po každé dílčí operaci sčítání / odčítání normalizuje — přeskakovaní nul a jedniček. • redundantní počet relativních číslic • redundance → přeskakování, co největšího počtu bitů – úprava dělence i dělitele před vlastní operací • redundance → určení číslice podílu — Stačí jenom několik bitů dílčího zbytku. • použití soustav se základem z > 2

MI-AAK

A4 – 17


rozšiřování zlomku

rozšiřování zlomku Ai+1 = Ai · Ki

A = A0 = A1 = A2 = A3 = . . . B B0 B1 B2 B3 A0 = A

Bi+1 = Bi · Ki Bi → 1 =⇒ Ai → A B

B0 = B

B = 1−δ

1 2

≤B<1

⇒

0<δ≤

1 2

Bi = 1 − δi Ki = 1 + δi = 2 − Bi

⇒

Ki = Bi + ε

Bi+1 = Bi · Ki = (1 − δi ) · (1 + δi ) ⇒

Bi+1 = 1 − δi2

Je-li δi ≪ 1 získá se každým krokem cca dvojnásobný počet platných číslic. MI-AAK

A4 – 18


použití iterací

Newtonova metoda (metoda tečen) [Newton – Raphson] Pozorování:

g(x) 6

a

ξ x2 x1

x0 b

-x

Předp.: Funkce g(x) nabývá v intervalu ha , bi hodnoty 0 (pro x = ξ) a je v něm spojitá, rostoucí a ryze konvexní. g(x ) g ′ (x0 ) = x −0x 0 1 g(x ) g ′ (x1 ) = x −1x 1 2

MI-AAK

=⇒ =⇒ .. . A4 – 19

g(x0 ) g ′ (x0 ) g(x ) x2 = x1 − ′ 1 g (x1 ) x1 = x0 −


použití iterací

Tedy xi+1 = xi −

ii

g(xi ) g ′ (xi )

pro i = 0, 1, 2, . . . Rovnice

g(x) = 0

má v intervalu ha , bi kořen, a to ξ = lim xi . i→∞

přesneji — viz následující fólii

MI-AAK

A4 – 20


použití iterací

iii

Existuje-li takové a a b > a, že • funkce g(x) je v intervalu ha , bi spojitá a má v něm spojitou první derivaci g ′ (x) a spojitou druhou derivaci g ′′ (x) , • g(a) · g(b) < 0, • (∀x ∈ ha , bi) g ′ (x)·g ′ (a) > 0 , • (∀x ∈ ha , bi) g ′′ (x)·g ′′ (a) > 0 a • (∃x0 ∈ ha , bi) g(x0 ) · g ′′ (x0 ) > 0 , má rovnice g(x) = 0 v intervalu ha , bi jediný kořen, a to ξ = lim xi , i→∞

kde

xi+1 = xi −

g(xi ) g ′ (xi )

pro i = 0, 1, 2, 3, . . . . Podmínky jsou postačující, nikoliv nutné. Rovnice g(x) = 0 může tedy mít v intervalu ha , bi jediný kořen, který lze určit uvedeným postupem, i když některá z podmínek splněna není. MI-AAK

A4 – 21


použití iterací

iv

A = A · 1 B B ξ= 1 B

1 −B =0 . x

je kořenem rovnice

ξ je tedy kořenem rovnice g(x) = 0, kde 1 − B, g ′ (x) = − 1 g(x) = x a g ′′ (x) = 23 . 2 x x g(x) 6

1 B

MI-AAK

A4 – 22

2 B-

x


použití iterací

v

g(xi ) = xi ·(2 − B·xi ) g ′ (xi ) 1 a vyhovuje libovolné a ∈ (0 , B ), 1 libovolné b ∈ ( B , ∞) a 1 ). libovolné x0 ∈ (0 , B

Tedy xi+1 = xi −

1 , Pozn.: Lze použít také libovolné x0 ∈ h B xi+1 1 B

2 ) B

6

- xi 1 B

MI-AAK

A4 – 23

2 B


použití iterací

vi

1 Výpočet hodnoty B xi+1 = xi ·(2 − B·xi ) ≤ B < 1 =⇒ 1 < 1 ≤ 2 B 1 [∀x0 ∈ (0 , 1)] x0 ∈ 0 , B normalizované B:

1 2

rychlost konvergence: xi =

1 ·(1 B

− δ)

=⇒

xi+1 =

1 ·(1 B

− δ2 )

|δ| ≪ 1 =⇒ každou iterací se získá dvojnásobný počet platných míst Je výhodné volit x0 tak, aby bylo |δ| co nejmenší. → malá tabulka v paměti ROM adresovaná několik prvními bity B MI-AAK

A4 – 24


Dělení. MI-AAK(Aritmetika a kódy)

Recommend Documents