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. 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 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):Zie de MathWorld Negabinary link.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 Bit Carry −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:,
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 Bestand:Grondtalmintwee.PNG Bestand:Grondtalmindrie.PNG Bestand:Grondtalminvier.PNG Bestand:Grondtalminvijf.PNG Bestand:Grondtalmintien.PNG
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
Categorie:Getal Categorie:Getalsysteem