Janusz Biernat, profesor nadzw.
Politechnika Wrocławska
Wydział Elektroniki
Instytut Informatyki, Automatyki i Robotyki
Zakład Architektury Komputerów
ARYTMETYKA KOMPUTERÓW
! Wrocław
p. 201 bud. C3
( 071 320 3916 (071 320 2745)
- Janusz.Biernat@pwr.wroc.pl
http://www.zak.ict.pwr.wroc.pl/materialy/arytmetyka
ARYTMETYKA KOMPUTERÓW program wykładu 2006
1. Reprezentacje stałoprzecinkowe dodatnich liczb wymiernych, konwersje podstawy.
2. Reprezentacje liczb znakowanych - uzupełnieniowa, spolaryzowana, SD.
Dodawanie i odejmowanie liczb znakowanych, nadmiar.
3. Mno enie w systemach uzupełnieniowych. Algorytm Booth a-McSorleya.
4. Dzielenie w systemach uzupełnieniowych. Obliczanie pierwiastka kwadratowego.
5. Kongruencje. Twierdzenie Eulera. Chi skie twierdzenie o resztach.
Systemy resztowe RNS. Konwersja na reprezentacj RNS i konwersja odwrotna.
6. Rozszerzanie zakresu działa arytmetycznych. Reprezentacje zmiennoprzecinkowe.
Standard IEEE754. Obliczenia zmiennoprzecinkowe, dokładno , zaokr glanie.
7. Dzielenie numeryczne. Metoda Newtona-Raphsona. Algorytm CORDIC obliczanie
funkcji elementarnych.
8. Kolokwium (algorytmy oblicze ).
9. Podstawy algebry Boole'a, realizacja funkcji logicznych. Sumatory.
10. Szybkie sumatory stałoprzecinkowe (CSA, PPA, COSA, CSLA, CSKA).
11. Układy szybkiego mno enia liczb w reprezentacjach stałoprzecinkowych.
12. Przy pieszanie dzielenia i obliczania pierwiastka kwadratowego.
13. Kolokwium (układy cyfrowe).
14. Architektura układów arytmetyki resztowej RNS.
ARYTMETYKA KOMPUTERÓW program ćwiczeń
Kodowanie liczb, konwersje podstawy
Dodawanie i odejmowanie w systemach naturalnych i uzupełnieniowych
Mno enie
Dzielenie i obliczanie pierwiastka kwadratowego
Arytmetyka resztowa
Arytmetyka zmiennoprzecinkowa i obliczenia numeryczne
Logika i układy cyfrowe
Układy mno ce
Układy arytmetyki resztowej
Arytmometr zmiennoprzecinkowy
Literatura
Literatura podstawowa
J.BIERNAT, Metody i układy arytmetyki komputerowej, Wrocław, Oficyna Wydawnicza
Politechniki Wrocławskiej, 2001.
I.KOREN, Computer Arithmetic Algorithms, A.K.Peters, Natick, MA, 2002
(wyd.1: Prentice Hall, Englewood Cliffs, NJ, 1993).
R.ZIMMERMANN, Lecture Notes on Computer Arithmetic: Principles, Architectures and
VLSI Design, Institut fr Integrierte Systeme, Eidgenssische Technische
Hochschule, Zurich, March, 1999.
ą
Literatura uzupełniaj ca
B.PARHAMI, Computer Arithmetic. Algorithms and Hardware Designs, New York-Oxford, Oxford
University Press, 2000
J-M.MUELLER, Elementary functions. Boston: Birkhauser 1997
B.POCHOPIE , Arytmetyka w systemach cyfrowych, Warszawa, AOW Exit, 2004
(Arytmetyka systemów komputerowych, Gliwice, Wyd. Polit. l skiej, 2000, wyd.V)
J.BIERNAT, Architektura komputerów, Wrocław, Oficyna Wydawnicza Politechniki Wrocławskiej,
2005 (wyd.IV).
J.BIERNAT, Arytmetyka komputerów, Warszawa, PWN, 1996.
N.KOBLITZ, Wykład z teorii liczb i kryptografii, WNT, 1995.
S.WASSER, M.J.FLYNN, Introduction to arithmetic for digital system designers, New York, Holt,
Rinehart, Winston 1982.
Arytmetyka
Algebra abstrakcyjne uogólnienie arytmetyki
System algebraiczny zbiór z działaniami zamkni tymi w tym zbiorze
" grupa (ang. group) zbiór z jednym działaniem ł cznym (dodawanie)
istnieje element przeciwny do ka dego oraz element neutralny
w grupie mo na dodawa i odejmowa
" pier cie (ang. ring) zbiór z dwoma działaniami (dodawanie, mno enie):
grupa przemienna wzgl dem dodawania, zamkni ty dla mno enia
mno enie jest ł czne i obustronnie rozdzielne wzgl dem dodawania
w pier cieniu mo na dodawa , odejmowa i mno y
Pier cie przemienny (niesko czony) liczb całkowitych .
" ciało (ang. field) zbiór z dwoma powi zanymi działaniami przemiennymi
jest grup ze wzgl du na dodawanie, dodawanie rozdzielne wzgl dem
mno enia, a bez elementu 0 jest grup ze wzgl du na mno enie
w ciele mo na dodawa , odejmowa , mno y i dzieli (mno y przez odwrotno )
Ciała liczb: całkowitych modulo liczba pierwsza p p (sko czone)
wymiernych ; rzeczywistych ; zespolonych (niesko czone).
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 AR I
Arytmetyka
Arytmetyka
Teoria liczb wła ciwo ci liczb naturalnych
Sposoby obliczania wyniku działa podstawowych (arytmetycznych)
" odejmowanie i dodawanie (... mo na wykona przez odejmowanie)
" mno enie sekwencyjne lub równoległe
o skalowanie mno enie przez całkowit pot g bazy
" dzielenie sekwencyjne lub mno enie przez odwrotno dzielnika
" wyci ganie pierwiastka kwadratowego sekwencyjne
Arytmetyka klasyczna dowolny rozmiar liczb (rozszerzenia niesko czone)
problem algorytm (jak to zrobi ?)
Arytmetyka komputerowa ograniczony zakres argumentów
problem nadmiar (przekroczenie zakresu)
problem szybko wykonania działa
problem dokładno wyniku
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 AR II
Arytmetyka
Dokładno i szybko oblicze
Dodawanie, odejmowanie, mno enie
" argumenty dokładne wynik tak e dokładny
" argumenty przybli one ze znan dokładno ci :
łatwa kontrola dokładno ci wyniku, kumulacja bł dów przybli e
Dzielenie, obliczanie pierwiastka kwadratowego
" wynik zwykle niedokładny (nawet gdy argumenty s dokładne)
" konieczna kontrola dokładno ci wyniku
WNIOSEK: Nale y najpierw wykona działania dokładne.
Obliczenia: działania składowe + przepis (algorytm)
działania składowe:
" elementarne szybkie czasochłonny algorytm (program)
" zło one czasochłonne prosty krótki algorytm (układ cyfrowy)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 AR III
Arytmetyka
Liczby i cyfry
Liczba abstrakcyjny wynik oblicze , warto , opis ilo ciowy obiektu
Cyfra znak (symbol) u ywany do zapisu (reprezentacji) liczb
Cyfry rzymskie
I V X L C D M / (I) D /(V) M /((I))
ć ć ć ć
ę ę ę ą ę ą ę ę
jeden pi dziesi pi dziesi t sto pi set tysi c 5 tysi cy 10 tysi cy
Cyfry arabskie (pochodz ce z Persji)
0 1 2 3 4 5 6 7 8 9
Cyfry indyjskie, u ywane w zapisie w j zyku arabskim
0 1 2 3 4 5 6 7 8 9
Umowa (niepisana) o zapisie cyfr o warto ciach wi kszych od dziewi ciu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7 8 9 A B C D E F
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 AR IV
Systemy liczenia
Miary i liczby systemy wagowe
system pomiaru czasu 1doba=24h, 1h=60min, 1min=60s
brytyjski system miar i wag
miary odległo ci miary wagi
inch (cal) 1 in (25,3995 mm) grain (ziarno) 1 gr (64,79891 mg)
foot (stopa) 1 ft = 12 in dram 1 dr (1,77185 g)
yard (jard) 1 yd = 3 ft ounce (uncja) 1 oz = 16 dr = 4371/2 gr
fathom 1 fathom= 2 yd pound (funt) 1 lb = 8 oz
rod (pr t) 1 rod = 51/2 yd stone (kamie ) 1 st = 14 lb
chain 1 chain = 4 rods quarter 1 q = 2 st
furlong 1 furlong = 10 chains hundredweight 1 cwt = 2 q
mile (mila) 1 mi = 8 furlongs ton (tona) 1 t = 20 cwt
league 1 lg = 3 m central 1 st = 100 Ib
Systemy abstrakcyjne system rzymski (tak e babilo ski)
I (=2050) jedno C (=2252) setka
V (=2051) pi tka D (=2253) pi setka
X (=2151) dziesi tka M (=2353) tysi c
L (=2152) pi dziesi tka D (=2354) pi tysi cy
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL I
Systemy liczenia
Działania w systemach wagowych
Systemy wagowe (weighted)
" reprezentacja warto ci zbiór par (liczba, waga), wiele reprezentacji
" zb dny (a wi c nieu ywany) symbol zera
skomplikowane algorytmy działa :
1q 6st 2lb 7oz 8 yd
+ 9st 9oz 9 in
2q 1st 3lb 2ź sqft
M C M X L V I I I C M X L I
M D C C X I V C D I V
?? M M M D C L X I I !? M C C C X L V
WNIOSEK:
Wagi warto uporz dkowa a zapis unormowa .
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL II
Systemy liczenia
Systemy pozycyjne
Systemy pozycyjne (positional, place-value)
" wagi uporz dkowane i przypisane pozycjom niezb dny symbol zero
" z ka d pozycj (wag ) skojarzona cyfra (mno nik wagi)
" reprezentacja liczby wektor warto ci, zwanych te cyframi (ang. digit)
Systemy z ustalon podstaw (radix-based)
" stałobazowe (fixed-radix) waga pozycji = pot ga podstawy (radix)
naturalne
negabazowe (negative radix) ujemna podstawa (baza)
z cyfr znakowan (signed digit, SD) cyfry ujemne
" uzupełnieniowe (radix-complement) ujemna waga pozycji najwy szej
Systemy z mieszanymi podstawami (mixed-radix) waga = iloczyn pot g baz
system aramejski dwunastkowo-pi tkowy (Mezopotamia, Babilon)
system rzymski regularne wagi przypisane znakom (a nie pozycjom):
(I=2050, V=2051, X=2151, L=2152, C=2252, D=2253, M=2353,...)
System resztowy (residue number system, RNS) liczba=: wektor reszt
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL III
Systemy liczenia
Systemy stałobazowe (pozycyjne)
System stałobazowy )#,D*# (fixed-radix), popularnie zwany pozycyjnym:
" ustalona podstawa (baza) zwykle liczba całkowita taka, e ||e"2
" dla ka dej pozycji okre lone:
i
o reguła tworzenia wag W = {wk -1,..., w1, w0 ,..., w-m}, wi =
i i
o zbiór dozwolonych cyfr Di = {di ,...,d1,d0 = 0}, xi"Di (zawiera zero)
p-1
Warto ci X liczby o reprezentacji X = {xk-1,..., x1, x0,..., x-m} , xi " Di , jest:
i=k-1
k -1 -1 -m i
X = xk-1 + ...+ x1 + x0 + x-1 ...+ x-m =
"x
i
i=-m
-m
" dokładno bezwzgl dna = waga najmniej znacz cej pozycji ulp =
" standardowy zbiór cyfr D = {0,1,..., -1}, " (e"2)
" redundantny zbiór cyfr ||D+||>
D+ = {0,d1 =1+ a1 ,d2 = 2 + a2 ,...,d -1 = -1+ a -1 ,d ,d +1,...}
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL IV
Systemy liczenia
Popularne systemy pozycyjne
naturalny )#,D*#, e"2,
" standardowy zbiór cyfr D = {0,1,..., -1}
z cyfr znakowan (signed digit, SD) )#,D*#, reprezentacja liczb ujemnych
" zbiór cyfr: D={dp 1,...,d1,d0=0; pe", |di|<},
dozwolone s ujemne warto ci cyfr, np. D={& , 2, 1, 0, 1, 2, & }
" nieredundantny De = {0,d1,...,d -1}, di a" i mod
Np: =10, D={0,1,8,3,4,5,4,7,2,1} (d=-d): 2=18, 56=144, 63=143
negabazowy )#,D*#, -e"2, reprezentacja liczb ujemnych
" standardowy zbiór cyfr: D = {0,1,..., -1}
" (du a asymetria), specyficzna arytmetyka
uzupełnieniowy (radix-complement) )#,D/DH*#
" niestandardowy i nieredundantny zbiór cyfr na pozycji najwy szej,
DH={ ą, ą+1,& ,0,1,& ,( 1 ą)}, 2ą=
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL V
Systemy liczenia
Reprezentacje systematyczne liczb
Reprezentacje stałoprzecinkowe
stałobazowe (i uzupełnieniowe) ustalone poło enie przecinka pozycyjnego
327145,12310 , 0,000000000003145910 , 327145,1238 , 010111010112
Reprezentacje zmiennoprzecinkowe zło enie pól
" znak liczby (sign),
" znacznik (significand) (cz ułamkowa (fraction), mantysa (mantissa)),
" wykładnik (exponent) pot gi bazy (radix) (podstawy)
o podstawa (baza) domniemana (stała dla systemu).
+3,27145123 E5 (=3,2714512310105), -31415,91010 4, 1,01001221011
Reprezentacje resztowe (residue number system, RNS)
" reprezentacja liczby wektor reszt wzgl dem stałych bazy RNS
" tylko liczby całkowite
56{2 , 3, 5, 7}={56mod2,56mod3,56mod5,56mod7}={0,2,1,0}
Reprezentacje logarytmiczne znak + logarytm warto ci bezwzgl dnej
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL VI
Systemy liczenia
Dodawanie i odejmowanie w systemach stałobazowych
X = {xk -1,..., x1, x0,..., x-m} , Y = {yk -1,..., y1, y0,..., y-m} , xi, yi " Di
Ó! (si " Di)
X ą Y = {sk -1,...,s1, s0,...,s-m} ! {sk -1,...,s1,s0,...,s-m} = X ą Y
Rekurencyjna reguła wyznaczania cyfr sumy lub ró nicy
istnieje tylko wtedy, gdy istnieje ogólne rozwi zanie równania:
xi ą yi ą ci = ą ci+ + si, xi yi si "Di
" standardowy zbiór cyfr: Di=D={0,1,& ,-1} rozwi zaniem jest:
xi ą yi ą ci xi ą yi ą ci < ci+ =
ńł
si =
łx ą yi ą ci m
xi ą yi ą ci e" ci+ =
ół i
" niestandardowy zbiór cyfr D={0,d1,d2,& ,d - 1,& ; dimod=i}
si = xi ą yi ą ci m k
, k mod "D
ci+ = k
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL VII
Systemy liczenia
Jednoznaczno reprezentacji stałobazowej
TWIERDZENIE
Reprezentacja liczby w standardowym systemie stałobazowym jest unikatowa.
D o w ó d . Niech X = {0,...,0, xj,..., x1, x0,..., x-m | xj `" 0} . Jako, e xj `" 0, wi c
j
j +1 -m
Xmax - Xmin < Pj - N = Z d" - .
j j j j
Z kolei, warto dowolnej liczby X (xj +1 e" 1) mo na obliczy jako
j +1
j +1
X = Xsd" j + xj +1j +1 .
j +1
j +! j+!
Poniewa |j+1|=1, zatem 0 < X - Xsd" j = xj +1j +1 d" . Skoro jednak
j +1
rozpi to zakresu liczb Xs< j nie przekracza j+1, zatem X `" Xsd" j .
j +1
Wynika st d dalej, e x1 `" x2 ! X1j `" X2, bo wówczas albo
j j j
2
X1j - X2 = {x1 - x2, x1-1,..., x1 } -{0, x2-1,..., x-m} gdy x1 > x2
j j j j -m j j j
2
albo X1j - X2 = {0, x1-1,..., x1 } -{x2 - x1, x2-1,..., x-m} gdy x1 < x2
j j -m j j j j j
1
Gdy za "s < i d" j : xi = xi2, to X1j - X2 = X1 - X2 , co dowodzi tezy.
j s s
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SL VIII
Działania
Dodawanie i odejmowanie w systemach naturalnych
W standardowym systemie naturalnym (i=1) równaniem dodawania jest
xi ą yi ą ci = ąci+1 + si
przy tym xi, yi,si "{0,1,..., -1} ! (ci "{0,1} ! ci+1 "{0,1}) oraz
{0, xi ą yi ą ci} 0 d" xi ą yi ą ci d"
gdy
ńł
{ci+1, si} =
ł{1, xi ą yi ą ci m } gdy 0 d" xi ą yi ą ci m d"
ół
xk 1 xk 2 & x m+3 x m+2 x m+1 x m
yk 1 yk 2 & y m+3 y m+2 y m+1 y m
ą
c m+1 s m
c m+2 s m+1
c m+3 s m+2
s m+3
ck 2 &
ck 1 sk 2
ck sk 1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ I
Działania
Dodawanie wieloargumentowe w systemach naturalnych (1)
" dodawanie jest przemienne i ł czne, wi c:
n-1 n-1 n-1 n-1
i i i i
X + Y + Z + ... = yi +
"x + " "z + ... = "(x + yi + zi...)
i i i
i=0 i=0 i=0 i=0
" ka da suma warto ci cyfr na ka dej pozycji i mo e by zapisana jako
liczba wielocyfrowa o wadze takiej jak waga pozycji (i):
2
xi + yi +...+ zi = ...+ ri+2 + vi+1 + ui
przy tym xi, yi,..., zi,ui,vi+1,ri+2 "{0,1,..., -1}
" je li suma oryginalna X+Y+Z+... ma m składników, to suma:
n+... n-1 n n+1
i i i i
X + Y + Z... =
"(u + vi + ri...) = "u +"v +"r + ... = U + R +V...
i i i i
i=0 i=0 i=1 i=2
ma około 1+log m składników, czyli znacznie mniej ni X+Y+Z+..
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ II
Działania
Dodawanie wieloargumentowe w systemach naturalnych (2)
2
xi + yi + ...+ zi = ...+ ri+2 + vi+1 + ui
przy tym xi, yi,..., zi,ui,vi+1,ri+2 "{0,1,..., -1}
Je li liczba składników jest d"+1, suma jest dwucyfrowa:
{vi+1,ui} = {k, xi + yi + ...+ zi - k} gdy 0 d" xi + yi +...+ zi - k < ,
dodawanie mo na wykona dwuetapowo:
" niezale nie obliczy sum na ka dej pozycji
" doda otrzymane liczby dwucyfrowe
xk 1 xk 2 xk 3 & x m+3 x m+2 x m+1 x m
yk 1 yk 2 yk 3 & y m+3 y m+2 y m+1 y m
& & & & & & & &
zk 1 zk 2 zk 3 & z m+3 z m+2 z m+1 z m
ą
uk 1 uk 2 uk 3 & u m+3 u m+2 u m+1 u m
vk vk 1 vk 2 & v m+4 v m+3 v m+2 v m+1
sk sk 1 sk 2 & & s m+3 s m+2 s m+1 s m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ III
Działania
Sekwencyjny algorytm mno enia w systemie naturalnym
Mno na (multiplicand) A =|{as-1,...,a- p+1,a- p} |,
Mno nik (multiplier) X =|{xk-1,..., x-m+1, x-m} |,
k-1 k-1
ł
i i
A" X = A"ł xi =
ł ł
" " (xi A)
łi=-m łł i=-m
algorytm pisemny dodawanie skalowanych iloczynów cz ciowych (S-m = 0)
i
Si+1 = Si + (xi A) , i=-m, -m+1,...,k-1
algorytm dodaj-przesu (add-and-shift) skalowanie sum cz ciowych
-i
Pi = Si
-1
Pi+1 = (Pi + xi A)
k -1
k i
Pk = P-m + A{
"x } = A" X
i
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ IV
Działania
Konstrukcja tabliczki mno enia w systemach naturalnych (1)
" dla 1d"kd"-1 cyframi iloczynu k"(-1) s k-1 i k (suma równa 1):
0
k( -1) = (k -1) + ( - k) = (k -1)1 + ( - k)
" iloczyn jest przemienny (a*b=b*a) wystarczy wypełni od przek tnej
" odległo ci liczb w rz dach i kolumnach s stałe
" przek tna: x2=(x 1)(x+1)+1 (np. 32=(3 1)*(3+1)+1=4*2+1
+2 +3 +4 +5 &
2 3 4 5 & -2 -1
+2 2 !
4 6 8 &
2 1(-2)
+3 3 !
6 9 3*4 5*3 &
3 2(-3)
+4 4 !
8 4*3 5*3+1 &
4 3(-4)
6*4+1
+5 6*4+1
5 5*3 6*4+1 & & 5 !
&
& & & & &
& &
&
(-4)4 (-3)2
-2
&
1(-2) 2(-3) 3(-4) 4(-5) (-3)2 (-2)1
-1
&
ę! 2 ę! 3 ę! 4 ę! 5 suma cyfr -1
WNIOSEK: wi kszo oblicze mo na wykona bez przeniesie &
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ V
Działania
Konstrukcja tabliczki mno enia w systemach naturalnych (2)
" odległo ci przek tnych te s stałe
" przek tne styczne wierzchołkami odliczane od przek tnej głównej
te mo na wypełnia niemal automatycznie, bo (n2=1+3+5+...+2n-1)
x2=(x 2)(x+2)+4=(x 2)(x+2)+1+3 (np. 42=(4 2)*(4+2)+4=6*2+4)
x2=(x 3)(x+3)+9=(x 3)(x+3)+1+3+5 (np. 52=(4 2)*(4+2)+4=6*2+4)
a2-1 ...-1-3
a2
...-1
...
a2-1 x2-1
-
-
-
x2
...-1
...-
...-
...-
...-1- x2-1
...- - -
...- -3 -
...- - -
& - -
& -1
x2-4 -
- -
-
x2-9 -3
- -
- -
- -
-5
-
-
-
" pozostałe przek tne s odległe od siebie kolejno o 2, o 4, o 6 itd.
x (x 1) =(x+1)(x 2)+2, (np. 5*4=6*3+2)
x (x 1) =(x+2)(x 3)+2+4, ... (np. 5*4=7*2+2+4)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ VI
Działania
Tabliczki mno enia w systemach naturalnych
5 6 7
2 3 4 2 3 4 5 2 3 4 5 6
4 4 4
2 2 2
11 14 10 13 6 12
3 3 3
13 22 31 12 20 24 11 15 22
4 4 4
14 23 32 41 13 21 26 34
5 5
15 24 33 42 51
6
9 11
2 3 4 5 6 7 8 2 3 4 5 6 7 8 9 A
4 4
2 2
6 10 6 9
3 3
8 13 17 8 11 15
4 4
11 16 22 27 A 14 19 23
5 5
13 20 26 33 40 11 17 22 28 33
6 6
15 23 31 38 46 54 13 1A 26 32 39 45
7 7
17 26 35 44 53 62 71 15 22 2A 37 44 51 59
8 8
17 25 33 41 4A 58 66 74
9
19 28 37 46 55 64 73 82 91
A
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ VII
Działania
Dzielenie całkowite
X, D, Q, R liczby całkowite
X dzielna (dividend), D`"0 dzielnik (divisor)
X=Q"D+R, |R|<|D|
Q iloraz (quotient), R reszta (remainder) z dzielenia X przez D
Równanie dzielenia mo e mie 2 rozwi zania spełniaj ce warunek |R|<|D|
|R1 R2|=|D|, 0<-R1,R2<|D|
X Ri=Qi"D
dzielenie znakowane (signed division) znak reszty jest taki jak znak dzielnej
dzielenie modularne (modulus division) znak reszty jest zawsze dodatni
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ VIII
Działania
Dzielenie sekwencyjne
W systemie pozycyjnym o danej podstawie
dzieln i dzielnik mo na łatwo skalowa przez pot gi podstawy,
ergo
iloraz mo na obliczy z dowoln dokładno ci p.
Je li X = {xk -1,..., x1, x0,..., x-m} oraz D = {dl-1,...,d1,d0,...,d-s} ,
to obliczony z dokładno ci p iloraz X/D jest równy:
k -l+1
i
Q = {qk -l+1,qk -l ,...,q0,...q- p} =
"q
i
i=- p
przy tym reszta jest nie wi ksza ni D* p.
Algorytm oblicze jest iteracyjny
na podstawie ju obliczonego przybli enia z dokładno ci s
obliczamy przybli enie z dokładno ci (s+1)
(kolejn cyfr ilorazu)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ IX
Działania
Przybli enia ilorazu
s
Pierwszym przybli eniem ilorazu jest {qs,0,...,0} = Qs,1 = qs takie, e
s s
qs D d" X < (qs +1) D ,
s s
0 d" R1 = X - qs D < D
s-1
Dokładniejsze przybli enie to {qs,qs-1,...,0} = Qs,2 = Qs,1 + qs-1 takie, e
s-1 s-1
qs-1 D d" R1 = X - Qs,1D < (qs-1 +1) D,
s-1 s-1
0 d" R2 = R1 - qs-1 D < D
s-i
Kolejnymi przybli eniami ilorazu s zatem Qs,i+1 = Qs,i + qs-i takie, e
s-i s-i
qs-i D d" Ri = X - Qs,iD < (qs-i +1) D,
s-i s-i
0 d" Ri+1 = Ri - qs-i D < D
i-s-1
co po skalowaniu (ri = Ri ) prowadzi do nierówno ci parametrycznej
0 d" ri+1 = ri - qs-i D < D
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 DZ X
Konwersja podstawy
Pozycyjne rozwini cie liczby w systemie naturalnym
Jednoznaczn reprezentacj liczby Xe"0 w systemie naturalnym o podstawie
jest rozwi zanie równania
k -1
i
{xk -1,..., x0, x-1,..., x-m} = xi = X , gdzie xi "{0,1,..., -1}
"
i=-m
Metoda tablicowa
1. Obliczamy wszystkie potrzebne dodatnie pot gi podstawy n
ujemnych, aby zapewni wymagan dokładno reprezentacji
problem: warto ci pot g ujemnych s przybli one, np. 0,110=0,(00011)2
2. Obliczamy cyfry metod odejmij i porównaj :
Xn 1=X qn>0 ale X (q+1)n<0, to xn-1=q,
Xn 2=Xn 1 pn 1, &
Bezpo rednie obliczenie
Znamy tabliczk mno enia w systemie ródłowym z zapisem warto ci
w systemie docelowym (na przykład konwersja na system dziesi tny)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 1
Konwersja podstawy
Generowanie reprezentacji pozycyjnej
Dla cz ci całkowitej XI oraz ułamkowej XF liczby X mamy odpowiednio
k -1
i
X = + xk -1)]}
I "x = x0 + {x1 + [x2 + ... (xk -2
i
i=0
-1
i -1 -1 -1 -1
X =
F "x = {x-1 + [x-2 + ...+ (x-m+1 + x-m )...]}
i
i=-m
Regularno wyra e prowadzi do algorytmów generowania reprezentacji:
" uniwersalnych niezale nych od systemu,
" dynamicznych niezale nych od warto ci liczby.
Algorytmy musz uwzgl dnia specyfik arytmetyki systemu pozycyjnego
" ujemn podstaw w systemach negabazowych
" ujemne cyfry w systemach SD
" ujemn wag /cyfry na najwy szej pozycji w systemach uzupełnieniowych
Najprostsze s algorytmy dla reprezentacji naturalnych
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 2
Konwersja podstawy
Konwersja cz ci całkowitej liczby
Amodb reszta z dzielenia A przez b
Adivb iloraz całkowity A przez b
X = I0 = x0 + {x1 + [x2 + (x3 + ... (xk-2 + xk -1)...)]}
I
x0 = I0 mod
I0 div = I1 = x1 + [x2 + (x3 + [x4 +... (xk-2 + xk -1)...])]
x1 = I1 mod
I1 div = I2 = x2 + (x3 + [x4 + (x5 +... (xk-2 + xk-1)...)])
x2 = I2 mod
&
cyframi rozwini cia cz ci całkowitej XI liczby X w systemie o podstawie s :
-1
xj = I mod , I = I div = int I , I0 = XI
j j+1 j j
Je li Ir=0, to xr+1=0, Ir+1=0 itd.
(kolejne cyfry lewostronnego rozwini cia s zerami)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 3
Konwersja podstawy
Algorytm konwersji cz ci całkowitej liczby
Procedura (na podstawie rozwini cia Hornera)
1. Podziel liczb przez podstaw systemu docelowego
2. Otrzymana reszta jest kolejn cyfr rozwini cia pozycyjnego
3. Otrzymany iloraz ponownie poddaj procedurze
4. Powtarzaj dopóki nie uzyskasz ilorazu równego 0
Algorytm wyznaczania reprezentacji cz ci całkowitej (A naturalne)
0. X(0)=A ; podstaw warto ci pocz tkowe
i=0
1. X(i+1)=int(X(i)/) ; iloraz całkowity
2. xi=X(i) X(i+1) ; reszta
3. i++ ; zwi ksz i
4. if X(i+1)`"0 goto 1 ; powtarzaj dopóki iloraz`"0
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 4
Konwersja podstawy
Konwersja cz ci ułamkowej liczby
intA cz całkowita liczby A
-1 -1 -1 -1 -1
X = F1 = {x-1 + [x-2 + (x-3 + ...+ (x-m+1 + x-m)...)]}
F
x-1 = int F1
-1 -1 -1 -1 -1
F1 - x-1 = F2 = [x-2 + (x-3 + [x-4 +...+ (x-m+1 + x-m)...])]}
x-2 = int F2
-1 -1 -1 -1 -1
F2 - x-2 = F3 = (x-3 + [x-4 + (x-5 + ...+ (x-m+1 + x-m)...)])
x-3 = int F3
cyframi rozwini cia cz ci ułamkowej XF liczby X w systemie o podstawie s
x- j = int Fj , Fj+1 = Fj - x- j < 1 , F1 = X < 1
F
Je li Fr=0, to x (r+1)=0, Fr+1=0 itd.
(kolejne cyfry prawostronnego rozwini cia s zerami)
Je li Fr=Fr k to rozwini cie jest okresowe (okres ma k cyfr)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 5
Konwersja podstawy
Algorytm konwersji cz ci ułamkowej liczby
Procedura (na podstawie rozwini cia rekurencyjnego)
1. Pomnó ułamek przez podstaw systemu docelowego
2. Cz całkowita iloczynu kolejn cyfr rozwini cia pozycyjnego
3. Cz ułamkow iloczynu ponownie poddaj procedurze
4. Powtarzaj tak długo a :
a) uzyskasz wymagan dokładno m (odpowiedni liczb cyfr),
b) otrzymasz iloczyn równy 0,
c) wykryjesz okresowo (pojawi si taki sam ułamek jak wcze niej).
Reprezentacja cz ci ułamkowej (A<1) z dokładno ci m
0. X(0)=A, x0=0 ; podstaw warto ci pocz tkowe
i=0
1. x i=int(X(i)) ; cz całkowita iloczynu
2. X(i+1)=X(i) x i ; cz ułamkowa iloczynu
3. i++ ; zwi ksz i
4. if id"m goto 1 ; powtarzaj dopóki mała dokładno
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 6
Konwersja podstawy
Konwersja podstawy w systemach naturalnych
" działania wykonywane s w systemie ródłowym (o podstawie )
" je li podstawa systemu docelowego jest wi ksza od podstawy systemu
ródłowego, to nale y wykonywa mno enie lub dzielenie przez warto
podstawy zakodowan w systemie ródłowym =|{bp,& ,b1,b0}|
" wyniki {zs 1,zs 1,& ,z r} w systemie o podstawie (s d" k log )
Konwersja ułamka okresowego
Zamiana ułamka okresowego na ułamek wymierny
-c -c
ł ł ł ł
1 z 1 z
0, x-1...x-k (z-k -1...z-k -c ) = ł x + ł = ł x + ł
k -c k c
ł ł ł
1- -1ł
ł łł ł łł
x=k|{x-1,& , x-k}| , z=c|{z-k-1,& , z-k-m}|
k liczba pozycji cz ci nieokresowej ułamka, c liczba pozycji okresu
Ułamek sko czony w bazie danej mo e by okresowy w bazie docelowej
za wynikiem konwersji ułamka okresowego mo e by ułamek sko czony.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 7
Konwersja podstawy
Konwersja ułamka wymiernego w systemach naturalnych
Uwaga
Wynikiem konwersji ułamka wymiernego jest ułamek sko czony lub okresowy
WAA CIWO konwersji ułamka
Je li ka dy dzielnik podstawy ródłowej jest dzielnikiem podstawy docelowej
, to wynikiem konwersji ułamka sko czonego jest ułamek sko czony
i=-1 i=-1
i
["p " P : NWD( p,) = p ! NWD( p, ) = p] ! "r < " :
"x i = "z
i i
i=-m i=-r
D o w ó d . Je li F jest ułamkiem sko czonym m-pozycyjnym w bazie , to
-1 m-1
F =
"x i = -m"x i = A-m, 0 d" A d" m -1, A" N .
i i-m
i=-m i=0
F ma sko czone rozwini cie tak e w bazie , je eli istnieje B"N i r< " takie,
-r r
e F = B , 0 d" B d" -1. Załó my, e NWD(p,)=1. Ale wówczas byłoby
r
A = Bm & NWD( p, ) = 1& NWD( p,) = p ! NWD( pm, A) = pm ,
wi c rozwini cie F byłoby niesko czone, chyba e A=kpm.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 8
Konwersja podstawy
Konwersja podstawy skojarzonej w systemach naturalnych przykłady
2345671,3215... = 2"106 + 34"104 + 56"102 + 71"100 + 32"10-2 +15"10-4... =
= 2"1003 + 34"1002 + 56"1001 + 71"1000 + 32"100-1 +15"100-2...
11 100 111, 011 1012 =112 " 26 +1002 " 23 +1112 " 20 + 0112 " 2-3 +1012 " 2-6 =
= 38 "82 + 48 "81 + 78 "80 + 38 "8-1 + 58 "8-2 = 347,358
2347,358 = 2"83 + 3"82 + 4"81 + 7 "80 + 3"8-1 + 5"8-2 =
= 0102 " 29 + 0112 " 26 +1002 " 23 +1112 " 20 + 0112 " 2-3 +1012 " 2-6 =
= 010 011 100 111, 011 1012 = 0100 1110 0111, 0111 01002 =
= 01002 " 28 +11102 " 24 + 01112 " 20 + 01112 " 2-4 + 01002 " 2-8 = 4E7,7416
Przykład (...)10(...)8(...)2 (83=512, 82=64, 8 1=0,125, 8 2=0,16625)
1
1937,0312510 = 3"512 + 3"64 + 2"8 +1+ 2" = 3"83 + 3"82 + 2"81 +1"80 + 2"8-2 =
64
= 3321,028 = 011 011 010 001, 000 0102
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 9
Konwersja podstawy
Konwersja podstawy skojarzonej w systemach naturalnych
5 4 2 2 1 0 -1 -2
X = ... + x5 + x4 + x3 + x2 + x1 + x0 + x-1 + x-2 ... =
4 2 0 -2
= ...(x5 + x4) + (x3 + x2) + (x1 + x0) + (x-1 + x-2) + ... =
2 3 2 0 2 -3
= ...(x5 + x4 + x3) + (x2 + x1 + x0) + (x-1 + x-2 + x-3) + ...
a zatem:
k -1 t-1 t-1
i s-1 s j s j
"x = "(x +...+ x + xjs )( ) = "z ( )
i js+s-1 js+1 j
i=-m j=-r j=-r
czyli {xk -1,..., x1, x0,..., x-m} = {zt-1,..., z1, z0,..., z-r}
s
s-1 s
gdzie z = xjs+s-1 + ...+ xjs+1 + xjs "{0,1,..., -1} warto cyfry w (..) ę! s
j
Zło enie konwersji (..) ę! k (..) ę! s
ę! ę!
ę! ę!
ę! ę!
(..) ę! k (..) ę! s ! (..) ę! k (..) || (..) (..) ę! s
< s ! zamiast konwersji (..)(..) wygodniej realizowa (..)(..) ę! s
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 10
Konwersja podstawy
Konwersja podstawy w systemach naturalnych przykłady
157,38610X8Z2 oraz 157,38610X9Z3 (8=23 9=32).
Ii mod 23 23 Fi Ii mod 32 32 Fi
157 0 386 157 0 386
19 =x0 x-1 = 088 17 =x0 x-1 = 474
5 3 4 3
2 =x1 x-2 = 704 1 =x1 x-2 = 266
3 0 8 4
0 =x2 x-3 = 632 0 =x2 x-3 = 394
2 5 1 2
157,38610 = 235,305...8 = 10011101,011000101...2
157,38610 = 184,3429 = 12211,101102...3.
235,3058X10 oraz 235,3058X9Z3 (działania w systemie ósemkowym)
Ii mod 128 128 Fi Ii mod 118 3 Fi
2358 0 3058 2358 0 3058
178 =x0 x-1 = 6628 218 =x0 x-1 = 3558
7 3 4 3
1 =x1 x-2 = 3648 1 =x1 x-2 = 1258
5 108 8 4
0 =x2 x-3 = 6108 0 =x2 x-3 = 3758
1 4 1 1
235,3058 =157,384...10 = 184,341...9 = 12211,101101...3.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 11
Konwersja podstawy
Konwersja ułamka wymiernego na system pozycyjny
" konwersja licznika i mianownika na system docelowy i dzielenie
" zgodnie z algorytmem:
o mno enie przez podstaw systemu docelowego
o odcinanie cz ci całkowitej uzyskanego iloczynu
548
X10
618
x0 =0 0 128=1010
608 6708
+ =
x 1=8 =108
618 618
478 7408
+ =
x 2=9 =118
618 618
578 6068
+ = &
x 3=7 =78
618 618
0,110=0,00011001100110011& 2=0,0(0011)2
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 12
Konwersja podstawy
Konwersja ułamków okresowych w systemach naturalnych
" zamiana na ułamek wymierny
" u ycie rozwini cia niesko czonego korekcja skróconego rozwini cia
" automatyczna korekcja okresu podczas mno enia
ułamek wymierny rozwini cie niesko czone
tylko 0,(xy...z)
53210
= X8
0,5(37)10
0,5(37)10X8 0,(386)10X7
99010
8 8 8 Fi 7 Fi
0 0 5 37 37 37 & 0 (386)
29610 425610 x 1= 2 98 98 96 x 1= (702)
4 2
=
x 1= +
4
2 98 98 98 (704)
99010 99010
38810 236810 x 2= 3 91 91 84 x 2= (928)
2 4
=
x 2= +
2
3 91 91 91 (932)
99010 99010
13410 310410 x 3= 1 35 35 28 x 3= (524)
3 6
=
x 3= +
3
1 35 35 35 (530)
99010 99010
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 13
Konwersja podstawy
Konwersja podstawy w systemach stałobazowych
Ka da liczba w systemie stałobazowym ma rozwini cie pozycyjne,
wi c mo e by te rozwini ta wg schematu Hornera
WNIOSEK
Algorytmy konwersji dla systemu naturalnego mo na stosowa tak e
w dowolnym systemie stałobazowym.
Problem: arytmetyka musi by odpowiednia do wła ciwo ci systemu
Przykład:
157,38610(..)SD-8. (D={4, 3, 2, 1, 0, 1, 2, 3}
Ii Ii mod 8 8 Fi(!<500) 8 Fi
157 0 386 0 386
19 5 3 =x0 x-1 = 088 x-1 = 3 088
3
20
3 =x1 x-2 = 704 !! x-2 = 1 296
4 0
0 =x2 x-3 = 5 x-3 = 2 368
3
632 ę!
x-4 = 3 056
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 KP 14
Liczby ujemne
Reprezentacja znak-moduł
pseudonaturalna +32,317, 214,554, ...
X = {s}||{xk -1,..., x1, x0,..., x-m}
k -1
i
X = (-1)s xi , xi "{0,1,..., -1}, s "{0,1}
"
i=-m
" dwie reprezentacje zera : +0 i -0
" na ograniczonej liczbie pozycji zakres liczb jest symetryczny
" problem w dodawaniu i odejmowaniu
o efektywne działanie zale y od znaków
ż komplikacja algorytmu i dłu szy czas wykonania
ż bardziej skomplikowany układ
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 1
Liczby ujemne
System negabazowy
(z baz ujemn ) wi = (- )i , e"2
k -1
X = {xk -1, xk -2,..., x0, x-1,..., x-m}- =
"x (- )i, xi "{0,1,..., -1}
i
i=-m
" znaczna asymetria (dodatnia je li k nieparzyste, ujemna gdy k parzyste)
-1
-m k
Q = [(- ) - (- ) ]
+1
" znak liczby okre la indeks najbardziej znacz cej pozycji niezerowej k
" zmiana znaku wykonalna tylko dla około 2/(+1) liczb
" skomplikowany algorytm i układ
o aby unikn odejmowania przeniesienia
xi ą yi ą ci = ą(- )ci+1 + si
wytwarzane s dwa przeniesienia: ci,i+1 = ( -1)ci+1 oraz ci,i+2 = ci+1
ci,i+1 = ci+1, co daje ci,i+1 - ci,i+2 = ( -1)ci+1 - ci+1 = -ci+1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 2
Liczby ujemne
Reprezentacja nadmiarowa system ze znakowan cyfr (SD)
System stałobazowy (pozycyjny) )#,1,D*#
1
1
1
" zbiór cyfr D = {a,...,1,0,1,...,a -1,a}, a d" -1 d" 2a, d = -d
n-1
i
|XSD | =
"x , xi "{a,...,1,0,1,...,a -1,a}, a d" -1 d" 2a
i
i=-m
- {xk -1, xk -2,..., x-m}SD = {-xk -1,-xk -2,...,-x-m}SD
XSD = X+- X-:
0, gdy xi < 0,
ńł
+ + +
X+ = {0, xk -1,..., x-m+1, x-m} , xi+ =
ł x , gdy xi e" 0,
ół i
0, gdy xi e" 0,
ńł
- - -
X- = {0, xk -1,..., x-m+1, x-m} , xi- =
ł- xi, gdy xi < 0.
ół
X+ - X- wykonalne w systemie SD, jak i w systemie uzupełnieniowym
Konwersja odwrotna mo e by niejednoznaczna wiele reprezentacji liczby.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 3
Liczby ujemne
Reprezentacja minimalna w dwójkowym systemie SD
reprezentacja minimalna Z ={zk -1,.., z-m+1, z-m} zawieraj ca najwi cej zer
[ (z = 1) (" (z = 1)]'"[ (zi zi-1 = 0)]
" " j " j "
sd"k -1 s< jd"k -1 s< jd"k -1 -m+1d"id"s-1
DOWÓD (dla dwójkowego systemu SD):
" ci g zawieraj cy izolowan cyfr 1 lub 1 nie daje si minimalizowa
" izolowany ci g 1 lub 1 (...,0, x,..., x,0,...) jest równowa ny (..., x,0,..., x,0,...)
" {..., x,b,b , z,...} = {..., x,0,b, z,...}, b = 1,1
" nie da si przekodowa ci gu cyfr 1 lub 1 na najwy szych pozycjach.
reprezentacja kanoniczna minimalna z wykluczeniem s siaduj cych nie-zer
Jest k reprezentacji liczby 1 oraz k reprezentacji liczby +1
1 = {0,0,& ,0, 1}={0,0,& , 1,1}=& ={ 1,1,& ,1,1}
" liczb reprezentowanych jest 2"2k, ró nych reprezentacji jest 3k
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 4
Liczby ujemne
Dwójkowa reprezentacja uzupełnieniowa intuicja
& rozszerzenie
0 ... 0 0 0 0 1 0 0 0 0 0 0 0 0
0 ... 0 0 0 0 0 1 1 1 1 1 1 1 1 +28 1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
0 ... 0 0 0 0 0 1 0 0 0 0 0 0 1 +27+1
0 ... 0 0 0 0 0 1 0 0 0 0 0 0 0 +27
0 ... 0 0 0 0 0 0 1 1 1 1 1 1 1 +27 1
0 ... 0 0 0 0 0 0 1 1 1 1 1 1 0 +27 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
0 ... 0 0 0 0 0 0 0 0 0 0 0 1 0 +2
0 ... 0 0 0 0 0 0 0 0 0 0 0 0 1 +1
0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 ... 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 ... 1 1 1 1 1 1 1 1 1 1 1 1 0 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1 ... 1 1 1 1 1 1 0 0 0 0 0 1 0 27+2
1 ... 1 1 1 1 1 1 0 0 0 0 0 0 1 27+1
1 ... 1 1 1 1 1 1 0 0 0 0 0 0 0 27
1 ... 1 1 1 1 1 0 1 1 1 1 1 1 1 27 1
1 ... 1 1 1 1 1 0 1 1 1 1 1 1 0 27 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1 ... 1 1 1 1 1 0 0 0 0 0 0 0 0 28
1 ... 1 1 1 1 0 1 1 1 1 1 1 1 1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 5
Liczby ujemne
Dziesi tna reprezentacja uzupełnieniowa intuicja
& rozszerzenie
0 ... 0 0 0 0 5 0 0 0 0 0 0 0
0 ... 0 0 0 0 4 9 9 9 9 9 9 9
+5"107 1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
0 ... 0 0 0 0 0 5 0 0 0 0 0 9
+5"106+2
0 ... 0 0 0 0 0 5 0 0 0 0 0 0
+5"106+1
0 ... 0 0 0 0 0 4 9 9 9 9 9 9
+5"106 1
0 ... 0 0 0 0 0 4 9 9 9 9 9 0
+5"106 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
0 ... 0 0 0 0 0 0 0 0 0 0 0 2 +2
0 ... 0 0 0 0 0 0 0 0 0 0 0 1 +1
0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0
9 ... 9 9 9 9 9 9 9 9 9 9 9 9 1
9 ... 9 9 9 9 9 9 9 9 9 9 9 8 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
9 ... 9 9 9 9 9 5 0 0 0 0 0 2
5"106+2
9 ... 9 9 9 9 9 5 0 0 0 0 0 1
5"106+1
9 ... 9 9 9 9 9 5 0 0 0 0 0 0
5"106
9 ... 9 9 9 9 9 4 9 9 9 9 9 9
5"106 1
9 ... 9 9 9 9 9 4 9 9 9 9 9 8
5"106 2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
9 ... 9 9 9 9 5 0 0 0 0 0 0 0
5"107
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 6
Liczby ujemne
Reprezentacja uzupełnieniowa
Jednolita formuła na obliczenie warto ci liczby
k-1
k i
|XU | = -(xk -1) +
"x ,
i
i=-m
1
gdzie (xk -1) = (1+ sgn(2xk -1- +1)) funkcja znaku liczby
2
Rozszerzenie niesko czone (arytmetyczne)
? {xk-1,..., x1, x0,..., x-m}U = {..., xk , xk-1,..., x1, x0,..., x-m,.x-m-1,.., x- p}U
intuicje
325,17U10 (+325,1710) 0..0325,17U10 325,1U8 (+325,18) 0..0325,10U8
674,83U10 ( 325,1710) 9..9674,83U10 452,7U8 ( 325,18) 7..7452,70U8
Je li wi c xe = (xk -1)( -1), to (zauwa , e (xe)( -1) = xe)
Xe = {..., xe, xk-1,..., x-m+1, x-m,0,...}
Uwaga: Zauwa my, e poprawne cyfry reprezentacji liczby przeciwnej
otrzymamy przez odejmowanie danej od zera
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 7
Liczby ujemne
Dwójkowa reprezentacja uzupełnieniowa U2
=2 ! xi "{0,1} ! (xk -1) = xk -1 ! (& bit znaku)
System uzupełnieniowy do 2 (2 s complement) (U2)
k-2
X = |{xk-1,..., x1, x0,..., x-m}U2 | = -xk-12k-1 +
U2 "x 2i
i
i=-m
Rozszerzenie niesko czone liczby w kodzie U2
Xe = {..., xk -1, xk -1, xk -2,..., x-m+1, x-m,0,0,...}U2.
Alternatywna interpretacja
k-1
X = |{xk-1,..., x1, x0,..., x-m}U2 | = "{1,0}, xi "{0,1}
U2 "x 2i , xk -1
i
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 8
Liczby ujemne
Reprezentacja spolaryzowana (liczb całkowitych)
przypisanie reprezentacji naturalnej warto ci pomniejszonej o N (obci enie)
k -1
i k
X =|{xk -1,..., x1, x0}+ N | = xi - N, 0 < N < xi "{0,1,..., -1}
"
i=0
reprezentacja z obci eniem N (biased N, excess N, XS-N)
zalety:
" zakres liczb dodatnich i ujemnych jest niesymetryczny
" unikatowa reprezentacja zera
" zgodno uporz dkowania liczb i ich reprezentacji (kodów)
wady:
" konieczno korekcji wyników działa arytmetycznych
" problematyczne u ycie w mno eniu lub dzieleniu
reprezentacja spolaryzowana quasisymetryczna (Q=k 1 2N)
k
1
" z asymetri ujemn N = (Q= 1)
2
k
1
" z asymetri dodatni N = -1 (Q=+1)
2
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 9
Liczby ujemne
Reprezentacja spolaryzowana liczb całkowitych w systemie dwójkowym
N = 2m 1 N = 2m 1-1
2m-1-1 1 1 1 ... 1 1 1 2m-1
2m-1-2 1 1 1 ... 1 1 0 2m-1-1
... ... ... ... ... ... ... ... ...
0 1 0 0 ... 0 0 0 1
-1 0 1 1 ... 1 1 1 0
... ... ... ... ... ... ... ... ...
-2m-1+1 0 0 0 ... 0 0 1 -2m-1+2
-2m-1 0 0 0 ... 0 0 0 -2m-1+1
" porz dek liczb zgodny z porz dkiem kodów
" dodawanie i odejmowanie wymaga korekcji
" łatwa konwersja na kod U2 i odwrotnie
{xm-1, xm-2,..., x1, x0}U2 = {(1- xm-1), xm-2,..., x1, x0}+2ę!m
- {xm-1, xm-2,..., x1, x0}U2 = {xm-1,(1- xm-2),...,(1- x1),(1- x0)}+2ę!m-1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 10
Liczby ujemne
Dwójkowa reprezentacja spolaryzowana i uzupełnieniowa
Gdy N = 2k -1 jest
k -1 k -2
X = xi 2i - 2k -1 = -(1- xk -1)2k -1 + xi 2i ,
" "
+ N
i=0 i=0
! {xk-1, xk-2,..., x0}U2 = {xk-1, xk-2,..., x0}+2ę!(k-1)
k -2
i
Gdy N = 2k -1-1 , to poniewa (2k -1 -1) =
"2 , wi c otrzymamy
i=0
k -1 k -2 k -2
-1
X = xi 2i -(2k -1 -1) = xk -12k -1 +
ł ł
" "(x -1)2i = -ł- xk 2k + "(1- xi )2i ł
+ N i -1
i=0 i=0 ł i=0 łł
! - {xk-1, xk-2,..., x-m}U2 = {xk-1, xk -2,..., x-m}+2ę!(k-1)-1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 11
Liczby ujemne
Bezpo rednia konwersja liczby na system uzupełnieniowy
Poniewa wagi / warto ci wszystkich cyfr reprezentacji uzupełnieniowych
oprócz najwy szej s dodatnie, wi c:
a) konwersja cz ci całkowitej wymaga nast puj cego post powania:
1) kolejne ilorazy maj taki znak jak liczba przetwarzana,
2) warunek stopu: iloraz równy warto ci cyfry rozszerzenia (0 lub 1)
b) konwersja ułamka wła ciwego
zamiana na posta 0+f lub 1+f
konwersja dodatniej cz ci ułamkowej f jak dla liczb dodatnich
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 12
Liczby ujemne
Dopełnienie liczby i liczba przeciwna
Dopełnienie liczby X = {xk -1,..., x1, x0,..., x-m} (digit-complement)
X = {xk -1,..., x1, x0,..., x-m : xi = ( -1) - xi}
X + X = { -1,..., -1} = Q
X = X i Q = 0
Je li jest wykonalne działanie X + Y , to mamy
X - Y = (Q - X) - Y = Q - (X + Y) = X + Y
Odwrotno addytywna liczby X = {xk -1,..., x1, x0,..., x-m} liczba przeciwna
~ ~
~
X = {~k -1,...,~1, x0,...,~-m} ! X + X = 0
x x x
Odwrotno addytywna jest relacj równowa no ci
~ ~ ~
Je li istnieje liczba Q, to X = 0 - X = Q + Q - X = Q + X i wtedy
~
X - Y = X + (Y + Q)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 13
Liczby ujemne
Reprezentacje dziesi tne kodowane dwójkowo
" do binarnego zakodowania jednej z cyfr potrzeba łlog2łł bitów
1
6
" " " " "
1
0
" jest = = mo liwo ci kodowania cyfr 0& 9
" " " "
Kod BCD (Binary Coded Decimal)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0 1 2 3 4 5 6 7 8 9
Kod BCD+3 (Excess-3, XS-3) i jego dopełnienie (~1930)
0 1 2 3 4 5 6 7 8 9
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 0000
9-0 9-1 9-2 9-3 9-4 9-5 9-6 9-7 9-8 9-9
" samodopełnianie negacja bitów cyfry dopełnienie warto ci cyfry
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 INT 14
Systemy komplementarne*
Systemy komplementarne
Dla liczb z ograniczonego zakresu 0d"|X |d"|R|
liczb przeciwn mo e reprezentowa jej uzupełnienie do stałej R
~ ~
X = R - X ! X = - X
~
~ ~ ~
Uzupełnianie jest odwracalne X = X, a poniewa R = 0 ! |R|= 0 wi c tak e
~ ~
X = R - X = 0 - X
Systemy komplementarne (Q = { -1,..., -1, -1}, ulp={0,...,0,1})
" do podstawy (radix-complement), uzupełnieniowe (pełne)
~
Q = R - Q = ulp
o nie istnieje reprezentacja R=Q+ulp
o unikatowa reprezentacja zera: ~ = R nie ma reprezentacji
0
" do cyfry (digit-complement), dopełnieniowe, u.niepełne (diminished r-c.)
~
Q = R - Q = 0, ~ = R - 0 = Q
0
o R=Q dwie reprezentacje zera: 0 oraz Q
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 1
Systemy komplementarne*
Reprezentacja liczby przeciwnej
X = {xk -1,..., x1, x0,..., x-m : xi = ( -1) - xi} = Q - X dopełnienie liczby X
liczb przeciwn (odwrotno addytywn ) je li istnieje reprezentuje kod
~
X = R - X = X + (R - Q)
" w systemie uzupełnieniowym (pełnym) R=Q+ulp, wi c
~
X = R - X = X + ulp
" w systemie dopełnieniowym (niepełnym) R=Q, wi c
~
X = R - X = X
~
W systemie uzupełnieniowym liczba Q = ulp zawsze istnieje, ergo
! ka de odejmowanie mo na zast pi dodawaniem
~ ~
X - Y = X + Y = X + Y + (R - Q) = X + Y + Q
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 2
Systemy komplementarne*
Wła ciwo ci systemów komplementarnych
Reprezentacja liczb dodatnich jak w kreuj cym systemie naturalnym
! Q nie jest miar asymetrii w systemie uzupełnieniowym.
Je eli podstawa systemu jest liczb nieparzyst , to
" w systemach dopełnieniowych musi wyst pi niewielka asymetria
" w systemach uzupełnieniowych zakres liczb mo e by symetryczny
" trudne wykrycie znaku niezb dne testowanie wszystkich pozycji
Je li podstawa systemu jest liczb parzyst , to
" w systemach dopełnieniowych zakres liczb mo e by symetryczny
" w systemach uzupełnieniowych musi wyst pi niewielka asymetria
" mo liwe łatwe wykrycie znaku ( + gdy 2xk -1 < , gdy 2xk -1 e" ),
! w systemach pełnych ujemna asymetria.
! podstawa systemu komplementarnego jest zwykle liczb parzyst
" uzupełnieniowy do podstawy (U2/ 2 s complement, U10/ 10 s compl.)
" dopełnieniowy do cyfr -1 (U1/ 1s complement/ D1)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 3
Systemy komplementarne*
Dodawanie i odejmowanie w systemach uzupełnieniowych
W systemach naturalnych reprezentacj liczby wi kszej (mniejszej) o jednostk
(ulp= m o reprezentacji {0,& ,0,1}) od danej jest wynik pozycyjnego dodania
(odj cia) ulp do (od) tej liczby.
" przeniesienie z pozycji najwy szej wiadczy o niewykonalno ci działania
Brak argumentów przeciw stosowaniu reguły w systemach uzupełnieniowych
(reprezentacj liczby przeciwnej jest 0 X}
" dodawanie i odejmowanie jednostki mo na wykona zgodnie z reguł
(i) xi ą yi ą ci = si ą ci+1,
" dodanie jednostki m do liczby najwi kszej ujemnej { -1,..., -1, -1}
o warto ci m , zgodnie z reguł (i) daje w wyniku poprawne 0
" odj cie jednostki m od 0, zgodnie z reguł (i) daje { -1,..., -1, -1}
" problem wykonalno ci działania
o jednopozycyjne rozszerzenie zakresu zapewnia poprawno wyniku
ka dego dodawania lub odejmowania wykonanego zgodnie z reguł (i)
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 4
Systemy komplementarne*
Reprezentacja uzupełnieniowa w systemie pełnym i niepełnym
podstawa parzysta
U2 D1/U1
k m k m
1 1
1
/2 -
/2 1 1 1 ... 1 1 1 /2 -
k m k m
1 1
1
/2 -2
/2 1 1 1 ... 1 1 2 /2 -2
& & & & & & & & &
m m
0 0 0 0 0 1
+ ... +
0 0 0 0 0 0 0
... +0
m
- 1 1 1 ... 1 1 1 -0
m m
-2 1 1 1 ... 1 1 2 -
& & & & & & & & &
k m k m
1
0 0 ... 0 0 1 -1/2 +2
-1/2 + /2
k k m
1
0 0 ... 0 0 0 -1/2 +
-1/2 /2
m
k k
R = R = -
k -2
k-1 i
XU e" 0 ! XU = xk-1 +
"x ,
i
i=-m
k -2
k -1 i
XU < 0 ! XU = xk -1 - R + xi
"
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 5
Systemy komplementarne*
Warto liczby w systemie komplementarnym
k-1
i
|XU | = -(xk-1)R +
"x ,
i
i=-m
1
gdzie (xk -1) = (1+ sgn(2xk-1- +1)) funkcja znaku liczby, R=k " m
2
(=0 w systemie uzupełnieniowym lub 1 w dopełnieniowym), sk d
k -1
k i -m
|XU | = -(xk-1) +
"x + (xk-1)
i
i=-m
Rozszerzenie niesko czone (arytmetyczne)
? {xk -1,..., x1, x0,..., x-m} = {xs-1,..., xk , xk -1,..., x1, x0,..., x-m,.x-m-1,.., x- p}
intuicje
325U10 (+32510) 00325,00U10 325U9 (+32510) 00325,00U9
675U10 ( 32510) 99675,00U10 674U9 ( 32510) 99674,99U9
Je li wi c xe = (xk -1)( -1), to (zauwa , e (xe)( -1) = xe)
" system uzupełnieniowy: Xe = {..., xe, xk-1,..., x-m+1, x-m,0,...},
" system dopełnieniowy: Xe = {..., xe, xk-1,..., x-m+1, x-m, xe,...}
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 6
Systemy komplementarne*
Dwójkowe systemy uzupełnieniowe
=2 ! xi "{0,1} ! (xk -1) = xk -1 ! (bit znaku!)
System uzupełnieniowy do 2 (2 s complement) (U2)
k -2
X = |{xk -1,..., x1, x0,..., x-m}U2 | = -xk -12k -1 + xi 2i
"
U2
i=-m
Rozszerzenie niesko czone liczby w kodzie U2
Xe = {..., xk -1, xk -1, xk -2,..., x-m+1, x-m,0,0,...}U2.
System dopełnieniowy do 1 (1 s complement) (D1/U1)
k -2
X = |{xk -1,..., x1, x0,..., x-m}U1 | = -xk -1(2k -1 - 2-m ) + xi 2i
"
U1
i=-m
Rozszerzenie niesko czone liczby w kodzie U1
Xe = {..., xk -1, xk -1, xk -2,..., x-m+1, x-m, xk -1, xk -1,...}U1.
Konwersja U1"!U2: |XU1| |XU2|= xk ulp = xk 2-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 7
Systemy komplementarne*
Kod uzupełnieniowy do 2 (U2) i dopełnieniowy do 1 (niepełny, D1)
U2 D1/U1
0 1 1 ... 1 1 1
+2m-1-1 +2m-1-1
0 1 1 ... 1 1 0
+2m-1-2 +2m-1-2
0 0 0 0 1 0
+2 ...
0 0 0 0 0 1
+1 ... +1
0 0 0 0 0 0 0
... +0
1 1 1 1 1 1
-1 ... -0
1 1 1 1 1 0
-2 ... -1
1 0 0 ... 0 0 1
-2m-1+1 -2m-1+2
1 0 0 ... 0 0 0
-2m-1 -2m-1+1
R =-2m-1 R =-2m-1+1
k -2
|X| = |{xk -1,..., x1, x0,..., x-m}| = -xk -1R +
"x 2i
i
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 8
Systemy komplementarne*
Kod uzupełnieniowy do 10 (U10) i dopełnieniowy do 9 (niepełny, D9/U9)
U10 D9/U9
(0) 4 9 9 & 9 9 9
+5"10k-1-1 +5"10k-1-1
(0) 4 9 9 & 9 9 8
+5"10k-1-2 +5"10k-1-2
& & & & & & & &
(0) 0 0 0 & 0 0 2
+2
(0) 0 0 0 & 0 0 1
+1 +1
0 0 0 0 0 & 0 0 0
+0
(9) 9 9 9 & 9 9 9 -0
-1
(9) 9 9 9 & 9 9 8 -1
-2
& & & & & & & &
(9) 5 0 0 & 0 0 2 -5"10k-1+2
-5"10k-1+1
(9) 5 0 0 & 0 0 1 -5"10k-1+1
-5"10k-1
R =-10k-1 R =-10k-1+1
k -1
i
|X| = |{xk -1,..., x1, x0,..., x-m}| = -(xk -1)R +
"x
i
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 9
Systemy komplementarne*
Kod uzupełnieniowy do 8 (U8) i dopełnieniowy do 7 (niepełny, D7/U7)
U9 D7/U7
(0) 3 7 7 ... 7 7 7
+4"8k-1-1 +4"8k-1-1
(0) 3 7 7 ... 7 7 6
+4"8k-1-2 +4"8k-1-2
& & & & & & & &
(0) 0 0 0 0 0 2
+2 ... +2
(0) 0 0 0 0 0 1
+1 ... +1
0 0 0 0 0 0 0 0
... +0
(7) 7 7 7 ... 7 7 7 -0
-1
(7) 7 7 7 ... 7 7 6 -1
-2
& & & & & & & &
(7) 4 0 0 0 0 2 -4"8k-1+2
-4"8k-1+1 ...
(7) 4 0 0 0 0 1 -4"8k-1+1
-4"8k-1 ...
R =-8k-1 R =-8k-1+1
k -1
i
|X| = |{xk -1,..., x1, x0,..., x-m}| = -(xk -1)R +
"x
i
i=-m
R=k "ulp
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 10
Liczby i wielomiany*
Liczby zespolone (1)
Liczba zespolona para liczb (a,b), której przypisano warto zespolon
|(a,b)|=a+ib, i2=-1
Dodawanie i odejmowanie
[a+ib]ą[a+ib]=[aąc]+i[bąd]
Mno enie
[a+ib]"[c+id]=[ac-bd]+i[ad+bc]
Dzielenie
[a+ib]/[c+id]=[a+ib] [c-id]/[c+id] [c-id]=
={[ac+bd]+i[ad+bc]}/[c2+d2]
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 1
Liczby i wielomiany*
Liczby zespolone (2)
Posta wykładnicza
ł a b ł
a + ib = a2 + b2 + i
ł ł
a2 + b2 a2 + b2
ł łł
wi c je li podstawimy z = a2 + b2 , x = arctan(b / a), to
a+ib=z(cosx+i sinx)=zei x
Wzór Laplace a ei Ą+1=0
Wzór de Moivre a-Laplace a
(ei x)n=(cosx+i sinx)n=cosnx+i sinnx=ei n x
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 2
Liczby i wielomiany*
Wielomiany (1)
n
(n)
W (x) = an xn + an-1xn-1 + ... + a1x1 + a0x0 =
"a xi
i
i=0
ALGORYTM DZIELENIA
Ka dy wielomian mo na zapisa w postaci
(n)
W (x) = P(n-k )(x) Q(k )(x) + R(k -1) (x)
Q(k)(x) dzielnik wielomianu (stopnia k)
R(k 1)(x) reszta z dzielenia (stopnia ni szego ni k)
WNIOSEK 1:
(n) (n)
W (x) = (x - x0) P(n-1) (x) +W (x0)
WNIOSEK 2:
Je li xi s pierwiastkami wielomianu (W(n)(xi)=0), to
(n)
W (x) = an (x - x1)(x - x2)...(x - xs ) P(n-s) (x)
gdzie P(n s)(x) dzielnik nierozkładalny na czynniki liniowe.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 3
Liczby i wielomiany*
Wielomiany (2)
ROZKAAD WIELOMIANU NA CZYNNIKI
WNIOSEK 3:
Całkowite pierwiastki wielomianu o współczynnikach całkowitych
s podzielnikami wyrazu wolnego a0=an x1 x2& xs.
WNIOSEK 4:
Mamy
n
(n)
xnW (x-1) = an + an-1x + ...+ a1xn-1 + a0xn =
"a xn-i
i
i=0
wi c pierwiastki wymierne wielomianu o współczynnikach całkowitych
s podzielnikami wyrazu najwy szego an=a0 x1 x2& xs.
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 4
Liczby i wielomiany*
Wielomian i wielomian podstawy
Wielomian (polynomial)
Wn={an,an 1,& a1,a0}: ai parametry, x zmienna
n
W (x) = an xn + an-1xn-1 + ... + a1x1 + a0 x0
n
n
W (x) =
"a xi
i
i=0
Wielomian podstawy (radix polynomial) reprezentacja stałobazowa jednolita
Z={zn,zn 1,& z1,z0}: zi zmienne, parametr
n n-1 0
Z ( ) = zn + zn-1 + ... + z11 + z0
n
i
Z( ) = Z =
"z
i
i=0
reprezentacja standardowa (pozycyjna) 0d"zid"-1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 5
Liczby i wielomiany*
Algebra wielomianów i algebra liczb
Algebra wielomianów
n n
Wan(x) + Wbn(x) =
"(a + bi) xi = "s xi
i i
i=0 i=0
si = ai + bi
Algebra liczb reprezentacja pozycyjna (stałobazowa standardowa)
algorytm dodawania:
n n
i i
Z( ) +Y ( ) =
"(z + yi) = "s
i i
i=0 i=0
zi + yi + ci < ! si = zi + yi + ci, ci+1 = 0
zi + yi + ci e" ! si = zi + yi + ci - , ci+1 =1
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 6
Liczby i wielomiany*
Obliczenia schemat Hornera
Warto wielomianu mo na obliczy jako
n
(n)
W (x) =
"a xi = a0 + x{a1 + x[a2 + x(a3 + ...+ x(an-1 + x an))]}
i
i=0
zło ono obliczeniowa
" schemat klasyczny suma iloczynów przez pot gi zmiennej
o n dodawa ,
o n mno e ,
o n 1 oblicze pot g,
o pami pot g
" schemat Hornera suma iloczynów przez zmienn
o n dodawa
o n mno e ,
o zb dna pami
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 7
Liczby i wielomiany*
Szybkie obliczanie warto ci liczby schemat Hornera
liczby całkowite
n
i 2 n
Z = {zn,..., z1, z0} =
"z = z0 + z1 + z2 +...+ zn
i
i=0
obliczanie rekurencyjne
n
i
Z =
"z = {[(zn + zn-1) + zn-2 ] + ...+ z1} + z0
i
i=0
liczby ułamkowe
-1
i -1 -2 -m
Z = {z-1,..., z-m+1, z-m} =
"z = z-1 + z-2 + ...+ z-m
i
i=-m
obliczanie rekurencyjne warto w postaci ułamka wymiernego
-1
i -m
Z =
"z = {[(z-1 + z-2 ) + ...+ z-m+1] + z-m}
i
i=-m
z
Janusz Biernat, 01-06-Systemy liczbowe.doc, 6 pa dziernika 2006 SK 8
Wyszukiwarka
Podobne podstrony:
2012 01 06 Nota na Rok Wiary
Systemy liczbowe i kodowanie
kalendarium 01 06
TI 01 06 05 GT T B pl
TI 01 06 21 B pl(1)
KWP Gorzów Niebieska Karta sprawozdanie 2012 01 06
TI 01 06 01 T B pl(1)
Cwiczenie 01 Instalowanie systemu Windows 2003
01 06 Nieznany
2004 charakterystyka systemow liczbowych
TI 01 06 07 T pl
TI 01 06 06 GT T B pl(2)
Przeliczanie systemów liczbowych
01 06
01 06
TI 01 06 05 T pl(1)
więcej podobnych podstron