ARYTMETYKA KOMPUTERÓW
1. Znajdź podstawę x systemu naturalnego, w którym: a) 41
, b) 22
c) a 2
x = 4
x = 5
=301 x , d) b 2 =562 x
2. Znajdź podstawę β systemu naturalnego, w którym liczby naturalne x 1 oraz x 2 są rozwiązaniami równania ax 2+ bx+ c = 0. Wykonaj obliczenia dla x 1 = 5β , x 2 = 8β i równania 5β x 2– 50β x+125β = 0
3* Znajdź podstawę systemu naturalnego, w którym x
∈
1 , x 2
są rozwiązaniami równania ax 2+ bx+ c = 0
gdzie a,b,c ∈
(całkowite).**Rozwiąż zadanie jeśli wiadomo, że w tym systemie a,x 1 ,x 2 są liczbami
jednocyfrowymi, b jest liczbą dwucyfrową b = b β
β 2
β
1 + b 0, zaś c jest liczbą o postaci c = c 2
+ c 1 + c 0,
c 2 = 0 lub 1. Wykonaj obliczenia dla x 1 = 5β , x 2 = 8β oraz a = 1 lub 3.
4. Wykaż, że w standardowym systemie naturalnym o podstawie β suma wartości cyfr iloczynu liczby
jednocyfrowej przez β − 1 jest stała. Ułóż tabliczki mnożenia w systemach o bazie β = 5, 7, 9, 11, 13.
5* Wykaż, że w dowolnym systemie naturalnym suma cyfr iloczynu dowolnej liczby jednocyfrowej przez
największą liczbę dwucyfrową {β–1, β–1}β jest stała. Spróbuj uogólnić uzyskany wynik.
6. Oblicz metodą pisemną iloczyn 0,324β × 2,41β i iloraz 43,4β : 3,2β dla β = 5, 7, 9, 11, 13 oraz dla β = α2,
korzystając z tabliczki mnożenia w systemie o podstawie α = 3, 4.
7. Przeprowadź konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,58110 = (…)16 = (…)4
b) 0CD,1216 = (…)2= (…)10
c) 3,0128 = … (…)2 …= (…)16
d) 34,56 ×
×
×
10
2–5 = (…)2 = (…)16
e) 102,213 5–2 = (…)5
f) 0BACA16 5–3 = (…)10
g) 6745,81
×
9 = (…)7 = (…)10
h) 0AA,1211 = (…)10 = (…)9
i) 102,213 15–2 = (…)5
j) 347/567 = (…)2
k) 234,(56)9 = (…)7
l) 12,3(45)7 = (…)10 = (…)11
8* Wykaż, że wynikiem konwersji ułamka nieskracalnego w systemie o danej podstawie, na reprezentację
w innym systemie naturalnym, może być ułamek nieskończony (**okresowy), jeśli istnieje nierozkła-
dalny podzielnik podstawy źródłowej, który nie jest podzielnikiem podstawy docelowej.
9. Przeprowadź konwersję ułamka okresowego na system, w którym jego reprezentacja jest skończona:
a) 0,(27)10 =
b) 0,(101)2 =
c) 1 – 0,(56)9 =
d) 0,(35)11 – 0,(2)11 =
e) 0,1(23)7=
* Wykaż, że taka konwersja ułamka okresowego jest wykonalna w każdym systemie naturalnym.
A. Wykaż, że w systemie naturalnym przeniesienie otrzymane w wyniku dodawania lub pożyczka
podczas odejmowania na każdej pozycji są zawsze równe 0 lub 1.
B. Opracuj algorytm dodawania lub odejmowania liczb znakowanych zapisanych w systemie znak-moduł
(SM). Przyjmij, że znak liczby jest kodowany standardowo (0 – plus, 1 –minus).
C. Opracuj algorytmy działań w systemie naturalnym o dowolnej podstawie:
a) dodawania i odejmowania,
b) mnożenia,
c) dzielenia
D. Oblicz odpowiednio wartości największej i najmniejszej liczby całkowitej, reprezentowanych przez
łańcuch k cyfr w systemie a) naturalnym o podstawie β b) negabazowym, c) z cyframi znakowanymi,
d)* uzupełnieniowym pełnym i niepełnym, e)* spolaryzowanym „+1/ β k–1
β k–1
2
” oraz „+1/2
–1”.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
0
ARYTMETYKA KOMPUTERÓW
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami części ułamkowej liczby:
a) – 674,58110
b) – 0A,1216
c) – 3,0128
d) + 34,5610
e) 4,5610 – 4,5(6)10
Porównaj otrzymane kody z notacją w systemie uzupełnieniowym do 1 (U1) i systemie znak-moduł.
2. Dodaj i odejmij liczby 4-cyfrowe podane w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745 ± 8123
b) 9,745 ± 0,8(23)
c) 31,56± 84,23
d) 9,994± 9,916
Używając lewostronnego rozszerzenia zweryfikuj poprawność wyników otrzymanych na 4 pozycjach.
3* Wykaż, że w systemie stałobazowym i uzupełnieniowym, w dodawaniu lub odejmowaniu o ustalonej
liczbie pozycji argumentów i wyniku, użycie dodatkowej pozycji lewostronnego rozszerzenia wyniku
i argumentów wystarczy do wykrycia nadmiaru (przekroczenia zakresu).
4* Wykaż, że w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy można
wykonać przez grupowanie (β → β S ) lub dekompozycję cyfr (β S → β ).
5. Oblicz sumę i różnicę liczb danych jako 10011101 i 01111001, 11011101 i 10111101, zakładając, że
podane łańcuchy k = 8 bitów (ciągi zero-jedynkowe) reprezentują liczby w kodzie
a) naturalnym (NB)
b) uzupełnieniowym pełnym (U2)
c) uzupełnieniowym niepełnym (U1)
d) znak-moduł (SM)
e) spolaryzowanym „+2 k–1–1”
f) spolaryzowanym „+2 k–1”.
Zweryfikuj poprawność otrzymanych wyników: A) wykonując działanie odwrotne (suma – argument,
różnica + odjemnik) B) używając lewostronnego rozszerzenia (oprócz e) i f)).
6. Znanych jest kilka najbardziej znaczących bitów liczb 48-bitowych w kodzie uzupełnieniowym U2.
11101010..?? oraz 10011110..?? Sprawdź, czy w ich dodawaniu i odejmowaniu wystąpi nadmiar.
7. Korzystając z zależności X − Y = X + Y i zakładając, że liczby są dane w systemie naturalnym, oblicz: a) 6745 – 8123
b) 9,745 – 0 , 823
c) 34,56– 81,23
d) 100111012 – 011110012
Sprawdź otrzymane wyniki wykonując działania odwrotne (różnica + odjemnik).
8. Wykaż, że w systemie naturalnym lub uzupełnieniowym pełnym mnożenie liczb m–pozycyjnych nie
powoduje nadmiaru, jeśli wynik jest kodowany na co najmniej 2 m pozycjach.
9. Wynik mnożenia m–bitowych liczb w kodzie U2 jest kodowany na 2 m–1 bitach. Czy jest możliwe
wystąpienie nadmiaru, a jeśli tak to przy jakich wartościach mnożnej i mnożnika?
A. Przyjmując, że 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) wykonaj mnożenia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111.
Wykonaj mnożenie (U2) stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia.
B. Pokaż, że w systemie naturalnym dwójkowym i systemie uzupełnieniowym do 2 mnożenie przez stałą,
która jest sumą lub różnicą potęg dwójki można wykonać jako dodawanie skalowanej mnożnej.
C. Oblicz iloczyn liczb 4-cyfrowych podanych w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745
×
×
×
×
U10
8123U10 b) 9745U10 0823 U10
c) 3156 U10 8423 U10
d) 9994 U10 9916 U10
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
1
ARYTMETYKA KOMPUTERÓW
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745
×
×
×
×
U8
7123U8
b) 7745U8 0723 U8
c) 3156 U8 6423 U8
d) 7774 U8 7716 U8
2. Oblicz bezpośrednio metodą sekwencyjną („kolejnych reszt”) z dokładnością do 4 pozycji znaczących
iloraz liczb reprezentowanych w systemie uzupełnieniowym pełnym
a) 01010011U2 : 1011U2
b) 1010011U2 : 01011U2 c) 876U10 : 176U10
d) 876U10 : 761U10.
3. Wykonaj bezpośrednio w systemie U10 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
4. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
5. Wykonaj bezpośrednio w kodzie U2 z dokładnością do 4 cyfr znaczących ilorazu dzielenie
nieodtwarzające liczb:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
6. Oblicz metodą sekwencyjną („kolejnych reszt”) pierwiastek kwadratowy z liczb
a) 1234567, b) 1010 0010 0111 11002, c) 98765432110 d) 123,4567, e) 10100 0100,1111 1002
z dokładnością do jednej, dwóch i siedmiu cyfr znaczących oraz podaj trzecią i czwartą resztę.
7. Dane jest przybliżenie pierwiastka kwadratowego z dokładnością do 3 cyfr znaczących i trzecia reszta.
Podaj dwie kolejne cyfry przybliżenia pierwiastka, jeśli:
a) Q 3 =1237, r 3 =34567, b) Q 3 =12310, r 3 = 345610, c) Q 3 =1012, r 3 =111012, 8. Dane jest przybliżenie pierwiastka kwadratowego z dokładnością do 4 cyfr znaczących i czwarta reszta
równa 0. Oszacuj wartość liczby pierwiastkowanej, jeśli: a) Q 4 =12,347, b) Q 4 =1,23410, c) Q 4 =11012.
9. Oblicz metodą nieodtwarzającą pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002
z dokładnością do dwóch i pięciu cyfr znaczących oraz podaj trzecią i czwartą resztę.
A* Pokaż, że w naturalnym systemie dwójkowym dzielenie przez stałą, która jest sumą lub różnicą
dwóch potęg dwójki, można wykonać przez odejmowanie, jeśli dzielenie nie wytwarza reszty.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
2
ARYTMETYKA KOMPUTERÓW
1. Twierdzenie Euklidesa o podzielności liczb orzeka, że największy wspólny podzielnik dwóch liczb
naturalnych jest podzielnikiem reszty z dzielenia większej przez mniejszą. Wykaż, równoważność tej tezy
z tezą, że największy wspólny podzielnik dwóch liczb jest podzielnikiem ich różnicy.
2. Korzystając z twierdzenia Euklidesa znajdź największy wspólny podzielnik liczb:
a) 6745 i 8123
b) 9994, 92 i 9916
c) 375, 243, 345 i 126
d) 220–1 oraz 25+1
3. Pokaż, że liczby 2 k + 1 i 2 k + 1 + 1 są względnie pierwsze ( k ∈ N – jest liczbą naturalną)
*Czy prawdziwe jest twierdzenie, że liczby 2 k + 1 i 2 r + 1 ( k , r ∈ N ) są względnie pierwsze?
4* Wykaż, że liczby (22 n + )
1 oraz (2 n + )
1 i (22 n 1
+ + 2) i (2 n − )
1 ( n∈ N ) są względnie pierwsze.
5. Nie wykonując dzielenia wyznacz resztę z dzielenia liczby 1011 0011 0111 11012 przez
a) 11112
b) 100012
c) 111112
d) 100000012.
6. Stosując reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) wobec modułów:
25710, 78 , 6510, 3F16, 1116, 0FF16 dla liczb 46528 i 0ABCD16, oraz ich sumy, różnicy i iloczynu.
7. Podaj reprezentację resztową liczby 2345610 w bazie: a) (29, 30, 31), b) (99, 100, 101), a) (63, 64, 65).
8* Znajdź odwrotności multyplikatywne iloczynów par modułów bazy systemu resztowego ( a–1, a, a+1)
względem trzeciego z nich, zakładając, że a jest liczbą parzystą.
9* Wektor (1, 2, 3) jest reprezentacja resztową liczby x w bazie (29, 30, 31). Znajdź tę liczbę w zbiorze
kongruencji naturalnych ( x∈[0, M=29⋅30⋅31)) i całkowitych ( x∈ –(M–1) /2, M–1 /2)).
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
a) 674,531
⋅
⋅
8
b) 0,128 8-51
c) – 0ABC,DE16
d) 10,1010101010U2 4 -61
B. Zapisz w 32-bitowym formacie zmiennoprzecinkowym IEEE 754 pierwiastki kwadratowe z liczb:
a) 1010 0010, 0111 11002, b) 123,4568, c) 10100 0100, 1111 1002
C. Oblicz i zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 z dokładnością do
5 cyfr znaczących pierwiastki kwadratowe z liczb danych w tym formacie:
a) 0 0100 0100 111 1100 1010 0010 0111 1100, b) 0 1010 0101 1111 1010 0100 1111 1111 1002
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 1002
D* Wykaż, że w odejmowaniu (dodawaniu) zmiennoprzecinkowym operandów dokładnych, bit S dla
znormalizowanej różnicy (sumy) może być wyznaczony przed wykonaniem działania.
E. Wyznacz z dokładnością do 4 bitów znacznika zaokrąglenia argumentów 1,101111011 i 1,101111001
uzupełnione bitami G, R, S. Wykonaj ich mnożenie i porównaj z wynikiem pełnego mnożenia.
F* Wykaż, że w mnożeniu znormalizowanych operandów, bit S znormalizowanego iloczynu może być
wyznaczony przed mnożeniem. Pokaż, że jeden z czynników może być zdenormalizowany.
G* Oszacuj maksymalny błąd przybliżenia różnicy podczas odejmowania znormalizowanych operandów
obliczonych z taką samą dokładnością bezwzględną znacznika (mantysy).
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
3
ARYTMETYKA KOMPUTERÓW
1. Stosując reguły działań w algebrze Boole’a uprość poniższe wyrażenia
a) x+( x⊕ y)
b) xyz+( x⊕ y) +( z⊕ y)
c) x+ xy+ xyz
d) zy+( x⊕ y)
e) z x+ z( x⊕1)
f) x+ xy+( x⊕ yz)
2. Na podstawie tabel wartości funkcji logicznych f 1 i f 2 (tzw. tabel prawdy) podaj ich wszystkie mintermy (konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x 3
x 2
x 1 f 1(x)
x 3
x 2
x 1 f 2(x)
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
2a. Ułóż tabele prawdy dla funkcji nadmiaru w dodawaniu / odejmowaniu w kodzie U2 i podaj wyraż enie
logiczne definiują ce tę funkcję
3. Wyznacz funkcje dualne i komplementarne do funkcji f (x) = x x + x x i f (x) = x x + x ( x + x ) 1
2
1
3
2
2
3 1
3
2
1
oraz ich sumy logicznej i iloczynu logicznego. Narysuj sieci logiczne realizujące te funkcje.
4. Korzystając z twierdzenia Shannona rozwiń wszystkie funkcje z zadania 3 względem zmiennej x 3.
5. Wykaż, że wartość funkcji logicznej [ z⋅ f( x)+( z⊕ f( x))] f( x) nie zależy od zmiennej z.
6* Pokaż, że każdą funkcję logiczną można wyrazić za pomocą tylko funkcji NOR (suma negacji) lub
tylko funkcji NAND (iloczyn negacji).
7. Wyznacz charakterystyki AT sieci logicznych realizujacych funkcje dane przez wyrażenia w zadaniu 1
8. Subtraktor 1-bitowy realizuje funkcje logiczne różnicy d = f ( x, y, z) i pożyczki b = h ( x, y, z) równoważne arytmetycznemu równaniu odejmowania 1-bitowego x – y – z = – 2 d + b ( x , y , z , d , b ∈ {0, 1}) . Podaj tabelę prawdy subtraktora i wyznacz charakterystyki AT subtraktora 8-bitowego.
9. Sumator 1-bitowy realizuje funkcje logiczne sumy s = f ( x, y, z) i przeniesienia c = h ( x, y, z) równoważne arytmetycznemu równaniu dodawania 1-bitowego x + y + z = 2 c + s ( x , y , z , s , c ∈ {0, 1}) . Zaprojektuj ogniwo inkrementera realizującego funkcje s = f ( x, 1 , z) oraz c = h ( x, 1 , z) i oblicz charakterystyki AT.
A. Sumator warunkowy 1-bitowy realizuje funkcje logiczne warunkowej sumy s 0 = f ( x, y, 0), s 1 = f ( x, y, 1) i przeniesienia c 0 = h ( x, y, 0), c 1 = h ( x, y, 1) równoważne równaniu dodawania 1-bitowego przy założeniu, że przeniesienie wejściowe jest odpowiednio równe 0 albo 1. Wyznacz te funkcje.
B* Narysuj schemat logiczny sumatora 1-bitowego, którego wyjścia sumy i przeniesienia są wytwarzane
z użyciem multiplekserów sterowanych przeniesieniem wejściowym na podstawie funkcji sumy
i przeniesienia zerowego i jedynkowego s 0 , s 1 , c 0 , c 1 . Wyznacz charakterystyki AT tego układu.
C* Pokaż, że charakterystyki AT sieci realizujących funkcję dualną i komplementarną są jednakowe.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
4
ARYTMETYKA KOMPUTERÓW
1. Oblicz charakterystyki AT sumatorów uniwersalnych RCA dla kodów k-bitowych:
a) uzupełnieniowego pełnego (U2)
b) uzupełnieniowego niepełnego (U1)
c) znak-moduł,
d) spolaryzowanego ujemnie „+2 k–1”
e) spolaryzowanego dodatnio „+2 k–1–1”
2. Zaproponuj sposób kodowania cyfr i zaprojektuj sumator jedno- i cztero-pozycyjny dla systemu
a) U10 z kodowaniem cyfr w kodzie „+3” i kodzie BCD
b) dwójkowego negabazowego (β = –2),
c)* naturalnego trójkowego (β = 3) i dwójkowego z cyfrą znakowaną SD (D={–1,0,+1})
3. Oblicz charakterystyki AT sumatora 24-bitowego z przeniesieniami przeskakującymi ( carry-skip) jeśli
ma on strukturę a) 3-4-4-3-4-4-2, b) 3-3-4-4-4-3-3, c) 4-4-4-4-4-4, d) 6-6-6-6, e) optymalną.
4. Zaprojektuj 8-bitowe układy inkrementacji i dekrementacji i wyznacz ich charakterystyki AT.
5. Zaprojektuj 4- i 8-bitowy sumator sum warunkowych i wyznacz ich charakterystyki AT.
6. Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA i wyznacz ich charakterystyki AT.
7. W celu dodania n operandów k-bitowych użyto sumatora CSA ( carry-save). Ile bitów zawiera suma?
Jakie jest opóźnienie (T) podczas obliczania sumy, jeśli sumę końcową wytwarza
a) sumator ze skrośną propagacją przeniesień RCA, b) sumator sum warunkowych COSA.
Obliczenia wykonaj dla n = 7, 15, 31 oraz k = 8, 16, 32.
8. Ile poziomów musi zawierać sumator CSA użyty do redukcji iloczynów częściowych tworzonych
w mnożeniu liczb 32-bitowych w kodzie naturalnym (NB)? Ile sumatorów elementarnych (3,2)
zawiera najbardziej skomplikowana gałąź CSA odpowiadająca bitom o tej samej wadze.
9. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
A. Wyznacz, uwzględniając czas końcowego dodawania, najkrótszy czas dodawania 32 operandów 64-
bitowych w sumatorze CSA jeśli dysponujesz:
a) reduktorami (3,2) generującymi przeniesienia 1-bitowe, wnoszące opóźnienia T = 4 każdy
b) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóźnienia T = 6 każdy
B* Opracuj i uzasadnij algorytmy konwersji dwójkowo–dziesiętnej liczb całkowitych dodatnich, bez
wykonywania dzielenia, jeśli cyfry dziesiętne są kodowane: a) w kodzie BCD, b) w kodzie BCD+3.
C* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie NB
a) mod 11112
b) mod 100012
c) mod 1112 d) mod 10012
D* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie U2
a) mod 11112
b) mod 100012
c) mod 1112 d) mod 10012
E. Zaprojektuj sumator mod (28–1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
F* Zaprojektuj sumatory mod (24–1) i mod (24+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
5
ARYTMETYKA KOMPUTERÓW
1. Zakoduj na 8 bitach według prostej i odwrotnej reguły Booth’a w bazie 2 oraz w bazie 4 liczby:
a) –8710
b) +12110
c) 1011012
c) 1011101U2
2. Przyjmując, że 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) i używając mnożnika przekodowanego wg reguły Booth’a w bazie 2 i 4 wykonaj
mnożenia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111
3. Oblicz charakterystyki AT matrycy mnożącej dwa operandy: a) 4-bitowe, b) 8-bitowe c)* n-bitowe
4* Zaprojektuj matrycę mnożącą operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mnożnika wg reguły Bootha w bazie 4. Porównaj z innymi układami matrycowymi.
5. Oblicz charakterystyki AT sumatora CSA użytego do redukcji iloczynów częściowych w mnożeniu
operandów 4-, 8- bitowych danych: a) w kodzie NB, b) w kodzie U2 z eliminacją bitów rozszerzenia.
*Podaj oszacowanie charakterystyk AT dla mnożenia operandów n-bitowych.
6. W dzieleniu w systemie naturalnym w bazie 4 skalowana reszta częściowa ma wartość 2,2 D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia, kolejne dwie cyfry ilorazu.
7. W dzieleniu w systemie U2 przeskalowana reszta częściowa ma wartość: i) –0,2 D, ii) +0,7 D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia kolejne dwie cyfry ilorazu, zakładając,
że dzielnik D jest: a) ujemny, b) dodatni.
8. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
9. Wykonaj wykres P-D dla dzielenia w bazie 4 i dzielnika z zakresu [1,2). Podaj ile bitów musi być
porównywanych w celu wyznaczenia cyfr ilorazu.
A. Oblicz charakterystyki AT matryc dzielących operandy 8-bitowe w kodzie NB i U2
B. Oblicz metodą Newtona iloraz 3,1416 :2,7183.
C. Oceń czas obliczania pierwiastka kwadratowego z liczby całkowitej metodą sekwencyjną („kolejnych
reszt”) oraz na podstawie tożsamości: „suma n kolejnych nieparzystych liczb naturalnych jest równa
kwadratowi z ich liczby” (np. 1+3+5=32 1+3+5+7=42, 1+3+5+7+9=52 itd.)
*Określ minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
D* Oszacuj liczbę kroków algorytmu CORDIC potrzebnych do obliczenia wartości funkcji exp, ln, sin,
cos, arctg dla argumentu z przedziału [–1,1] z dokładnością do 32 bitów części ułamkowej.
E* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zależności:
n
n
n
j 1
n 1
j
3
n − n = ∑ 3
( ⋅ 2
i − 3⋅ i) = ∑
3
( i ⋅ ( i − )
1 ) = ∑
3
∑−2 i = ∑−
6
∑ i
i=1
i=1
j=1 i=0
j=1 i=1
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
6
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Znajdź podstawę x systemu naturalnego, w którym: a) 41
, b) 22
c) a 2
x = 4
x = 5
=301 x , d) b 2 =562 x
Wskazówka: a) i b): Należy podnieść obie strony równości do kwadratu i rozwiązać stosowne równanie ze
względu na nieznaną podstawę. Trzeba też zauważyć, że szukana podstawa musi być większa od
największej z cyfr występujących w równaniu (stąd wynika, że wartości cyfr <10 można uważać za
wartości w systemie dziesiętnym). Na przykład 5 ×
x 5 x =41 x skąd wynika, że 25=4 x+1, zatem x=6. Jeśli
liczba pierwiastkowana ma k cyfr, to trzeba rozwiązać równanie stopnia k–1 względem x. Na przykład
c) i d): Ponieważ kwadrat jest liczbą trzycyfrową, to x musi być liczbą dwucyfrową, co więcej
starszą cyfrą musi być 1 (bo (β)2 < 301β = 3β 2+1 <(2β)2). Mamy stąd równanie (β+ z)2 = 3β 2+1, czyli
2β 2–2zβ+(1– z 2) = 0. Zatem (wzory Viete’y), ponieważ z nie może być równe 1 (bo wtedy wystąpi
sprzeczność β = 1 ), jedno z rozwiązań musi być ujemne (ujemny jest iloczyn pierwiastków (1– z 2)).
Ponieważ oba rozwiązania muszą być też całkowite (ich suma wynosi z), to wystarczy badać wartości
nieparzyste z (3,5,7,...). I tak przy z=3 otrzymamy β = 4 (lub –1), gdy z=11 to β = 15 (lub –4).
Podobnie, dla przykładu d) mamy (2β)2 < 562β = 5β 2+6β +2 <(3β)2), skąd wynika, że starszą cyfrą
liczby b jest 2. Mamy stąd równanie (2β+ z)2 = 5β 2+6β +2, czyli β 2+(6–4 z)β +(2– z 2) = 0 z warunkiem β > 6 , a ponieważ z nie może być równe 1 (bo wtedy β = –1), iloczyn pierwiastków (2– z 2) jest ujemny
zaś suma (4 z–6) dodatnia. Otrzymamy odpowiednio dla kolejnych z zestawy ( z: suma, iloczyn) takie
jak: (2:+2, –2), (3,+6,–7) – β = 7 , (4,+10,–14), (5,+14,–23), (6,+18,–34), ... Jeśli kwadrat jest liczbą k-
cyfrową, to trzeba analizować równanie stopnia k–1 względem nieznanej podstawy β.
2. Znajdź podstawę β systemu naturalnego, w którym liczby naturalne x 1 oraz x 2 są rozwiązaniami równania ax 2+ bx+ c = 0. Wykonaj obliczenia dla x 1 = 5β , x 2 = 8β i równania 5β x 2– 50β x+125β = 0
Wskazówka: Ponieważ znamy pierwiastki, więc na podstawie wzorów Viete’y należy ułożyć równania ze
względu na β . W tym zadaniu mamy 5β ( x
) =
1 + x 2
50β , skąd natychmiast wynika (5β ×10β =50β ) że x 1
+ x
×
×
2 = 10β = β . Trzeba jeszcze sprawdzić, czy 513 (513 813) = 12513 (OK., bo 132+2×13+1 = 200).
*Jeśli rozwiązania równania x 2– 15β x+53β
= β
=
= 0 są naturalne, to x 1 + x 2
+ 5 oraz = x 1 x 2 5β + 3.
Musi więc być x 1 > 5 oraz x 2 < β (w przeciwnym razie jeden musi być ujemny) Jeśli x 1 = 6 , x 2 = β − 1 , to β = 9 . (powinny być dwa symetryczne rozwiązania dla x 1 oraz x 2 – jedno rozwiązanie dla β ).
3* Znajdź podstawę systemu naturalnego, w którym x
∈
1 , x 2
są rozwiązaniami równania ax 2+ bx+ c = 0
gdzie a,b,c ∈
(całkowite).**Rozwiąż zadanie jeśli wiadomo, że w tym systemie a,x 1 ,x 2 są liczbami
jednocyfrowymi, b jest liczbą dwucyfrową b = b β
β 2
β
1 + b 0, zaś c jest liczbą o postaci c = c 2
+ c 1 + c 0,
c 2 = 0 lub 1. Wykonaj obliczenia dla x 1 = 5β , x 2 = 8β oraz a = 1 lub 3.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
7
ARYTMETYKA KOMPUTERÓW
rozwiązania
Wskazówka: *Na podstawie wzorów Viete’y ułożyć układ równań względem nieznanej podstawy β
i nieznanego drugiego pierwiastka x
) =
=
2: – a ( x 1 + x 2
b oraz a x 1 x 2 c. **Pierwiastki całkowite muszą
być podzielnikami c – zależnie od wartości c można określić dozwolony zakres ich wartości. Powstałe
przypadki przeanalizować (łatwo to zrobić gdy pierwiastki są jednocyfrowe), zbadać też wyróżnik ∆.
4. Wykaż, że w standardowym systemie naturalnym o podstawie β suma wartości cyfr iloczynu liczby
jednocyfrowej przez β − 1 jest stała. Ułóż tabliczki mnożenia w systemach o bazie β = 5, 7, 9, 11, 13.
Wskazówka: x × ( β – 1 ) = ( x – 1 ) β + ( β – x ), zaś ( x – 1 ) + ( β – x ) = β – 1. Sąsiednie wielokrotności m najłatwiej obliczyć wykonując dodawanie lub odejmowanie: m⋅( a ± 1) = m⋅ a ± m.
5* Wykaż, że w dowolnym systemie naturalnym suma cyfr iloczynu dowolnej liczby jednocyfrowej przez
największą liczbę dwucyfrową {β–1, β–1}β jest stała. Spróbuj uogólnić uzyskany wynik.
Wskazówka: x×|{(β–1),(β–1)}| = x×(β 2–1)=( x–1)β 2+ β(β–1)+(β– x). Podobnie x×|{(β–1),…(β–1),(β–1)}|=
= x×(β k–1) = ( x–1)β k +(β–1)β k–1 +…+β(β–1)+(β– x) , zatem suma cyfr wynosi k(β–1).
6. Oblicz metodą pisemną iloczyn 0,324β × 2,41β i iloraz 43,4β : 3,2β dla β = 5, 7, 9, 11, 13 oraz dla β = α2,
korzystając z tabliczki mnożenia w systemie o podstawie α = 3, 4.
Wskazówka: Jeśli α = β 2, to { z,…,x}α= {( z div β),( z mod β),…,( x div β),( x mod β)}β , np. 0,539 = 0,12103
7. Przeprowadź konwersje podstawy (bazy), z dokładnością do 4 cyfr części ułamkowej wyniku:
a) 674,58110 = (…)16 = (…)4
b) 0CD,1216 = (…)2= (…)10
c) 3,0128 = … (…)2 …= (…)16
d) 34,56 ×
×
×
10
2–5 = (…)2 = (…)16
e) 102,213 5–2 = (…)5
f) 0BACA16 5–3 = (…)10
g) 6745,81
×
9 = (…)7 = (…)10
h) 0AA,1211 = (…)10 = (…)9
i) 102,213 15–2 = (…)5
j) 347/567 = (…)2
k) 234,(56)9 = (…)7
l) 12,3(45)7 = (…)10 = (…)11
Wskazówka: Konwersja przez podstawę skojarzoną (α = β k) przyśpiesza obliczenia – wyznaczamy k cyfr
w każdym kroku (np. konwersję na system dwójkowy łatwo wykonać przez system ósemkowy). Jeśli
mnożnik jest potęgą podstawy źródłowej, to skalowanie należy wykonać przed konwersją, a jeśli jest
potęgą bazy docelowej, skalowanie przeprowadzić po konwersji. Konwersję ułamka wymiernego (po
skróceniu) wykonać jako konwersję licznika i mianownika (zawsze dokładna) a następnie dzielenie
z żądaną dokładnością. Ułamek okresowy należy zamienić na ułamek wymierny, albo używając kilku
(>2) cykli okresu zaobserwować regularność zapisu wielokrotności ułamka.
8* Wykaż, że wynikiem konwersji ułamka nieskracalnego w systemie o danej podstawie, na reprezentację
w innym systemie naturalnym, moż e być ułamek nieskończony (**okresowy), jeśli istnieje nierozkła-
dalny podzielnik podstawy źródłowej, który nie jest podzielnikiem podstawy docelowej.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
8
ARYTMETYKA KOMPUTERÓW
rozwiązania
Wskazówka: Znajdź licznik ułamka danego w bazie β w bazie pβ gdy ( p,β)=1. (dowód podobnej tezy jest
w książce „Metody i układy arytmetyki komputerowej”). Twierdzenie kategoryczne („ jest” zamiast
„ moż e”) jest fałszywe, bo są przypadki gdy tak nie jest np. 0,510 = 0,12, ale np. 0,110 = 0,(00011)2.
9. Przeprowadź konwersję ułamka okresowego na system, w którym jego reprezentacja jest skończona:
a) 0,(27)10 =
b) 0,(101)2 =
c) 1 – 0,(56)9 =
d) 0,(35)11 – 0,(2)11 =
e) 0,1(23)7=
* Wykaż, że taka konwersja ułamka okresowego jest wykonalna w każdym systemie naturalnym.
Wskazówka: Wartość ułamka okresowego jest równa granicy szeregu nieskończonego. Należy obliczyć tę
granicę w postaci ułamka wymiernego, skrócić go i wtedy mianownik jest szukaną podstawą systemu
a licznik wyznacza wartość ułamka w systemie o tej podstawie. Na przykład 0,(3)10 = 0,3 + 0,03 + … =
= 0,3 / ( 1 – 0,1 ) = 1/3 = 0,13, c) 1 – 0,(56)9 = 0,(32)9 , d) 0,(35)11 – 0,(2)11 = 0,(35)11 – 0,(22)11 = 0,(13)11
A. Wykaż, że w systemie naturalnym przeniesienie otrzymane w wyniku dodawania lub pożyczka
podczas odejmowania na każdej pozycji są zawsze równe 0 lub 1.
Dowód: Ponieważ największą liczbą jest β –1, więc ich największą sumą jest β +(β –2), co oznacza
wystąpienie przeniesienia =1. Jeśli tę liczbę powiększymy o 1 przeniesienie będzie bez zmian.
Ponieważ na pozycji najniższej przeniesienie jest równe 0, więc nigdy nie może wystąpić
przeniesienie inne niż 0 lub 1.
B. Opracuj algorytm dodawania lub odejmowania liczb znakowanych zapisanych w systemie znak-moduł
(SM). Przyjmij, że znak liczby jest kodowany standardowo (0 – plus, 1 –minus).
Wskazówka: Sprawdź, jakie działanie należy faktycznie wykonać w zależności od znaków argumentów.
C. Opracuj algorytmy działań w systemie naturalnym o dowolnej podstawie:
a) dodawania i odejmowania,
b) mnożenia,
c) dzielenia
Wskazówka: Zapisz algorytm dodawania / odejmowania jednopozycyjnego. Utwórz tabliczki mnożenia.
D. Oblicz odpowiednio wartości największej i najmniejszej liczby całkowitej, reprezentowanych przez
łańcuch k cyfr w systemie a) naturalnym o podstawie β b) negabazowym, c) z cyframi znakowanymi,
d)* uzupełnieniowym pełnym i niepełnym, e)* spolaryzowanym „+1/ β k–1
β k–1
2
” oraz „+1/2
–1”.
Odpowiedź: Należy podstawić do ogólnego wzoru wartości odpowiadające skrajnym liczbom –
w systemie naturalnym i spolaryzowanym odpowiednio zero lub największą cyfrę na każdej pozycji,
w systemach uzupełnieniowych odpowiednio {β/2 –1, β –1,…, β –1} dla podstaw parzystych oraz
{β/2,0,…,0} dla nieparzystych, tak aby zakres był symetryczny.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
9
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z czterema bitami części ułamkowej liczby:
a) – 674,58110
b) – 0A,1216
c) – 3,0128
d) + 34,5610
e) 4,5610 – 4,5(6)10
Porównaj otrzymane kody z notacją w systemie uzupełnieniowym do 1 (U1) i systemie znak-moduł.
Wskazówka: Najpierw kodujemy wartość bezwzględną, roszerzając ją lewostronnie zerem (w systemie
znak-moduł rozszerzenie jest zbędne), potem wykonujemy „wchłonięcie” znaku.
2. Dodaj i odejmij liczby 4-cyfrowe podane w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745 ± 8123
b) 9,745 ± 0,8(23)
c) 31,56± 84,23
d) 9,994± 9,916
Używając lewostronnego rozszerzenia zweryfikuj poprawność wyników otrzymanych na 4 pozycjach.
Uwaga: Dodawanie jak w systemie dziesiętnym, rozszerzeniem dodatniej jest „0”, ujemnej „9”. Jeśli
wynik bez cyfry rozszerzenia oznacza tę samą liczbę co z cyfrą rozszerzenia nie wystąpił nadmiar. Na
przykład (9)6745 + (9)8123= (9)4858 jest ujemne ale 4858 jest dodatnie, zatem wystąpił nadmiar.
Poprawne zaokrąglenie w b) wymaga użycia 2 cykli okresu.
3* Wykaż, że w systemie stałobazowym i uzupełnieniowym, w dodawaniu lub odejmowaniu o ustalonej
liczbie pozycji argumentów i wyniku, użycie dodatkowej pozycji lewostronnego rozszerzenia wyniku
i argumentów wystarczy do wykrycia nadmiaru (przekroczenia zakresu).
Wskazówka: Zakres argumentów z użyciem pozycji rozszerzenia jest większy od oryginalnego, tyle razy,
jaka jest podstawa. Zatem wynik z rozszerzeniami jest zawsze poprawny. Rozszerzenie wyniku jest
zbędne, jeśli nie zostanie przekroczony oryginalny zakres, więc wystarczy to sprawdzić.
4* Wykaż, że w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy można
wykonać przez grupowanie (β → β S ) lub dekompozycję cyfr (β S → β ).
Wskazówka: Liczby ujemne zapisz w konwencji znak-moduł.
5. Oblicz sumę i różnicę liczb danych jako 10011101 i 01111001, 11011101 i 10111101, zakładając, że
podane łańcuchy k = 8 bitów (ciągi zero-jedynkowe) reprezentują liczby w kodzie
a) naturalnym (NB)
b) uzupełnieniowym pełnym (U2)
c) uzupełnieniowym niepełnym (U1)
d) znak-moduł (SM)
e) spolaryzowanym „+2 k–1–1”
f) spolaryzowanym „+2 k–1”.
Zweryfikuj poprawność otrzymanych wyników: A) wykonując działanie odwrotne (suma – argument,
różnica + odjemnik) B) używając lewostronnego rozszerzenia (oprócz e) i f)).
Wskazówka: W systemach spolaryzowanych wygodnie jest wykonać konwersję na system U2.
6. Znanych jest kilka najbardziej znaczących bitów liczb 48-bitowych w kodzie uzupełnieniowym U2.
11101010..?? oraz 10011110..?? Sprawdź, czy w ich dodawaniu i odejmowaniu wystąpi nadmiar.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
10
ARYTMETYKA KOMPUTERÓW
rozwiązania
Wskazówka: Należy znaleźć najwyższą pozycję na której jest zawsze wytwarzane przeniesienie
w dodawaniu (1+1) albo pożyczka w odejmowaniu (0–1), a następnie (wynik na pozycjach wyższych
od tak znalezionej nie zależy od wartości na pozycjach niższych) zbadać 2 najwyższe przeniesienia
lub celowość użycia bitów rozszerzenia lewostronnego.
7. Korzystając z zależności X − Y = X + Y i zakładając, że liczby są dane w systemie naturalnym, oblicz: a) 6745 – 8123
b) 9,745 – 0 , 823
c) 34,56– 81,23
d) 100111012 – 011110012
Sprawdź otrzymane wyniki wykonując działania odwrotne (różnica + odjemnik).
Uwaga: Należy sprawdzić, czy nie powstaje nadmiar (w systemie naturalnym wynik musi być dodatni!).
8. Wykaż, że w systemie naturalnym lub uzupełnieniowym pełnym mnożenie liczb m–pozycyjnych nie
powoduje nadmiaru, jeśli wynik jest kodowany na co najmniej 2 m pozycjach.
Wskazówka: Zakresem iloczynu jest [0, (β m–1 )2]= [0, β 2 m–2β m +1<β 2 m–1]
9. Wynik mnożenia m–bitowych liczb w kodzie U2 jest kodowany na 2 m–1 bitach. Czy jest możliwe
wystąpienie nadmiaru, a jeśli tak to przy jakich wartościach mnożnej i mnożnika?
Wskazówka: Zakresem iloczynu jest [–2 m–1×(2 m–1–1), (–2 m–1)2]= [–22 m–2+2 m–1, 22 m–2]. Liczba 22 m–2 musi być zakodowana na 2 m bitach, dla pozostałych wystarczy 2 m–1 bitów.
A. Przyjmując, że 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) wykonaj mnożenia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111.
*Wykonaj mnożenie (U2) stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia.
Uwaga: Iloczyn częściowy odpowiadający najwyższemu bitowi mnożnika ma wagę ujemną. Pamiętaj
o bitach
rozszerzenia,
zaś w kodzie U1 uwzględnij przeniesienie okrężne ( e-a-c).
* Pamiętaj o poprawnym kodowaniu zera, przekodowaniu iloczynu częściowego odpowiadającego
najwyższemu bitowi mnożnika oraz korekcji wyniku.
B. Pokaż, że w systemie naturalnym dwójkowym i systemie uzupełnieniowym do 2 mnożenie przez stałą,
która jest sumą lub różnicą potęg dwójki można wykonać jako dodawanie skalowanej mnożnej.
Rozwią zanie: Oczywiste, to jest po prostu zwykły sekwencyjny algorytm mnożenia.
C. Oblicz iloczyn liczb 4-cyfrowych podanych w dziesiętnym uzupełnieniowym systemie pełnym (U10):
a) 6745
×
×
×
×
U10
8123U10 b) 9745U10 0823 U10
c) 3156 U10 8423 U10
d) 9994 U10 9916 U10
Wskazówka: Wartość przypisana najbardziej znaczącej cyfrze liczby ujemnej jest ujemna i wynosi d − β,
gdzie d jest standardową wartością cyfry (| ” β−1”| = β−1− β = −1) (w systemie U10 |”9”| = −1).
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
11
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Oblicz iloczyn liczb 4-cyfrowych podanych w ósemkowym uzupełnieniowym systemie pełnym (U8):
a) 5745
×
×
×
×
U8
7123U8
b) 7745U8 0723 U8
c) 3156 U8 6423 U8
d) 7774 U8 7716 U8
Wskazówka: Zauważ, że wartość przypisana najbardziej znaczącej cyfrze liczby ujemnej jest ujemna
i w systemie U8 wynosi d − 8, gdzie d jest standardową wartością cyfry, zatem |”7”|= −1.
2. Oblicz bezpośrednio metodą sekwencyjną („kolejnych reszt”) z dokładnością do 4 pozycji znaczących
iloraz liczb reprezentowanych w systemie uzupełnieniowym pełnym
a) 01010011U2 : 1011U2
b) 1010011U2 : 01011U2 c) 876U10 : 176U10
d) 876U10 : 761U10.
Wskazówka: Nie zapomnij o skalowaniu, tak aby | X|<| D| oraz odwrotnym przeskalowaniu ilorazu. Aby uniknąć generowania nieznaczących bitów, zadbaj aby | D/2|<| X|<| D|.
3. Wykonaj bezpośrednio w systemie U10 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
Wskazówka: Zauważ, że można tak przeskalować dzielnik (dzielną), aby iloraz był ułamkiem właściwym
4. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
Wskazówka: Przeskaluj dzielnik (dzielną) tak, aby iloraz był ułamkiem.
5. Wykonaj w kodzie U2 z dokładnością do 4 cyfr znaczących ilorazu dzielenie nieodtwarzające liczb:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Wskazówka: Przeskaluj dzielnik (dzielną) tak, aby iloraz był ułamkiem. Wykonaj pierwsze działanie
stosownie do znaków dzielnej i dzielnika (dodaj dzielnik gdy znaki są przeciwne).
6. Oblicz metodą sekwencyjną („kolejnych reszt”) pierwiastek kwadratowy z liczb
a) 1234567, b) 1010 0010 0111 11002, c) 98765432110 d) 123,4567, e) 10100 0100,1111 1002
z dokładnością do jednej, dwóch i siedmiu cyfr znaczących oraz podaj trzecią i czwartą resztę.
Uwaga: Zwróć uwagę na poprawne wstępne skalowanie.
7. Dane jest przybliżenie pierwiastka kwadratowego z dokładnością do 3 cyfr znaczących i trzecia reszta.
Podaj dwie kolejne cyfry przybliżenia pierwiastka, jeśli:
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
12
ARYTMETYKA KOMPUTERÓW
rozwiązania
a) Q 3 =1237, r 3 =34567, b) Q 3 =12310, r 3 = 345610, c) Q 3 =1012, r 3 =111012, Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia czwartej cyfry ilorazu – występuje
w niej podwojone skalowane trzecie przybliżenie Q 3 oraz reszta r 3 :
8. Dane jest przybliżenie pierwiastka kwadratowego z dokładnością do 4 cyfr znaczących i czwarta reszta
równa 0. Oszacuj wartość liczby pierwiastkowanej, jeśli: a) Q 4 =12,347, b) Q 4 =1,23410, c) Q 4 =11012.
Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia piątej cyfry ilorazu – występuje
w niej podwojone skalowane czwarte przybliżenie Q 4 oraz reszta r 4. Zastanów się jaka musiała być
czwarta reszta, jeśli piąta jest zerem. Zauważ, że może istnieć wiele rozwiązań.
9. Oblicz metodą nieodtwarzającą pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002
z dokładnością do dwóch i pięciu cyfr znaczących oraz podaj trzecią i czwartą resztę.
A* Pokaż, że w naturalnym systemie dwójkowym dzielenie przez stałą, która jest sumą lub różnicą
dwóch potęg dwójki, można wykonać przez odejmowanie, jeśli dzielenie nie wytwarza reszty.
Wskazówka: Przyjmij dla uproszczenia, że stałą jest 2 m–1±1. Zauważ, że wtedy X = (2 m–1±1) Q, skąd wynika, że Q = ± ( X–2 m–1 Q), zatem wartości ( k–1) najniższych bitów ilorazu są takie jak najniższe bity dzielnej, a drugi argument odejmowania lub dodawania na wyższych pozycjach jest sekwencyjnie
wyznaczany jako wartość o ( k–1) pozycji niższego bitu obliczonych już pozycji ilorazu.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
13
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Twierdzenie Euklidesa o podzielności liczb orzeka, że największy wspólny podzielnik dwóch liczb
naturalnych jest podzielnikiem reszty z dzielenia większej przez mniejszą. Wykaż, równoważność tej
tezy z tezą, że największy wspólny podzielnik dwóch liczb jest podzielnikiem ich różnicy.
Wskazówka: Reszta jest wynikiem wielokrotnego odejmowania mniejszej od większej – tyle razy ile
wynosi iloraz. Różnica jest więc równa wielokrotności mniejszej liczby + reszta...( X mod Y= X– kY<Y) 2. Korzystając z twierdzenia Euklidesa znajdź największy wspólny podzielnik liczb:
a) 6745 i 8123
b) 9994, 92 i 9916
c) 375, 243, 345 i 126
d) 220–1 oraz 25+1
Wskazówka: Zastosuj twierdzenie Euklidesa b) NWD( a,b,c)= NWD(NWD( a,b), NWD( b,c))
3. Pokaż, że liczby 2 k + 1 i 2 k + 1 + 1 są względnie pierwsze ( k ∈ N – jest liczbą naturalną)
*Czy prawdziwe jest twierdzenie, że liczby 2 k + 1 i 2 r + 1 ( k , r ∈ N ) są względnie pierwsze?
Wskazówka: Zastosuj twierdzenie Euklidesa. Zauważ, że 2 k + 1 = 2 ×2 k = 2 k + 2 k
*Pokaż kontrprzykład – (21+1,23+1) = 3. Udowodnij, że gdy k jest nieparzyste, to (2 k + 1 , 2 k + 2 ) = 3 .
4* Wykaż, że liczby (22 n + )
1 oraz (2 n + )
1 i (22 n 1
+ + )
2 i (2 n − )
1 ( n∈ N ) są względnie pierwsze.
Wskazówka: Zastosuj twierdzenie Euklidesa i związki potęg oraz wzory skróconego mnożenia.
5. Nie wykonując dzielenia wyznacz resztę z dzielenia liczby 1011 0011 0111 11012 przez
a) 11112
b) 100012
c) 111112
d) 100000012.
Wskazówka: Zastosuj właściwości kongruencji i zależność ( m ± 1) mod m = ± 1 .
6. Stosując reguły arytmetyki resztowej oblicz reszty całkowite (dodatnie lub ujemne) wobec modułów:
25710, 78 , 6510, 3F16, 1116, 0FF16 dla liczb 46528 i 0ABCD16, oraz ich sumy, różnicy i iloczynu.
Wskazówka: Zastosuj właściwości kongruencji i zależność ( m ± 1) mod m = ± 1 .
7. Podaj reprezentację resztową liczby 2345610 w bazie: a) (29, 30, 31), b) (99, 100, 101), a) (63, 64, 65).
Wskazówka: Wyznacz reprezentację liczby w systemie o podstawie a) 30, b) 100, c) 64 oraz zastosuj
właściwości kongruencji i zależność ( m ± 1) mod m = ± 1 .
8* Znajdź odwrotności multyplikatywne iloczynów par modułów bazy systemu resztowego ( a–1, a, a+1)
względem trzeciego z nich, zakładając, że a jest liczbą parzystą.
Wskazówka: Wykorzystaj zależność ( m ± 1) mod m = ± 1
9* Wektor (1, 2, 3) jest reprezentacja resztową liczby x w bazie (29, 30, 31). Znajdź tę liczbę w zbiorze
kongruencji naturalnych ( x∈[0, M=29⋅30⋅31)) i całkowitych ( x∈ –(M–1) /2, M–1 /2)).
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
14
ARYTMETYKA KOMPUTERÓW
rozwiązania
Wskazówka: Wykorzystując zależność ( m ± 1) mod m = ± 1 znajdź odwrotności multyplikatywne niepełnych iloczynów modułów bazy i zastosuj chińskie twierdzenie o resztach. Zauważ, że jeśli m 0
jest najmniejszym modułem bazy, to ( x, x, x, … , x) = x oraz (– x, –x, –x, … , – x) = – x = M– x, na przykład zawsze jest (1, 1, 1, … , 1) = 1 oraz (–1, – 1, – 1, … , – 1) = –1 = M –1, a także ( m 1–1, m 2– 1,
m 3– 1, … , mk– 1) = M –1 = –1.
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
a) 674,531
⋅
⋅
8
b) 0,128 8-51
c) – 0ABC,DE16
d) 10,1010101010U2 4 -61
Wskazówka: Zapisz liczbę w systemie znak-moduł i tak przeskaluj, aby moduł był standardowy.
B. Zapisz w 32-bitowym formacie zmiennoprzecinkowym IEEE 754 pierwiastki kwadratowe z liczb:
a) 1010 0010, 0111 11002, b) 123,4568, c) 10100 0100, 1111 1002
Wskazówka: Pamiętaj o skalowaniu i bicie ukrytym.
C. Oblicz i zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 z dokładnością do
5 cyfr znaczących pierwiastki kwadratowe z liczb danych w tym formacie:
a) 0 0100 0100 111 1100 1010 0010 0111 1100, b) 0 1010 0101 1111 1010 0100 1111 1111 1002
c) 0 0100 0101 111 1100 1010 0010 0111 1100, d) 0 1010 0100 1111 1010 0100 1111 1111 1002
Wskazówka: Zwróć uwagę na nieparzyste wykładniki. Pamiętaj o skalowaniu i bicie ukrytym.
D* Wykaż, że w odejmowaniu (dodawaniu) zmiennoprzecinkowym operandów dokładnych, bit S dla
znormalizowanej różnicy (sumy) może być wyznaczony przed wykonaniem działania.
Wskazówka: Rozpatrz przypadki składników o identycznych i różnych wykładnikach.
E. Wyznacz z dokładnością do 4 bitów znacznika zaokrąglenia argumentów 1,101111011 i 1,101111001
uzupełnione bitami G, R, S. Wykonaj ich mnożenie i porównaj z wynikiem pełnego mnożenia.
Wskazówka: Bit G to bit piąty, bit R wynika z przybliżenia do najbliższej (tu obojętne czy parzystej czy
nieparzystej, bit S wskazuje, czy na odcinanych pozycjach była choć jedna „1”.
F* Wykaż, że w mnożeniu znormalizowanych operandów, bit S znormalizowanego iloczynu może być
wyznaczony przed mnożeniem. Pokaż, że jeden z czynników może być zdenormalizowany.
Wskazówka: Zauważ, że iloczyn ma tyle samo pozycji znaczących, co każdy z czynników, a co najmniej
jeden z czynników ma określony zakres (jest znormalizowany).
G* Oszacuj maksymalny błąd przybliżenia różnicy podczas odejmowania znormalizowanych operandów
obliczonych z taką samą dokładnością bezwzględną znacznika (mantysy).
Wskazówka: Zbadaj najgorszy przypadek. Wykorzystaj analizę z zad. D
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
15
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Stosując reguły działań w algebrze Boole’a uprość poniższe wyrażenia
a) x+( x⊕ y)
b) xyz+( x⊕ y) +( z⊕ y)
c) x+ xy+ xyz
d) zy+( x⊕ y)
e) z x+ z( x⊕1)
f) x+ xy+( x⊕ yz)
Wskazówka: Zamień wyrażenia zawierające ⊕ na sumy iloczynów i zminimalizuj.
2. Na podstawie tabeli prawdy (tabeli wartości) funkcji logicznych f 1 i f 2 podaj ich wszystkie mintermy (konstytuenty iloczynu) i maxtermy (konstytuenty sumy) oraz postaci formalne
x 3
x 2
x 1 f 1(x)
x 3
x 2
x 1 f 2(x)
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
Wskazówka: Zapisz funkcje jako sumy iloczynów lub iloczyny sum. Upraszczaj wyrażenia bezpośrednio
na podstawie podobieństw ciągów wartości zmiennych odpowiadających tej samej wartości funkcji,
np. f( x 1, … , x i–1, φ, x i+1, … , xn) = f( x 1, … , x i–1, 0, x i+1, … , xn) + f( x 1, … , x i–1, 1, x i+1, … , xn) .
3. Wyznacz funkcje dualne i komplementarne do funkcji f (x) = x x + x x i f (x) = x x + x ( x + x ) 1
2
1
3
2
2
3 1
3
2
1
oraz ich sumy logicznej i iloczynu logicznego. Narysuj sieci logiczne realizujące te funkcje.
Wskazówka: Zastosuj prawa de’Morgana.
4. Korzystając z twierdzenia Shannona rozwiń wszystkie funkcje z zadania 3 względem zmiennej x 3.
Wskazówka: Oblicz f( x 3 = 0) oraz f( x 3 = 1) i wyniki podstaw do wzoru Shannona.
5. Wykaż, że wartość funkcji logicznej [ z⋅ f( x)+( z⊕ f( x))] f( x) nie zależy od zmiennej z.
Wskazówka: Zamień wyrażenie zawierające ⊕ na sumę iloczynów i zminimalizuj lub pokaż, że różnica
boole’owska względem z wynosi 0.
6* Pokaż, że każdą funkcję logiczną można wyrazić za pomocą tylko funkcji NOR (suma negacji) lub
tylko funkcji NAND (iloczyn negacji).
Wskazówka: Przedstaw funkcje sumy, iloczynu i negacji za pomocą funkcji NOR lub NAND
7. Wyznacz charakterystyki AT sieci logicznych realizujacych funkcje dane przez wyrażenia w zadaniu 1
Odpowiedź: Wyznacz najdłuższą ścieżkę, policz bramki przeliczeniowe na tej ścieżce (T) i wszystkie (A).
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
16
ARYTMETYKA KOMPUTERÓW
rozwiązania
8. Subtraktor 1-bitowy realizuje funkcje logiczne różnicy d = f ( x, y, z) i pożyczki b = h ( x, y, z) równoważne arytmetycznemu równaniu odejmowania 1-bitowego x – y – z = – 2 d + b ( x , y , z , d , b ∈ {0, 1}) . Podaj tabelę prawdy subtraktora i wyznacz charakterystyki AT subtraktora 8-bitowego.
Odpowiedź: Opóźnienie (T) oblicz osobno dla obu funkcji.
9. Sumator 1-bitowy realizuje funkcje logiczne sumy s = f ( x, y, z) i przeniesienia c = h ( x, y, z) równoważne arytmetycznemu równaniu dodawania 1-bitowego x + y + z = 2 c + s ( x , y , z , s , c ∈ {0, 1}) . Zaprojektuj ogniwo inkrementera realizującego funkcje s = f ( x, 1 , z) oraz c = h ( x, 1 , z) i oblicz charakterystyki AT.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
A. Sumator warunkowy 1-bitowy realizuje alternatywne funkcje logiczne warunkowej sumy s 0 = f ( x, y, 0), s 1 = f ( x, y, 1) i przeniesienia c 0 = h ( x, y, 0), c 1 = h ( x, y, 1) równoważne arytmetycznemu równaniu dodawania 1-bitowego przy założeniu, że przeniesienie wejściowe jest odpowiednio równe 0 albo 1.
Podaj tabelę prawdy sumatora i wyznacz te funkcje.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
B* Narysuj schemat logiczny sumatora 1-bitowego, którego wyjścia sumy i przeniesienia są wytwarzane
z użyciem multiplekserów sterowanych przeniesieniem wejściowym na podstawie funkcji sumy i
przeniesienia zerowego i jedynkowego s 0 , s 1 , c 0 , c 1 . Wyznacz charakterystyki AT tego układu.
Wskazówka: Wyznacz i zminimalizuj funkcje sumy i przeniesienia.
C* Pokaż, że charakterystyki AT sieci realizujących funkcję dualną i komplementarną są jednakowe.
Wskazówka: Wykorzystaj prawa de’Morgana i równoważność charakterystyk AT dla sumy logicznej
i iloczynu logicznego.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
17
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Oblicz charakterystyki AT sumatorów uniwersalnych RCA dla kodów k-bitowych:
a) uzupełnieniowego pełnego (U2)
b) uzupełnieniowego niepełnego (U1)
c) znak-moduł,
d) spolaryzowanego ujemnie „+2 k–1”
e) spolaryzowanego dodatnio „+2 k–1–1”
Wskazówka: Wykorzystaj charakterystyki AT sumatora 1-bitowego.
2. Zaproponuj sposób kodowania cyfr i zaprojektuj sumator jedno- i cztero-pozycyjny dla systemu
a) U10 z kodowaniem cyfr w kodzie „+3” i kodzie BCD
b) dwójkowego negabazowego (β = –2),
c)* naturalnego trójkowego (β = 3) i dwójkowego z cyfrą znakowaną SD, (D={–1,0,+1})
Wskazówka: a), b) wykorzystaj związki z sumatorem dwójkowym; c) wyznacz tabele prawdy.
3. Oblicz charakterystyki AT sumatora 24-bitowego z przeniesieniami przeskakującymi ( carry-skip) jeśli
ma on strukturę a) 3-4-4-3-4-4-2, b) 3-3-4-4-4-3-3, c) 4-4-4-4-4-4, d) 6-6-6-6, e) optymalną.
Wskazówka: Area: Oblicz liczbę ogniw sumatora i liczbę ogniw łańcucha przeskoku przeniesienia,
Time:Wyznacz ścieżki krytyczne i oblicz opóźnienie.
4. Zaprojektuj 8-bitowe układy inkrementacji i dekrementacji i wyznacz ich charakterystyki AT.
Wskazówka: Wykorzystaj charakterystyki 1-bitowego ogniwa inkrementera/dekrementera, wyznacz
najdłuższa scieżkę propagacji przeniesienia.
5. Zaprojektuj 4- i 8-bitowy sumator sum warunkowych i wyznacz ich charakterystyki AT.
Wskazówka: Zauważ, że sumatory wejściowe są uproszczone, oblicz liczbę multiplekserów.
6. Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA i wyznacz ich charakterystyki AT.
Wskazówka: Oceń charakterystyki AT stopnia wejściowego, poziomu sieci PPA i stopnia wyjściowego.
7. W celu dodania n operandów k-bitowych użyto sumatora CSA ( carry-save). Ile bitów zawiera suma?
Jakie jest opóźnienie (T) podczas obliczania sumy, jeśli sumę końcową wytwarza
a) sumator ze skrośną propagacją przeniesień RCA, b) sumator sum warunkowych COSA.
Obliczenia wykonaj dla n = 7, 15, 31 oraz k = 8, 16, 32.
Wskazówka: Liczbę bitów sumy wyznacza jej zakres [0, n (2 k –1)]. Liczba poziomów s ≤ (lg n/2) / lg 3/2.
Opóźnienie jednego poziomu T=4 (do obu wyjść)
8. Ile poziomów musi zawierać sumator CSA użyty do redukcji iloczynów częściowych tworzonych
w mnożeniu liczb 32-bitowych w kodzie naturalnym (NB)? Ile sumatorów elementarnych (3,2)
zawiera najbardziej skomplikowana gałąź CSA odpowiadająca bitom o tej samej wadze.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
18
ARYTMETYKA KOMPUTERÓW
rozwiązania
Wskazówka: Patrz poprzednie zadanie.
9. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
Wskazówka: Nie zapomnij o bitach rozszerzenia. Sprawdź skutki, jeśli bity te zostaną pominięte.
A. Wyznacz, uwzględniając czas końcowego dodawania, najkrótszy czas dodawania 32 operandów 64-
bitowych w sumatorze CSA jeśli dysponujesz:
c) reduktorami (3,2) generującymi przeniesienia 1-bitowe, wnoszące opóźnienia T = 4 każdy
d) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóźnienia T = 6 każdy
Wskazówka: *Oblicz liczbę poziomów i liczbę bitów końcowego dodawania.
D* Opracuj i uzasadnij algorytmy konwersji dwójkowo–dziesiętnej liczb całkowitych dodatnich, bez
wykonywania dzielenia, jeśli cyfry dziesiętne są kodowane: a) w kodzie BCD, b) w kodzie BCD+3.
Wskazówka: Konwersja BCD na dwójkowy: Zbadaj skutki przesunięcia o jeden bit w prawo liczby k ≥ 2-
pozycyjnej w kodzie BCD. Konwersja dwójkowy na BCD/BCD+3: Wykorzystaj dodawanie.
E* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie NB
a) mod 11112
b) mod 100012
c) mod 1112 d) mod 10012
Uwaga: *Jest wiele argumentów wejściowych, które mają (b) i d)) różne znaki. Konieczne może być
użycie bitów rozszerzenia.
F* Zaprojektuj generator reprezentacji resztowej liczby całkowitej 8- i 16-bitowej w kodzie U2
a) mod 11112
b) mod 100012
c) mod 1112 d) mod 10012
Wskazówka: Rozważ kongruencje w zbiorze liczb całkowitych. Zauważ, że najwyższ grupa bitów ma
k −2
k −2
s −1
znak
k −
−
1
x
2
x 2 i
2 s ( x
2 k
s
x 2 i s )
x 2 i
k 1
+
i
=
−
1
k 1
+
i
+
−
∑
− −
−
i=0
∑
−
i= s
∑ i=0 i
H. Zaprojektuj sumator mod (28–1) dwóch liczb całkowitych 8-bitowych w kodzie U2.
Wskazówka: Rozważ kongruencje w zbiorze liczb całkowitych.
G* Zaprojektuj sumatory mod (24–1) i mod (24+1) 4 liczb całkowitych 4-bitowych w kodzie U2.
Wskazówka: Rozważ kongruencje w zbiorze liczb całkowitych. Przeanalizuj struktury PPA.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
19
ARYTMETYKA KOMPUTERÓW
rozwiązania
1. Zakoduj na 8 bitach według prostej i odwrotnej reguły Booth’a w bazie 2 oraz w bazie 4 liczby:
a) –8710
b) +12110
c) 1011012
c) 1011101U2
Wskazówka: Zapisz liczby w systemie U2.
2. Przyjmując, że 6-bitowe operandy są dane w dwójkowym kodzie uzupełnieniowym a) pełnym (U2),
b) niepełnym (U1) i używając mnożnika przekodowanego wg reguły Booth’a w bazie 2 i 4 wykonaj
mnożenia: i) 110101×011011 ii) 011101×110111 iii) 101001×111111
Wskazówka: Nie zapomnij o bitach rozszerzenia iloczynów częściowych.
3. Oblicz charakterystyki AT matrycy mnożącej dwa operandy: a) 4-bitowe, b) 8-bitowe c)* n-bitowe
Wskazówka: Policz liczbę elementarnych sumatorów oraz liczbę poziomów akumulacji.
4* Zaprojektuj matrycę mnożącą operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mnożnika wg reguły Bootha w bazie 4. Porównaj z innymi układami matrycowymi.
Wskazówka: Zaprojektuj element podstawowy matrycy.
5. Oblicz charakterystyki AT sumatora CSA użytego do redukcji iloczynów częściowych w mnożeniu
operandów 4-, 8- bitowych danych: a) w kodzie NB, b) w kodzie U2 z eliminacją bitów rozszerzenia.
*Podaj oszacowanie charakterystyk AT dla mnożenia operandów n-bitowych.
Wskazówka: Ad b) zauważ, że każdy operand ma inną wagę.
6. W dzieleniu w systemie naturalnym w bazie 4 skalowana reszta częściowa ma wartość 2,2 D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia, kolejne dwie cyfry ilorazu.
Wskazówka: a) rozwiąż dwa kolejne równania dzielenia; b) zaznacz resztę na osi odciętych i graficznie
znajdź kolejną resztę (pierwsze odwzorowanie wg odcinka „ q=2”), przeskaluj ją i powtórz czynności.
7. W dzieleniu w systemie U2 przeskalowana reszta częściowa ma wartość: i) –0,2 D, ii) +0,7 D. Wyznacz:
analitycznie i na podstawie parametrycznego wykresu dzielenia kolejne dwie cyfry ilorazu, zakładając,
że dzielnik D jest: a) ujemny, b) dodatni.
Wskazówka: Patrz poprzednie zadanie.
8. Wykonaj bezpośrednio w kodzie U2 dzielenia z dokładnością do 4 cyfr znaczących ilorazu:
a) 110101 : 011011
b) 011101 : 110111 c) 101001 : 11111
d) 101001 : 10011
e) 1,10101 : 01101,1
f) 0,11101 : 110,111 g) 1010,01 : 111,11
h) 101001 : 100,11
Sprawdź, wykonując mnożenie, poprawność otrzymanych wyników.
Wskazówka: Nie zapomnij przeskalować dzielnej (i/lub dzielnika)
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
20
ARYTMETYKA KOMPUTERÓW
rozwiązania
9. Wykonaj wykres P-D dla dzielenia w bazie 4 i dzielnika z zakresu [1,2). Podaj ile bitów musi być
porównywanych w celu wyznaczenia cyfr ilorazu.
Wskazówka:
A. Oblicz charakterystyki AT matryc dzielących operandy 8-bitowe w kodzie NB i U2
Wskazówka: Przeanalizuj pełną ścieżkę propagacji przeniesienia.
B. Oblicz metodą Newtona iloraz 3,1416 :2,7183.
Wskazówka: Wybierz pierwsze przybliżenie
C. Oceń czas obliczania pierwiastka kwadratowego z liczby całkowitej metodą sekwencyjną („kolejnych
reszt”) oraz na podstawie tożsamości: „suma n kolejnych nieparzystych liczb naturalnych jest równa
kwadratowi z ich liczby” (np. 1+3+5=32 1+3+5+7=42, 1+3+5+7+9=52 itd.)
*Określ minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
i= k
i= k 1
−
Wskazówka: Zauważ, że ∆
, więc
k = X − ∑
(2 i + )
1 = [ X −
i
∑ (2 i + )1]− (2 k + )1 = ∆ k− −(2 k + )1
1
=0
i=0
oszacowaniem pierwiastka jest takie k, przy którym odstęp sumy od X zmienia znak.
D* Oszacuj liczbę kroków algorytmu CORDIC potrzebnych do obliczenia wartości funkcji exp, ln, sin,
cos, arctg dla argumentu z przedziału [–1,1] z dokładnością do 32 bitów części ułamkowej.
Wskazówka: Zastosuj odpowiednio wzory.
E* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zależności:
n
n
n
j 1
n 1
j
3
n − n = ∑ 3
( ⋅ 2
i − 3⋅ i) = ∑
3
( i ⋅ ( i − )
1 ) = ∑
3
∑−2 i = ∑−
6
∑ i
i=1
i=1
j=1 i=0
j=1 i=1
Wskazówka: Zauważ związek sumy zewnętrznej z wewnętrzną.
© Janusz Biernat, ARYT-ZADANIA-schematy’02
25 października 2004
21