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 

A

RYTMETYKA 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. 

A

RYTMETYKA 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.B

IERNAT

, Metody i układy arytmetyki komputerowej, Wrocław, Oficyna Wydawnicza 

Politechniki Wrocławskiej, 2001. 

I.K

OREN

, Computer Arithmetic Algorithms, A.K.Peters, Natick, MA, 2002  

(wyd.1: Prentice Hall, Englewood Cliffs, NJ, 1993). 

R.Z

IMMERMANN

, Lecture Notes on Computer Arithmetic: Principles, Architectures and 

VLSI Design, Institut für Integrierte Systeme, Eidgenössische Technische 
Hochschule, Zurich, March, 1999. 

 

Literatura uzupełniaj

ą

ca 

B.P

ARHAMI

, Computer Arithmetic. Algorithms and Hardware Designs, New York-Oxford, Oxford 

University Press, 2000 

J-M.M

UELLER

, Elementary functions. Boston: Birkhauser 1997 

B.P

OCHOPIE

, Arytmetyka w systemach cyfrowych, Warszawa, AOW Exit, 2004  

(Arytmetyka systemów komputerowych, Gliwice, Wyd. Polit.  l skiej, 2000, wyd.V) 

J.B

IERNAT

, Architektura komputerów, Wrocław, Oficyna Wydawnicza Politechniki Wrocławskiej, 

2005 (wyd.IV). 

J.B

IERNAT

, Arytmetyka komputerów, Warszawa, PWN, 1996. 

N.K

OBLITZ

, Wykład z teorii liczb i kryptografii, WNT, 1995. 

S.W

ASSER

, M.J.F

LYNN

, Introduction to arithmetic for digital system designers, New York, Holt, 

Rinehart, Winston 1982. 

 

Arytmetyka 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

AR–I 

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). 

 

Arytmetyka 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

AR–II 

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 

 

Arytmetyka 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

AR–III 

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 

 
W

NIOSEK

: 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) 

 

Arytmetyka 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

AR–IV 

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 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–I 

Miary i liczby – systemy wagowe 

– system pomiaru czasu – 1 doba =24 h, 1 h=60 min,  1 min =60 s 
– 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 = 437

1

/

2

gr 

fathom 

– 1 fathom= 2 yd 

 

pound (funt) 

– 1 lb = 8 oz 

rod (pr t) 

– 1 rod = 5

1

/

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  

(= 2

0

5

0

)

 

jedno  

 

 

C  

(= 2

2

5

2

)

 

setka 

 

 

V   (= 2

0

5

1

)

 

pi tka 

 

 

D  

(= 2

2

5

3

)

 

pi

setka 

 

 

X   (= 2

1

5

1

)

 

dziesi tka 

 

 

M  

(= 2

3

5

3

)

 

tysi c 

 

 

L   (= 2

1

5

2

)

 

pi

dziesi tka 

 

 

D  

(= 2

3

5

4

)

 

pi

 tysi cy 

 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–II 

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 

 
W

NIOSEK

: 

Wagi warto uporz dkowa  a zapis unormowa . 
 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–III 

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 = 2

0

5

0

, V = 2

0

5

1

,  X = 2

1

5

1

,  L = 2

1

5

2

,  C = 2

2

5

2

,  D = 2

2

5

3

,  M = 2

3

5

3

,...) 

 

System resztowy (residue number system, RNS) – liczba=: wektor reszt  

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–IV 

Systemy stałobazowe (pozycyjne) 

System stałobazowy 〈

β

,D〉 (fixed-radix), popularnie zwany pozycyjnym:  

• 

ustalona podstawa (baza) – zwykle liczba całkowita taka,  e |

β

|≥2 

 

• 

dla ka dej pozycji okre lone: 

o 

reguła tworzenia wag 

}

,...,

,

,...,

{

0

1

1

m

k

w

w

w

w

−

−

=

W

, 

i

i

w

β

=

 

o 

zbiór dozwolonych cyfr 

}

0

,

,...,

{

0

1

1

=

=

−

i

i

i
p

i

d

d

d

D

,  x

i

∈

D

i

 (zawiera zero) 

 
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

−

=

β

 

• 

standardowy zbiór cyfr 

}

1

,...,

1

,

0

{

−

=

β

D

, 

β

∈

 (

β

≥2)

 

• 

redundantny zbiór cyfr ||D

+

|| >

β

 

,...}

,

,

1

,...,

2

,

1

,

0

{

1

1

1

2

2

1

1

+

−

−

+

+

−

=

+

=

+

=

=

β

β

β

β

β

β

β

β

d

d

a

d

a

d

a

d

D

 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–

V 

Popularne systemy pozycyjne  

 

naturalny 〈

β

,D〉

, 

 

β

≥2

,  

• 

standardowy zbiór cyfr 

}

1

,...,

1

,

0

{

−

=

β

D

  

 

z cyfr  znakowan  (signed digit, SD

) 〈

β

,D〉

, reprezentacja liczb  ujemnych 

• 

zbiór cyfr

: D = {d

p–1

, ..., d

1

, d

0

= 0; p

≥

β

, |

d

i

|

<

β

},  

dozwolone s  ujemne warto ci cyfr, np. D={…, 2, 1, 0, 1, 2, …} 

• 

nieredundantny 

β

β

mod

   

},

,...,

,

0

{

1

1

i

d

d

d

i

e

≡

=

−

D

 

Np: 

β

= 10, D={0,1,8,3,4,5,4,7,2,1} (d =

−

d

): 2 = 18, 56 = 144, 63 = 143  

 

negabazowy

 〈

β

,D〉

, 

 

−

β

≥2

, reprezentacja liczb ujemnych 

• 

standardowy zbiór cyfr

: 

}

1

,...,

1

,

0

{

−

=

β

D

  

• 

 

(du a asymetria), specyficzna arytmetyka  

 

uzupełnieniowy

 (radix-complement) 〈

β

,D/D

H

〉

 

• 

niestandardowy i nieredundantny zbiór cyfr na pozycji najwy szej,  

D

H

= {–

α

,–

α

+1

,…,0,1, …, (

β

–1–

α

)}, 2

α

=

β

 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–

VI 

Reprezentacje systematyczne liczb 

Reprezentacje stałoprzecinkowe  
– stałobazowe (i uzupełnieniowe) ustalone poło enie przecinka pozycyjnego 

327145,123

10

 ,     0,0000000000031459

10

 ,     327145,123

8

 ,    01011101011

2 

 

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,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 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–

VII 

Dodawanie i odejmowanie w systemach stałobazowych  

β

β

}

,...,

,

,...,

{

     

,

}

,...,

,

,...,

{

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

 

 

Rekurencyjna reguła wyznaczania cyfr sumy lub ró nicy  

istnieje tylko wtedy, gdy istnieje ogólne rozwi zanie równania: 

i

i

i

i

i

s

c

c

y

x

+

±

=

±

±

+

1

β

,   

i

i

i

i

s

y

x

D

∈

 

 

• 

standardowy zbiór cyfr: D

i

= D = {0,1,…,

β

−

1} – rozwi zaniem jest:  

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

 

 

• 

niestandardowy zbiór cyfr D = {0, d

1

,d

2

,…,d

β

−

1

,…; d

i

mod

β

=

i } 

k

c

k

c

y

x

s

i

i

i

i

i

=

±

±

=

+

1

β

m

,   

D

∈

β

mod

k

 

 

Systemy liczenia 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

SL–VIII 

Jednoznaczno  reprezentacji stałobazowej 

T

WIERDZENIE

  

Reprezentacja liczby w standardowym systemie stałobazowym jest unikatowa. 

 

D o w ó d .  Niech 

β

}

0

|

,...,

,

,...,

,

0

,...,

0

{

0

1

≠

=

−

j

m

j

j

x

x

x

x

x

X

. Jako,  e 

0

≠

j

x

, wi c 

m

j

j

j

j

j

j

−

+

−

≤

=

−

<

−

β

β

1

min

max

Z

N

P

X

X

. 

Z kolei, warto  dowolnej liczby 

1

+

j

X

 

)

1

(

1

≥

+

j

x

 mo na obliczy  jako 

1

1

1

1

+

+

+

≤

+

+

=

j

j

j

j

s

j

x

β

λ

X

X

. 

Poniewa   |

λ

j+1

|=1, zatem 

!

!

1

1

1

0

+

+

+

+

≤

+

≤

=

−

<

j

j

j

j

j

s

j

x

β

β

λ

X

X

. Skoro jednak 

rozpi to  zakresu liczb 

j

s

<

X

 nie przekracza 

β 

j+1

, zatem 

j

s

j

≤

+

≠

X

X

1

.  

 

Wynika st d dalej,  e 

2

1

2

1

j

j

j

j

x

x

X

X

≠

⇒

≠

, bo wówczas albo 

2

1

2

2

1

1

1

1

2

1

2

1

gdy   

     

}

,

..

,.

,

0

{

}

,

..

,.

,

{

j

j

m

j

m

j

j

j

j

j

x

x

x

x

x

x

x

x

>

−

−

=

−

−

−

−

−

X

X

 

albo 

2

1

2

2

1

1

2

1

1

1

2

1

gdy   

     

}

,

..

,.

,

{

}

,

..

,.

,

0

{

j

j

m

j

j

j

m

j

j

j

x

x

x

x

x

x

x

x

<

−

−

=

−

−

−

−

−

X

X

 

Gdy za  

2

1

2

1

2

1

 

 to

,

:

s

s

j

j

i

i

x

x

j

i

s

X

X

X

X

−

=

−

=

≤

<

∀

, co dowodzi tezy.  

 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–

I 

Dodawanie i odejmowanie w systemach naturalnych 

W standardowym systemie naturalnym (

λ

i

= 1) równaniem dodawania jest 

i

i

i

i

i

s

c

c

y

x

+

±

=

±

±

+

1

β

 

 

przy tym 

})

1

,

0

{

}

1

,

0

{

(

}

1

,...,

1

,

0

{

,

,

1

∈

⇒

∈

⇒

−

∈

+

i

i

i

i

i

c

c

s

y

x

β

 oraz  

 







≤

±

±

≤

≤

±

±

≤

±

±

±

±

=

+

β

β

β

β

m

m

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

c

y

x

c

y

x

c

y

x

s

c

0

0

gdy  

  

gdy  

  

}

,

1

{

}

,

0

{

}

,

{

1

 

 

 

x

k–1

 

x

k–2

 

… 

x

–m+3

 

x

–m+2

 

x

–m+1

 

x

–m 

±

 

y

k–1

 

y

k–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

 

 

 

 

 

 

c

k–2

 

… 

 

 

 

 

 

c

k–1

 

s

k–2

 

 

 

 

 

 

c

k

 

s

k–1

 

 

 

 

 

 

 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–II 

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

  

 

• 

je li suma oryginalna  X+Y+Z+... ma  m składników, to suma: 

...

...

...)

(

...

1

2

1

1

0

...

0

V

R

U

r

v

u

r

v

u

Z

Y

X

n

i

i

i

n

i

i

i

n

i

i

i

n

i

i

i

i

i

+

+

=

+

+

+

=

+

+

=

+

+

∑

∑

∑

∑

+

=

=

−

=

+

=

β

β

β

β

 

 

ma około 1+log

β

m  składników, czyli znacznie mniej ni  X+Y+Z+.. 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–III 

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 liczba składników jest 

≤

β

+1

, 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

 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–IV 

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 

i

i

i

S

P

−

=

β

 

)

(

1

1

A

x

P

P

i

i

i

+

=

−

+

β

 

X

A

x

A

P

P

k

m

i

i

i

m

k

k

⋅

=

+

=

∑

−

−

=

−

1

}

{

β

β

 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–V 

Konstrukcja tabliczki mno enia w systemach naturalnych (1) 

• 

dla 1

≤

k

≤

β

−1

 cyframi iloczynu k

⋅

(

β

−1

) s  k

−1

 i 

β

– k  (suma równa 

β

– 1): 

0

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 przeniesie  … 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–VI 

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) 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–VII 

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 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–VIII 

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|  

|R

1

–R

2

| = |D| ,   0<

−

R

1

, R

2

< |D| 

X – R

i

= Q

i

⋅

D 

 
dzielenie znakowane (signed division) – znak reszty jest taki jak znak dzielnej 
dzielenie modularne (modulus division) – znak reszty jest zawsze dodatni  

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–IX 

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 

β

}

,...,

,

,...,

{

0

1

1

m

k

x

x

x

x

X

−

−

=

 oraz 

β

}

,...,

,

,...,

{

0

1

1

s

l

d

d

d

d

D

−

−

=

,  

to obliczony z dokładno ci  

β

–p

 iloraz X/D jest równy:  

i

l

k

p

i

i

p

l

k

l

k

q

q

q

q

q

Q

β

β

∑

+

−

−

=

−

−

+

−

=

=

1

0

1

}

,...

,...,

,

{

 

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) 

 

Działania 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

DZ–X 

Przybli enia ilorazu 

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

 

 

Dokładniejsze przybli enie to 

1

1

1

,

2

,

1

}

0

,...,

,

{

−

−

−

+

=

=

s

s

s

s

s

s

q

Q

Q

q

q

β

β

 takie,  e 

D

q

D

Q

X

R

D

q

s

s

s

s

s

1

1

1

,

1

1

1

)

1

(

−

−

−

−

+

<

−

=

≤

β

β

, 

D

D

q

R

R

s

s

s

1

1

1

1

2

0

−

−

−

<

−

=

≤

β

β

 

 

Kolejnymi przybli eniami ilorazu s  zatem  

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

 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–1 

Pozycyjne rozwini cie liczby w systemie naturalnym 

 

Jednoznaczn  reprezentacj  liczby X

≥

0 w systemie naturalnym o podstawie 

β

  

jest rozwi zanie równania 

X

x

x

x

x

x

k

m

i

i

i

m

k

=

=

∑

−

−

=

−

−

−

1

1

0

1

}

,...,

,

,...,

{

β

β

, gdzie 

}

1

...,

,

1

,

0

{

−

∈

β

i

x

 

 

Metoda tablicowa 

1. Obliczamy wszystkie potrzebne dodatnie pot gi podstawy 

β

n

< X i tyle pot g 

ujemnych, aby zapewni  wymagan  dokładno  reprezentacji 
problem: warto ci pot g ujemnych s  przybli one, np. 0,1

10

= 0,(00011)

2

 

2. Obliczamy cyfry metod  „odejmij i porównaj”: 

X

n–1

= X – q

β

n

> 0   ale X – ( q+1)

β

n

< 0, to x

n-1

=q

, 

X

n–2

= X

n–1

– p

β

n–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) 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–2 

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  wag /cyfry na najwy szej pozycji w systemach uzupełnieniowych 

 
Najprostsze s  algorytmy dla reprezentacji naturalnych 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–3 

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) 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–4 

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. 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  

 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–5 

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  F

r

= F

r–k

  to rozwini cie jest okresowe (okres ma k cyfr) 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–6 

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,  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  goto 1 

; powtarzaj dopóki mała dokładno  

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–7 

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 

β

= |{b

p

, …, b

1

, b

0

}

ω

| 

• 

wyniki {z

s–1

, z

s–1

, …, z

–r

}

β

 – w systemie o podstawie 

β

  (

ω

β

log

k

s

≤

) 

 

Konwersja ułamka okresowego 

Zamiana ułamka okresowego na ułamek wymierny 













−

+

=













−

+

=

−

−

−

−

−

−

−

−

−

1

1

1

1

)

...

(

...

,

0

1

1

c

c

k

c

c

k

c

k

k

k

z

x

z

x

z

z

x

x

β

β

β

β

β

β

β

 

 

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.  

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–8 

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 o w ó 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

. 

 

 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–9 

Konwersja podstawy skojarzonej w systemach naturalnych – 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

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

=

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

−

−

−

−

−

−

 

 
Przykład  (...)

10

→

(...)

8

→

(...)

2

  (8

3

=512, 8

2

=64, 8

–1

=0,125, 8

–2

=0,16625) 

2

8

2

0

1

2

3

64

1

10

010

000

,

001

010

011

011

02

,

3321

8

2

8

1

8

2

8

3

8

3

2

1

8

2

64

3

512

3

03125

,

1937

=

=

=

⋅

+

⋅

+

⋅

+

⋅

+

⋅

=

⋅

+

+

⋅

+

⋅

+

⋅

=

−

 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–10 

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

 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–11 

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

. 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–12 

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 

 

 

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

=

+

 … 

 
0,1

10

= 0,00011001100110011…

2

= 0,0(0011)

2 

 

Konwersja podstawy 

© Janusz Biernat,

 

01-06-Systemy liczbowe.doc, 6 pa

ź

dziernika 2006

 

KP–13 

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)

β

 

0,5(37)

10

  =

8

10

10

990

532

X

→

 

 

 

  0,5(37)

10

→

X

8 

 

 

  0,(386)

10

→

X

7 

×8

 

 

×8   

×8

 

  F

i 

 

×7

 

  F

i 

  0   

 

  0  5 37 37 37 …   

  0  (386) 

  x

–1

=

 

4  2 98 98 96  

 

x

–1

=

 

2  (702) 

x

–1

=

 

4 

10

10

10

10

990

4256

990

296

=

+

 

 

 

  2 98 98 98  

 

 

  (704) 

  x

–2

=

 

2  3 91 91 84 

 

x

–2

=

 

4  (928) 

x

–2

=

 

2 

10

10

10

10

990

2368

990

388

=

+

 

 

 

  3 91 91 91  

 

 

  (932) 

  x

–3

=

 

3  1 35 35 28 

 

x

–3

=

 

6  (524) 

x

–3

=

 

3 

10

10

10

10

990

3104

990

134

=

+

 

 

    1 35 35 35 

 

 

  (530)