Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–1
Dzielenie sekwencyjne
dzielenie całkowite
Iloraz Q (quotient) i reszta R (remainder) z dzielenia
dzielnej X (dividend) przez dzielnik D
≠
0 (divisor),
to liczby Q oraz R takie, e
X = Q
⋅
D + R, |R| < |D|
•
s 2 rozwi zania (Q
1
,R
1
) oraz (Q
2
,R
2
) takie, e X – R
i
= Q
i
⋅
D, przy tym
|R
1
–R
2
| = |D| , –|D|< R
1
, R
2
< |D| oraz |Q
1
–Q
2
| = 1
X
⋅
R > 0 – dzielenie znakowane (signed division) – znak reszty = znak dzielnej
R > 0 – dzielenie modularne (modulus division) – znak reszty dodatni
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–2
Przybli enia ilorazu (1)
dzielenie dowolne
Iloraz ułamkowy Q mo na obliczy z dowoln dokładno ci
ε
−
=
+
=
D
R
D
D
R
Q
D
X
,
m
i
n
,
ε
ε
W jednorodnym systemie stałobazowym o podstawie
β
i ze zbiorem cyfr D,
iloraz X/D mo na obliczy z dokładno ci nie gorsz ni
β
–r
jako:
D
∈
<
−
=
=
≅
−
−
=
−
+
−
−
∑
i
r
i
s
r
i
s
i
s
r
s
q
Q
D
X
q
q
q
q
Q
D
X
,
,
}
,
.
.
.
,
,
{
)
(
1
0
β
β
β
β
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–2a
Przybli enia ilorazu (2)
Pierwszym przybli eniem ilorazu jest
s
s
s
s
q
Q
q
β
β
=
=
1
,
}
0
,...,
0
,
{
takie, e
D
D
q
X
D
q
D
s
s
s
s
s
s
1
)
1
(
+
<
+
<
≤
≤
β
β
β
β
, gdy X D > 0
lub
D
D
q
X
D
q
D
s
s
s
s
s
s
1
)
1
(
+
>
+
>
≥
≥
β
β
β
β
, gdy X D < 0
czyli
D
D
q
X
s
s
s
β
β
<
−
,
sk d wynika numer s i warto wagi
β
s
najwy szej cyfry ilorazu oraz
D
D
q
X
R
s
s
s
β
β
<
−
=
1
Dokładniejsze przybli enie to
1
1
1
,
2
,
1
}
0
,...,
,
{
−
−
−
+
=
=
s
s
s
s
s
s
q
Q
Q
q
q
β
β
takie, e
D
D
q
R
R
s
s
s
1
1
1
1
2
−
−
−
<
−
=
β
β
,
Maj c wi c przybli enie z dokładno ci do
β
s–p
i bie
c reszt , mo na
obliczy przybli enie z dokładno ci do
β
s–p–1
D
D
q
R
R
p
s
p
s
p
s
p
p
−
−
−
+
<
−
=
β
β
)
(
)
1
(
,
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–2b
Przybli enia ilorazu (3)
Po skalowaniu reszt R
#
przez pot g podstawy odpowiadaj c indeksowi reszty
otrzymamy nierówno parametryczn
D
D
q
r
r
p
s
p
p
<
−
=
−
+
)
(
)
1
(
β
,
której odpowiadaj podane ni ej wykresy dzielenia
q
s–i
= 0
q
s–i
= 1
r
i+1
β
r
i
q
s–i
= 0
q
s–i
= 1
q
s–i
= 0
q
s–i
= 1
q
s–i
= 0
q
s–i
= 1
–r
i+1
–
β
r
i
r
#
≥
0, D>0
r
#
≥
0, D<0
r
#
<0, D>0
r
#
<0, D<0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–2c
Przybli enia ilorazu w systemie naturalnym (1)
Pierwszym przybli eniem ilorazu jest
s
s
s
s
q
Q
q
β
β
=
=
1
,
}
0
,...,
0
,
{
takie, e
D
D
q
X
D
q
D
s
s
s
s
s
s
1
)
1
(
+
<
+
<
≤
≤
β
β
β
β
,
sk d wynika numer s i warto wagi
β
s
najwy szej cyfry ilorazu oraz
D
D
q
X
R
s
s
s
β
β
<
−
=
≤
1
0
gdzie q
s
– liczba całkowita (dodatnia), q
s
∈
{0, 1, 2, … ,
β
– 1 }
Dokładniejsze przybli enie to
1
1
1
,
2
,
1
}
0
,...,
,
{
−
−
−
+
=
=
s
s
s
s
s
s
q
Q
Q
q
q
β
β
takie, e
D
q
D
Q
X
R
D
q
s
s
s
s
s
1
1
1
,
1
1
1
)
1
(
−
−
−
−
+
<
−
=
≤
β
β
,
D
D
q
R
R
s
s
s
1
1
1
1
2
0
−
−
−
<
−
=
≤
β
β
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–2d
Przybli enia ilorazu w systemie naturalnym (2)
Dokładniejsze przybli enie to
1
1
1
,
2
,
1
}
0
,...,
,
{
−
−
−
+
=
=
s
s
s
s
s
s
q
Q
Q
q
q
β
β
takie, e
D
q
D
Q
X
R
D
q
s
s
s
s
s
1
1
1
,
1
1
1
)
1
(
−
−
−
−
+
<
−
=
≤
β
β
,
D
D
q
R
R
s
s
s
1
1
1
1
2
0
−
−
−
<
−
=
≤
β
β
Kolejnymi przybli eniami ilorazu s zatem
i
s
i
s
i
s
i
s
q
Q
Q
−
−
+
+
=
β
,
1
,
takie, e
D
q
D
Q
X
R
D
q
i
s
i
s
i
s
i
i
s
i
s
−
−
−
−
+
<
−
=
≤
β
β
)
1
(
,
,
D
D
q
R
R
i
s
i
s
i
s
i
i
−
−
−
+
<
−
=
≤
β
β
1
0
co po skalowaniu (
1
−
−
=
s
i
i
i
R
r
β
) prowadzi do nierówno ci parametrycznej
D
D
q
r
r
i
s
i
i
<
−
=
≤
−
+
β
1
0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–3
Zbie no procedury dzielenia
Aby w standardowym systemie stałobazowym mo liwe było
obliczenie lepszego przybli enia ilorazu (kolejnej cyfry)
na podstawie przybli enia poprzedniego,
czyli aby istniało
1
1
1
,
2
,
−
−
+
=
s
s
s
s
q
Q
Q
β
takie, e
i
s
i
s
Q
D
X
Q
D
X
,
1
,
−
<
−
+
,
to kolejna reszta musi spełnia warunek
D
D
q
r
r
p
s
p
p
<
−
=
−
+
)
(
)
1
(
β
,
Je li obliczyliby my
D
r
p
≥
+
)
1
(
, to kolejna nierówno
D
D
q
r
r
p
s
p
p
<
−
=
+
−
+
+
)
1
(
)
1
(
)
2
(
β
,
nie ma rozwi zania w zbiorze dozwolonych warto ci cyfr (
β
<
#
q
).
Na przykład przy dodatnich r
#
oraz D, je li
δ
+
=
+
D
r
p
)
1
(
, to
D
D
D
q
D
q
D
r
p
s
p
s
p
>
+
≥
+
−
=
−
+
=
+
−
+
−
+
βδ
βδ
β
δ
β
)
(
)
(
)
1
(
)
1
(
)
2
(
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–4
Procedura dzielenia sekwencyjnego w systemie naturalnym
Parametryczne (X>0, D>0)
D
q
r
r
i
s
i
i
−
+
−
=
β
1
,
D
r
i
<
≤
0
,
X
r
s 1
0
−
−
=
β
Warunki zbie
Ŝ
no
ś
ci procedury
•
D
D
q
r
q
D
r
i
s
i
i
s
i
<
−
≤
<
≤
∃
⇒
<
−
−
β
β
0
:
)
0
(
•
D
D
q
r
q
D
r
i
s
i
i
s
i
≥
−
<
≤
∀
⇒
≥
−
−
β
β
:
)
0
(
(3)
(3)
q
s–i
= 0
q
s–i
= 1
r
i+1
2r
i
2D
D
D
(0,0)
q
s–i
= 0
q
s–i
= 1
r
i+1
2r
i
2D
D
D
(0,0)
...(2)
...(2)
(2)
(2)
(1)
(1)
a)
b)
Wykres dzielenia sekwencyjnego w systemie dwójkowym a) wyznaczanie
cyfry ilorazu (1) i reszty cz ciowej (2), b) skalowanie reszty cz ciowej (3)
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–4a
Zbie no dzielenia w systemie naturalnym (1)
r
i+1
2r
i+1
2D
D
(0,0)
q
s–i
= 0
q
s–i
= 1
r
i+1
2r
i
2D
D
D
(0,0)
r
i
<
D
0
≤
q <
β
(zbie
Ŝ
ne)
r
i
≥
D
? q=
β
–1
rozbie
Ŝ
ne
q
s–i
= 0
q
s–i
= 1
r
i+2
β
= 2
r
i+2
> r
i+1
D
D
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–4b
Zbie no dzielenia w systemie naturalnym (2)
4r
i+1
4D
2D
(0,0)
q
s–i
= 0
q
s–i
= 3
r
i+1
4r
i
4D
2D
D
(0,0)
r
i
<
D
0
≤
q <
β
(zbie
Ŝ
ne)
r
i
≥
D
? q=
β
–1
rozbie
Ŝ
ne
q
s–i
= 0
q
s–i
= 3
r
i+2
β
= 4
r
i+2
> r
i+1
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–5
Dzielenie w systemach uzupełnieniowych
•
dzielna, dzielnik i iloraz mog by liczbami ujemnymi
•
liczba w systemie uzupełnieniowym – liczba w systemie stałobazowym
z niestandardowym zbiorem cyfr na wiod cej pozycji
∑
∑
−
−
=
−
−
−
−
=
−
−
−
+
=
+
−
=
2
1
1
2
1
1
1
]
)]
(
[
|
|
k
m
i
i
i
k
k
k
m
i
i
i
k
k
k
U
x
d
x
x
x
β
β
β
β
βϕ
β
X
,
gdzie
))
1
2
(
sgn
1
(
)
(
1
2
1
1
+
−
+
=
−
−
β
ϕ
k
k
x
x
– funkcja znaku liczby,
}
1
,...,
1
,
0
,
1
,...,
{
)
(
2
1
2
1
1
1
1
1
−
=
∈
−
=
−
−
−
−
β
β
βϕ
k
k
k
k
x
x
d
D
W
NIOSKI
:
•
je li X D < 0, to warto pierwszej cyfry ilorazu jest ujemna
•
wszystkie pozostałe cyfry ilorazu maj warto ci dodatnie
•
aby spełniony był warunek zbie no ci dzielenia |R|<|D|,
znak ka dej reszty musi by zgodny ze znakiem dzielnika (R D > 0)
•
pierwsza wielokrotno dzielnika musi by taka aby |R|<|D| oraz R D > 0
(je
ś
li byłoby R D < 0, odj
ę
cie ka
Ŝ
dej dodatniej wielokrotno
ś
ci D
prowadziłoby, wskutek skalowania, do naruszenia warunku |R|<|D|)
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–6
Standaryzacja ilorazu w systemach uzupełnieniowych (1)
iloraz mo na łatwo skalowa do warto ci ułamkowej
m
F
m
F
Q
D
X
Q
D
X
Q
β
β
=
=
⇒
<
=
−
1
ułamek w systemie uzupełnieniowym ma zawsze posta (
1
→
”
β
−1
”):
0
0
,...}
,
,
,
1
{
,...}
,
,
,
0
{
3
2
1
3
2
1
<
>
=
−
−
−
−
−
−
F
F
F
Q
gdy
Q
gdy
q
q
q
q
q
q
Q
po standaryzacji ilorazu:
•
je li X D > 0, to q
0
= 0 oraz r
1
= X
β
−
m
−0⋅
D = X
β
−
m
•
je li X D < 0, to q
0
=
1
oraz r
1
= X
β
−
m
−(−1)⋅
D = X
β
−
m
+
D
•
warunkiem poprawno ci jest r
i
D
≥0
•
wszystkie kolejne cyfry ilorazu q
i
reprezentuj warto ci dodatnie,
a nast pn reszt jest r
i+1
=
β
r
i
−
q
i
D , r
i+1
D
≥0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–6a
Standaryzacja ilorazu w systemach uzupełnieniowych (2)
Je li X D < 0, to
1
<
=
−
D
X
Q
m
F
β
, ale tak e
1
1
0
<
+
=
+
<
−
−
D
D
X
D
X
m
m
β
β
wi c po dodaniu dzielnika do przeskalowanej dzielnej
znak pierwszej reszty jest taki sam jak znak dzielnika.
Zatem wszystkie kolejne cyfry ilorazu s dodatnie i spełniaj nierówno ci
|r
i+1
=
β
r
i
−
q
i
D | < | D | , r
i+1
D
≥0
Algorytm
1. Przeskaluj dzieln X, tak aby |r
0
=
β
−
m
X / D| < 1.
2. Je li X D > 0, to q
0
= 0 oraz r
1
= r
0
−
0
⋅
D = r
0
3. Je li X D < 0, to q
0
=
1
oraz r
1
= r
0
−
1
⋅
D = r
0
+ D
4. Obliczaj kolejno |r
i+1
=
β
r
i
−
q
i
D | < | D | , r
i+1
D
≥0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–6b
Standaryzacja ilorazu w dwójkowych systemach uzupełnieniowych
Je li X D < 0, to
1
2
<
=
−
D
X
Q
m
F
, ale tak e
1
2
1
2
0
<
+
=
+
<
−
−
D
D
X
D
X
m
m
wi c po dodaniu dzielnika do przeskalowanej dzielnej
znak pierwszej reszty jest taki sam jak znak dzielnika.
Wszystkie kolejne cyfry ilorazu s dodatnie, znak ka dej kolejnej reszty musi
by taki jak znak dzielnika (r
i+1
D
≥0)
, przy tym
je li |r
i+1
=
2
r
i
−
D | < | D | , t o q
i
= 1
je li |r
i+1
=
2
r
i
−
D | > | D | , t o q
i
= 0 oraz r
i+1
=
2
r
i
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–7
Dzielenie w systemie uzupełnieniowym (przykład – U10)
!! standaryzacja ilorazu – skalowanie dzielnej tak, aby |X
β
−
m
|
<|
D|
X = 7, 6 5 4
:
3 1, 2 = D
X = 7 6 5, 4
:
6, 8 8 = D
−
2, 3 6 6 :
+
3 1, 2
−
2 3 6, 6 :
−
3, 1 2
,
→
1
,
←
2
9, 2 4 8
X D < 0
0, 7 5 1
X D > 0
9 7 6. 5 4
: 3 1, 2
q
0
=−
1
9 7. 6 5 4
: 6, 8 8
q
0
=
0
+
0 3 1, 2
0
0 0 7 7 4
q
−
1
=
2
9 7 6 5 4
q
−
1
=
7
−
0 0 6 2 4
+
0 2 1 8 4 *
0 1 5 0 0
q
−
2
=
4
9 8 3 8 0
q
−
2
=
5
−
0 1 2 4 8
+
0 1 5 6 0 *
0 2 5 2 0
q
−
3
=
8
9 9 4 0 0
q
−
3
=
1
−
0 2 4 9 6
+
0 0 3 1 2
…
…
Q
=
9, 2 4 8 …
×
10
−
1
Q
=
0, 7 5 1 …
×
10
2
*
)
zamiast –qD mo
Ŝ
na wykona
ć
q(–D)
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–8
Dzielenie odtwarzaj ce (restytucyjne)
standaryzacja ilorazu – skalowanie dzielnej, tak aby |X
⋅
2
−
m
|
<|
D|
1
0
0
0
gdy
gdy
2
2
0
0
0
=
⇒
=
⇒
<
>
+
=
−
−
q
q
D
X
D
X
D
X
X
r
m
m
D
q
r
r
i
i
i
−
=
−
1
2
,
0
|,
|
|
|
>
<
D
r
D
r
i
i
, i = 1,2,...
≥
<
=
−
−
.
|
|
|
2
|
|,
|
|
2
|
gdy
gdy
,
1
,
0
1
1
D
r
D
r
q
i
i
i
metody dzielenia restytucyjnego lub odtwarzaj
ą
cego (restoring division)
•
odj cie dzielnika D od tymczasowej reszty cz ciowej 2r
i
→
je li
0
)
2
(
1
<
−
−
D
D
r
i
– korekcja reszty przez dodanie dzielnika
•
porównanie tymczasowej reszty cz ciowej 2r
i
i dzielnika D
→
je li
0
)
2
(
1
≥
−
−
D
D
r
i
– odj cie dzielnika
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–9
Dzielenie nieodtwarzaj ce (nierestytucyjne)
W wyniku odj cia dzielnika od reszty r
i
=
2 r
i
−
1
−
D mo e powsta :
•
reszta r
i
poprawna, je eli r
i
⋅
D > 0
– odpowiada jej cyfra ilorazu o warto ci q
i
=
1
•
reszta r
i
niepoprawna, je eli r
i
⋅
D < 0
– odpowiada jej cyfra ilorazu o warto ci q
i
= 0
je li reszta r
i
jest niepoprawna, to
•
wła ciw kolejn reszt jest r
i
= 2 r
i
−
1
•
podstaw wyznaczenia warto ci kolejnej cyfry ilorazu jest
r
i
+
1
= 2 (2 r
i
−
1
)
−
D
•
t sam warto otrzymamy w wyniku opó nionej korekcji, dodaj c D
r
i
+
1
= 2 (2 r
i
−
1
−
D)
+
D
Je
ś
li X D < 0 to X
⋅
2
−
m
jest niepoprawn reszt , wi c
0
0
gdy
gdy
2
2
0
<
≥
+
−
=
−
−
D
X
D
X
D
X
D
X
r
m
m
,
0
0
gdy
gdy
1
0
0
0
0
>
<
=
D
r
D
r
q
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–10
Dzielenie nieodtwarzaj ce (nierestytucyjne)
Zale no kolejnej reszty od poprzedniej i wyznaczonej z niej q
•
0
0
2
1
=
⇒
<
−
=
−
i
i
i
q
D
r
r
oraz
D
r
D
D
r
r
i
i
i
+
=
+
−
=
−
+
2
)
2
(
2
1
1
•
1
0
2
1
=
⇒
≥
−
=
−
i
i
i
q
D
r
r
oraz
D
r
D
D
r
r
i
i
i
−
=
−
−
=
−
+
2
)
2
(
2
1
1
Algorytm dzielenia nieodtwarzaj cego w kodzie U2 (|X
⋅
2
−
m
|
<|
D|)
Krok 0.
0
0
gdy
gdy
2
2
0
<
≥
+
−
=
−
−
D
X
D
X
D
X
D
X
r
m
m
Krok 1. Je eli: a)
0
≥
D
r
i
podstaw
1
=
i
q
i oblicz
D
r
r
i
i
−
=
+
2
1
,
b)
0
<
D
r
i
podstaw
0
=
i
q
i oblicz
D
r
r
i
i
+
=
+
2
1
.
0
0
gdy
gdy
1
0
>
<
=
D
r
D
r
q
i
i
i
D
q
r
r
i
i
i
)
2
1
(
2
1
−
+
=
+
, i = 0, 1, 2, ...
Krok 2. Zwi ksz i. Je li i < p, wró do kroku 1.
Krok 3.
ulp
Q
Q
D
r
r
D
r
p
p
p
−
←
+
←
⇒
<
,
0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–11
Procedura dzielenia nieodtwarzaj cego
D
q
i
= 0
q
i
= 1
r
i+1
2r
i
−
D
(1)
(2)
(3)
−
D
D
−
2
D
2D
(0,0)
q
i+1
= 0
q
i+1
= 1
Wykres dzielenia nieodtwarzaj
ą
cego w kodzie U2 (D>0)
schemat wyznaczania cyfry ilorazu (1), reszty cz ciowej (2)
i przeskalowanej reszty cz ciowej (3)
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–12
Schemat dzielenia nieodtwarzaj cego
R
X/R
Q
D
Σ
C
ShL
0
Schemat blokowy układu dziel
ą
cego liczby całkowite w kodzie U2:
C||X/R – przedłu ony rejestr dzielnej i reszt cz ciowych,
Q – rejestr ilorazu, D – rejestr dzielnika
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–13
Dzielenie odtwarzaj ce i nieodtwarzaj ce (U2) – maszynowe (przykład 1)
X
( 0 ) 0 , 1 0 1 1 (
11
/
16
)
X D > 0,
zb
ę
dne skalowanie, |X / D | < 1
D
( 0 ) 0 , 1 1 0 1 (
13
/
16
)
(nieodtwarzaj
ą
ce)
X
( 0 ) 0 , 1 0 1 1
(odtwarzaj
ą
ce)
– D
( 1 ) 1 , 0 0 1 1
r
0
= X
( 0 ) 0 , 1 0 1 1
q
0
= 0
r
0
= X– D
( 1 ) 1 , 1 1 1 0
rD
<
0
q
0
= 0
2r
0
= 2X
( 0 ) 1 , 0 1 1 0
2r
0
( 1 ) 1 , 1 1 0 0
– D
( 1 ) 1 , 0 0 1 1
+ D
( 0 ) 0 , 1 1 0 1
r
1
= 2r
0
– D ( 0 ) 0 , 1 0 0 1
rD
≥
0
q
1
= 1
r
1
= 2r
0
+ D ( 0 ) 0 , 1 0 0 1
rD
≥
0
q
1
= 1
2r
1
( 0 ) 1 , 0 0 1 0
2r
1
( 0 ) 1 , 0 0 1 0
– D
( 1 ) 1 , 0 0 1 1
– D
( 1 ) 1 , 0 0 1 1
r
2
= 2r
1
– D ( 0 ) 0 , 0 1 0 1
rD
≥
0
q
2
= 1
r
2
= 2r
1
– D ( 0 ) 0 , 0 1 0 1
rD
≥
0
q
2
= 1
2r
2
( 0 ) 0 , 0 1 0 1
2r
2
( 0 ) 0 , 0 1 0 1
– D
( 1 ) 1 , 0 0 1 1
– D
( 1 ) 1 , 0 0 1 1
r
3
= 2r
2
– D ( 1 ) 1 , 1 0 0 0
rD < 0
q
3
= 0
r
3
= 2r
2
– D ( 1 ) 1 , 1 0 0 0
rD < 0
q
3
= 0
2r
3
= 2
⋅
2r
2
( 0 ) 0 , 1 0 1 0
2r
3
( 1 ) 1 , 0 0 0 0
– D
( 1 ) 1 , 0 0 1 1
+ D
( 0 ) 0 , 1 1 0 1
r
4
= 2r
3
– D ( 1 ) 1 , 1 1 0 1
rD
<
0
q
4
= 0
r
4
= 2r
3
+ D ( 1 ) 1 , 1 1 0 1
rD < 0
q
4
= 0
Q = 0,1100…
U2
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–14
Dzielenie odtwarzaj ce i nieodtwarzaj ce (U2) – maszynowe (przykład 2)
X
0 1 0 , 1 0 0 1 (
41
/
16
)
X D < 0,
skalowanie, |X / D | > 1
D
1 , 0 1 0 1 (–
11
/
16
)
– D
( 0 ) 0 , 1 0 1 1 (
11
/
16
)
X’= X
×
2
–2
( 0 ) 0 , 1 0 1 0 0 1 0 …
X’= X
×
2
–2
( 0 ) 0 , 1 0 1 0 0 1 0 …
D
( 1 ) 1 , 0 1 0 1
D
( 1 ) 1 , 0 1 0 1
r
0
= X’+D
( 1 ) 1 , 1 1 1 1
q
0
= 1
r
0
= X’+ D ( 1 ) 1 , 1 1 1 1 rD
≥
0 q
0
= 1
2r
0
= 2X
( 1 ) 1 , 1 1 1 0
2r
0
( 1 ) 1 , 1 1 1 0
– D
( 0 ) 0 , 1 0 1 1
– D
( 0 ) 0 , 1 0 1 1
r
1
= 2r
0
– D ( 0 ) 0 , 1 0 0 1 rD
<
0 q
1
= 0
r
1
= 2r
0
– D ( 0 ) 0 , 1 0 0 1 rD
<
0 q
1
= 0
2r
1
= 2
⋅
2r
0
( 1 ) 1 , 1 1 0 1
2r
1
( 0 ) 1 , 0 0 1 1
– D
( 0 ) 0 , 1 0 1 1
+ D
( 1 ) 1 , 0 1 0 1
r
2
= 2r
1
– D ( 0 ) 0 , 1 0 0 0 rD
<
0 q
2
= 0
r
2
= 2r
1
+ D ( 0 ) 0 , 1 0 0 0 rD
<
0 q
2
= 0
2r
2
= 2
⋅
2r
1
( 1 ) 1 , 1 0 1 0
2r
2
( 0 ) 1 , 0 0 0 0
– D
( 0 ) 0 , 1 0 1 1
+ D
( 1 ) 1 , 0 1 0 1
r
3
= 2r
2
– D ( 0 ) 0 , 0 1 0 1 rD
<
0 q
3
= 0
r
3
= 2r
2
+ D ( 0 ) 0 , 0 1 0 1 rD
<
0 q
3
= 0
2r
3
= 2
⋅
2r
2
( 1 ) 1 , 0 1 0 0
2r
3
( 0 ) 0 , 1 0 1 0
– D
( 0 ) 0 , 1 0 1 1
+ D
( 1 ) 1 , 0 1 0 1
r
4
= 2r
3
– D ( 1 ) 1 , 1 1 1 1 rD
≥
0 q
4
= 1
r
4
= 2r
3
+ D ( 1 ) 1 , 1 1 1 1 rD
≥
0 q
4
= 1
Q = 1,0001…
U2
×
2
2
=100,01…
U2
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–15
Dzielenie nieodtwarzaj ce w kodzie dwójkowym SD oraz U2
•
iloraz w kodzie U2 – warto cyfry zale y od znaku dzielnika
•
iloraz w ograniczonej reprezentacji SD (bez zer)
<
≥
=
−
−
,
0
2
gdy
,
1
,
0
2
gdy
,
1
1
1
i
i
i
r
r
q
D
q
r
r
i
i
i
−
=
−
1
2
•
dzielna i dzielnik w kodzie U2, wynik w systemie SD
•
dzielna ujemna – znak ilorazu jest ustalany automatycznie
•
dzielnik ujemny – odwrotne przypisanie cyfr ilorazu, zatem
.
0
,
0
&
&
0
0
lub
lub
0
gdy
,
1
0
gdy
,
1
1
-
1
-
1
-
1
-
=
=
<
>
<
>
=
i
i
i
i
i
r
r
D
D
D
r
D
r
q
albo
≥
<
=
−
−
.
0
gdy
,
0
gdy
,
sgn
,
sgn
1
1
i
i
i
r
r
D
D
q
sgn D = |D|/D
•
korekcja je li XR < 0: (XD > 0 ⇒ R+D, Q–1), (XD < 0 ⇒ R–D, Q+1)
•
korekcja gdy
0
1
=
−
i
r
– w algorytmie brak mo liwo ci wytworzenia zera
iloraz
,...}
1
,
1
,
1
,
,...,
{
1
i
q
q
=
Q
zamiast
,...}
0
,
0
,
0
,
,...,
{
1
i
q
q
=
Q
. (!!|R| = |D|)
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–16
Schemat dzielenia nieodtwarzaj cego w kodzie SD oraz U2
•
iloraz w ograniczonej reprezentacji SD (bez zer)
r
|D|
–|D|
(0,0)
|D|
|D|
|D|
–|D|
r
–1
i
2
i
2
–2
q =
i
sgn
q =
i
sgn D
D
Parametryczny wykres dzielenia nieodtwarzaj cego w kodzie U2
iloraz Q
w kodzie SD
→
przekodowanie na kod U2: podstawienie
1
2
−
=
i
i
z
q
.
p
i
p
i
i
i
p
i
i
p
i
p
i
i
z
z
z
z
Q
−
−
−
=
+
+
−
=
−
−
=
+
+
−
−
=
+
−
−
=
−
=
∑
∑
∑
2
2
)
1
(
2
)
2
1
(
2
)
1
2
(
1
1
1
1
1
1
1
)
1
(
2
1
i
i
q
z
+
=
⇒
|
}
...,
,
,
,
0
{
|
|
}
1
,
...,
,
),
1
{(
|
3
2
1
2
3
2
1
SD
n
U
n
q
q
q
q
z
z
z
z
=
−
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–17
Dzielenie nieodtwarzaj ce (SD) – maszynowe (przykład)
D = 0,0110 X = 0,0011
U2–SD
NB
2r
0
= 2X
( 0 ) 0 , 0 1 1 0
≥
0 q
1
= 1
– D
( 1 ) 1 , 1 0 1 0
r
1
= 2r
0
– D ( 0 ) 0 , 0 0 0 0
≥
0 q
1
= 1
2r
1
( 0 ) 0 , 0 0 0 0
≥
0 q
2
= 1
– D
( 1 ) 1 , 1 0 1 0
r
2
= 2r
1
– D ( 1 ) 1 , 1 0 1 0
< 0 q
2
= 0
2r
2
( 1 ) 1 , 0 1 0 0 < 0 q
3
=
1
+ D
( 0 ) 0 , 0 1 1 0
q
2
q
3
= 01
r
3
= 2r
2
+ D ( 1 ) 1 , 1 0 1 0
< 0 q
3
= 0
2r
3
( 1 ) 1 , 0 1 0 0 < 0 q
4
=
1
+ D
( 0 ) 0 , 0 1 1 0
q
3
q
4
= 01
r
4
= 2r
3
+ D ( 1 ) 1 , 1 0 1 0 < 0
< 0 q
4
= 0
Q = 0,1001
korekcja
( 0 ) 0 , 0 1 1 0
q
4
= 0
Q = 0,1000
R = r
4
+ D
( 0 ) 0 , 0 0 0 0
Q = 0,1000
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–18
Dzielenie w dowolnym systemie SD
iloraz mo na łatwo skalowa do warto ci ułamkowej
m
F
m
F
Q
D
X
Q
D
X
Q
β
β
=
=
⇒
<
=
−
1
ułamek w systemie uzupełnieniowym ma zawsze posta (
1
→
”
β
−1
”):
0
0
,...}
,
,
,
1
{
,...}
,
,
,
0
{
3
2
1
3
2
1
<
>
=
−
−
−
−
−
−
F
F
F
Q
gdy
Q
gdy
q
q
q
q
q
q
Q
po standaryzacji ilorazu:
•
je li X D > 0, to q
0
= 0 oraz r
1
= X
β
−
m
−0⋅
D = X
β
−
m
je li X D < 0, to q
0
=
1
oraz r
1
= X
β
−
m
Zatem wszystkie kolejne cyfry ilorazu s dodatnie i spełniaj nierówno ci
|r
i+1
=
β
r
i
−
q
i
D | < | D | , r
i+1
D
≥0
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–12a
Dzielenie odtwarzaj ce i nieodtwarzaj ce (U2) – pisemne (1)
0, 1
0
1
1
====
−−−−
D
X =
0 1, 1
1 0
: 1, 0
1 0
1
====
++++
D
k=–2
++++
D
1, 0
1
0
1
1
1
1
0
0
0
q
0
= 1
–D
0
1
0
1
1
0
0
0
1
1
0
q
1
= 0
++++
D
1
0
1
0
1
1
1
0
1
1
0
q
2
= 1
–D
0
1
0
1
1
0
0
0
0
1
q
3
= 0
Iloraz jest równy Q =
.
1,010...
××××
2
2
= 101,0...
0
0
1
1
1
0
1
0
1
0
1
====
−−−−
D
X =
1, 1 0
0
1 0
:
0
1
0 1, 1
====
++++
D
k= 3
++++
D
0
1
0 1, 1
0
0
1
0
0
0
q
0
= 1
–D
1
0
1
0
1
1
1
1
0
1
0
q
1
= 0
++++
D
0
1
0
1
1
0
0
1
0
1
0
q
2
= 1
–D
1
0
1
0
1
1
1
1
1
1
q
3
= 0
Iloraz jest równy Q =
.
1,010...
××××
2
–3
= 1,111010...
Dzielenie
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
DIV–12b
Dzielenie odtwarzaj ce i nieodtwarzaj ce (U2) – pisemne (2)
0
1 0, 1
====
−−−−
D
X = (0) 0, 1 1 1 1
:
1 0 1, 1
====
++++
D
k=+1
++++
D
1
0 1, 1
1
1
1
0
1
rD
≥
0
q
0
= 1
−−−−
D
0
1
0
1
0
0
1
0
1
<0
q
1
= 0
++++
D
1
0
1
1
0
0
0
0
0
≥
0 (=0)
q
2
= 1, q
3+
= 0
−−−−
D
0
1 0
1
q
2
= 0
−−−−
2D
++++
D =
−−−−
D
0
1
0
1
0
( = – 2D)
<0
q
3+
= 111…
Iloraz jest równy Q = 1,01
U2
××××
2
–1
= 1,101
U2
lub Q = 1,00(1)
××××
2
–1
= 1,101
U2
0, 1
1
1
1
0, 0
1
1
====
−−−−
D
X = (1) (1) 1, 0 0 0 1
: 1, 1
0
1
====
++++
D
k= –1
−−−−
D
0 0, 1
1
(0) 0
0
1
0
rD <0
q
0
= 0
+D
1
1
0
1
(1) 1 1
1
0
≥
0
q
1
= 1
−−−−
D
0
0
1
1
0
0
0
1
1
<0
q
2
= 0
++++
D
1
1
0
1
0
0
0
0
0
≥
0 (=0)
q
3
= 1(0)
Iloraz jest równy Q =
.
1,010...
××××
2
–3
= 1,111010...
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–1a
Oszacowanie pierwiastka kwadratowego – algorytm intuicyjny
X
A
≅
z dokładno ci
ε
je li
2
2
)
(
ε
+
<
≤
A
X
A
•
jedyny uniwersalny algorytm – zgadywanie lub przegl
ą
d zupełny
suma kolejnych naturalnych liczb nieparzystych jest kwadratem ich liczby
(1=1
2
; 1+3=2
2
; 1+3+5=3
2
; 1+3+5+7=4
2
; 1+3+5+7+9=5
2
; …)
∑
=
=
−
⇒
−
=
−
−
n
i
n
i
n
n
n
1
2
2
2
)
1
2
(
1
2
)
1
(
•
n
X
≅
je li
2
2
)
1
(
+
<
≤
n
X
n
algorytm
0. i
=−1,
d
=−1,
S
=
X
1. i
=
i
+1,
d
=
d
+2
2. S
=
S
−
d
3. je li S<0 to
i
X
≅
, w przeciwnym razie id do 1
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–1b
Poprawa dokładno ci oszacowania w systemie pozycyjnym
Przybli eniem pierwiastka kwadratowego z liczby X
z dokładno ci do 1 cyfry znacz cej jest q
s
β
s
takie, e
2
2
2
2
2
2
)
(
)
)
1
(
(
)
(
+
≤
+
=
+
<
≤
≤
s
s
s
s
s
s
s
s
s
q
q
X
q
β
β
β
β
β
β
•
2s – najwy sza parzysta pot ga podstawy nie wi ksza od X
•
dokładno bezwzgl dna wynosi
β
s
•
2
2
2
)
1
(
+
<
≤
−
s
s
s
q
X
q
β
.
Dokładniejsze przybli enie
1
1
−
−
+
s
s
s
s
q
q
β
β
takie, e
2
1
1
2
1
1
)
)
1
(
(
)
(
−
−
−
−
+
+
<
≤
+
s
s
s
s
s
s
s
s
q
q
X
q
q
β
β
β
β
)
1
)
)
(
1
(
2
(
)
2
(
1
1
2
2
1
1
+
+
+
<
−
≤
+
−
−
−
−
−
s
s
s
s
s
s
s
s
q
q
q
q
X
q
q
q
β
β
β
Podobnie mo na obliczy dokładniejsze przybli enie pierwiastka Q
(r)
+q
r–1
β
r–1
na podstawie poprzedniego przybli enia Q
(r)
z dokładno ci
β
r
.
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–1
Przybli enia
Niech
β
,
.
.
.
}
0
,
.
.
.
,
,
,
{
2
1
)
(
p
s
s
s
p
q
q
q
Q
−
−
−
=
p
s
p
s
p
p
q
Q
Q
−
−
−
+
=
β
)
1
(
)
(
X
Q
p
≅
)
(
z dokładno ci
p
s
−
β
je li
2
)
(
2
)
(
)
(
)
(
p
s
p
p
Q
X
Q
−
+
<
≤
β
p
s
p
s
p
s
p
p
s
p
s
p
p
p
q
Q
X
q
Q
Q
Q
−
−
−
−
−
−
−
−
+
+
<
≤
+
=
≤
β
β
β
)
1
(
)
1
(
)
(
)
1
(
Jak znale
kolejn cyfr
q
s–p
rozwini cia i lepsze przybli enie
Q
(
p
)
pierwiastka
X
Q
Q
p
p
≅
≤
−
)
(
)
1
(
na podstawie wyznaczonego wcze niej przybli enia
Q
(
p
–
1
)
?
Mamy
2
)
1
(
2
)
1
(
)
)
1
(
(
)
(
p
s
p
s
p
p
s
p
s
p
q
Q
X
q
Q
−
−
−
−
−
−
+
+
<
≤
+
β
β
czyli
.
.
.
)
.
.
.
2
(
)
2
(
)
1
(
)
1
(
2
)
1
(
)
1
(
+
<
=
−
≤
+
−
−
−
−
−
−
−
−
p
p
p
p
s
p
s
p
s
p
s
p
Q
R
Q
X
q
q
Q
β
β
Wynika st d rekurencyjna zale no kolejnych reszt
]
2
[
]
[
]
[
)
1
(
2
)
(
2
)
1
(
)
1
(
)
(
p
s
p
s
p
p
s
p
s
p
p
p
p
q
Q
q
Q
Q
R
R
−
−
−
−
−
−
−
+
−
=
−
=
−
β
β
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–2
Algorytm odr czny
Kolejn p-t cyfr przybli enia pierwiastka jest najwi ksza taka
q
s–p
, e
)
1
(
)
1
(
)
2
(
−
−
−
−
−
−
≤
+
p
p
s
p
s
p
s
p
s
p
R
q
q
Q
β
β
gdzie
]
2
[
)
1
(
)
1
(
)
(
p
n
p
n
p
p
n
p
n
p
p
q
Q
q
R
R
−
−
−
−
−
−
+
−
=
β
β
Po skalowaniu
2
)
(
)
(
)
(
p
s
p
p
R
r
−
−
=
β
, kład c
)
(
)
(
p
p
s
p
Q
Q
−
−
=
β
, otrzymamy:
]
2
[
1
1
2
p
s
p
p
s
p
p
q
Q
q
r
r
−
−
−
−
+
−
=
β
β
gdzie
Q
p–
1
jest obliczonym poprzednim przybli eniem pierwiastka
skalowanym do warto ci całkowitej
algorytm
1.
s
X
r
2
0
−
=
β
2. przeskaluj poprzedni reszt cz ciow
r
p–
1
przez
β
2
3. podwój i przeskaluj przez
β
obliczone przybli enie pierwiastka
Q
p–
1
4. znajd najwi ksz
Q
s–p
, dla której kolejna reszta jest najmniejsza dodatnia
5. powtarzaj od 1. a do uzyskania wymaganej dokładno ci
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–3
Algorytm odr czny – przykład
8 4 3, 3 5 4 4
→
q
1
=2
843
10
= 29 29 +2
4 Q
1
=2
→
2
⋅
2
⋅
10
4 4 3 (40+q
0
)
×
q
0
≤
443
→
q
0
=9
4 4 1 Q
2
=29
→
2
⋅
29
⋅
10
2 3 5 (580+q
–1
)
×
q
–1
≤
235
→
q
–1
=0
2 3 5 4 4 Q
3
=290
→
2
⋅
290
⋅
10
2 3 2 1 6 (5800+q
–2
)
×
q
–2
≤
23544
→
q
–2
=4
1 1 0 1 0 0 1 0 1 1
→
q
4
=1
843
10
= 29
2
+2
1 Q
1
=1
1 0 0 1 (100+q
3
)
×
q
3
≤
1001
→
q
3
=1
1 0 1 Q
2
=11
1 0 0 0 0 (1100+q
2
)
×
q
2
≤
10000
→
q
2
=1
1 1 0 1 Q
3
=111
0 0 1 1 1 0 (11100+q
1
)
×
q
1
≤
1111
→
q
1
=0
0 0 0 0 0 Q
4
=1110
0 1 1 1 0 1 1 (111000+q
0
)
×
q
0
≤
111011
→
q
0
=1
1 1 1 0 0 1 Q
5
=11101
29
10
1 0 1 0 r
5
=10
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–4
Algorytm odr czny – sekwencyjne generowanie podwojenia
8 4 3, 3 5 4 4
→
q
1
=2
2
4 Q
1
=2
→
2
⋅
2
⋅
10
+2
4 4 3 (4q)
×
q
≤
443
→
q
0
=9
4 9
4 4 1 Q
2
=29
→
2
⋅
29
⋅
10
+9
2 3 5 (58q)
×
q
≤
235
→
q
–1
=0
5 8 0
2 3 5 4 4 Q
3
=290
→
2
⋅
290
⋅
10
=0
2 3 2 1 6 (580q)
×
q
≤
23544
→
q
–2
=4
5 8 0 4
1 1 0 1 0 0 1 0 1 1
→
q
4
=1
1
1 Q
1
=1
+1
1 0 0 1 (10q)
×
q
≤
1001
→
q
3
=1
1 0 1
1 0 1 Q
2
=11
1
1 0 0 0 0 (110q)
×
q
≤
10000
→
q
2
=1
1 1 0 1
1 1 0 1 Q
3
=111
+1
0 0 1 1 1 0 (1110q)
×
q
≤
1111
→
q
1
=0
1 1 1 0 0
0 0 0 0 0 Q
4
=1110
+0
0 1 1 1 0 1 1 (11100q)
×
q
≤
111011
→
q
0
=1
1 1 1 0 0 1
1 1 1 0 0 1 Q
5
=11101
+1
1 0 1 0 r
5
=10
1 1 1 0 1 0
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–5
Obliczanie pierwiastka kwadratowego w systemie NB
]
2
[
]
[
]
[
)
1
(
2
)
(
2
)
1
(
)
1
(
)
(
p
n
p
n
p
p
n
p
n
p
p
p
p
q
Q
q
Q
Q
R
R
−
−
−
−
−
−
−
+
−
=
−
=
−
β
β
,
Po skalowaniu
)
(
)
(
)
(
p
n
p
p
R
r
−
−
=
β
, otrzymamy wzór podobny jak w dzieleniu:
]
2
[
)
1
(
)
1
(
)
(
p
n
p
n
p
p
n
p
p
q
Q
q
r
r
−
−
−
−
−
+
−
=
β
β
analogia do dzielenia
→
obliczanie pierwiastka kwadratowego w układzie dziel cym
W systemie dwójkowym reguła upraszcza si bo
}
1
,
0
{
2
∈
=
i
i
q
q
.
Po normalizacji
n
X
X
2
0
−
=
β
i uproszczeniu indeksów (q
n–i
→
q
i
) otrzymamy
)
2
2
(
2
1
1
−
−
−
+
−
=
i
i
i
i
i
Q
q
r
r
, i = 1,2,..., p,
X
r
=
0
,
+
≥
+
<
=
−
−
−
−
−
−
).
2
2
(
2
gdy
,
1
),
2
2
(
2
gdy
,
0
1
1
1
1
i
i
i
i
i
i
i
Q
r
Q
r
q
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–6
Obliczanie pierwiastka kwadratowego w systemie NB –przykład
2
–i
+ 2Q
i – 1
q
i
r
0
= X
0 0 , 1 0 1 0 1 1 1 1
–
q
0
= 0 0,
2r
0
0 1 , 0 1 0 1 1 1 1 0
≥
00,1
q
1
= 1 0,1
– d
1
= – (2
–1
+ 2Q
0
)
1 1 , 1 0 0 0 0 0 0 0
r
1
= 2r
0
– d
1
0 0 , 1 1 0 1 1 1 1 0
2r
1
0 1 , 1 0 1 1 1 1 0 0
≥
01,01
q
2
= 1 0,11
– d
2
= – (2
–2
+ 2Q
1
)
1 0 , 1 1 0 0 0 0 0 0
r
2
= 2r
1
– d
2
0 0 , 0 1 1 1 1 1 0 0
2r
2
0 0 , 1 1 1 1 1 0 0 0 < 01,101
q
3
= 0 0,110
2r
3
= 2
⋅
2r
2
0 1 , 1 1 1 1 0 0 0 0
≥
01,1001
q
4
= 1 0,1101
– d
4
= – (2
–4
+ 2Q
3
)
1 0 , 0 1 1 1 0 0 0 0
r
4
= 2r
3
– d
4
0 0 , 0 1 1 0 0 0 0 0
2r
4
0 0 , 1 1 0 0 0 0 0 0 < 01,10101
q
5
= 0 0,11010
2r
5
= 2
⋅
2r
4
0 1 , 1 0 0 0 0 0 0 0 < 01,101001
q
6
= 0 0,110100
2r
6
= 2
⋅
2r
5
0 1 1 , 0 0 0 0 0 0 0 0
≥
01,1010001
q
7
= 1 0,1101001
– d
7
= – (2
–7
+ 2Q
6
)
1 1 0 , 0 1 0 1 1 1 1 0
r
7
= 2r
6
– d
7
0 0 1 , 0 1 0 1 1 1 1 0
2r
7
0 1 0 , 1 0 1 1 1 1 0 0
≥
01,10100101 q
8
= 1 0,11010011
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–7
Obliczanie pierwiastka kwadratowego – metoda nierestytucyjna
algorytm oparty na regule
)
2
2
(
2
1
1
−
−
−
+
−
=
i
i
i
i
i
Q
q
r
r
, i = 1,2,..., p,
X
r
=
0
mo na zrealizowa w wersji nieodtwarzaj cej reszty cz ciowe.
Bezpo rednie zastosowanie niemo liwe – kolejna cyfra jest wyznaczana po
okre leniu znaku nast pnej reszty. W pierwiastkowania warto tej reszty
zale ałaby od warto ci cyfry wyznaczanej na jej podstawie!
Problem znika, je li wynik wytwarzamy w kodzie SD
)
2
2
(
,
2
1
1
−
−
−
+
=
−
=
i
i
i
i
i
i
i
Q
q
d
d
r
r
,
X
r
=
0
, i = 1,2,...,p,
<
≥
=
−
−
,
0
2
gdy
,
1
,
0
2
gdy
,
1
1
1
i
i
i
r
r
q
! konieczna jest bie
ca korekcja po wyst pieniu cyfry ujemnej
Obliczanie
√√√√
—
© Janusz Biernat, Dzielenie'04, 19 listopada 2004
SQRT–8
Obliczanie pierwiastka kwadratowego – metoda nierestytucyjna
X =
49
/
256
2
–i
+ 2Q
i – 1
q
i
(SD) Q
i
r
0
= X
00,00110001
–
q
0
= 0
0,
2r
0
00,01100010
≥
0 00,1
q
1
= 1
– d
1
= – (2
–1
+ 2Q
0
)
11,10000000
0,1
r
1
= 2r
0
– d
1
11,11100010
2r
1
11,11000100
< 0 01,01
q
2
=
1
0,1
1
+ d
2
= + (2
–2
+ 2Q
1
) 00,11000000
00,11
0,01
r
2
= 2r
1
+ d
2
00,10000100
q
1
q
2
= 0 1
2r
2
01,00001000
≥
0 0,101
– d
3
= – (2
–3
+ 2Q
2
)
11,01100000
q
3
= 1
0,011
r
3
= 2r
2
– d
3
00,01101000
2r
3
00,11010000
≥
0 0,1101
– d
4
= – (2
–4
+ 2Q
3
)
11,00110000
q
4
= 1
0,0111
R = r
4
= 2r
3
– d
4
01,00000000
Pierwiastek ma sko czone rozwini cie Q = 0,0111 (
16
7
).
W drugim kroku dokonano zamiany przybli enia pierwiastka z kodu SD na U2