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:
többszörösei (10 000) |
többszörösei (−1000) |
többszörösei (100) |
többszörösei (−10) |
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:
ahol minden jegy egy 0 és 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 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
í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 alapú számrendszerben a pozitív számrendszerekhez hasonlóan, -rel való sorozatos osztással áll elő. Ügyelnünk kell arra, hogy a maradékok nem negatívak, és a számok közül kerülnek ki. Ezeket fordított sorrendben összefűzve kapjuk a szám ábrázolását. Vagyis, ha , és a maradék , akkor . Például:
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 . Mivel , a pozitív maradék . 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;
}
(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:
- .
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:
- .
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