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 , dan kan elk geheel getal  op een unieke manier geschreven worden als:

waarbij elk cijfer een geheel getal is gaande van  tot . De grondtal  expansie van  wordt dan gegeven door .

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

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:
 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.

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

Converteren naar negatief grondtal

Algoritme 
De grondtal  expansie van een getal kan gevonden worden door herhaaldelijk te delen door  en de niet-negatieve resten aan elkaar te plakken. Merk op dat als  rest , geldt dat  en dus . Om het juiste resultaat te bekomen dient men  zo te kiezen dat  minimaal en niet negatief is.

Bijvoorbeeld, om 146 in decimaal naar negaternair te converteren:

Als we de resten van achter naar voren lezen krijgen we 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 . Omdat  is  de positieve rest. Dus, om het correcte resultaat in zo'n geval te krijgen dient een computerimplementatie 1 aan het quotiënt en  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):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.

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

Bijvoorbeeld:,

 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 .

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:,
 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.

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 en bij systemen waar alleen cijfers gebruikt kunnen worden (zonder tekens als de -).

Externe links 
 http://mathworld.wolfram.com/Negabinary.html
 http://mathworld.wolfram.com/Negadecimal.html

Getal
Getalsysteem