S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
I
Liczby, cyfry, systemy liczbowe
Liczba
– abstrakcyjny wynik oblicze , warto , opis ilo ciowy obiektu
Cyfra
– znak (symbol) u ywany do zapisu (reprezentacji) liczb,
Systemy pozycyjno-wagowe
(positional, place-value)
• wagi uporz dkowane i przypisane pozycjom → niezb dny symbol „zero”,
• z pozycj skojarzony mno nik oznaczony cyfr o warto ci całkowitej,
• reprezentacja liczby – wektor cyfr (ang. digit).
Systemy pozycyjne
(radix-based) i pokrewne (z ustalon podstaw )
– waga pozycji = pot ga podstawy (radix)
• stałobazowe (fixed-radix)
– naturalne – podstawa naturalna, cyfry tylko dodatnie
– z cyfr znakowan (signed digit, SD) – cyfry ujemne
– negabazowe (negative radix) – ujemna podstawa całkowita (baza)
• uzupełnieniowe (radix-complement) – rozszerzenie systemów naturalnych
wg reguły: reprezentacja –X to wynik działania 0 – X
System resztowy
(residue number system, RNS) – liczba=: wektor reszt
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
II
Reprezentacje systematyczne liczb
Reprezentacje stałoprzecinkowe
– stałobazowe (i uzupełnieniowe), ustalone poło enie przecinka pozycyjnego
(współczynnika skali m) przy danej podstawie
β
– izomorficzne z całkowitymi:
• liczba = liczba całkowita
×
××
×
β
–m
np. (m = 3,
β
=8). 7145,123
8
=7145123
×8
–3
, 0031,456
8
=31456
×8
–3
,
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) – podstawa stała
+3,27145123
E5 ( = 3,27145123
10
×10
5
),
−31415,9
10
×10
–4
, 1,01001
2
×2
1011
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}
= {56 mod 2, 56 mod 3, 56 mod 5, 56 mod 7}={0, 2, 1, 0}
Reprezentacje logarytmiczne – znak & logarytm warto ci bezwzgl dnej
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
III
Systemy stałobazowe (pozycyjne)
System stałobazowy 〈
β
,D〉
(fixed-radix), popularnie zwany pozycyjnym:
• ustalona podstawa (baza) – zwykle liczba całkowita taka, e |
β
| ≥2
• waga pozycji jest całkowit pot g podstawy
i
i
w
β
=
• ustalony zbiór warto ci cyfr, zwykle ten sam dla wszystkich pozycji; musi
zawiera nie mniej ni
β
warto ci w tym 0:
,...}
,...,
,
,
0
{
1
2
1
−
=
β
d
d
d
D
, przy tym
i
d
i
=
β
mod
dla i <
β
.
Warto ci
X liczby o reprezentacji
β
}
,...,
,
,...,
{
0
1
1
m
k
x
x
x
x
−
−
=
X
,
i
i
x
D
∈
, jest:
∑
−
=
−
=
−
−
−
−
−
−
=
+
+
+
+
+
=
1
1
1
0
1
1
1
...
...
k
i
m
i
i
i
m
m
k
k
x
x
x
x
x
x
X
β
β
β
β
β
• dokładno bezwzgl dna = waga najmniej znacz cej pozycji
m
ulp
−
=
β
Skalowanie
: X
I
– liczba całkowita, m – rozmiar przesuni cia przecinka w prawo
I
m
m
k
i
j
j
m
j
m
k
i
m
i
i
i
X
x
x
X
−
−
+
=
=
−
−
−
=
−
=
=
=
=
∑
∑
β
β
β
β
1
0
1
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
IV
Jednolita reprezentacja liczb ujemnych i dodatnich
standardowy zbiór cyfr
}
1
,...,
1
,
0
{
−
=
β
D
,
β
∈ (
β
≥2)
znak-moduł –
osobny kod (symbol) znaku, moduł naturalny
uzupełnieniowa
(radix-complement) – rozszerzenie systemu naturalnego
• liczb „–X” reprezentuje wynik działania pozycyjnego 0–X
obci
ona
(biased N, excess N) – naturalna reprezentacja liczby pomniejszonej
o stał naturaln N, najcz ciej repr. spolaryzowana (N
≅ ½ zakresu).
z cyfr znakowan (signed digit, SD
)
• dozwolone s ujemne warto ci cyfr, np. D={…, 2, 1, 0, 1, …}||D||≥
β
},
nieredundantny
: D
β
={d
i
: d
i
=i
∨ i–
β
, d
0
=0}, np. D
10
={0,1,8,3,4,5,4,7,2,1}
inne systemy:
negabazowy
– ujemna baza
β
≤−2, standardowy zbiór cyfr:
}
1
,...,
1
,
0
{
−
=
β
D
• (du a asymetria), specyficzna arytmetyka – podwójne przeniesienia
dopełnieniowy –
liczby dodatnie: naturalne, liczby ujemne: dopełnienia cyfr
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
V
System z ujemn podstaw (negabazowy)*
i
i
w
)
(
β
−
=
,
β
≥2 i całkowite
}
1
...,
,
1
,
0
{
,
)
(
}
,...,
,
,...,
,
{
1
1
0
2
1
−
∈
−
=
=
∑
−
−
=
−
−
−
−
−
β
β
β
i
k
m
i
i
i
m
k
k
x
x
x
x
x
x
x
X
• znaczna asymetria (dodatnia je li k nieparzyste, ujemna gdy k parzyste):
rozszerzenie lewostronne reprezentacji n-pozycyjnej o 1 pozycj powoduje
doł czenie do zbioru liczb (
β
–1)
β
n
liczb tego samego znaku
• 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
i
i
i
i
i
s
c
c
y
x
+
−
±
=
±
±
+1
)
(
β
wytwarzane s dwa przeniesienia:
1
1
,
)
1
(
+
+
−
=
i
i
i
c
c
β
oraz
1
2
,
+
+
=
i
i
i
c
c
1
1
,
+
+
=
i
i
i
c
c
β
, co daje
1
1
1
2
,
1
,
)
1
(
+
+
+
+
+
−
=
−
−
=
−
i
i
i
i
i
i
i
c
c
c
c
c
β
β
β
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
VI
Reprezentacja znak-moduł
pseudonaturalna
– +32,317, –214,554, ...
}
1
,
0
{
},
1
...,
,
1
,
0
{
,
)
1
(
}
,...,
,
}{
{
1
2
1
∈
−
∈
−
=
=
∑
−
−
=
−
−
−
s
x
x
x
x
x
s
i
k
m
i
i
i
s
m
k
k
β
β
β
X
Reprezentacja dopełnieniowa
dopełnienie cyfry
:
d
d
−
−
=
)
1
(
β
dopełnienie liczby
:
0
1
2
2
1
0
1
2
2
1
...
...
x
x
x
x
x
x
x
x
x
x
k
k
k
k
−
−
−
−
=
Np. reprezentacj – 35642
10
jest
64357
35642
=
(bo 35642
10
+64357
10
= 99999
10
)
)
(
},
1
...,
,
1
,
0
{
,
)
(
}
,...,
,
{
1
1
k
i
k
m
i
i
i
s
m
k
m
k
k
x
s
x
x
x
x
x
ϕ
β
β
β
β
β
=
−
∈
+
−
−
=
=
∑
−
−
=
−
−
−
X
Cechy wspólne reprezentacji znak-moduł i dopełnieniowej
• dwie reprezentacje zera : „+ 0” i „−0”
• zakres liczb symetryczny
• w dodawaniu i odejmowaniu – faktyczne działanie zale y od znaków
o
komplikacja algorytmu (układu) i dłu szy czas wykonania
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
VII
Reprezentacja uzupełnieniowa
Pozycyjne dodawanie wykonuje si tak:
2735
…000 2735
99…99
…000 99…99
+7329
+…000 7329
+1
+…000 00…01
= 1 0064
= …001 0064
= 1 00…00
= …001 00…00
– 7329
– …000 7329
– 1
– …000 00…01
= 0 2735
= …000 2735
= 0 99…99
= …000 99…99
W ten sam sposób wykonamy odejmowanie – symbol
1
oznacza „minus jeden”:
0064
= …000 0064
… (0)0064
00..00
= (0)00…00
– 7329
– …000 7329 … – (0)7329
– 1
– (0)00…01
= 1 2735
= …999 2735 … = (9)2735
=1 99..99
= (9)99…99
+7329
+…000 7329 … + (0)7329
+1
+(0)00…01
0 0064
…000 2735 … = (0)2735
0 99..99
(0)00…00
Wnioski:
• reprezentacje liczb dodatnich s takie jak w zapisie naturalnym
• reprezentacj liczby przeciwnej jest wynik odejmowania od zera
• reguły arytmetyki s takie jak w naturalnym systemie pozycyjnym
• zapis liczby mo na rozszerzy lewostronnie na dowoln liczb pozycji
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
VIII
Rozszerzenie niesko czone – ekstrapolacja zapisu
Rozszerzenie niesko czone w uzupełnieniowym systemie dziesi tnym:
0 – 2146
10
=0 – (0)2146
U10
= 17854
U10
= (9)7854
U10
= 7854
U10
Rozszerzenie niesko czone w uzupełnieniowym systemie ósemkowym:
0 – 2146
8
=0 – (0)2146
U8
= 15632
U8
= (7)5632
U8
= 5632
U8
A zatem (9)
U10
=
1
, (7)
U8
=
1
, podobnie (1)
U2
=
1
i (F)
U16
=
1
.
Podstawa nieparzysta
– w zapisie liczby konieczne rozszerzenie
Podstawa parzysta
– wiod ca cyfra okre la znak, mo na pomija rozszerzenie,
st d wzór na obliczenie warto ci liczby w systemie uzupełnieniowym
∑
−
=
−
−
−
+
=
k
i
i
i
k
k
k
k
x
x
x
x
x
x
β
β
ϕ
β
gdzie
ϕ
(x
k
–1
) – warto rozszerzenia dla cyfry wiod cej x
k
–1
.
• symetria zakresu (wykonalno 0 – X).
• łatwe skalowanie – przez przesuni cie
• rozszerzenie lewostronne reprezentacji ułatwia weryfikacj wyniku
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
IX
Dziesi tna reprezentacja uzupełnieniowa
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
⋅10
7
–1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
...
... 0 ... 0 0 0 0 0 5 0 0 0 0 0 1
+5
⋅10
6
+1
... 0 ... 0 0 0 0 0 5 0 0 0 0 0 0
+5
⋅10
6
... 0 ... 0 0 0 0 0 4 9 9 9 9 9 9
+5
⋅10
6
–1
... 0 ... 0 0 0 0 0 4 9 9 9 9 9 0
+5
⋅10
6
–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
⋅10
6
+2
... 9 ... 9 9 9 9 9 5 0 0 0 0 0 1
–5
⋅10
6
+1
... 9 ... 9 9 9 9 9 5 0 0 0 0 0 0
–5
⋅10
6
... 9 ... 9 9 9 9 9 4 9 9 9 9 9 9
–5
⋅10
6
–1
... 9 ... 9 9 9 9 9 4 9 9 9 9 9 8
–5
⋅10
6
–2
... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
...
... 9 ... 9 9 9 9 5 0 0 0 0 0 0 0
–5
⋅10
7
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
X
Dwójkowa reprezentacja uzupełnieniowa
... 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
+2
8
–1
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
... 0 ... 0 0 0 0 0 1 0 0 0 0 0 0 1
+2
7
+1
... 0 ... 0 0 0 0 0 1 0 0 0 0 0 0 0
+2
7
... 0 ... 0 0 0 0 0 0 1 1 1 1 1 1 1
+2
7
–1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
...
... 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 0 1
–2
7
+1
... 1 ... 1 1 1 1 1 1 0 0 0 0 0 0 0
–2
7
... 1 ... 1 1 1 1 1 0 1 1 1 1 1 1 1
–2
7
–1
... 1 ... 1 1 1 1 1 0 1 1 1 1 1 1 0
–2
7
–2
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
... 1 ... 1 1 1 1 1 0 0 0 0 0 0 0 0
–2
8
... 1 ... 1 1 1 1 0 1 1 1 1 1 1 1 1
∑
∑
∑
−
=
−
+
−
=
−
−
+
−
−
=
−
−
+
+
−
=
+
−
2
0
2
1
1
1
1
2
0
1
1
2
2
2
2
2
m
i
i
i
m
n
m
i
i
m
m
n
m
m
i
i
i
m
m
x
x
x
x
x
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
XI
System ze znakowan cyfr (SD)
• zbiór cyfr
d
d
a
a
a
a
a
−
=
≤
−
≤
−
=
,
2
1
},
,
1
,...,
1
,
0
,
1
,...,
{
β
D
a
a
a
a
a
x
x
i
n
m
i
i
i
2
1
},
,
1
,...,
1
,
0
,
1
,...,
{
,
|
|
1
SD
≤
−
≤
−
∈
=
∑
−
−
=
β
β
X
SD
2
1
SD
2
1
}
,...,
,
{
}
,...,
,
{
m
k
k
m
k
k
x
x
x
x
x
x
−
−
−
−
−
−
−
−
−
=
−
−
+
−
=
X
X
X
SD
– wykonalne w systemie SD i w systemie uzupełnieniowym:
≥
<
=
=
+
+
−
+
+
−
+
−
+
,
0
gdy
,
,
0
gdy
,
0
,
}
,
,...,
,
0
{
1
1
i
i
i
i
m
m
k
x
x
x
x
x
x
x
β
X
<
−
≥
=
=
−
−
−
−
+
−
−
−
−
.
0
gdy
,
,
0
gdy
,
0
,
}
,
,...,
,
0
{
1
1
i
i
i
i
m
m
k
x
x
x
x
x
x
x
β
X
reprezentacja minimalna
}
,
,..,
{
1
1
m
m
k
z
z
z
−
+
−
−
=
Z
– zawieraj ca najwi cej zer
)]
0
(
[
)]
1
(
)
1
(
[
1
1
1
1
1
1
=
∧
=
∨
=
−
−
≤
≤
+
−
−
≤
<
−
≤
<
−
≤
∀
∀
∀
∃
i
i
s
i
m
j
k
j
s
j
k
j
s
k
s
z
z
z
z
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
XII
Reprezentacja obci
ona
}
1
,...,
1
,
0
{
0
,
|
}
,
,...,
{
|
1
0
0
1
1
−
∈
<
<
−
=
=
∑
−
=
+
−
β
β
β
i
k
k
i
i
i
N
k
x
N
N
x
x
x
x
X
+
unikatowa reprezentacja zera
+
zgodno uporz dkowania liczb i ich reprezentacji (kodów)
–
konieczno korekcji wyników działa arytmetycznych
–
problematyczne u ycie w mno eniu lub dzieleniu
Reprezentacja spolaryzowana
– asymetria ujemna, gdy N = ½
β
k
, asymetria dodatnia, gdy N = ½
β
k
– 1.
W systemie dwójkowym otrzymujemy:
Gdy N = 2
k
–1
, to
∑
∑
−
=
−
−
−
=
−
+
+
−
−
=
−
=
−
2
0
1
1
1
0
1
2
2
2
)
1
(
2
2
1
k
i
i
i
k
k
k
i
k
i
i
x
x
x
X
k
,
Gdy N = 2
k
–1
–1, to
−
+
−
−
=
−
−
=
∑
∑
−
=
−
−
−
−
=
−
+
−
2
0
1
1
1
1
0
1
2
2
)
1
(
2
)
1
2
(
2
1
k
i
i
i
k
k
k
k
i
i
i
x
x
x
X
k
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
XIII
Dwójkowa reprezentacja spolaryzowana i uzupełnieniowa
łatwa konwersja reprezentacji spolaryzowanej na kod U2 i odwrotnie
1
1
2
0
1
2
1
2
0
1
2
1
U2
0
1
2
1
}
,
,...,
,
{
}
,
,...,
),
1
{(
}
,
,...,
,
{
−
−
+
−
−
+
−
−
−
−
=
−
=
k
k
x
x
x
x
x
x
x
x
x
x
x
x
m
k
m
k
k
k
1
-
2
0
1
2
1
1
-
2
0
1
2
1
U2
0
1
2
1
1
1
}
,
,...,
,
{
)}
1
(
),
1
(
),...,
1
(
,
{
}
,
,...,
,
{
−
−
+
−
−
+
−
−
−
−
=
−
−
−
=
−
k
k
x
x
x
x
x
x
x
x
x
x
x
x
k
k
k
k
k
k
N
=
2
k–
1
N
=
2
k
–1
−1
2
k
−1
−1
1
1
1
...
1
1
1
2
k
−1
2
k
−1
−2
1
1
1
...
1
1
0
2
k
−1
−1
...
...
...
...
...
...
...
...
...
0
1
0
0
...
0
0
0
1
−1
0
1
1
...
1
1
1
0
...
...
...
...
...
...
...
...
...
−2
k
−1
+1
0
0
0
...
0
0
1
−2
k
−1
+2
−2
k
−1
0
0
0
...
0
0
0
−2
k
−1
+1
S
YSTEMY LICZENIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
SL–
XIV
Cechy reprezentacji liczb całkowitych (stałoprzecinkowych)
kodowanie
umowne (intuicyjne):
• znak-moduł – „znak” | warto bezwzgl dna liczby
o
skomplikowana arytmetyka
(dodawanie, skalowanie, mno enie, …)
• dopełnianie – liczba ujemna = dopełnienie cyfr liczby przeciwnej dodatniej
o
skomplikowana arytmetyka
(dodawanie, skalowanie, mno enie, …)
kodowanie
arytmetyczne (nast pna: +1, poprzednia: –1):
• uzupełnianie – liczba ujemna = 0 – liczba przeciwna (dodatnia)
o
łatwa arytmetyka
(pozycyjna), porównanie i skalowanie
• polaryzacja – warto = warto naturalna – stała (tylko liczby całkowite)
o
sztywny zakres
, trudne mno enie, ograniczone dzielenie
o
łatwe porównanie
, dodawanie i odejmowanie
o
przydatno w zapisie zmiennoprzecinkowym
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
I
Dopełnienie liczby i liczba przeciwna*
Dopełnienie
liczby
β
}
,...,
,
,...,
{
0
1
1
m
k
x
x
x
x
−
−
=
X
(digit-complement)
β
β
}
)
1
(
:
,...,
,
,...,
{
0
1
1
i
i
m
k
x
x
x
x
x
x
−
−
=
=
−
−
X
Q
X
X
=
−
−
=
+
β
β
β
}
1
,...,
1
{
X
X
=
i
0
Q
=
Je li jest wykonalne działanie
Y
X
+
lub
Y
X
−
to mamy
Y
X
Y
X
Q
Y
X
Q
Y
X
Y
X
Y
X
Q
Y
X
Q
Y
X
−
=
−
−
=
+
−
=
+
+
=
+
−
=
−
−
=
−
)
(
)
(
)
(
)
(
Odwrotno addytywna
liczby
β
}
,...,
,
,...,
{
0
1
1
m
k
x
x
x
x
−
−
=
X
– liczba przeciwna
0
X
X
X
=
+
⇔
=
−
−
~
}
~
,...,
~
,
~
,...,
~
{
~
0
1
1
β
m
k
x
x
x
x
Je li istnieje liczba Q
~
, to
X
Q
X
Q
Q
X
0
X
+
=
−
+
=
−
=
~
~
~
i wtedy
)
~
(
Q
Y
X
Y
X
+
+
=
−
W systemach uzupełnieniowych
}
1
,
0
,...,
0
[
~
=
= ulp
Q
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
II
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ł
1
+
±
=
±
±
i
i
i
i
i
c
s
c
y
x
β
,
• 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)
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
III
Dodawanie i odejmowanie w systemach stałobazowych
Podstawowe działanie: odejmowanie
– umo liwia wytworzenie 0 (0=X–X) oraz liczby przeciwnej (–X=0–X)
(dodawanie: odejmowanie liczby przeciwnej: X+ Y=
df
X– ( 0 – Y), 0 = X– X))
(odejmowanie przez dodawanie wymaga tworzenia liczb przeciwnych)
Problem:
Dla ustalonego zbioru (zbiorów) dozwolonych warto ci cyfr (
∈D
*
) opisa
odwzorowanie wektorów cyfr reprezentuj cych składniki w reprezentacj
liczby, której warto jest ró nic / sum warto ci argumentów:
β
β
}
,...,
,
,...,
{
,
}
,...,
,
,...,
{
0
1
1
0
1
1
m
k
m
k
y
y
y
y
x
x
x
x
−
−
−
−
=
=
Y
X
,
i
i
i
y
x
D
∈
,
⇓ (
i
i
s
D
∈
)
Y
X
Y
X
±
=
⇔
=
±
−
−
−
−
β
β
}
,...,
,
,...,
{...,
}
,...,
,
,...,
{...,
0
1
1
0
1
1
m
k
m
k
s
s
s
s
s
s
s
s
W systemie stałobazowym mo na to zrealizowa wg schematu rekurencyjnego,
wykonuj c działania na kolejnych pozycjach pocz wszy od najni szej:
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
IV
Dodawanie i odejmowanie w systemach standardowych
Je li zbiór cyfr jest standardowy, D= {0,1,…,
β
−1} a podstawa dodatnia, to
jednoznacznym rozwi zaniem problemu jest:
.
1
,
0
wtedy
i
wtedy
i
|
|
|
|
gdy
gdy
,
,
1
1
=
=
≥
±
±
<
±
±
±
±
±
±
=
+
+
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
c
c
c
y
x
c
y
x
c
y
x
c
y
x
s
β
β
β
m
co mo na zapisa w postaci jednego równania z ograniczeniami;
i
i
i
i
i
s
c
c
y
x
+
±
=
±
±
+1
β
gdzie
})
1
,
0
{
}
1
,
0
{
(
}
1
,...,
1
,
0
{
,
,
1
∈
⇒
∈
⇒
−
∈
+
i
i
i
i
i
c
c
s
y
x
β
oraz
Je li zbiór cyfr jest niestandardowy D= {0, d
1
,d
2
,…,d
β
− 1
,…; d
i
mod
β
=i }, to
rozwi zania s specyficzne i mog by niejednoznaczne
β
1
+
±
±
=
i
i
i
i
i
w
c
y
x
s
m
,
przy tym
D
∈
i
i
i
i
c
s
y
x
,
,
,
oraz
D
∈
+
β
mod
1
i
w
.
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
V
Dodawanie wieloargumentowe w systemach naturalnych (1)
• dodawanie jest przemienne i ł czne, wi c:
∑
∑
∑
∑
−
=
−
=
−
=
−
=
+
+
=
+
+
+
=
+
+
+
1
0
1
0
1
0
1
0
...)
(
...
...
n
i
i
i
i
i
n
i
i
i
n
i
i
i
n
i
i
i
z
y
x
z
y
x
Z
Y
X
β
β
β
β
• 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
):
i
i
i
i
i
i
u
v
r
z
y
x
+
+
+
=
+
+
+
+
+
1
2
2
...
...
β
β
przy tym
}
1
,...,
1
,
0
{
,
,
,
,...,
,
2
1
−
∈
+
+
β
i
i
i
i
i
i
r
v
u
z
y
x
• przekształcenie redukuje m składników do 1+log
β
m
składników
...
...)
(
...
1
2
1
1
0
1
0
2
1
+
+
+
=
+
+
=
+
+
∑
∑
∑
∑
+
=
=
−
=
−
=
+
+
n
i
i
i
n
i
i
i
n
i
i
i
n
i
i
i
i
i
r
v
u
r
v
u
Y
X
β
β
β
β
• redukcja mo e by wykonana równolegle na poszczególnych pozycjach,
co pozwala szybko zredukowa sumowanie m liczb n-pozycyjnych do
sumowania dwóch liczb o rozmiarze m+log
β
m
pozycji ka da.
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
VI
Dodawanie wieloargumentowe w systemach naturalnych (2)
i
i
i
i
i
i
u
v
r
z
y
x
+
+
+
=
+
+
+
+
+
1
2
2
...
...
β
β
przy tym
}
1
,...,
1
,
0
{
,
,
,
,...,
,
2
1
−
∈
+
+
β
i
i
i
i
i
i
r
v
u
z
y
x
Je li jest
≤
β
+1 składników jednocyfrowych, to ich suma jest dwucyfrowa:
β
β
β
<
−
+
+
+
≤
−
+
+
+
=
+
k
z
y
x
k
z
y
x
k
u
v
i
i
i
i
i
i
i
i
...
0
gdy
}
...
,
{
}
,
{
1
,
dodawanie mo na wykona dwuetapowo:
• niezale nie obliczy sum na ka dej pozycji,
• doda otrzymane liczby dwucyfrowe.
x
k
–1
x
k
–2
x
k
–3
…
x
–m
+3
x
–m
+2
x
–m
+1
x
–m
y
k
–1
y
k
–2
y
k
–3
…
y
–m
+3
y
–m
+2
y
–m
+1
y
–m
…
…
…
…
…
…
…
…
±
z
k
–1
z
k
–2
z
k
–3
…
z
–m
+3
z
–m
+2
z
–m
+1
z
–m
u
k
–1
u
k
–2
u
k
–3
…
u
–m
+3
u
–m
+2
u
–m
+1
u
–m
v
k
v
k
–1
v
k
–2
…
v
–m
+4
v
–m
+3
v
–m
+2
v
–m
+1
s
k
s
k
–1
s
k
–2
…
…
s
–m
+3
s
–m
+2
s
–m
+1
s
–m
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
VII
Sekwencyjny algorytm mno enia w systemie naturalnym
Mno na (multiplicand)
|
}
,
,...,
{
|
1
1
β
p
p
s
a
a
a
A
−
+
−
−
=
,
Mno nik (multiplier)
|
}
,
,...,
{
|
1
1
β
m
m
k
x
x
x
X
−
+
−
−
=
,
∑
∑
−
−
=
−
−
=
=
⋅
=
⋅
1
1
)
(
k
m
i
i
i
k
m
i
i
i
A
x
x
A
X
A
β
β
algorytm pisemny – dodawanie skalowanych iloczynów cz ciowych (
0
=
−m
S
)
)
(
1
A
x
S
S
i
i
i
i
β
+
=
+
, i =
−m, −m+1,...,k−1
algorytm dodaj-przesu (add-and-shift) – skalowanie sum cz ciowych S
i
i
i
i
S
P
−
=
β
wtedy
)
(
1
1
A
x
P
P
i
i
i
+
=
−
+
β
X
A
x
A
P
P
k
m
i
i
i
m
k
k
⋅
=
+
=
∑
−
−
=
−
1
}
{
β
β
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
VIII
Konstrukcja tabliczki mno enia w systemach naturalnych (1)
• dla 1≤k≤
β
−1 iloczyn k⋅(
β
−1) jest liczb dwucyfrow o sumie cyfr
β
– 1:
β
β
β
β
β
}
,
1
{
)
(
)
1
(
)
1
(
k
k
k
k
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: x
2
=(x–1)(x+1)+1 (np. 3
2
=(3–1)*(3+1)+1=4*2+1)
↓+2
↓+3
↓+4
↓+5
…
ββββ
2
3
4
5
…
β−
2
β−
1
→+2
2
4
6
8
…
(1,
β−
2)
–2
←
→+3
3
6
9
3*4
5*3
…
(2,
β−
3)
–3
←
→+4
4
8
4*3
5*3+1
…
(3,
β−
4)
–4
←
→+5
5
5*3
6
6
6
*
*
*
4
4
4
+
+
+
1
1
1
…
…
–5
←
…
…
…
…
…
…
…
…
β−
2
… (
β−
4,4) (
β−
3,2)
β−
1 (1,
β−
2) (2,
β−
3) (3,
β−
4) (4,
β−
5)
… (
β−
3,2) (
β−
2,1)
↑–2
↑–3
↑–4
↑–5
…
suma cyfr
β−
1
W
NIOSEK
: wi kszo oblicze mo na wykona bez generowania przeniesie …
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
IX
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 (n
2
=1+3+5+...+2n
−1)
x
2
=(x–2)(x+2)+4=(x–2)(x+2)+1+3
(np. 4
2
=(4–2)*(4+2)+4=6*2+4)
x
2
=(x–3)(x+3)+9=(x–3)(x+3)+1+3+5 (np. 5
2
=(4–2)*(4+2)+4=6*2+4)
a
2
−1
...−1−3
a
2
...−1
a
2
−−−−1
...
x
2
−1
...−
...−
...−
...−1
x
2
...−
...−
...−
...−1−−−−3
x
2
−−−−1
…
x
2
−−−−4
…
−−−−1
x
2
−−−−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)
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
X
Tabliczki mno enia w systemach naturalnych
5
2
3
4
6
2
3
4
5
7
2
3
4
5
6
2
4 — —
2
4 — — —
2
4 — — — —
3
11 14 —
3
10 13 — —
3
6 12 — — —
4
13 22 31
4
12 20 24 —
4
11 15 22 — —
5
14 23 32 41
5
13 21 26 34 —
6
15 24 33 42 51
9
2
3
4
5
6
7
8
11
2
3
4
5
6
7
8
9
A
2
4 — — — — — —
2
4 — — — — — — — —
3
6 10 — — — — —
3
6 9 — — — — — — —
4
8 13 17 — — — —
4
8 11 15 — — — — — —
5
11 16 22 27 — — —
5
A 14 19 23 — — — — —
6
13 20 26 33 40 — —
6
11 17 22 28 33 — — — —
7
15 23 31 38 46 54 —
7
13 1A 26 32 39 45 — — —
8
17 26 35 44 53 62 71
8
15 22 2A 37 44 51 59 — —
9
17 25 33 41 4A 58 66 74 —
A
19 28 37 46 55 64 73 82 91
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
XI
Algorytm dzielenia całkowitego
Dla danych liczb całkowitych X (dzielna,
ang.
dividend) oraz D
≠ 0 (dzielnik
ang.
divisor
) istniej liczby całkowite Q (iloraz,
ang.
quotient
) oraz R (reszta,
ang.
remainder
) takie, e
X = Q
⋅
D + R, |R|<|D|
Dla R
≠0 równanie dzielenia ma 2 rozwi zania – je li 0 < R < D, to
X = Q
⋅
D + R =
(Q+1)
⋅
D +
( R–D),
Wyró nia si :
• dzielenie znakowane (signed div.) – zgodne znaki reszty i dzielnej (R D≥0)
• dzielenie modularne (modulus div.) – znak reszty dodatni (R ≥0)
W systemie pozycyjnym o podstawie
β
dzieln i dzielnik mo na skalowa
przez
β
n
, ergo iloraz mo na obliczy z dowoln dokładno ci
β
–p
.
Je li
β
,...}
,
,...,
{
0
1
1
x
x
x
X
k
−
=
i
β
,...}
,
,...,
{
0
1
1
d
d
d
D
l
−
=
, to:
i
l
k
p
i
i
p
l
k
l
k
q
q
q
q
q
Q
β
β
∑
+
−
−
=
−
−
+
−
=
=
1
0
1
}
,...
,...,
,
{
, przy tym X – Q
⋅
D
≤ D*
β
–p
D
ZIAŁANIA
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
DZ–
XII
Dzielenie sekwencyjne w systemie naturalnym
Algorytm
oblicze jest iteracyjny
– na podstawie przybli enia obliczonego z dokładno ci
β
i
oblicza si
kolejn cyfr ilorazu wyznaczaj c przybli enie z dokładno ci
β
i
–1
Pierwszym przybli eniem ilorazu jest
s
s
s
s
q
Q
q
β
β
=
=
1
,
}
0
,...,
0
,
{
takie, e
D
q
X
D
q
s
s
s
s
β
β
)
1
(
+
<
≤
,
D
D
q
X
R
s
s
s
β
β
<
−
=
≤
1
0
Je li Q
s,i
jest przybli eniem ilorazu z dokładno ci
β
s
–i+1
(i cyfr znacz cych), to
przybli eniem z dokładno ci
β
s
–i
(i+1 cyfr) jest
i
s
i
s
i
s
i
s
q
Q
Q
−
−
+
+
=
β
,
1
,
takie, e
D
q
D
Q
X
R
D
q
i
s
i
s
i
s
i
i
s
i
s
−
−
−
−
+
<
−
=
≤
β
β
)
1
(
,
,
D
D
q
R
R
i
s
i
s
i
s
i
i
−
−
−
+
<
−
=
≤
β
β
1
0
,
co po skalowaniu (
1
−
−
=
s
i
i
i
R
r
β
) prowadzi do nierówno ci parametrycznej
D
D
q
r
r
i
s
i
i
<
−
=
≤
−
+
β
1
0
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
1
Pozycyjne rozwini cie liczby w systemie naturalnym
W systemie naturalnym o podstawie
β
jednoznaczn reprezentacj liczby X
≥0,
β
,...}
,...,
,
,...,
{
1
0
1
m
k
x
x
x
x
−
−
−
, jest rozwi zanie równania
X
x
x
x
x
m
m
k
k
k
k
k
m
i
i
i
=
+
+
+
+
=
−
−
−
−
−
−
−
−
=
∑
...
...
2
2
1
1
1
β
β
β
β
,
z warunkami:
}
1
...,
,
1
,
0
{
−
∈
β
i
x
.
UWAGA: Rozwini cie cz ci ułamkowej mo e by niesko czone (okresowe).
W praktyce warto liczby jest zapisana w jakim systemie pozycyjnym,
wi c rozwi zanie problemu nazywa si konwersj podstawy.
• działania wykonywane s w systemie ródłowym (o podstawie
ω
)
• podstawa systemu docelowego
β
jest zakodowana w systemie ródłowym
β
= |{b
p
, …, b
1
, b
0
}
ω
|
• wyniki {z
s–
1
, z
s–
1
, …, z
–r
}
β
– w systemie o podstawie
β
(
ω
β
log
k
s
≤
)
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
2
Konwersja tablicowa
1. Utwórz tablic pot g podstawy docelowej
β
n
,
β
n
–1
,…,
β
–m
,
β
n
< X<
β
n
+1
2. Metod „odejmij i porównaj” wyznacz kolejne cyfry reprezentacji:
i = n , X
n
= X
Powtarzaj, dopóki i > m (dokładno oblicze
β
–m
)
a) Je li q
β
i
≤ X
i
<
( q+1)
β
i
< 0, to x
i
=q
,
b) i : = i – 1, X
i
–1
= X
i
– x
i
β
i
problem
: warto ci pot g ujemnych s przybli one, np. 0,1
10
= 0,(00011)
2
wada: dokładno oblicze narzucona z góry
Przykład (...)
10
→(...)
8
(8
3
=512, 8
2
=64, 8
–1
=0,125, 8
–2
=0,16625)
1937,03125
10
=3
⋅512+3⋅64+2⋅8+1+2⋅64
–1
=3
⋅8
3
+3
⋅8
2
+2
⋅8
1
+1
⋅8
0
+2
⋅8
–2
=3321,02
8
Bezpo rednie obliczenie
Zapisujemy podstaw i warto ci cyfr w systemie docelowym i wykonujemy obliczenie.
W praktyce dotyczy to tylko konwersji na system dziesi tny…
Przykład:
11011011
2
=(1*2
7
+1*2
6
+1*2
4
+1*2
3
+1*2
1
+1*2
0
=128+64+16+8+2+1)
10
=219
10
3542
8
=(3*8
3
+5*8
2
+4*8
1
+2*8
0
=3*512+5*64+4*8+2*1=1536+320+32+2)
10
=1890
10
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
3
Schemat Hornera
warto wielomianu mo na obliczy jako:
))]}
(
...
(
[
{
)
(
1
3
2
1
0
0
)
(
n
n
n
i
i
i
n
a
x
a
x
a
x
a
x
a
x
a
x
a
x
W
+
+
+
+
+
+
=
=
−
=
∑
schemat klasyczny
–
suma iloczynów przez pot gi zmiennej
• n dodawa i n mno e ,
• n–1 oblicze pot g
• potrzebna pami pot g
schemat Hornera
– suma iloczynów przez zmienn
• n dodawa i n mno e ,
• zb dna pami
Szybkie obliczanie warto ci liczby w systemie pozycyjnym
liczby całkowite
0
1
2
2
1
0
}
]
...
]
)
{[...[(
z
z
z
z
z
z
z
Z
n
n
n
n
i
i
i
+
+
+
+
+
+
=
=
−
−
=
∑
β
β
β
β
β
β
β
liczby ułamkowe – skalowanie ułamka U, aby otrzyma U=Z
β
–m
, albo (uniwersalnie)
1
2
3
1
1
0
1
}
]
...
)
{[...(
−
−
−
+
−
−
−
−
=
−
−
−
−
=
+
+
+
+
+
=
=
=
∑
∑
u
u
u
u
u
u
u
U
m
m
m
m
s
m
s
m
s
m
i
i
i
β
β
β
β
β
β
β
β
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
4
Generowanie reprezentacji pozycyjnej
Dla cz ci całkowitej X
I
oraz ułamkowej X
F
liczby X mamy odpowiednio
)]}
(
...
[
{
1
2
2
1
0
1
0
−
−
−
=
+
+
+
+
=
=
∑
k
k
k
i
i
i
I
x
x
x
x
x
x
X
β
β
β
β
β
)...]}
(
...
[
{
1
1
1
2
1
1
1
1
m
m
m
i
i
i
F
x
x
x
x
x
X
−
−
+
−
−
−
−
−
−
−
−
=
+
+
+
+
=
=
∑
β
β
β
β
β
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 warto cyfry rozszerzenia w systemach uzupełnieniowych
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
5
Konwersja cz ci całkowitej liczby
A
mod b – reszta z dzielenia A przez b
A
div b – iloraz całkowity A przez b
)...)]}
(
...
(
[
{
1
2
3
2
1
0
0
−
−
+
+
+
+
+
=
=
k
k
I
x
x
x
x
x
x
I
X
β
β
β
β
β
β
mod
0
0
I
x
=
)...])]
(
...
[
(
[
div
1
2
4
3
2
1
1
0
−
−
+
+
+
+
+
=
=
k
k
x
x
x
x
x
x
I
I
β
β
β
β
β
β
β
mod
1
1
I
x
=
)...)])
(
...
(
[
(
div
1
2
5
4
3
2
2
1
−
−
+
+
+
+
+
=
=
k
k
x
x
x
x
x
x
I
I
β
β
β
β
β
β
β
mod
2
2
I
x
=
…
cyframi rozwini cia cz ci całkowitej X
I
liczby X w systemie o podstawie
β
s :
I
0
1
1
,
int
div
,
mod
X
I
I
I
I
I
x
j
j
j
j
j
=
=
=
=
−
+
β
β
β
Je li I
r
= 0, to x
r+
1
= 0, I
r+
1
= 0 itd.
(kolejne cyfry lewostronnego rozwini cia s zerami)
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
6
Algorytm konwersji cz ci całkowitej liczby
Procedura
(na podstawie rozwini cia Hornera):
Powtarzaj, dopóki nie uzyskasz ilorazu równego 0:
1. Oblicz iloraz i reszt z dzielenia liczby przez podstaw systemu docelowego
2. Otrzymana reszta jest kolejn cyfr rozwini cia pozycyjnego w systemie
o podstawie docelowej
β
3. Otrzymany iloraz poddaj procedurze dzielenia
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. x
i
= X
(i)
–
β
X
(i+1)
; reszta
3. i ++
; zwi ksz i
4. if X
(i+1)
≠ 0 goto 1
; powtarzaj dopóki iloraz
≠ 0
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
7
Konwersja cz ci ułamkowej liczby
int A – cz
całkowita liczby A
)...)]}
(
...
(
[
{
1
1
1
3
1
2
1
1
1
1
m
m
F
x
x
x
x
x
F
X
−
−
+
−
−
−
−
−
−
−
−
+
+
+
+
+
=
=
β
β
β
β
β
1
1
int F
x
β
=
−
)...])]}
(
...
[
(
[
1
1
1
4
1
3
1
2
1
2
1
1
m
m
x
x
x
x
x
F
x
F
−
−
+
−
−
−
−
−
−
−
−
−
+
+
+
+
+
=
=
−
β
β
β
β
β
β
2
2
int F
x
β
=
−
)...)])
(
...
(
[
(
1
1
1
5
1
4
1
3
1
3
2
2
m
m
x
x
x
x
x
F
x
F
−
−
+
−
−
−
−
−
−
−
−
−
+
+
+
+
+
=
=
−
β
β
β
β
β
β
3
3
int F
x
β
=
−
cyframi rozwini cia cz ci ułamkowej X
F
liczby X w systemie o podstawie
β
s
1
,
1
,
int
F
1
1
<
=
<
−
=
=
−
+
−
X
F
x
F
F
F
x
j
j
j
j
j
β
β
Je li F
r
= 0, to x
–
(r+1)
= 0, F
r
+1
= 0 itd.
(kolejne cyfry prawostronnego rozwini cia s zerami)
Je li dla r>r
0
jest F
r
= F
r–k
, to rozwini cie jest okresowe (okres ma k cyfr)
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
8
Algorytm konwersji ułamka wymiernego
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 :
– uzyskasz wymagan dokładno
β
–m
(odpowiedni liczb cyfr),
– otrzymasz iloczyn równy 0,
– wykryjesz okresowo (pojawi si ułamek argument taki jak wcze niej).
Reprezentacja cz ci ułamkowej (A <
1) z dokładno ci
β
– m
0. X
(0)
= A, x
0
= 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 i
≤m & X
(i+1)
≠ 0 goto 1
; powtarzaj dopóki za mała dokładno
; i niezerowy argument
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
9
Konwersja ułamka wymiernego w systemach naturalnych
Uwaga
Wynikiem konwersji ułamka wymiernego jest ułamek sko czony lub okresowy
W
ŁA 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
∑
∑
−
=
−
=
−
=
−
=
=
∞
<
∃
⇒
=
⇒
=
∈
∀
1
1
:
]
)
,
(
)
,
(
:
[
i
r
i
i
i
i
m
i
i
i
z
x
r
p
p
NWD
p
p
NWD
p
β
ω
β
ω
P
D
OWÓD
. Je li F jest ułamkiem sko czonym m-pozycyjnym w bazie
ω
, to
N
∈
−
≤
≤
=
=
=
−
−
=
−
−
−
−
=
∑
∑
A
A
A
x
x
F
m
m
m
i
i
m
i
m
m
i
i
i
,
1
0
,
1
0
1
ω
ω
ω
ω
ω
.
F
ma sko czone rozwini cie tak e w bazie
β
, je eli istnieje B
∈N i r< ∞ takie,
e
1
0
,
−
≤
≤
=
−
r
r
B
B
F
β
β
. Załó my, e NWD(p,
β
) = 1. Ale wówczas byłoby
m
m
m
r
p
A
p
NWD
p
p
NWD
p
NWD
B
A
=
⇒
=
=
=
)
,
(
)
,
(
&
1
)
,
(
&
ω
β
ω
β
,
wi c rozwini cie F byłoby niesko czone, chyba e A = k p
m
.
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
10
Konwersja liczby ujemnej na system uzupełnieniowy
1. Ka dy ujemny ułamek wła ciwy mo na przedstawi jako 1+f, gdzie f jest
dodatnim ułamkiem wła ciwym, wi c
liczb –(X + f ) mo na przedstawi jako –(X+1)+(1 – f )
–1573
10
→X
U8
→Z
U2
I
i
mod 8
–1573
–197 3 =x
0
–25 3 =x
1
–4 7 =x
2
–1 4 =x
3
–1 7 =x
4
… 7 =x
5
(7)
–1573
10
= (7)4733
U8
=
2. Wagi wszystkich cyfr reprezentacji
uzupełnieniowych s dodatnie, wi c
konwersja cz ci całkowitej wymaga
nast puj cego post powania:
1) kolejne ilorazy maj taki znak jak
liczba przetwarzana,
2) warunek stopu:
dwa kolejne ilorazy identyczne, czyli
iloraz równy warto ci ci gu cyfr
rozszerzenia (0 lub –1)
(1)100 111 011 011
U2
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
11
Konwersja podstawy skojarzonej – przykłady
...
100
15
100
32
100
71
100
56
100
34
100
2
...
10
15
10
32
10
71
10
56
10
34
10
2
...
3215
,
2345671
2
1
0
1
2
3
4
2
0
2
4
6
−
−
−
−
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
8
2
8
1
8
0
8
1
8
2
8
6
2
3
2
0
2
3
2
6
2
2
35
,
347
8
5
8
3
8
7
8
4
8
3
2
101
2
011
2
111
2
100
2
11
101
011
,
111
100
11
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
−
−
−
−
16
8
2
4
2
0
2
4
2
8
2
2
2
6
2
3
2
0
2
3
2
6
2
9
2
2
1
0
1
2
3
8
74
,
7
E
4
2
0100
2
0111
2
0111
2
1110
2
0100
0100
0111
,
0111
1110
0100
101
011
,
111
100
011
010
2
101
2
011
2
111
2
100
2
011
2
010
8
5
8
3
8
7
8
4
8
3
8
2
35
,
2347
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
=
=
=
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
−
−
−
−
−
−
6
1
U
2
U
8
U
2
U
2
U
74
,
7
E
)
F
(
0100
0111
,
0111
1110
)
1111
(
35
,
47
)
7
(
101
011
,
111
100
)
111
(
011101
,
100111
)
1
(
=
=
=
=
=
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
12
Konwersja podstawy skojarzonej w systemach naturalnych
...
)
(
)
(
)
...(
...
)
(
)
(
)
(
)
...(
...
...
3
3
2
2
1
0
0
1
2
2
3
3
4
2
5
2
2
1
0
0
1
2
2
3
4
4
5
2
2
1
1
0
0
1
1
2
2
2
3
4
4
5
5
+
+
+
+
+
+
+
+
+
=
=
+
+
+
+
+
+
+
+
=
=
+
+
+
+
+
+
+
+
=
−
−
−
−
−
−
−
−
−
−
−
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
β
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
X
a zatem:
∑
∑
∑
−
−
=
−
−
=
+
−
−
+
−
−
=
=
+
+
+
=
1
1
1
1
1
1
)
(
)
(
)
...
(
t
r
j
j
s
j
t
r
j
j
s
js
js
s
s
js
k
m
i
i
i
z
x
x
x
x
β
β
β
β
β
czyli
{
}
{
}
s
r
t
m
k
z
z
z
z
x
x
x
x
β
β
−
−
−
−
=
,...,
,
,...,
,...,
,
,...,
0
1
1
0
1
1
gdzie
}
1
,...,
1
,
0
{
...
1
1
1
−
∈
+
+
+
=
+
−
−
+
s
js
js
s
s
js
j
x
x
x
z
β
β
β
– warto cyfry w (..)
β
↑ s
Zło enie konwersji – (..)
ββββ
↑
↑
↑
↑ k
→
→
→
→(..)
ββββ
↑
↑
↑
↑ s
(..)
β
↑ k
→(..)
β
↑ s
⇔ (..)
β
↑ k
→(..)
β
|| (..)
β
→(..)
β
↑ s
ω
<
β
s
⇒ zamiast konwersji (..)
ω
→(..)
β
wygodniej realizowa (..)
ω
→(..)
β
↑ s
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
13
Konwersja podstawy w systemach naturalnych – przykłady
157,386
10
→X
8
→Z
2
oraz 157,386
10
→X
9
→Z
3
(8=2
3
9=3
2
).
I
i
mod 2
3
×2
3
F
i
I
i
mod 3
2
×3
2
F
i
157
0 386
157
0 386
19 5 =x
0
x
-1
=
3 088
17 4 =x
0
x
-1
=
3 474
2 3 =x
1
x
-2
=
0 704
1 8 =x
1
x
-2
=
4 266
0 2 =x
2
x
-3
=
5 632
0 1 =x
2
x
-3
=
2 394
157,386
10
= 235,305...
8
= 10011101,011000101...
2
157,386
10
= 184,342
9
= 12211,101102...
3
.
235,305
8
→X
10
oraz 235,305
8
→X
9
→Z
3
(działania w systemie ósemkowym)
I
i
mod 12
8
×12
8
F
i
I
i
mod 11
8
×3 F
i
235
8
0 305
8
235
8
0 305
8
17
8
7 =x
0
x
-1
=
3
662
8
21
8
4 =x
0
x
-1
=
3 355
8
1
5 =x
1
x
-2
=
10
8
364
8
1 8 =x
1
x
-
2
=
4 125
8
0 1 =x
2
x
-3
=
4
610
8
0 1 =x
2
x
-3
=
1 375
8
235,305
8
=157,384...
10
= 184,341...
9
= 12211,101101...
3
.
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
14
Konwersja ułamka wymiernego
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.
0,1
10
= 0,00011001100110011…
2
= 0,0(0011)
2
10
8
8
61
54
X
→
x
0
=0
0
×12
8
=10
10
x
–1
=8
=10
8
8
8
8
8
61
670
61
60
=
+
x
–2
=9
=11
8
8
8
8
8
61
740
61
47
=
+
x
–3
=7
=7
8
8
8
8
8
61
606
61
57
=
+
…
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
15
Konwersja ułamków okresowych w systemach naturalnych
• zamiana na ułamek wymierny
−
+
=
−
+
=
−
−
−
−
−
−
−
−
1
1
1
1
)
...
(
...
,
0
1
1
c
k
c
c
k
c
k
k
k
z
x
z
x
z
z
x
x
β
β
β
β
β
β
• automatyczna korekcja okresu podczas mno enia
– przeniesienie wewn trz okresu jest cykliczne
ułamek wymierny
ułamek okresowy
tylko
0,(
xy...z
)
β
0,5(37)
10
=
8
10
10
990
532
X
→
0,5(37)
10
→X
8
0,(386)
10
→X
7
×7
0
×8
0 5 (37) ×8
0 (386)
…2 (96) x
–1
=
2
(702)
x
–1
=
4
10
10
10
10
990
4256
990
296
=
+
x
–1
=
4 2 (98)
(704)
…7 (84) x
–2
=
4 (928)
x
–2
=
2
10
10
10
10
990
2368
990
388
=
+
x
–2
=
2 3 (91)
(932)
…7 (28) x
–3
=
6 (524)
x
–3
=
3
10
10
10
10
990
3104
990
134
=
+
x
–3
=
3 1 (35)
(530)
K
ONWERSJA PODSTAWY
© Janusz Biernat
,
AK1-2-09- Liczby i konwersje.doc, 23 wrze nia 2009
KP–
16
Konwersja podstawy w systemach stałobazowych
Schemat Hornera mo e by u yty do zapisu warto ci liczby w dowolnym
systemie stałobazowym
W
NIOSEK
Algorytmy konwersji dla systemu naturalnego mo na stosowa tak e
w dowolnym systemie stałobazowym lub uzupełnieniowym.
Problem: arytmetyka musi by odpowiednia do wła ciwo ci systemu
Przykład:
157,386
10
→(..)
SD-8
. (D = { 4 , 3, 2, 1, 0, 1, 2, 3}
I
i
I
i
mod 8
×8
F
i
(!<500)
×8
F
i
157
0 386
0 386
19 5 → 20 3 =x
0
x
-1
=
3 088
x
-1
=
3 088
3 4 =x
1
x
-2
=
0 704 !!
x
-2
=
1 296
0 3 =x
2
x
-3
=
5
632
↑
x
-3
=
2 368
x
-4
=
3 056
Wyszukiwarka
Podobne podstrony:
konwers. II 2009, ~ NOTATKI, przedmioty obowiązkowe I rok, Chemia Nieorganiczna
układy logiczne, wyk7a, Algorytm konwersji liczby binarnej na liczb˙ w kodzie BCD
Wykład 6 2009 Użytkowanie obiektu
Przygotowanie PRODUKCJI 2009 w1
Wielkanoc 2009
przepisy zeglarz 2009
Kształtowanie świadomości fonologicznej prezentacja 2009
zapotrzebowanie ustroju na skladniki odzywcze 12 01 2009 kurs dla pielegniarek (2)
perswazja wykład11 2009 Propaganda
Wzorniki cz 3 typy serii 2008 2009
2009 2010 Autorytet
Cw 1 Zdrowie i choroba 2009
download Prawo PrawoAW Prawo A W sem I rok akadem 2008 2009 Prezentacja prawo europejskie, A W ppt
Patologia przewodu pokarmowego CM UMK 2009
Wykład VIp OS 2009
więcej podobnych podstron