Naar inhoud springen

Negatief grondtal

Uit Wikipedia, de vrije encyclopedie

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

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[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 een even aantal cijfers hebben en positieve getallen een oneven aantal cijfers hebben.

Converteren naar negatief grondtal

[bewerken | brontekst bewerken]

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.

Naar negabinair

[bewerken | brontekst bewerken]
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

[bewerken | brontekst bewerken]
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

[bewerken | brontekst bewerken]
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

[bewerken | brontekst bewerken]

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

Som Output Commentaar
Bit Carry
−2 010−2 0 1 01−2 −2 komt enkel voor bij aftrekken.
−1 011−2 1 1 01−2
0 000−2 0 0 00−2
1 001−2 1 0 00−2
2 110−2 0 −1 11−2
3 111−2 1 −1 11−2 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:,

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

[bewerken | brontekst bewerken]

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

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

[bewerken | brontekst bewerken]

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

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

[bewerken | brontekst bewerken]