Rok I ARYTMETYKA KOMPUTERÓW Lista nr 1
1. Znajdz
podstawę x systemu naturalnego, w którym: a) 41x = 5 , b) 22x = 4 c) a2 =301x , d) b2 =562x
2. Znajdz
podstawÄ™ ² systemu naturalnego, w którym liczby naturalne x1 oraz x2 sÄ… rozwiÄ…zaniami
równania ax2+ bx+c = 0. Wykonaj obliczenia dla x1 = 5² , x2 = 8² i równania 5² x2 50² x+125² = 0
3* Znajdz
podstawę systemu naturalnego, w którym równanie ax2+bx+c=0 (a,b,c " ) ma pierwiastki
całkowite. *Rozwią\
zadanie zakładając, \
e a,x1,x2 sÄ… liczbami jednocyfrowymi, b = b1²+b0 jest liczbÄ…
2
dwucyfrowÄ…, zaÅ› c = c2² +c1²+c0, c2 = 0 lub 1. Wykonaj obliczenia dla x1 = 5² , x2 = 8² oraz a = 1 i 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. *Uogólnij wynik dla kÅ"|{² 1, & , ² 1, ² 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.
7. Przeprowadz
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,5610 ×2 5 = (& )2 = (& )16 e) 102,213×5 2 = (& )5 f) 0BACA16 ×5 3 = (& )10
g) 6745,819 = (& )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 jeśli istnieje nierozkładalny podzielnik podstawy z
ródłowej, który nie jest podzielnikiem
podstawy docelowej, to wynikiem konwersji ułamka skończonego w systemie o danej podstawie, na
reprezentację w innym systemie naturalnym jest ułamek okresowy.
9. Znajdz
system o najmniejszej podstawie, w którym reprezentacja danego ułamka jest skończona:
a) 0,(27)10 b) 0,(101)2 c) 1  0,(56)9 d) 0,0(0011)2 e) 0,(35)11  0,(2)11 f) 0,1(23)7
A. Wyka\
, \
e w systemie naturalnym przeniesienie otrzymane podczas dodawania lub po\
yczka podczas
odejmowania na ka\
dej pozycji są zawsze równe 0 lub 1.
B. Opracuj algorytm dodawania i odejmowania liczb zapisanych w systemie znak-moduł (SM). Przyjmij,
\
e znak liczby jest kodowany standardowo (0  plus, 1  minus).
C* Opracuj algorytm dodawania i odejmowania w systemie naturalnym z niestandardowym zbiorem cyfr.
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/2² k 1 oraz  +1/2² k 1 1 .
E* Wyka\
, \
e w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy mo\
na
S S
wykonać przez grupowanie (² ² ) lub dekompozycjÄ™ cyfr (² ² ).
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
1
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 2
1. Zapisz w systemie uzupełnieniowym do 2 (U2) z ośmioma 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 dodawaniu lub odejmowaniu w systemie stałobazowym i uzupełnieniowym u\
ycie cyfr
lewostronnego rozszerzenia operandów wystarczy do wykrycia nadmiaru (przekroczenia zakresu).
4. Wykonaj zmianÄ™ znaku liczby danej w quasi-symetrycznym kodzie spolaryzowanym +2k oraz +2k-1
a) 10101001 b) 0101010 c) 1100001 c) 00110101
5. Zakładając, \
e podane 8-bitowe sekwencje 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  +28 1 1 f) spolaryzowanym  +28 1 .
oblicz sumę i ró\
nicÄ™ liczb o kodach: i) 10011101 i 01111001, ii) 11011101 i 10111101. Sprawdz

poprawność wyników wykonując działanie odwrotne (suma  argument, ró\
nica + odjemnik)
6. Znając kilka najbardziej znaczących bitów liczb n-bitowych w kodzie uzupełnieniowym U2, sprawdz
,
czy w ich dodawaniu i odejmowaniu wystÄ…pi nadmiar:
a) 11101010..?? Ä… 10011110..?? b) 1011010..?? Ä… 1001110..?? c) 011101..?? Ä… 11011001..??
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
Sprawdz
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 2m pozycjach.
9. Wynik mno\
enia m bitowych liczb w kodzie U2 jest kodowany na 2m 1 bitach. Czy jest mo\
liwe
wystąpienie nadmiaru, a jeśli tak to przy jakich wartościach mno\
nej i mno\
nika?
A. Wykonaj mno\
enie liczb w dwójkowym kodzie uzupełnieniowym pełnym (U2) u\
ywając bitów
rozszerzenia i stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia:
a) 110101×011011 b) 011101×110111 c) 101001×111111 d) 1101010×1111101.
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 uzupełnieniowym systemie pełnym (U10/U8):
a) 6745U10 × 8123U10 b) 9745U10 × 0823 U10 c) 3156 U10 × 8423 U10 d) 9994 U10 × 9916 U10
e) 5745U8 × 7123U8 f) 7745U8 × 0723 U8 g) 3156 U8 × 6423 U8 h) 7774 U8 × 7716 U8
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
2
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 3
1. Zakoduj na 8 bitach według prostej i alternatywnej reguły Booth a i Booth a-McSorley a:
a)  81710 b) +132110 c) 101111012 d) 1011101U2 e)* 1011101( 2)
2. U\
ywajÄ…c przekodowania Booth a oraz Booth a-McSorley a i przyjmujÄ…c, \
e operandy sÄ… w kodzie
A) dwójkowym naturalnym, B) uzupełnieniowym U2, C)* dopełnieniowym U1, oblicz iloczyny:
a) 11000101×01110011 b) 011101×11011110 c) 101001×1011111 d) 010011×010111110.
3. Wykonując dzielenie odtwarzające (metodą sekwencyjną  kolejnych reszt ) oblicz 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) 576U10 : 176U10 d) 424U10 : 824U10
e) 6465U10 : 353,5U10 f) 6465U8 : 353,5U8 g) 5465U10 : 150,7U10 h) 2465U8 : 753,5U8.
Sprawdz
poprawność otrzymanych wyników wykonując mno\
enie.
4. Wykonaj w kodzie U2 z dokładnością do 5 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.
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
5. Oblicz metodą nieodtwarzającą z dokładnością do 4 cyfr znaczących iloraz liczb naturalnych (NB):
a) 1101012 : 0110112 b) 0111012 : 1101112 c) 1010012 : 111112 d) 1010012 : 100112,
e) 1,101012 : 01101,12 f) 0,111012 : 110,1112 g) 1010,012 : 111,112 h) 1010012 : 100,112.
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 sÄ… 3 cyfry przybli\
enia pierwiastka kwadratowego i trzecia reszta. Podaj dwie kolejne cyfry, jeśli:
a) Q3 =1237, r3 =34567, b) Q3 =12310, r3 = 345610, c) Q3 =1012, r3 =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) Q4 =12,347, b) Q4 =1,23410, c) Q4 =11012.
9. Oblicz metodą nieodtwarzającą z dokładnością do 5 cyfr znaczących pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002 d) 0,0000000371b (b = 2, 8, 10)
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.
B. Analitycznie i na podstawie wykresu dzielenia dwójkowego: a) odtwarzającego, b) nieodtwarzającego
wyznacz 3 kolejne cyfry ilorazu, je\
eli znormalizowany dzielnik (1 d" D < 2) ma wartość i) D = 1,1012,
ii) D = 1,11012, a bie\
Ä…cÄ… resztÄ… (przed skalowaniem) jest: a) 0,3D, b) -0,2D, c) +0,7D.
C* Narysuj wykresy P-D dla dzielenia w bazie 4 (² = 4) i dzielnika z zakresu [1,2). Podaj ile bitów musi
być porównywanych w celu wyznaczenia cyfr ilorazu.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
3
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 4
1. Wyka\
, \
e największy wspólny podzielnik dwóch liczb jest podzielnikiem ich ró\
nicy.
2. KorzystajÄ…c z twierdzenia Euklidesa znajdz
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 2k + 1 i 2k+1+1 są względnie pierwsze (k " N  jest liczbą naturalną).
*Wyka\
, \
e liczby 2n+1, 22n+1+2 oraz 2n-1 są względnie pierwsze z liczbą 22n+1 (n" N ).
*Kiedy prawdziwe jest twierdzenie, \
e liczby 2k + 1 i 2r + 1 (k `" r " N ) są względnie pierwsze?
4. Na podstawie twierdzenia Eulera lub małego twierdzenia Fermata oblicz:
a) 13267mod 63, b) 172167mod 19 c) 40167mod 41 d) (1726713267)mod 55
5. Nie wykonujÄ…c dzielenia wyznacz resztÄ™ z dzielenia liczby d 1011 0011 0111 1101U2 (d=0, 1) przez
a) 11112 b) 100012 c) 111112 d) 100000012 e) 1012.
6. Stosując reguły arytmetyki resztowej oblicz najmniejsze reszty całkowite (dodatnie lub ujemne) sumy,
ró\
nicy i iloczynu liczb 46528 i 0ABCD16 względem modułów: 25710, 78 , 6510, 3F16, 1116, 0FF16
7. Podaj reprezentacjÄ™ liczby 2345610 w bazie RNS: a) {29, 30, 31}, b) {99, 100, 101}, c) {63, 64, 65}.
8* Znajdz
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. Znajdz
jedynki resztowe w zbiorze kongruencji naturalnych (x"[0, M)) w systemie RNS:
a) {29, 30, 31} b) {99, 100, 101} c) {63, 64, 65} d)* {11, 13, 15, 16}
Znajdz
liczbę, której reprezentacją resztową jest ((a),b),c)): (1, 2, 3), (d): (1, 2, 2, 1).
**RozwiÄ…\
zadanie w zbiorze kongruencji caÅ‚kowitych (x" ðÅ‚ (M 1)ûÅ‚ /2, ðÅ‚M 1ûÅ‚ /2))
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
-61
a) 674,5318 b) 0,128 Å" 8-51 c)  0ABC,DE16 d) 10,1010101010U2 Å" 4
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
E. Wyznacz z dokładnością do 4 bitów ułamka zaokrąglenia argumentów 1,10111101101 i 1,1011110010
uzupełnione bitami G, R, X. Wykonaj ich mno\
enie i porównaj z wynikiem pełnego mno\
enia.
F* Wyka\
, \
e w dodawaniu (mno\
eniu) zmiennoprzecinkowym znormalizowanych operandów, bit X dla
znormalizowanej sumy (iloczynu) mo\
e być wyznaczony przed wykonaniem działania.
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-ZAD+ROZW 02 5 paz
dziernika 2005
4
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 5
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) zx+z(x•"1) f) x+xy+(x•"yz)
g) [zÅ"f(x)+(z•"f(x))] f(x) h) (g(x)+z•"f(x))+z f(x)(1•"g(x)
2* Poka\
, \
e ka\
dÄ… funkcjÄ™ logicznÄ… mo\
na wyrazić za pomocą funkcji NOR albo funkcji NAND.
3. Wyznacz funkcje dualne i komplementarne do funkcji f1(x) = x2 x1 + x3x2 i f2 (x) = x3x1 + x3 (x2 + x1) ,
oraz (f1+f2)(x) i (f1 f2)(x). Narysuj stosowne sieci logiczne. Na podstawie twierdzenia Shannona rozwiń
funkcje (f1+f2)(x), (f1 f2)(x) i (f1•"f2)(x) wzglÄ™dem zmiennej x3.
4* Poka\
, \
e charakterystyki AT sieci realizujÄ…cych funkcjÄ™ dualnÄ… i komplementarnÄ… sÄ… jednakowe.
5* 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 s0 , s1 , c0 , c1 . Wyznacz charakterystyki AT tego układu.
6. Oblicz charakterystyki AT uniwersalnych sumatorów kaskadowych RCA dla kodów k-bitowych:
a) uzupełnieniowego pełnego (U2) b) uzupełnieniowego niepełnego (U1) c) znak-moduł,
d) spolaryzowanego ujemnie  +2k 1 e) spolaryzowanego dodatnio  +2k 1 1
7. 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})
8. 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Ä….
9. Zaprojektuj 4- i 8-bitowy sumator sum warunkowych i wyznacz ich charakterystyki AT.
A* Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA w strukturze Ladnera-Fischera i Hana-Carsona.
Wyznacz funkcje wytwarzania (G*) i przekazywania (P*) przeniesień na kolejnych poziomach bloku
generowania przeniesień. **Wyznacz charakterystyki AT sumatora k-bitowego.
B. Zaprojektuj 8-bitowe układy inkrementacji i dekrementacji liczby zakodowanej w kodzie U2. Wyznacz
charakterystyki AT zaprojektowanych układów.
C. Zaprojektuj uniwersalny ukÅ‚ad realizujÄ…cy skalowanie liczby 8-bitowej w kodzie U2 przez 2, ½ oraz ź.
Wyznacz charakterystyki AT tego układu. Wskazówka: Zrealizuj układ jako przesuwnik kaskadowy
(barrel shifter) z u\
yciem multiplekserów 2-wejściowych. Pamiętaj o pozycjach rozszerzenia.
D* Zaprojektuj uniwersalny sumator, którego wejścia są zakodowane w dwójkowym kodzie naturalnym,
a wyjścia w kodzie znak-moduł.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
5
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 6
1. W celu dodania n operandów k-bitowych u\
yto sumatora CSA (carry-save). Ile bitów zawiera suma?
Jakie jest opóz
nienie (T) dodawania, jeśli końcowy wynik wytwarza sumator:
a) kaskadowy RCA, b) prefiksowy PPA c) sum warunkowych COSA.
Obliczenia wykonaj dla n = 7, 15, 31 oraz k = 8, 16, 32.
2. 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łąz
CSA odpowiadajÄ…ca bitom o tej samej wadze.
3. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
4. 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óz
nienia T = 4 ka\
dy
b) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóz
nienia T = 6 ka\
dy
5. Oblicz charakterystyki AT matrycy mno\
Ä…cej dwa operandy: a) 4-bitowe, b) 8-bitowe c)* n-bitowe
6* Zaprojektuj matrycÄ™ mno\
Ä…cÄ… operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mno\
nika w bazie 4 (wg reguły Bootha-McSorley a). Porównaj z innymi układami matrycowymi.
7. 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.
8. Oblicz charakterystyki AT matryc dzielÄ…cych operandy 8-bitowe w kodzie NB i U2
9* Zaprojektuj układ mno\
enia akumulacyjnego (pomnó\
i dodaj) operandów 8-bitowych w kodzie U2
wykorzystujÄ…cy matrycÄ™ mno\
ącą. Porównaj z innymi układami matrycowymi.
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-ZAD+ROZW 02 5 paz
dziernika 2005
6
Rok I ARYTMETYKA KOMPUTERÓW Lista nr 7
1. Oblicz metodą Newtona odwrotność dzielnika 1,1011012 z dokładnością do 16 bitów.
2. Oblicz metodą Newtona odwrotność pierwiastka kwadratowego z 102 . z dokładnością do 16 bitów.
3. Oblicz metodÄ… uzbie\
niania iloraz 3,14168 :2,71638.
4. Opracuj algorytm obliczania pierwiastka kwadratowego z liczby całkowitej 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.).
*Oceń czas obliczeń i porównaj z algorytmem klasycznym ( kolejnych reszt ) w wersji podstawowej
i nierestytucyjnej. Zaproponuj ulepszenie algorytmu dla du\
ych argumentów.
*Określ minimalny czas obliczeń, jeśli liczba jest zakodowana odpowiednio na 8, 16, 32 bitach.
5* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zale\
ności:
n n n j-1 n-1 j
2
n3 - n =
"(3Å"i - 3Å"i) = 3"(i Å"(i -1)) = 3""2i = 6""i
i=1 i=1 j=1 i=0 j=1 i=1
6* 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.
7. KorzystajÄ…c z przybli\
enia (1 x) 1 = 1+x+x2+... oraz (1+x) 1 = 1 x+x2 x3+... oblicz odwrotności dla
poni\
szych reprezentacji zmiennoprzecinkowych. Określ wartości bitów GRS. Oceń dokładność
przybli\
enia i podaj warunki stosowalności algorytmu.
Wskazówka: Sprawdz
przydatność przybli\
eń dla ró\
nych rozwinięć części ułamkowej (mno\
ników
o postaci 2-f oraz 1+f, gdzie f jest małym ułamkiem.
8.*Korzystając z rozwinięcia w szereg Taylora (McLaurina) podaj algorytm obliczania przybli\
enia
odwrotności liczby w formacie zmiennprzecinkowym o postaci 1ąax, gdzie a=2q. Określ warunki
stosowalnosci algorytmu i sposób wyznaczania wartości bitów GRX. Oceń dokładność przybli\
enia.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
7
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 1
1. Znajdz
podstawę x systemu naturalnego, w którym: a) 41x = 5 , b) 22x = 4 c) a2 =301x , d) b2 =562x
Wskazówka: a) i b) Po podniesieniu stron równości do kwadratu, rozwiązać ze względu na nieznaną
podstawę. Oczywiście musi ona być większa od największej cyfry występującej w równaniu (wartości
cyfr <10 sÄ… takie jak w systemie dziesiÄ™tnym). Na przykÅ‚ad 5x×5x=41x, czyli 25=4x+1, wiÄ™c x=6.
Jeśli liczba pierwiastkowana ma k cyfr, to trzeba rozwiązać równanie stopnia k 1 względem x.
c) I sposób: Mamy równanie a2 = 3x2+1, skąd x2=(a+1)(a-1)/3. Wynika stąd, \
e a musi być parzyste
lub a=6k-1 lub a=6k+1. Musi być te\
a>x. Na przykład gdy a=7, to x=4 (7=134), itd
II sposób: Kwadrat jest liczbą trzycyfrową, więc a musi być liczbą dwucyfrową, a jej starszą cyfrą
musi być 1 (bo x2<301x = 3x2+1<(2x)2). Mamy stąd równanie (x+z)2 = 3x2+1, czyli 2x2 2zx +(1 z2)= 0.
Jedno z rozwiązań musi być ujemne (wzory Viete y  iloczyn pierwiastków (1 z2)/2 jest ujemny).
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 x=4 (lub  1), gdy z=11 to x=15 (lub  4).
d) starszą cyfrą liczby b jest 2, bo (2x)2 < 562x= 5x2+6x+2 <(3x)2). Mamy stąd równanie parametryczne
(2x+z)2 = 5x2+6x+2, czyli x2+(6 4z)x+(2 z2)=0 z warunkami: x > 6 , zDla x=7 otrzymujemy (2Å"7+z)2=289, skÄ…d z=3.
JeÅ›li kwadrat jest liczbÄ… k-cyfrowÄ…, to trzeba analizować równanie stopnia k 1 wzglÄ™dem podstawy ².
2. Znajdz
podstawÄ™ ² systemu naturalnego, w którym liczby naturalne x1 oraz x2 sÄ… rozwiÄ…zaniami
równania ax2+ bx+c = 0. Wykonaj obliczenia dla x1 = 5² , x2 = 8² i równania 5² x2 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² ( x1 +x2) = 50² , skÄ…d natychmiast wynika (5² ×10² =50² ) \
e x1
+x2 = 10² = ² . Trzeba jeszcze sprawdzić, czy 513×(513×813) = 12513 (OK., bo 132+2×13+1 = 200).
*JeÅ›li rozwiÄ…zania równania x2 15² x+53² = 0 sÄ… naturalne, to x1 + x2 = ² + 5 oraz = x1 x2 = 5² + 3.
Musi wiÄ™c być x1 > 5 oraz x2 < ² (w przeciwnym razie jeden musi być ujemny) JeÅ›li x1 = 6 , x2 = ² - 1 ,
to ² = 9 . (powinny być dwa symetryczne rozwiÄ…zania dla x1 oraz x2  jedno rozwiÄ…zanie dla ² ).
3**Znajdz
podstawę systemu naturalnego, w którym równanie ax2+bx+c=0 (a,b,c " ) ma pierwiastki
całkowite. Rozwią\
zadanie zakładając, \
e a,x1,x2 sÄ… liczbami jednocyfrowymi, b = b1²+b0 jest liczbÄ…
2
dwucyfrowÄ…, zaÅ› c = c2² +c1²+c0, c2 = 0 lub 1. Wykonaj obliczenia dla x1 = 5² , x2 = 8² oraz a = 1 i 3.
Wskazówka: Na podstawie wzorów Viete y uło\
yć ukÅ‚ad równaÅ„ wzglÄ™dem podstawy ² i nieznanego
drugiego pierwiastka x2:  a (x1 + x2) = b oraz a x1 x2= c. Pierwiastki całkowite są podzielnikami liczby
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
8
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
c, co pozwala określić dozwolony zakres ich wartości. Powstałe przypadki nale\
y 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. *Uogólnij wynik dla kÅ"|{² 1, & , ² 1, ² 1}|²
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. Przeprowadz
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,5610 ×2 5 = (& )2 = (& )16 e) 102,213×5 2 = (& )5 f) 0BACA16 ×5 3 = (& )10
g) 6745,819 = (& )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 z
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 jeśli istnieje nierozkładalny podzielnik podstawy z
ródłowej, który nie jest podzielnikiem
podstawy docelowej, to wynikiem konwersji ułamka skończonego w systemie o danej podstawie, na
reprezentację w innym systemie naturalnym jest ułamek okresowy.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
9
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: Znajdz
licznik uÅ‚amka danego w bazie ² w bazie p² gdy (p,²)=1. (dowód podobnego
twierdzenia podano w ksiÄ…\
ce  Metody i układy arytmetyki komputerowej ). Twierdzenie jest
fałszywe, bowiem są przypadki gdy tak nie jest np. 0,510 = 0,12, ale np. 0,110 = 0,(00011)2.
9. Znajdz
system o najmniejszej podstawie, w którym reprezentacja danego ułamka 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=
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 + & =
1
= 0,3 / ( 1  0,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 podczas 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ę zwiększymy o 1 przeniesienie będzie bez zmian.
Poniewa\
na pozycji najni\
szej przeniesienie jest równe 0, więc 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: Sprawdz
, jakie działanie nale\
y faktycznie wykonać w zale\
ności od znaków argumentów.
Wskazówka: Dla zadanego zbioru cyfr opracuj tabliczki działań. Sprawdz
poprawność tego zbioru.
Zbadaj problem przeniesienia. Zauwa\
, \
e jeśli zbiór cyfr jest niestandardowy, to nie ma gwarancji
wytworzenia poprawnej cyfry wyniku na \
adnej pozycji i konieczna jest korekcji cyfr na pozycjach.
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/2² k 1 oraz  +1/2² k 1 1 .
Odpowiedz
: Podstaw 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.
E* Wyka\
, \
e w systemach uzupełnieniowych pełnych o bazach skojarzonych konwersję podstawy mo\
na
S S
wykonać przez grupowanie (² ² ) lub dekompozycjÄ™ cyfr (² ² ).
Wskazówka: Liczby ujemne zapisz w konwencji znak-moduł lub (lepiej) u\
yj pozycji rozszerzenia.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
10
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 2
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: I) Zapisz wartość bezwzględną, roszerzając ją lewostronnie zerem (w systemie znak-moduł
rozszerzenie jest zbędne), potem wykonaj  wchłonięcie znaku  w systemie U1 negując wszystkie
bity, w systemie U2 odejmując od 0 (lub mnemotechnicznie). II)*Liczbę zapisz jako Z+f, 0Konwersja liczby całkowitej Z mo\
e być wykonana bezpośrednio (kolejne ilorazy mają taki znak jak
liczba, procedura kończy się gdy kolejne cyfry są cyframi rozszerzenia (lub uzyskamu iloraz  1).
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 dodawaniu lub odejmowaniu w systemie stałobazowym i uzupełnieniowym u\
ycie cyfr
lewostronnego rozszerzenia operandó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. Wykonaj zmianÄ™ znaku liczby danej w quasi-symetrycznym kodzie spolaryzowanym +2k oraz +2k-1
a) 10101001 b) 0101010 c) 1100001 c) 00110101
Wskazówka: Opracuj algorytm. Sprawdz
, \
e w kodzie +2k algorytm jest identyczny jak w kodzie
uzupełnieniowym (zaneguj wszystkie bity i dodaj ulp, czyli 1  reprezentowane są tylko całkowite),
zaś w kodzie +2k-1 po negowaniu bitów nale\
y wykonać odejmowanie 1)
5. Zakładając, \
e podane 8-bitowe sekwencje 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  +28 1 1 f) spolaryzowanym  +28 1 .
oblicz sumę i ró\
nicÄ™ liczb o kodach: i) 10011101 i 01111001, ii) 11011101 i 10111101. Sprawdz

poprawność wyników wykonując działanie odwrotne (suma  argument, ró\
nica + odjemnik)
Wskazówka: W systemach spolaryzowanych wygodnie jest wykonać konwersję na system U2.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
11
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
6. Znając kilka najbardziej znaczących bitów liczb n-bitowych w kodzie uzupełnieniowym U2, sprawdz
,
czy w ich dodawaniu i odejmowaniu wystÄ…pi nadmiar:
a) 11101010..?? Ä… 10011110..?? b) 1011010..?? Ä… 1001110..?? c) 011101..?? Ä… 11011001..??
Wskazówka: Znajdz
najwy\
szą pozycję na której jest wytwarzane przeniesienie w dodawaniu (1+1) albo
po\
yczka w odejmowaniu (0 1), a następnie (wynik na pozycjach wy\
szych od znalezionej nie zale\
y
od stanu pozycji ni\
szych) zbadaj 2 najwy\
sze przeniesienia lub celowość u\
ycia bitów rozszerzenia.
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
Sprawdz
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 2m pozycjach.
Wskazówka: Zakresem iloczynu jest [0, (² m 1 )2]= [0, ² 2m 2² m +1<² 2m 1]
9. Wynik mno\
enia m bitowych liczb w kodzie U2 jest kodowany na 2m 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 [ 2m 1×(2m 1 1), ( 2m 1)2]= [ 22m 2+2m 1, 22m 2]. Liczba 22m 2 musi
być zakodowana na 2m bitach, dla pozostałych wystarczy 2m 1 bitów.
A. Wykonaj mno\
enie liczb w dwójkowym kodzie uzupełnieniowym pełnym (U2) u\
ywając bitów
rozszerzenia i stosując przekodowanie iloczynów częściowych eliminujące rozszerzenia:
a) 110101×011011 b) 011101×110111 c) 101001×111111 d) 1101010×1111101.
Uwaga: Iloczyn odpowiadajÄ…cy najwy\
szemu bitowi mno\
nika ma wagę ujemną. Pamiętaj o bitach
rozszerzenia. Zwróć uwagę na poprawne kodowanie zera i przekodowanie iloczynu częściowego
odpowiadajÄ…cego najwy\
szemu bitowi mno\
nika. Nie zapomnij o 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) 6745U10 × 8123U10 b) 9745U10 × 0823 U10 c) 3156 U10 × 8423 U10 d) 9994 U10 × 9916 U10
a) 5745U8 × 7123U8 b) 7745U8 × 0723 U8 c) 3156 U8 × 6423 U8 d) 7774 U8 × 7716 U8
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-ZAD+ROZW 02 5 paz
dziernika 2005
12
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 3
1. Zakoduj na 8 bitach według prostej i alternatywnej reguły Booth a i Booth a-McSorley a:
a)  81710 b) +132110 c) 101111012 d) 1011101U2 e)* 1011101( 2)
Wskazówka: Najpierw zapisz liczby w systemie U2.
2. U\
ywajÄ…c przekodowania Booth a oraz Booth a-McSorley a i przyjmujÄ…c, \
e operandy sÄ… w kodzie
A) dwójkowym naturalnym, B) uzupełnieniowym U2, C)* dopełnieniowym U1, oblicz iloczyny:
a) 11000101×01110011 b) 011101×11011110 c) 101001×1011111 d) 010011×010111110.
Wskazówka: Nie zapomnij o bitach rozszerzeń. W kodzie U1 uwzględnij eac (przeniesienie okrę\
ne)
3. Wykonując dzielenie odtwarzające (metodą sekwencyjną  kolejnych reszt ) oblicz 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) 576U10 : 176U10 d) 424U10 : 824U10
e) 6465U10 : 353,5U10 f) 6465U8 : 353,5U8 g) 5465U10 : 150,7U10 h) 2465U8 : 753,5U8.
Sprawdz
poprawność otrzymanych wyników wykonując mno\
enie.
Wskazówka: Nie zapomnij o skalowaniu, tak aby |D/2|<|X² p|<|D|, co pozwoli te\
uniknąć generowania
nieznaczących bitów. Zauwa\
, \
e po skalowaniu iloraz jest ułamkiem właściwym (0+f lub  1+f).
4. Wykonaj w kodzie U2 z dokładnością do 5 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.
Sprawdz
, wykonujÄ…c mno\
enie, poprawność otrzymanych wyników.
Wskazówka: Przeskaluj dzielnik (dzielną) tak, aby iloraz był ułamkiem.
5. Oblicz metodą nieodtwarzającą z dokładnością do 4 cyfr znaczących iloraz liczb naturalnych (NB):
a) 1101012 : 0110112 b) 0111012 : 1101112 c) 1010012 : 111112 d) 1010012 : 100112,
e) 1,101012 : 01101,12 f) 0,111012 : 110,1112 g) 1010,012 : 111,112 h) 1010012 : 100,112.
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 sÄ… 3 cyfry przybli\
enia pierwiastka kwadratowego i trzecia reszta. Podaj dwie kolejne cyfry, jeśli:
a) Q3 =1237, r3 =34567, b) Q3 =12310, r3 = 345610, c) Q3 =1012, r3 =111012,
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
13
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia czwartej cyfry ilorazu  występuje
w niej podwojone skalowane trzecie przybli\
enie Q3 oraz reszta r3 :
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) Q4 =12,347, b) Q4 =1,23410, c) Q4 =11012.
Wskazówka: Przeanalizuj nierówność, która jest podstawą obliczenia piątej cyfry ilorazu  występuje
w niej podwojone skalowane czwarte przybli\
enie Q4 oraz reszta r4. 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ą z dokładnością do 5 cyfr znaczących pierwiastek kwadratowy z liczb:
a) 1010 0010 0111 11002, b) 123,4568, c) 10100 0100,1111 1002
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 2m 1ą1. Zauwa\
, \
e wtedy X = (2m 1Ä…1)Q, skÄ…d
wynika, \
e Q = ą (X 2m 1Q), 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.
B. Analitycznie i na podstawie wykresu dzielenia dwójkowego: a) odtwarzającego, b) nieodtwarzającego
wyznacz 3 kolejne cyfry ilorazu, je\
eli znormalizowany dzielnik (1 d" D < 2) ma wartość i) D = 1,1012,
ii) D = 1,11012, a bie\
Ä…cÄ… resztÄ… (przed skalowaniem) jest: a) 0,3D, b) -0,2D, c) +0,7D.
Wskazówka: a) rozwią\
dwa kolejne równania dzielenia; b) zaznacz resztę na osi odciętych i graficznie
znajdz
kolejną resztę (pierwsze odwzorowanie wg odcinka  q=2 ), przeskaluj ją i powtórz czynności.
C* Narysuj wykresy P-D dla dzielenia w bazie 4 (² = 4) i dzielnika z zakresu [1,2). Podaj ile bitów musi
być porównywanych w celu wyznaczenia cyfr ilorazu.
Wskazówka: Zaplanuj dokładność wykresu i odpowiednio wrysuj linie graniczne, pamiętając o
dokładności wykresu.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
14
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 4
1. Wyka\
, \
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...(XmodY=X kY2. Korzystając z twierdzenia Euklidesa znajdz
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))
k k + 1
3. Poka\
, \
e liczby 2 + 1 i 2 + 1 są względnie pierwsze (k " N  jest liczbą naturalną)
*Wyka\
, \
e liczby 2n+1, 22n+1+2 oraz 2n-1 są względnie pierwsze z liczbą 22n+1 (n" N ).
k r
**Kiedy prawdziwe jest twierdzenie, \
e liczby 2 + 1 i 2 + 1 (k , r " N ) są względnie pierwsze?
k + 1 k k k
Wskazówka: Zastosuj twierdzenie Euklidesa. Zauwa\
, \
e 2 = 2 ×2 = 2 + 2
* Wykorzystaj związki potęg oraz wzory skróconego mno\
enia.
**Twierdzenie nie jest zawsze prawdziwe  kontrprzykład  (21+1,23+1) = 3.
Udowodnij, \
e gdy k jest nieparzyste, to NWD(2k+1, 2k+2+1)=3 i NWD(2kp+1, 2p+1)=2p+1, itp.
4. Na podstawie twierdzenia Eulera lub małego twierdzenia Fermata oblicz:
a) 13267mod 63, b) 172167mod 19 c) 40167mod 41 d) (1726713267)mod 55
Wskazówka: Sprawdz
, czy konieczne jest stosowanie tw. Eulera. Jeśli tak, wyznacz podzielniki pierwsze
modułu oraz funkcję Eulera i stosownie zredukuj potęgę. (ew. zastosuj małe tw. Fermata)
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 najmniejsze reszty całkowite (dodatnie lub ujemne) sumy,
ró\
nicy i iloczynu liczb 46528 i 0ABCD16 względem modułów: 25710, 78 , 6510, 3F16, 1116, 0FF16
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* Znajdz
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
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
15
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
9. Znajdz
jedynki resztowe w zbiorze kongruencji naturalnych (x"[0, M)) w systemie RNS:
a) {29, 30, 31} b) {99, 100, 101} c) {63, 64, 65} d)* {11, 13, 15, 16}
Znajdz
liczbę, której reprezentacją resztową jest ((a),b),c)): (1, 2, 3), (d): (1, 2, 2, 1).
**RozwiÄ…\
zadanie w zbiorze kongruencji caÅ‚kowitych (x" ðÅ‚ (M 1)ûÅ‚ /2, ðÅ‚M 1ûÅ‚ /2))
Wskazówka: Wykorzystując zale\
ność (m ą 1) mod m = ą 1 (oprócz d)) znajdz
odwrotności niepełnych
iloczynów modułów bazy i zastosuj chińskie twierdzenie o resztach. Zauwa\
, \
e zawsze jest
(1, 1, 1, & , 1) = 1, ( 1,  1,  1, & ,  1) =  1 = M 1, a tak\
e (m1 1, m2 1, m3 1, & , mk 1)=M 1=  1.
**  Do uzyskanych wyników dodaj ąM&
A. Zapisz w 32-bitowym formacie zmiennoprzecinkowym standardu IEEE 754 liczby o wartościach:
-61
a) 674,5318 b) 0,128 Å" 8-51 c)  0ABC,DE16 d) 10,1010101010U2 Å" 4
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 dodawaniu (mno\
eniu) zmiennoprzecinkowym znormalizowanych operandów, bit X dla
znormalizowanej sumy (iloczynu) mo\
e być wyznaczony przed wykonaniem działania.
Wskazówka: Rozpatrz przypadki składników o identycznych i ró\
nych wykładnikach. W mno\
eniu
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).
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, X. 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* 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-ZAD+ROZW 02 5 paz
dziernika 2005
16
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 5
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) zx+z(x•"1) f) x+xy+(x•"yz)
g) [zÅ"f(x)+(z•"f(x))] f(x) h) (g(x)+z•"f(x))+z f(x)(1•"g(x)
Wskazówka: Zamień wyra\
enia zawierajÄ…ce •" na sumy iloczynów i zminimalizuj. 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(x1, & , xi
, Ć, xi+1, & , xn) = f(x1, & , xi 1, 0, xi+1, & , xn) + f(x1, & , xi 1, 1, xi+1, & , xn) .
1
2* Poka\
, \
e ka\
dÄ… funkcjÄ™ logicznÄ… mo\
na wyrazić za pomocą funkcji NOR albo funkcji NAND.
Wskazówka: Przedstaw funkcje sumy, iloczynu i negacji za pomocą funkcji NOR lub NAND
3. Wyznacz funkcje dualne i komplementarne do funkcji f1(x) = x2 x1 + x3x2 i f2 (x) = x3x1 + x3 (x2 + x1) ,
oraz (f1+f2)(x) i (f1 f2)(x). Narysuj stosowne sieci logiczne. Na podstawie twierdzenia Shannona rozwiń
funkcje (f1+f2)(x), (f1 f2)(x) i (f1•"f2)(x) wzglÄ™dem zmiennej x3.
Wskazówka: Zastosuj prawa de Morgana.
4* Poka\
, \
e charakterystyki AT sieci realizujÄ…cych funkcjÄ™ dualnÄ… i komplementarnÄ… sÄ… jednakowe.
Wskazówka: Zauwaz
podobieństwo rozwinięcia funkcji w postaci sumy iloczynów i iloczynu sum.
5* 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 s0 , s1 , c0 , c1 . Wyznacz charakterystyki AT tego układu.
Odpowiedz
: Wyznacz najdłu\
szą ście\
kę, policz bramki przeliczeniowe na tej ście\
ce (T) i wszystkie (A).
6. 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  +2k 1 e) spolaryzowanego dodatnio  +2k 1 1
Wskazówka: Wykorzystaj charakterystyki AT sumatora 1-bitowego.
7. 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.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
17
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
8. 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óz
nienie.
9. 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.
A* Zaprojektuj 4- i 8-bitowy sumator prefiksowy PPA w strukturze Ladnera-Fischera i Hana-Carsona.
Wyznacz funkcje wytwarzania (G*) i przekazywania (P*) przeniesień na kolejnych poziomach bloku
generowania przeniesień. **Wyznacz charakterystyki AT sumatora k-bitowego.
Wskazówka: Oceń charakterystyki AT stopnia wejściowego, poziomu sieci PPA i stopnia wyjściowego.
**Znajdz
zale\
ność na parametry AT dla n=2k a następnie uogólnij ten wynik.
B. 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.
C. Zaprojektuj uniwersalny ukÅ‚ad realizujÄ…cy skalowanie liczby 8-bitowej w kodzie U2 przez 2, ½ oraz ź.
Wyznacz charakterystyki AT tego układu. Wskazówka: Zrealizuj układ jako przesuwnik kaskadowy
(barrel shifter) z u\
yciem multiplekserów 2-wejściowych. Pamiętaj o pozycjach rozszerzenia.
Wskazówka: Zauwa\
, \
e układ mo\
na zrealizować jako przesuwnik w prawo (o 0, 1, 2 lub 3 pozycje)
z przekierowaniem (przenumerowaniem) wyjść (co odpowiada obligatoryjnemu przesunieciu w lewo).
D* Zaprojektuj uniwersalny sumator 4-bitowy, którego wejścia są zakodowane w dwójkowym kodzie
naturalnym, a wyjścia w kodzie znak-moduł .
Wskazówka: Rozwa\
, ró\
ne warianty rozwiÄ…zania  zdublowany sumator, sumator U2 z korekcjÄ…, itp
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
18
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 6
1. W celu dodania n operandów k-bitowych u\
yto sumatora CSA (carry-save). Ile bitów zawiera suma?
Jakie jest opóz
nienie (T) dodawania, jeśli końcowy wynik wytwarza sumator:
a) kaskadowy RCA, b) prefiksowy PPA c) 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 (2k  1)]. Liczba poziomów s d" (lg n/2) / lg 3/2.
Opóz
nienie jednego poziomu T=4 (do obu wyjść)
2. 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łąz
CSA odpowiadajÄ…ca bitom o tej samej wadze.
Wskazówka: Patrz poprzednie zadanie.
3. Zaprojektuj sumator CSA dodający odpowiednio 3, 4 i 8 operandów 4-bitowych w kodzie U2.
Wskazówka: Nie zapomnij o bitach rozszerzenia. Sprawdz
skutki, jeśli bity te zostaną pominięte.
4. 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óz
nienia T = 4 ka\
dy
d) *reduktorami (4,2) generującymi przeniesienia 2-bitowe, wnoszące opóz
nienia T = 6 ka\
dy
Wskazówka: *Oblicz liczbę poziomów i liczbę bitów końcowego dodawania.
5. 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.
6* Zaprojektuj matrycÄ™ mno\
Ä…cÄ… operandy 4-bitowe w kodzie U2 z wykorzystaniem przekodowania
mno\
nika w bazie 4 (wg reguły Bootha-McSorley a). Porównaj z innymi układami matrycowymi.
Wskazówka: Zaprojektuj element podstawowy matrycy.
7. 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Ä™.
8. Oblicz charakterystyki AT matryc dzielÄ…cych operandy 8-bitowe w kodzie NB i U2
Wskazówka: Wyznacz najdłu\
szą ście\
kę propagacji zmiany sygnału wejściowego.
9* Zaprojektuj układ mno\
enia akumulacyjnego (pomnó\
i dodaj) operandów 8-bitowych w kodzie U2
wykorzystujÄ…cy matrycÄ™ mno\
ącą. Porównaj z innymi układami matrycowymi.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
19
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
A* 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 e" 2-
pozycyjnej w kodzie BCD. Konwersja dwójkowy na BCD/BCD+3: Wykorzystaj dodawanie.
B. Zaprojektuj sumatory mod (24 1) i (24+1) dwóch liczb całkowitych 4-bitowych w kodzie U2.
Wskazówka: Rozwa\
kongruencje w zbiorze liczb całkowitych. Przeanalizuj struktury PPA.
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
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.
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
Wskazówka: Rozwa\
kongruencje w zbiorze liczb całkowitych. Zauwa\
, \
e najwy\
sz grupa bitów ma
k -2 k-2 s-1
znak - xk -12k -1 + xi 2i =2s (-xk -12k -1-s + xi 2i-s ) + xi 2i
" " "
i=0 i=s i=0
E*Zaprojektuj sumator mod 23 liczb 6-bitowych w kodzie U2
Wskazówka: Wykorzystaj okresowość reszt mod 23.
F*Zaprojektuj generatory reszt mod (23 1) dwóch liczb całkowitych 32-bitowych w kodzie U2.
Wskazówka: Wykorzystaj sumatory CSA w strukturze MOMA (z bie\
Ä…cÄ… redukcjÄ… przeniesienia
okrÄ™\
nego).
G**Zaprojektuj generatory reszt mod (23+1) dwóch liczb całkowitych 32-bitowych w kodzie U2.
Wskazówka: Wykorzystaj sumatory CSA w strukturze MOMA. Zauwa\
, \
e operandy wejściowe są
zredukowane (nie ma operandów o wartości 23) i mają przeciwne znaki.
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
20
Rok I ARYTMETYKA KOMPUTERÓW rozwiązania
Lista nr 7
1. Oblicz metodą Newtona odwrotność dzielnika 1,1011012 z dokładnością do 16 bitów.
2. Oblicz metodą Newtona odwrotność pierwiastka kwadratowego z 102 . z dokładnością do 16 bitów.
Wskazówka: Znajdz
funkcję monotoniczną i wymyśl sposób ustalania pierwszego przybli\
enia
3. Oblicz metodÄ… uzbie\
niania iloraz 3,14168 :2,71638.
Wskazówka: Wybierz pierwsze przybli\
enie ...
4. Opracuj algorytm obliczania pierwiastka kwadratowego z liczby całkowitej 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.).
*Oceń czas obliczeń i porównaj z algorytmem klasycznym ( kolejnych reszt ) w wersji podstawowej
i nierestytucyjnej. Zaproponuj ulepszenie algorytmu dla du\
ych argumentów.
*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 "k = X - (2i +1) = [X - (2i +1)] - (2k +1) = "k -1 - (2k +1) , więc
" "
i=0 i=0
oszacowaniem pierwiastka jest takie k, przy którym odstęp sumy od X zmienia znak.
*KorzystajÄ…c z zale\
ności (n+p)2  n2 = (2n+1)(2n+3)& [2(n+p) 1]
5* Oceń czas obliczania pierwiastka trzeciego stopnia na podstawie algorytmu opartego na zale\
ności:
n n n j-1 n-1 j
2
n3 - n =
"(3Å"i - 3Å"i) = 3"(i Å"(i -1)) = 3""2i = 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ą.
6* 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.
7. KorzystajÄ…c z przybli\
enia (1 x) 1 = 1+x+x2+... oraz (1+x) 1 = 1 x+x2 x3+... oblicz odwrotności dla
poni\
szych reprezentacji zmiennoprzecinkowych. Określ wartości bitów GRX. Oceń dokładność
przybli\
enia i podaj warunki stosowalności algorytmu.
Wskazówka: Sprawdz
przydatność przybli\
eń dla ró\
nych rozwinięć części ułamkowej (mno\
ników
o postaci 2-f oraz 1+f, gdzie f jest małym ułamkiem.
8.*Korzystając z rozwinięcia w szereg Taylora (McLaurina) podaj algorytm obliczania przybli\
enia
odwrotności liczby w formacie zmiennprzecinkowym o postaci 1ąax, gdzie a=2q. Określ warunki
stosowalności algorytmu i sposób wyznaczania wartości bitów GRX. Oceń dokładność przybli\
enia.
Wskazówka: Wykorzystaj rozwinięcie w szereg Taylora (McLaurina).
©Janusz Biernat, ARYT-ZAD+ROZW 02 5 paz
dziernika 2005
21