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