Negatív alapú számrendszer

A Wikipédiából, a szabad enciklopédiából

A negatív alapú számrendszerek helyi értékes számjelölési rendszerek, ahol az alapszám negatív. Általában felteszik, hogy az alapszám -1-nél kisebb.

Ezekben a számrendszerekben is ábrázolható minden valós szám, ahogy a pozitív alapú számrendszerekben. A negatív számok előjel nélkül is ábrázolhatók, viszont a számok összehasonlítása és a műveletek bonyolultabbak lesznek. Az előjelről szóló információt a szám hossza tárolja; a negatív számok egy jeggyel hosszabbak az ellentettjüknél.

Hogy pozitív alapú megfelelőjüktől megkülönböztessék ezeket a számrendszereket, annak neve elé teszik a nega- előtagot. Például a -2 alapú számrendszer negabináris, a -3 alapú negaternáris, a -10 alapú negadecimális, és így tovább.[1]

Példa[szerkesztés | forrásszöveg szerkesztése]

Tekintsük a 12 243 ábrázolás jelentését, ahol az alap -10:

\scriptstyle b^4 többszörösei
(10 000)
\scriptstyle b^3 többszörösei
(−1000)
\scriptstyle b^2 többszörösei
(100)
\scriptstyle b^1 többszörösei
(−10)
\scriptstyle b^0 többszörösei
(1)
1 2 2 4 3

Mivel 10 000 + (−2000) + 200 + (−40) + 3 = 8163, a negadecimális 12 243 jelentése 8163 a tízes számrendszerben.

Története[szerkesztés | forrásszöveg szerkesztése]

Elsőként Vittorio Grünwald foglalkozott negatív számrendszerekkel a Giornale di Matematiche di Battaglini című művében, ami 1885-ben jelent meg. Grünwald algoritmusokat adott az összeadásra, kivonásra, szorzásra, osztásra, gyökvonásra, oszthatóság megállapítására és a más számrendszerre való áttérésre. Később egymástól függetlenül újrafelfedezte A. J. Kempner 1936-ban és Zdzisław Pawlak és A. Wakulicz 1959-ben.

Z. Pawlak és A. Lazarkiewicz elképzelései alapján a lengyel Matematikai Intézet Varsóban 1957 és 1959 között megépítette a BINEG nevű számítógépet, amely implementálta a negabináris számrendszert. Azóta a megvalósítások ritkák.[2]

Használata[szerkesztés | forrásszöveg szerkesztése]

Jelölje az alapot -r. Ekkor minden egész szám egyértelműen felírható, mint:

a = \sum_{i=0}^{n}d_{i}(-r)^{i}

ahol minden \scriptstyle d_k jegy egy 0 és \scriptstyle r - 1 közötti egész, és az első jegy pozitív, ha az n is pozitív. Ekkor az a egész -r alapú számrendszerben \scriptstyle d_n d_{n-1} \ldots d_1 d_0 alakú.

A negatív alapú számrendszerek összehasonlíthatók az előjeles jegyeket használó számrendszerekkel, köztük a kiegyensúlyozott hármas alapú számrendszerrel. Az előjeles jegyek lehetnek pozitívok vagy negatívak is, amit nyomokban több nyelvben is fellelhetünk. A kiegyensúlyozott hármas számrendszerben a számjegyek 0, 1 és -1; ezekkel a jegyekkel minden valós szám felírható.

Vannak számok, amelyek a -r alapú számrendszerben ugyanúgy néznek ki, mint az r alapú számrendszerben. Erre triviális példák a nem negatív egy jegyű számok. Kevésbé triviális a 107 a tízes és a negadecimális számrendszerben. Hasonlóan, a

17=2^4+2^0=(-2)^4+(-2)^0,

így 10001 a kettes számrendszerben, és 10001 a negabináris számrendszerben.

Negatív alapú számrendszerben a negatív számok páros, a pozitív számok páratlan hosszúak.

Néhány szám pozitív és a megfelelő negatív alapú számrendszerben:

Decimális Negadecimális Bináris Negabináris Ternáris Negaternáris
−15 25 −1111 110001 −120 1220
 :  :  :  :  :  :
−5 15 −101 1111 −12 21
−4 16 −100 1100 −11 22
−3 17 −11 1101 −10 10
−2 18 −10 10 −2 11
−1 19 −1 11 −1 12
0 0 0 0 0 0
1 1 1 1 1 1
2 2 10 110 2 2
3 3 11 111 10 120
4 4 100 100 11 121
5 5 101 101 12 122
6 6 110 11010 20 110
7 7 111 11011 21 111
8 8 1000 11000 22 112
9 9 1001 11001 100 100
10 190 1010 11110 101 101
11 191 1011 11111 102 102
12 192 1100 11100 110 220
13 193 1101 11101 111 221
14 194 1110 10010 112 222
15 195 1111 10011 120 210
16 195 10000 10000 121 211
17 197 10001 10001 122 212

Átváltás[szerkesztés | forrásszöveg szerkesztése]

Egy szám alakja a \scriptstyle -r alapú számrendszerben a pozitív számrendszerekhez hasonlóan, \scriptstyle -r-rel való sorozatos osztással áll elő. Ügyelnünk kell arra, hogy a maradékok nem negatívak, és a \scriptstyle 0, 1,\ldots r-1 számok közül kerülnek ki. Ezeket fordított sorrendben összefűzve kapjuk a szám ábrázolását. Vagyis, ha \scriptstyle a / b = c, és a maradék d, akkor \scriptstyle bc + d = a. Például:

\begin{align}
 146 & ~/~ -3 = & -48, & ~\mbox{marad}~ 2 \\
 -48 & ~/~ -3 = &  16, & ~\mbox{marad}~ 0 \\
  16 & ~/~ -3 = &  -5, & ~\mbox{marad}~ 1 \\
  -5 & ~/~ -3 = &   2, & ~\mbox{marad}~ 1 \\
   2 & ~/~ -3 = &   0, & ~\mbox{marad}~ 2 \\
\end{align}

Tehát a 146 negaternáris számrendszerben 21 102.

A legtöbb programozási nyelvben a negatív számok osztási maradékát negatív előjellel képzik. Ekkor \scriptstyle a = (-r)c + d = (-r)c + d - r + r = (-r)(c + 1) + (d + r). Mivel \scriptstyle |d| < r, a pozitív maradék \scriptstyle (d + r). Emiatt a programokban a hányadoshoz 1-et, a maradékhoz r-et kell hozzáadni.

Az implementáció Pythonban:

def negaternary(i):
    digits = ''
    if not i:
        digits = '0'
    else:
        while i != 0:
            i, remainder = divmod(i, -3)
            if remainder < 0:
                i, remainder = i + 1, remainder + 3
            digits = str(remainder)+ digits
    return digits

C#-ban:

static string negatenary(int value)
{
	string result = string.Empty;
 
	while (value != 0)
	{
		int remainder = value % -3;
		value = value / -3;
 
		if (remainder < 0)
		{
			remainder += 3;
			value += 1;
		}
 
		result = remainder.ToString() + result;
	}
 
	return result;
}

Common Lispben:

(defun negaternary (i)
  (if (zerop i)
      "0"
      (let ((digits "")
	    (rem 0))
	(loop while (not (zerop i)) do
	     (progn
	       (multiple-value-setq (i rem) (truncate i -3))
	       (when (minusp rem)
	         (incf i)
	         (incf rem 3))
	       (setf digits (concatenate 'string (write-to-string rem) digits))))
	digits)))

Alapműveletek[szerkesztés | forrásszöveg szerkesztése]

A következő szakaszokban a számpéldák a negabináris számrendszerből valók. Más negatív alapú számrendszerekben a számítások hasonlóan végezhetők el.

Összeadás[szerkesztés | forrásszöveg szerkesztése]

Két negabináris szám összeadásakor az átvitel kezdetben nulla, és az összeadást a legalacsonyabb helyi értéktől kezdve a magasabb helyi értékek felé haladva végezzük az átvitel figyelembe vételével. Az összeg bitjei és az átvitel az alábbi táblázat szerint számítható:

Összeg Bit Átvitel Megjegyzés
−2 0 1 Csak kivonás esetén fordulhat elő
−1 1 1
0 0 0
1 1 0
2 0 −1
3 1 −1 Csak összeadás esetén fordulhat elő

Példaként adjuk össze az 1010101 (1 + 4 + 16 + 64 = 85) és az 1110100 (4 + 16 − 32 + 64 = 52) számokat:

átvitel:             1 −1  0 −1  1 −1  0  0  0
első szám:                 1  0  1  0  1  0  1
második szám:              1  1  1  0  1  0  0 +
                      --------------------------
bitenkénti összegek: 1 −1  2  0  3 −1  2  0  1
bit (eredmény):      1  1  0  0  1  1  0  0  1
átvitel:             0  1 −1  0 −1  1 −1  0  0

így az összeg 110011001 (1 − 8 + 16 − 128 + 256 = 137).

Alternatív algoritmus[szerkesztés | forrásszöveg szerkesztése]

Ha az átvitel átlépi az alap ellentettjét, akkor extra átvitel keletkezik, amit a következő utáni jegynél kell számításba venni:

extra átvitel:       1  1  0  1  0  0  0   
átvitel:          1  0  1  1  0  1  0  0  0
első szám:              1  0  1  0  1  0  1
második szám:           1  1  1  0  1  0  0 +
               --------------------------
összeg:           1  1  0  0  1  1  0  0  1

Kivonás[szerkesztés | forrásszöveg szerkesztése]

Kivonáskor a kivonandó minden bitjét megszorozzuk mínusz eggyel, és összeadjuk a kisebbítendővel a fenti táblázat szerint. Példaként vonjunk ki 1101001 (1 − 8 − 32 + 64 = 25)-ből 1110100 (4 + 16 − 32 + 64 = 52)-t:

átvitel:            0  1 −1  1  0  0  0
első szám:          1  1  0  1  0  0  1
második szám:      −1 −1 −1  0 −1  0  0 +
                    --------------------
bitenkénti összeg:  0  1 −2  2 −1  0  1
bit (összeg):       0  1  0  0  1  0  1
átvitel:            0  0  1 −1  1  0  0

így az eredmény 100101 (1 + 4 −32 = −27).

A szám ellentettjének kiszámítására vonjuk ki a számot nullából.

Szorzás[szerkesztés | forrásszöveg szerkesztése]

A balra való eltolás -2-vel szoroz, a jobbra való eltolás -2-vel oszt. A szorzás megfelel a kettes számrendszerbeli szorzásnak, de a fenti módszerrel kell a részösszegeket összeadni.

első szám:                             1  1  1  0  1  1  0
második szám:                          1  0  1  1  0  1  1 *
                           -------------------------------------
                                       1  1  1  0  1  1  0
                                    1  1  1  0  1  1  0

                              1  1  1  0  1  1  0
                           1  1  1  0  1  1  0

                     1  1  1  0  1  1  0                   +
                        -------------------------------------
átvitel:             0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0
bitenkénti összeg:   1  0  2  1  2  2  2  3  2  0  2  1  0
bit (szorzat):       1  0  0  1  0  0  0  1  0  0  0  1  0
átvitel:                0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0

Minden oszlopra az átvitelt hozzáadjuk a bitenkénti összeghez; az eredményt maradékosan osztjuk -2. A hányados az átvitel, és a maradék a szorzat bitje.

Törtek[szerkesztés | forrásszöveg szerkesztése]

A negatív alapú számrendszerekben is ábrázolhatók törtek a pozitív alapokhoz hasonlóan, a tizedesvessző után írt jegyekkel.

A véges tizedestörtté alakításának az a feltétele, hogy a tört nevezője osztója legyen az alap egy hatványának. Minden törtszám ábrázolható végtelen szakaszos tizedestörtként.

Nem egyértelmű reprezentációk[szerkesztés | forrásszöveg szerkesztése]

A pozitív alapoktól eltérően az egészeknek nincs alternatív ábrázolása. Azonban ez nem minden törtre igaz. Például a negaternáris rendszerben az 1/4 kétféle reprezentációja:

0,(02)\ldots_{(-3)} = \frac{1}{4} = 1,(20)\ldots_{(-3)}.

Az efféle nem egyértelmű reprezentációk abból adódnak, hogy tekintjük a legnagyobb 0 egészrészű és a legkisebb 1 egészrészű reprezentációkat, és belátjuk, hogy egyenlőek. A nem egyértelműen reprezentálható törtek alakja:

\frac{ar + 1}{b(r + 1)}.

Komplex bázisok[szerkesztés | forrásszöveg szerkesztése]

Ahogy a negatív alapú számrendszerek lehetővé teszik a valós számok előjel nélküli reprezentációját, úgy az alkalmas komplex számok közül egyet kiválasztva ábrázolhatók a Gauss-egészek. Donald Knuth 1955-ben javasolta a 2i alapú számrendszert.[3]

Az imaginárius alapú számrendszerek hasonlóak a negatív alapú számrendszerekhez, mivel egy ilyen bázisban ábrázolt számnál könnyen elkülöníthető a valós és a képzetes rész. Az INTERCAL-72 jelölésével:

x(2i) + (2i)y(2i) = x(2i) ¢ y(2i).

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Knuth 1998 és Weisstein hivatkozik a negadecimális számrendszerre. A Knuth 1998 tartalomjegyzékében szerepel a negabináris elnevezés, ami Weisstein-nél is előfordul. A negaternáris rendszerről szó van itt is: Petkovšek, Marko (1990), "Ambiguous numbers are dense", The American Mathematical Monthly 97 (5): 408–411, ISSN 0002-9890, DOI 10.2307/2324393.
  2. Marczynski, R. W., "The First Seven Years of Polish Computing", IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
  3. D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"

Források[szerkesztés | forrásszöveg szerkesztése]

  • Vittorio Grünwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
  • A. J. Kempner. (1936), 610-617
  • Z. Pawlak and A. Wakulicz Bulletin de l'Academie Polonaise des Scienses, Classe III, 5 (1957), 233-236; Serie des sciences techniques 7 (1959), 713-721
  • L. Wadel IRE Transactions EC-6 1957, 123
  • N. M. Blachman, Communications of the ACM (1961), 257
  • IEEE Transactions 1963, 274-276
  • Computer Design May 1967, 52-63
  • R. W. Marczynski, Annotated History of Computing, 1980, 37-48

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]