Negatív alapú számrendszerek

Számrendszerek Negatív alapú számrendszerek

Negatív alapú számrendszerek Németh Bence

2015. március 4.

Németh Bence

Negatív alapú számrendszerek


Bevezetés Negatív számok

Bevezetés Számrendszerek Legyen b > 1 egy adott egész szám. Ekkor bármely N ≥ 0 egész szám egyértelműen felírható N=

m X

ak b k

k=1

alakban, ahol 0 ≤ ak < b egész szám.

Németh Bence




Bevezetés Számrendszerek Legyen b > 1 egy adott egész szám. Ekkor bármely N ≥ 0 egész szám egyértelműen felírható N=

m X

ak b k

k=1

alakban, ahol 0 ≤ ak < b egész szám. Elnevezések a b számot alapszámnak a 0, . . . , b − 1 számokat számjegyeknek (am am−1 . . . a1 a0 )b -t az N szám b alapú felírásának nevezzük a fenti definícióban. Németh Bence




Negatív számok

Mi a helyzet a negatív számokkal?

Németh Bence




Negatív számok

Előjel használata A számítógépek is így működnek, de a műveletek bonyolultabbak lesznek.

Németh Bence




Negatív számok

Előjel használata A számítógépek is így működnek, de a műveletek bonyolultabbak lesznek. Negatív számjegyek Megengedünk a számjegyek közt negatív számokat is.

Németh Bence




Negatív számok

Előjel használata A számítógépek is így működnek, de a műveletek bonyolultabbak lesznek. Negatív számjegyek Megengedünk a számjegyek közt negatív számokat is. Negatív alap Negatív számot választunk a számrendszer alapjának.

Németh Bence


Bevezetés Műveletek Aritmetika



Negatív alapú számrendszer Legyen b < −1 egy adott negatív egész szám. Ekkor bármely N egész szám egyértelműen felírható N=

m X

ak b k

k=1

alakban, ahol 0 ≤ ak < |b| egész szám.

Németh Bence





Egzisztencia Legyen q0 = N, továbbá qk = qk+1 b + ak Vagyis ak ≡ qk mod b és qk+1 = Mivel azonban qi -k egészek és

qk −ak b .

|q0 | > |q1 | > |q2 | > . . . így az algoritmus biztosan véges lépésben befejeződik.

Németh Bence





Unicitás Tegyük fel, hogy létezik két különböző felírás a = (am am−1 . . . a1 a0 )b és c = (cm cm−1 . . . c1 c0 )b Az előbbi algoritmus alaján q0 ≡ a0 ≡ c0 mod b ⇒ a0 = c0 q1 ≡ a1 ≡ c1 mod b ⇒ a1 = c1 .. . qm ≡ am ≡ cm mod b ⇒ am = cm

Németh Bence




Műveletek

Előjel meghatározása Ha a szám felírása páratlan sok jegyből áll akkor pozitív, ha páros sokból akkor negatív. Rendezés Vegyük a legnagyobb helyiértéket, ahol a felírásban a jegyek eltérnek! Ha párosadik helyen térnek el, akkor az a nagyobb, amelyikben nagyobb a jegy értéke, ha páratlanadik helyen térnek el, akkor fordítva.

Németh Bence




Aritmetika

Továbbvitel Az összes művelet a megszokott módon hajtható végre. Ez egyetlen különbséget a továbbvitt jegyek fogják jelenteni. |b| = (1|b| − 10)b Ha a továbbvitt jegy |b|-ben ak lenne, akkor az 1|b| − ak jegyeket kell továbbvinnünk.

Németh Bence




Műveletek

Összeadás

+

2 1

Németh Bence

0 0

4 7




Műveletek

Összeadás

+

1 2 1

Németh Bence

9 0 0

4 7 1




Műveletek

Összeadás

+

1 2 1

Németh Bence

0 0 9

4 7 1




Műveletek

Összeadás

+

2 1 4

Németh Bence

0 0 9

4 7 1




Műveletek

Szorzás 2 X

Németh Bence

0

4 7




Műveletek

Szorzás 1 2 X

Németh Bence

8 0

4 7 8




Műveletek

Szorzás 1 2

0

X 8

Németh Bence

4 7 8




Műveletek

Szorzás 1

9 2

0

5

8

X

Németh Bence

4 7 8




Műveletek

Szorzás

1

X 9

Németh Bence

2

0

5

8

4 7 8




Műveletek

Kivonás

-

Németh Bence

5 4

7 8




Műveletek

Kivonás

-

Németh Bence

1 5 4

7 8 9




Műveletek

Kivonás

-

Németh Bence

5 4 2

7 8 9




Műveletek Összeadás

+

Németh Bence

5 2

5 7





1 +

Németh Bence

9 5 2

5 7 2





1

9 1 +

Németh Bence

5 2 6

5 7 2




Műveletek Összeadás 1

9 1

+ 0

Németh Bence

5 2 6

5 7 2





9 1

0

Németh Bence

+ 0

5 2 6

5 7 2





9 1

0

+ 0

5 2 6

5 7 2

Megoldás Ha két legfeljebb m hosszú számot összeadunk, akkor az összeg legfeljebb m + 2 hosszú. Németh Bence




Törtek Legyen b < −1 egy adott negatív egész szám. Ekkor bármely valós szám egyértelműen felírható m X

ak b k

k=−∞

alakban, ahol 0 ≤ ak < |b| egész szám.

Németh Bence




Törtek Legyen b < −1 egy adott negatív egész szám. Ekkor bármely valós szám egyértelműen felírható m X

ak b k

k=−∞

alakban, ahol 0 ≤ ak < |b| egész szám. Végtelen tizedes törtek A kétféle ábrázolás problémája itt is fennáll. 1 = (.010101 . . . ) = (1.101010 . . . ) 3 Németh Bence




Köszönöm a figyelmet!

Németh Bence


Negatív alapú számrendszerek

Recommend Documents