Negatief grondtal

Een positiestelsel kan een negatief grondtal hebben. Deze talstelsels zijn voor het eerst beschreven door Vittorio Grunwald in zijn werk Giornale di Matematiche di Battaglini uit 1885. Naderhand zijn negatieve talselsels herontdekt door A. J. Kempner in 1936 en Z. Pawlak and A. Wakulicz in 1959.

Met een negatief talstelsel is het mogelijk positieve en negatieve getallen te laten zien zonder een minteken te gebruiken. De naam van een negatief talstelsel wordt gevormd door de prefix nega- toe te voegen aan de naam van het positieve talstelsel; bijvoorbeeld, negadecimaal (grondtal -10) voor decimaal (grondtal 10), negabinair (grondtal -2) voor binair (grondtal 2), negaternair (grondtal -3) voor ternair (grondtal 3) en negaquaternair (grondtal -4) voor quaternair (grondtal 4).

Notatie

Schrijven we het grondtal als $-r$ , dan kan elk geheel getal $a$ op een unieke manier geschreven worden als:

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

waarbij elk cijfer $d_{k}$ een geheel getal is gaande van $0$ tot $r-1$ . De grondtal $-r$ expansie van $a$ wordt dan gegeven door $d_{n}d_{n-1}\dots d_{1}d_{0}$ .

Met het grondtal –2 als voorbeeld, worden de eerste getallen:

{\begin{matrix}0&=&0&=&\qquad \qquad \qquad \qquad \qquad 0\times (-2)^{0}&=&0\\1&=&1&=&\qquad \qquad \qquad \qquad \qquad 1\times (-2)^{0}&=&1\\10&=&-2&=&\qquad \qquad \quad 1\times (-2)^{1}+0\times (-2)^{0}&=&-2+0\\11&=&-1&=&\qquad \qquad \quad 1\times (-2)^{1}+1\times (-2)^{0}&=&-2+1\\100&=&4&=&1\times (-2)^{2}+0\times (-2)^{1}+0\times (-2)^{0}&=&4+0+0\\101&=&5&=&1\times (-2)^{2}+0\times (-2)^{1}+1\times (-2)^{0}&=&4+0+1\\110&=&2&=&1\times (-2)^{2}+1\times (-2)^{1}+0\times (-2)^{0}&=&4-2+0\\111&=&3&=&1\times (-2)^{2}+1\times (-2)^{1}+1\times (-2)^{0}&=&4-2+1\end{matrix}}

Uit het bovenstaande voorbeeld blijkt dat ook de negatieve gehele getallen voorgesteld kunnen worden zonder gebruik te maken van het minteken. Dat het systeem tot dusver niet toegepast wordt, heeft te maken met de "springerige" aard van de opeenvolgende waarden. Zo hebben de eerste 16 waarden van met het grondtal -2 achtereenvolgens de volgende decimale waarden^[1]:

0, 1, –2, –1, 4, 5, 2, 3, –8, –7, –10, –9, –4, –3, –6, –5

Dit werkt niet alleen met –2, maar met elk negatief geheel getal dat geen –1 is.

Onderstaande tabel geeft de expansie van enkele getallen in zijn positieve en corresponderende negatieve grondtalrepresentatie.

Decimaal	Negadecimaal	Binair	Negabinair	Ternair	Negaternair	Gebalanceerd ternair	Quaternair	Negaquaternair
−15	25	−1111	110001	−120	1220	T110	−33	1301
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
−5	15	−101	1111	−12	21	T11	−11	23
−4	16	−100	1100	−11	22	TT	−10	10
−3	17	−11	1101	−10	10	T0	−3	11
−2	18	−10	10	−2	11	T1	−2	12
−1	19	−1	11	−1	12	T	−1	13
0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1
2	2	10	110	2	2	1T	2	2
3	3	11	111	10	120	10	3	3
4	4	100	100	11	121	11	10	130
5	5	101	101	12	122	1TT	11	131
6	6	110	11010	20	110	1T0	12	132
7	7	111	11011	21	111	1T1	13	133
8	8	1000	11000	22	112	10T	20	120
9	9	1001	11001	100	100	100	21	121
10	190	1010	11110	101	101	101	22	122
11	191	1011	11111	102	102	11T	23	123
12	192	1100	11100	110	220	110	30	110
13	193	1101	11101	111	221	111	31	111
14	194	1110	10010	112	222	1TTT	32	112
15	195	1111	10011	120	210	1TT0	33	113
16	196	10000	10000	121	211	1TT1	40	100
17	197	10001	10001	122	212	1T0T	41	101

Merk op dat negatieve getallen in grondtal $-r$ een even aantal cijfers hebben en positieve getallen een oneven aantal cijfers hebben.

Converteren naar negatief grondtal

Algoritme

De grondtal $-r$ expansie van een getal kan gevonden worden door herhaaldelijk te delen door $-r$ en de niet-negatieve resten aan elkaar te plakken. Merk op dat als $a/b=c$ rest $d$ , geldt dat $bc+d=a$ en dus $d=a-bc$ . Om het juiste resultaat te bekomen dient men $c$ zo te kiezen dat $d$ minimaal en niet negatief is.

Bijvoorbeeld, om 146 in decimaal naar negaternair te converteren:

{\begin{array}{rr}146\div (-3)=&-48~\operatorname {rest} ~2\\-48\div (-3)=&16~\operatorname {rest} ~0\\16\div (-3)=&-5~\operatorname {rest} ~1\\-5\div (-3)=&2~\operatorname {rest} ~1\\2\div (-3)=&0~\operatorname {rest} ~2\end{array}}

Als we de resten van achter naar voren lezen krijgen we $146_{10}=2(-3)^{4}+(-3)^{3}+(-3)^{2}+2(-3)^{0}=21102_{-3}$ als resultaat.

Let op: in de meeste programmeertalen wordt het resultaat van een integer deling tussen twee negatieve getallen afgerond naar nul, wat een negatieve rest kan opleveren. In zo'n geval hebben we dat $a=(-r)c+d=(-r)c+d-r+r=(-r)(c+1)+(d+r)$ . Omdat $|d|<r$ is $(d+r)$ de positieve rest. Dus, om het correcte resultaat in zo'n geval te krijgen dient een computerimplementatie 1 aan het quotiënt en $r$ aan de rest toe te voegen.

Code

Naar negabinair

C#

static string ToNegabinary(int value)
{
	string result = string.Empty;

	while (value != 0)
	{
		int remainder = value % -2;
		value = value / -2;

		if (remainder < 0)
		{
			remainder += 2;
			value += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}

Of eenvoudiger (C implementatie):^[2]

unsigned int toNegaBinary(unsigned int value) // invoer in binair
{
	unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010
	return (value + Schroeppel2) ^ Schroeppel2; // exclusieve OF
	// resulterende unsigned int interpreteren als string met elementen ε {0,1}
}

Naar negaquaternair

C#

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;
}

Of eenvoudiger (C implementatie):

unsigned int toNegaQuaternary(unsigned int value) // invoer in binair
{
	unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030
	return (value + Schroeppel4) ^ Schroeppel4; // exclusieve OF
	// resulterende unsigned int interpreteren als string met elementen ε {0,1,2,3}
}

Naar willekeurig negatief grondtal

Java

public List<Integer> negativeBase(int integer, int base) {
    List<Integer> digits = new ArrayList<>();
    while (integer != 0) {
        int i = integer % base;
        integer /= base;
        if(i < 0) {
            i += Math.abs(base);
            integer++;
        }
        digits.add(0, i);
    }
    return digits;
}

Wiskundige operaties

Optellen

Het optellen van twee negabinaire getallen gebeurt bit per bit, startende met de minst significante bits.

Som		Output			Commentaar
Som		Bit	Carry		Commentaar
−2	010₋₂	0	1	01₋₂	−2 komt enkel voor bij aftrekken.
−1	011₋₂	1	1	01₋₂
0	000₋₂	0	0	00₋₂
1	001₋₂	1	0	00₋₂
2	110₋₂	0	−1	11₋₂
3	111₋₂	1	−1	11₋₂	3 komt enkel voor bij optellen.

De tweede rij van de tabel toont bv. dat −1 = 1 + 1 × −2; de vijfde rij zegt dat 2 = 0 + −1 × −2; etc.

Bijvoorbeeld: $1010101_{-2}(1+4+16+64=85)+1110100_{-2}(4+16-32+64=52)$ ,

Carry:          1 −1  0 −1  1 −1  0  0  0
Eerste getal:         1  0  1  0  1  0  1
Tweede getal:         1  1  1  0  1  0  0 +
               --------------------------
Getal:          1 −1  2  0  3 −1  2  0  1
Resultaat:      1  1  0  0  1  1  0  0  1
Carry:          0  1 −1  0 −1  1 −1  0  0

Het resultaat is dus $110011001_{-2}(1-8+16-128+256=137)$ .

Andere methode

Een andere methode om op te tellen bestaat eruit een extra carry bit te propageren naar de volgende positie.

Extra carry:       1  1  0  1  0  0  0     
Carry:          1  0  1  1  0  1  0  0  0
Eerste getal:         1  0  1  0  1  0  1
Tweede getal:         1  1  1  0  1  0  0 +
               --------------------------
Resultaat:      1  1  0  0  1  1  0  0  1

Aftrekken

Om getallen van elkaar af te trekken dient, dient het tweede getal vermenigvuldigd te worden met -1 (één plaats schuiven naar links en optellen) waarna de getallen opgeteld worden.

Bijvoorbeeld: $1101001_{-2}(1-8-32+64=25)-1110100_{-2}(4+16-32+64=52)$ ,

Carry:          0  1 −1  1  0  0  0
Eerste getal:   1  1  0  1  0  0  1
Tweede getal:  −1 −1 −1  0 −1  0  0 +
               --------------------
Getal:          0  1 −2  2 −1  0  1
Resultaat:      0  1  0  0  1  0  1
Carry:          0  0  1 −1  1  0  0

Het resultaat is dus $100101_{-2}(1+4-32=-27)$ .

Vermenigvuldigen

Naar links schuiven is vermenigvuldigen met -2 en naar rechts schuiven is delen door -2.

Om te vermenigvuldigen volgt men dezelfde stappen als het algoritme in decimaal en binair maar past men de regels van negabinair toe tijdens het optellen.

Eerste getal:                   1  1  1  0  1  1  0
Tweede getal:                   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                   +
              -------------------------------------
Carry:        0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0
Getal:        1  0  2  1  2  2  2  3  2  0  2  1  0
Resultaat:    1  0  0  1  0  0  0  1  0  0  0  1  0
Carry:           0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0

Grafieken

Opmerkelijk is dat de lijn door de x-as gaat bij de positieve vorm van iedere macht van het grondtal. Bij grondtal –2 snijdt de lijn op 2, 4, 8, 16, 32... Bij grondtal -10 gebeurt dat bij 10, 100, 1000...

Mogelijke toepassingen van dit soort getallen zijn te vinden in de cryptografie^[bron?] en bij systemen waar alleen cijfers gebruikt kunnen worden (zonder tekens als de -).

Externe links

Bronnen, noten en/of referenties

Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Negative base op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.

↑ rij A053985 in OEIS
↑ Zie de MathWorld Negabinary link.

[1] rij A053985 in OEIS

[2] Zie de MathWorld Negabinary link.

[1]

[2]