Negatív alapú számrendszer

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

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

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

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_{i}$ 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 egyjegyű 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

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{aligned}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{aligned}}

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 negaternary(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

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

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

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

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

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

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

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

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

↑ 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.
↑ Marczynski, R. W., "The First Seven Years of Polish Computing" Archiválva 2011. július 19-i dátummal a Wayback Machine-ben, IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
↑ D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"

Források szerkesztés

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

Számrendszer

[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" Archiválva 2011. július 19-i dátummal a Wayback Machine-ben, 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"

[1]

[2]

[3]