Dzielenie
Dzielenie sekwencyjne
Dla dzielnej X (dividend) i dzielnika D`"0 (divisor) liczby Q oraz R takie, \e
X=Q"D+R, |R|<|D|
nazywa się ilorazem Q (quotient) i resztą R (remainder) z dzielenia X przez D.
Równanie dzielenia mo\e mieć 2 rozwiązania spełniające warunek |R|<|D|
|R1 R2|=|D|, |D|
X Ri=Qi"D
X"R>0 dzielenie znakowane (signed division) (znak reszty = znak dzielnej)
R>0 dzielenie modularne (modulus division) (znak reszty dodatni)
W naturalnym systemie pozycyjnym Re"0 i jeśli X = {xk -1,..., x1, x0,..., x-m}
oraz D = {dl-1,...,d1,d0,...,d-s} , to z dokładnością p mo\na obliczyć
k-l+1
i
Q = {qk-l+1,qk-l ,...,q0,...q- p} = .
"q
i
i=- p
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 1
Dzielenie
Przybli\enia ilorazu
s
Pierwszym przybli\eniem ilorazu jest {qs,0,...,0} = Qs,1 = qs takie, \e
s s
qs D d" X < (qs +1) D ,
s s
0 d" R1 = X - qs D < D
s-1
Dokładniejsze przybli\enie to {qs,qs-1,...,0} = Qs,2 = Qs,1 + qs-1 takie, \e
s-1 s-1
qs-1 D d" R1 = X - Qs,1D < (qs-1 +1) D,
s-1 s-1
0 d" R2 = R1 - qs-1 D < D
s-i
Kolejnymi przybli\eniami ilorazu są zatem Qs,i+1 = Qs,i + qs-i takie, \e
s-i s-i
qs-i D d" Ri = X - Qs,iD < (qs-i +1) D,
s-i s-i
0 d" Ri+1 = Ri - qs-i D < D
i-s-1
co po skalowaniu (ri = Ri ) prowadzi do nierówności parametrycznej
0 d" ri+1 = ri - qs-iD < D
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 2
Dzielenie
Procedura dzielenia sekwencyjnego w systemie naturalnym
Parametryczne (X>0, D>0)
-s-1
ri+1 = ri - qs-iD , 0 d" ri < D , r0 = X
Warunki zbie\ności procedury
" ri < D!"(0 d" qs-i < ) : 0 d" ri - qs -iD < D
" ri e" D!"(0 d" qs-i < ) : ri - qs-iD e" D
a) b)
ri+1 ri+1
D D
qs i =0 qs i =1 qs i =0 qs i =1
(2) ...(2)
(1)
(2) ...(2)
(1)
2ri 2ri
(3) (3)
(0,0) D 2D (0,0) D 2D
Wykres dzielenia sekwencyjnego w systemie dwójkowym a) wyznaczanie
cyfry ilorazu (1) i reszty częściowej (2), b) skalowanie reszty częściowej (3)
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 3
Dzielenie
Zbie\ność dzielenia w systemie naturalnym
qs i =0 qs i =1
ri+1 ri+1
D
2ri
2D D (0,0)
(0,0) D 2D
2ri+1
ri < D ri e" D
0 d" q < ? q= 1
(zbie\ne) rozbie\ne
ri+2
qs i =1 qs i =0
ri+2 > ri+1
= 2
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 4
Dzielenie
Dzielenie w systemach uzupełnieniowych
" dzielna, dzielnik i iloraz mogą być liczbami ujemnymi
" liczbę w systemie uzupełnieniowym mo\na interpretować jako
liczbę w systemie stałobazowym
z niestandardowym zbiorem cyfr na wiodącej pozycji
k -2 k -2
k -1 i k -1 i
|XU | = [xk -1 -(xk -1)] ] + = dk -1 + ,
"xi "xi
i=-m i=-m
1
gdzie (xk -1) = (1+ sgn(2xk -1- +1)) funkcja znaku liczby,
2
1
dk -1 = xk -1 - (xk -1)" Dk -1 = {1 ,...,1,0,1,..., -1}
2 2
WNIOSKI:
" jeśli XD<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 (RD>0)
" pierwsza wielokrotność dzielnika musi być taka aby |R|<|D| oraz RD>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|)
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 5
Dzielenie
Standaryzacja ilorazu w systemach uzupełnieniowych
iloraz mo\na łatwo skalować do wartości ułamkowej
-m
X X
m m
QF = <1!Q = = QF
D D
ułamek w systemie uzupełnieniowym ma zawsze postać (1 -1 ):
{0,q-1,q-2,q-3,...} gdy QF > 0
ńł
QF =
ł{1,q ,q-2,q-3,...} gdy QF
< 0
ół -1
po standaryzacji ilorazu:
" jeśli XD>0, to q0=0 oraz r1=X- m-0"D=X- m
" jeśli XD<0, to q0= 1 oraz r1=X- m-(-1)"D=X- m+D
" warunkiem poprawności jest riDe"0
" wszystkie kolejne cyfry ilorazu qi reprezentują wartości dodatnie,
a następną resztą jest ri+1=ri-qiD, ri+1De"0
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 6
Dzielenie
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 -1 q0 = 0
9 7. 6 5 4 : 6, 8 8
q0 =
0 3 1, 2 0
+
0 0 7 7 4 9 7 6 5 4
q-1 = 2 q-1 = 7
0 0 6 2 4 0 2 1 8 4 *
- +
0 1 5 0 0 9 8 3 8 0
q-2 = 4 q-2 = 5
0 1 2 4 8 0 1 5 6 0 *
- +
0 2 5 2 0 9 9 4 0 0
q-3 = 8 q-3 = 1
0 2 4 9 6 0 0 3 1 2
- +
& &
2
Q 9, 2 4 8 & 10 -1 Q 0, 7 5 1 & 1
= =
0
*) zamiast qD mo\na wykonać q( D)
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 7
Dzielenie
Dzielenie odtwarzające (restytucyjne)
standaryzacja ilorazu skalowanie dzielnej, tak aby |X"2- m|<|D|
gdy X D > 0 ! q0 = 0
ńł 2-m X
r0 =
ł
-m
ół2 X + D gdy X D < 0 ! q0 =1
ri = 2ri-1 - qiD, | ri |<|D |, ri D > 0, i=1,2,...
0, gdy | 2ri-1 |<|D |,
ńł
qi =
ł
ół1, gdy |2ri-1 |e"|D | .
metody dzielenia restytucyjnego lub odtwarzającego (restoring division)
" odjęcie dzielnika D od tymczasowej reszty częściowej 2ri
jeśli (2ri-1 - D)D< 0 korekcja reszty przez dodanie dzielnika
" porównanie tymczasowej reszty częściowej 2ri i dzielnika D
jeśli (2ri-1 - D)De" 0 odjęcie dzielnika
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 8
Dzielenie
Dzielenie nieodtwarzające (nierestytucyjne)
W wyniku odjęcia dzielnika od reszty ri=2ri-1-D mo\e powstać:
" reszta ri poprawna, je\eli ri"D>0
odpowiada jej cyfra ilorazu o wartości qi=1
" reszta ri niepoprawna, je\eli ri"D<0
odpowiada jej cyfra ilorazu o wartości qi=0
jeśli reszta ri jest niepoprawna, to
" właściwą kolejną resztą jest ri=2ri-1
" podstawą wyznaczenia wartości kolejnej cyfry ilorazu jest
ri+1=2(2ri-1)-D
" tę samą wartość otrzymamy w wyniku opóznionej korekcji, dodając D
ri+1=2(2ri-1-D)+D
Jeśli XD<0 to X"2- m jest niepoprawną resztą, więc
gdy X D e" 0 0 gdy r0 D < 0
ńł2-m X - D ńł
r0 = , q0 =
ł ł
-m
ół1 gdy r0 D > 0
ół2 X + D gdy X D < 0
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 9
Dzielenie
Dzielenie nieodtwarzające (nierestytucyjne)
Zale\ność kolejnej reszty od poprzedniej i wyznaczonej z niej q
" ri = 2ri-1 - D < 0!qi = 0 oraz ri+1 = 2(2ri-1 - D) + D = 2ri + D
" ri = 2ri-1 - D e" 0!qi = 1 oraz ri+1 = 2(2ri-1 - D) - D = 2ri - D
Algorytm dzielenia nieodtwarzającego w kodzie U2 (|X"2- m|<|D|)
gdy X D e" 0
ńł2-m X - D
Krok 0. r0 =
ł
-m
ół2 X + D gdy X D < 0
Krok 1. Je\eli: a) ri D e" 0 podstaw qi = 1 i oblicz ri+1 = 2ri - D,
b) ri D < 0 podstaw qi = 0 i oblicz ri+1 = 2ri + D .
0 gdy ri D < 0
ńł
qi = ri+1 = 2ri + (1- 2qi )D , i=0,1,2,...
ł
ół1 gdy ri D > 0
Krok 2. Zwiększ i. Jeśli iKrok 3. rpD < 0!rp ! rp + D, Q ! Q - ulp
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 10
Dzielenie
Procedura dzielenia nieodtwarzającego
ri+1
D
(1) (2)
qi+1=1
qi=0 qi=1
2ri
(3)
(0,0) D 2D
- 2D - D
qi+1=0
- D
Wykres dzielenia nieodtwarzającego w kodzie U2 (D>0)
schemat wyznaczania cyfry ilorazu (1), reszty częściowej (2)
i przeskalowanej reszty częściowej (3)
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 11
Dzielenie
Schemat dzielenia nieodtwarzającego
ShL
C X/R Q 0 D
Ł
R
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
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 12
Dzielenie
Dzielenie odtwarzające i nieodtwarzające (U2) przykład 1
X D > 0 zbędne skalowanie, |X / D | < 1
X= D =
X ( 0 ) 0 , 0 1 1 1
X ( 0 ) 0 , 0 1 1 1 D ( 1 ) 1 , 0 0 1 1
rD e" 0 rD < 0
r0 = X ( 0 ) 0 , 0 1 1 1 q0 = 0 r0 = X D ( 1 ) 1 , 1 0 1 0
q0=0
2r0 = 2X ( 0 ) 0 , 1 1 1 0 2r0 ( 1 ) 1 , 0 1 0 0
D ( 1 ) 1 , 0 0 1 1 13/16 + D ( 0 ) 0 , 1 1 0 1
rD e" 0 rD e" 0
r1 = 2r0 D ( 0 ) 0 , 0 0 0 1 q1 = 1 r1 = 2r0 + D ( 0 ) 0 , 0 0 0 1
q1=1
2r1 ( 0 ) 0 , 0 0 1 0 2r1 ( 0 ) 0 , 0 0 1 0
D ( 1 ) 1 , 0 0 1 1 D ( 1 ) 1 , 0 0 1 1
rD < 0
r2 = 2r1 D ( 1 ) 1 , 0 1 0 1 q2 = 0 r2 = 2r1 D ( 1 ) 1 , 0 1 0 1 < 0
q2=0
( 0 ) 0 , 0 1 0 0 2r2 ( 1 ) 0 , 1 0 1 0
2r2 = 2 " 2r1
D ( 1 ) 1 , 0 0 1 1 + D ( 0 ) 0 , 1 1 0 1
rD < 0
r3 = 2r2 D ( 1 ) 1 , 0 1 1 1 q3 = 0 r3 = 2r2 + D ( 1 ) 1 , 0 1 1 1 < 0
q3=0
( 0 ) 0 , 1 0 0 0 2r3 ( 1 ) 0 , 1 1 1 0
2r3 = 2 " 2r2
D ( 1 ) 1 , 0 0 1 1 + D ( 0 ) 0 , 1 1 0 1
rD < 0
r4 = 2r3 D ( 1 ) 1 , 1 0 1 1 q4 = 0 r4 = 2r3 + D ( 1 ) 1 , 1 0 1 1 < 0
q4=0
R = 2r3 ( 0 ) 0 , 1 0 0 0 R = 2r4 + D ( 0 ) 0 , 1 0 0 0
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 13
Dzielenie
Dzielenie nieodtwarzające w kodzie SD oraz U2
" iloraz w kodzie U2 wartość cyfry zale\y od znaku dzielnika
" iloraz w ograniczonej reprezentacji SD (bez zer)
1, gdy 2ri-1 e" 0,
ńł
qi =
ł1, gdy 2r < 0, ri = 2ri-1 - qi D
ół i-1
" dzielna i dzielnik w kodzie U2, wynik w systemie SD
" dzielna ujemna znak ilorazu jest ustalany automatycznie
" dzielnik ujemny odwrotne przypisanie cyfr ilorazu, zatem
1, gdy ri-1 D > 0 lub D > 0 & ri-1 = 0,
ńł
qi =
ł
1, gdy ri-1 D < 0 lub D < 0 & ri-1 = 0.
ół
ńł gdy ri-1 < 0,
sgn D,
albo qi = sgnD= |D|/D
ł
ółsgn D, gdy ri-1 e" 0.
" korekcja jeśli XR<0: (XD>0 ! R+D, Q 1), (XD<0 ! R D, Q+1)
" korekcja gdy ri-1 = 0 w algorytmie brak mo\liwości wytworzenia zera
iloraz Q = {q1,...,qi ,1,1,1,...} zamiast Q = {q1,..., qi ,0,0,0,...}. (!!|R|=|D|)
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 14
Dzielenie
Schemat dzielenia nieodtwarzającego w kodzie SD oraz U2
" iloraz w ograniczonej reprezentacji SD (bez zer)
ri
|D|
q = sgnD q = sgn D
i i
2 ri 1
2|D|
2|D| |D| (0,0) |D|
|D|
Parametryczny wykres dzielenia nieodtwarzającego w kodzie U2
iloraz Q w kodzie SD przekodowanie na kod U2: podstawienie qi = 2zi -1.
p p p-1
p
Q = zi 2-i+1 = -(1- z1) + zi+12-i + 2- p
"(2z -1)2-i = -(1- 2- ) + " "
i
i=1 i=1 i=1
1
zi = (1+ qi ) ! |{(1- z1), z2, z3..., zn ,1}U 2 | = |{0,q1,q2,q3...,qn}SD |
2
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 15
Dzielenie
Dzielenie nieodtwarzające (SD) przykład
D=0,0110 X=0,0011 U2 SD NB
2r0=2X (0)0,0110 q1=1
e" 0
D (1)1,1010
r1=2r0 D (0)0,0000 q1=1
e" 0
2r1 (0)0,0000 q2=1
e" 0
D (1)1,1010
r2=2r1 D (1)1,1010 < 0 q2=0
2r2 (1)1,0100 < 0 q3= 1
+D (0)0,0110 q2q3=01
r3=2r2+D (1)1,1010 < 0 q3=0
2r3 (1)1,0100 < 0 q4= 1
+D (0)0,0110 q3q4=01
r4=2r3+D (1)1,1010 < 0 < 0 q4=0
Q=0,1001
korekcja (0)0,0110 q4=0 Q=0,1000
R=r4+D (0)0,0000 Q=0,1000
Janusz Biernat, Dzielenie, 14 grudnia 2003 DIV 16
Obliczanie "
"
"
"
Przybli\enia
Niech Q = {qn-1,qn-2,...,q0,...,q-m} i Q( p) = {qn-1,qn-2,...,qn- p,0,...,0} . Mamy
n- p n- p
Q( p-1) + qn- p = Q( p) d" Q( p-1) + (qn- p +1)
n- p n-( p-1)
Q( p-1) d" Q( p) d" ... d" Q d" ... d" Q( p) + d" Q( p-1) +
n- p n- p
Q(p) przybli\enie Q z dokładnością (Q - Q( p) d" )
n- p n- p
Q( p) E" X z dokładnością jeśli (Q( p))2 d" X < (Q( p) + )2
Jak znalezć kolejną cyfrę qn p rozwinięcia i przybli\enie Q(p) pierwiastka
Q = X na podstawie wyznaczonego wcześniej przybli\enia Q(p 1)? Mamy
n- p n- p
(Q( p-1) + qn- p )2 = (Q( p))2 d" X < (Q( p) + )2
qn- p jest taka, \e reszta częściowa R( p) = X -[Q( p)]2 jest najmniejsza i dodatnia
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 1
Obliczanie "
"
"
"
Algorytm odręczny
n- p n- p
R( p) - R( p-1) = [Q( p-1)]2-[Q( p)]2= -qn- p [2Q( p-1) + qn- p ]
n- p n- p
R( p) = R( p-1) - qn- p [2Q( p-1) + qn- p ]
-(n- p) -(n- p)
Po skalowaniu rp = R( p)( )2, kładąc Qp = Q( p), otrzymamy:
2
rp = rp-1 - qn- p[2Qp-1 + qn- p]
algorytm
-2n
0. r0 = X
1. przeskaluj poprzednią resztę częściową r(p 1) przez 2
2. podwój i przeskaluj przez obliczone przybli\enie pierwiastka q(p 1)
3. znajdz największą qn-p, dla której kolejna reszta jest najmniejsza dodatnia
4. powtarzaj od 1. a\ do uzyskania wymaganej dokładności
Pierwsza cyfrą rozwinięcia spełnia oczywiście nierówność
2 -2(n-1)
2
(qn-1) d" X < (qn-1 +1)
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 2
Obliczanie "
"
"
"
Algorytm odręczny przykład
8 4 3, 3 5 4 4 84310 = 29 29 +2
q1=2
4
Q1 =2 2"2"10
4 4 3
(40+q0)q0 d" 443 q0=9
4 4 1
Q2 =29 2"29"10
2 3 5
(580+q 1)q 1 d" 235 q 1=0
2 3 5 4 4
Q3 =290 2"290"10
2 3 2 1 6
(5800+q 2)q 2 d" 23544 q 2=4
1 1 0 1 0 0 1 0 1 1 84310 = 292 +2
q4=1
1 Q1 =1
1 0 0 1
(100+q3)q3 d" 1001 q3=1
1 0 1 Q2 =11
1 0 0 0 0
(1100+q2)q2 d" 10000 q2=1
1 1 0 1 Q3 =111
0 0 1 1 1 0
(11100+q1)q1 d" 1111 q1=0
0 0 0 0 0 Q4 =1110
0 1 1 1 0 1 1
(111000+q0)q0d" 111011 q0=1
1 1 1 0 0 1 Q5 =11101 2910
1 0 1 0 r5 =10
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 3
Obliczanie "
"
"
"
Algorytm odręczny sekwencyjne generowanie podwojenia
8 4 3, 3 5 4 4 2
q1=2
4 +2
Q1 =2 2"2"10
4 4 3 4 9
(4q)q d" 443 q0=9
4 4 1
+9
Q2 =29 2"29"10
2 3 5 5 8 0
(58q)q d" 235 q 1=0
2 3 5 4 4
=0
Q3 =290 2"290"10
2 3 2 1 6 5 8 0 4
(580q)q d" 23544 q 2=4
1 1 0 1 0 0 1 0 1 1 1
q4=1
1 Q1 =1 +1
1 0 0 1 1 0 1
(10q)q d" 1001 q3=1
1 0 1 Q2 =11 1
1 0 0 0 0 1 1 0 1
(110q)q d" 10000 q2=1
1 1 0 1 Q3 =111 +1
0 0 1 1 1 0 1 1 1 0 0
(1110q)q d" 1111 q1=0
0 0 0 0 0 Q4 =1110 +0
0 1 1 1 0 1 1 1 1 1 0 0 1
(11100q)qd" 111011 q0=1
1 1 1 0 0 1 Q5 =11101 +1
1 0 1 0 r5 =10 1 1 1 0 1 0
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 4
Obliczanie "
"
"
"
Obliczanie pierwiastka kwadratowego w systemie NB
n- p n- p
R( p) - R( p-1) = [Q( p-1)]2-[Q( p)]2= -qn- p [2Q( p-1) + qn- p ],
-(n- p)
Po skalowaniu r( p) = R( p) , otrzymamy wzór podobny jak w dzieleniu:
n- p
r( p) = r( p-1) - qn- p[2Q( p-1) + qn- p ]
analogia do dzielenia
obliczanie pierwiastka kwadratowego w układzie dzielącym
W systemie dwójkowym reguła upraszcza się bo qi2 = qi "{0,1}.
0 -2n
Po normalizacji X = X i uproszczeniu indeksów (qn i qi) otrzymamy
ri = 2ri-1 - qi (2-i + 2Qi-1), i=1,2,..., p, r0 = X ,
ńł
0, gdy 2ri-1 < (2-i + 2Qi-1),
qi =
ł
e" (2-i + 2Qi-1).
ół1, gdy 2ri-1
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 5
Obliczanie "
"
"
"
Obliczanie pierwiastka kwadratowego w systemie NB przykład
2 i + 2Qi 1 qi
r0 = X 0 0 , 1 0 1 0 1 1 1 1 q0 = 0 0,
2r0 0 1 , 0 1 0 1 1 1 1 0 00,1 q1 = 1 0,1
e"
d1 = (2 1 + 2Q0 ) 1 1 , 1 0 0 0 0 0 0 0
r1 = 2r0 d1 0 0 , 1 1 0 1 1 1 1 0
2r1 0 1 , 1 0 1 1 1 1 0 0 01,01 q2 = 1 0,11
e"
d2 = (2 2 + 2Q1 ) 1 0 , 1 1 0 0 0 0 0 0
r2 = 2r1 d2 0 0 , 0 1 1 1 1 1 0 0
2r2 0 0 , 1 1 1 1 1 0 0 0 < 01,101 q3 = 0 0,110
0 1 , 1 1 1 1 0 0 0 0 01,1001 q4 = 1 0,1101
2r3 = 2 " 2r2 e"
d4 = (2 4 + 2Q3 ) 1 0 , 0 1 1 1 0 0 0 0
r4 = 2r3 d4 0 0 , 0 1 1 0 0 0 0 0
2r4 0 0 , 1 1 0 0 0 0 0 0 < 01,10101 q5 = 0 0,11010
0 1 , 1 0 0 0 0 0 0 0 < 01,101001 q6 = 0 0,110100
2r5 = 2 " 2r4
0 1 1 , 0 0 0 0 0 0 0 0 01,1010001 q7 = 1 0,1101001
2r6 = 2 " 2r5 e"
d7 = (2 7 + 2Q6 ) 1 1 0 , 0 1 0 1 1 1 1 0
r7 = 2r6 d7 0 0 1 , 0 1 0 1 1 1 1 0
2r7 0 1 0 , 1 0 1 1 1 1 0 0 01,10100101 q8 = 1 0,11010011
e"
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 6
Obliczanie "
"
"
"
Obliczanie pierwiastka kwadratowego metoda nierestytucyjna
algorytm oparty na regule
ri = 2ri-1 - qi (2-i + 2Qi-1), i=1,2,..., p, r0 = X
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
ri = 2ri-1 - di , di = qi (2-i + 2Qi-1), r0 = X , i=1,2,...,p,
1, gdy 2ri-1 e" 0,
ńł
qi =
ł1, gdy 2r < 0,
ół i-1
! konieczna jest bie\ąca korekcja po wystąpieniu cyfry ujemnej
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 7
Obliczanie "
"
"
"
Obliczanie pierwiastka kwadratowego metoda nierestytucyjna
X=49/256 2 i+ 2Qi 1 qi (SD) Qi
r0=X 00,00110001 q0=0 0,
2r0 00,01100010 00,1 q1=1
e" 0
d1= (2 1+2Q0) 11,10000000 0,1
r1=2r0 d1 11,11100010
2r1 11,11000100 < 0 01,01 q2= 1 0,11
+d2=+(2 2+2Q1) 00,11000000 00,11 0,01
r2=2r1+d2 00,10000100 q1q2=01
2r2 01,00001000 0,101
e" 0
d3= (2 3+2Q2) 11,01100000 q3=1 0,011
r3=2r2 d3 00,01101000
2r3 00,11010000 0,1101
e" 0
d4= (2 4+2Q3) 11,00110000 q4=1 0,0111
R=r4=2r3 d4 01,00000000
7
Pierwiastek ma skończone rozwinięcie Q = 0,0111 (16 ).
W drugim kroku dokonano zamiany przybli\enia pierwiastka z kodu SD na U2
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 8
Obliczanie "
"
"
"
Janusz Biernat, Dzielenie, 14 grudnia 2003 SQRT 9
Wyszukiwarka
Podobne podstrony:
dzielenie wielomianów
dzielenie wyrazow
13 Czas i przestrzeń w dziele literackim1
więcej podobnych podstron