Waar de notatie tekortschiet
Getallen die te groot zijn, en getallen die niet passen
Na deze les kan je:
- voorspellen wat een teller van vaste breedte doet wanneer hij zijn hoogste waarde voorbijgaat
- beoordelen of een breuk exact in binair past
- uitleggen waarom een computer sommige heel gewone kommagetallen niet exact kan bewaren, en wat dat betekent voor het vergelijken ervan
Een byte is acht bits, en dat aantal ligt vast. Op papier schrijf je er een cijfer bij zodra je er een nodig hebt, maar een computer heeft die ruimte niet. Deze les gaat over wat daaruit volgt. Je botst op drie manieren tegen die grens aan. Het getal is te groot voor de bits die er zijn. De patronen raken op. Of het getal past er principieel niet in, hoeveel bits je er ook aan geeft.
1 Als de teller overloopt
Zet een byte op zijn hoogste waarde, \(11111111_2\), en tel er \(1\) bij op. Uit de eerste les van deze reeks weet je dat een rij van acht enen samen \(2^8 - 1 = 255\) is, dus precies één tekort voor \(256\). Binair optellen levert dan
\[ 11111111_2 + 1 = 100000000_2 = 256 . \]
Die som klopt, en ze past niet. Het antwoord heeft negen bits nodig en de byte heeft er acht. Het negende bit bestaat eenvoudigweg niet en valt weg. Wat overblijft is \(00000000_2\), dus \(0\). De teller is rondgelopen. Dat verschijnsel heet overloop, in het Engels overflow, en dat is de term die je in foutmeldingen en documentatie zal tegenkomen.
Dit is geen randgeval maar de regel. Een computer rekent binnen een vast aantal bits, en alles wat daarbuiten valt, verdwijnt. Elke optelling verloopt daarmee in werkelijkheid modulo \(2^n\), zoals een kilometerteller die na \(999\,999\) opnieuw bij nul begint. Staat een byte op \(200\) en komt er \(100\) bij, dan is het resultaat niet \(300\) maar \(300 \bmod 256 = 44\). In Python schrijf je die rest als 300 % 256, met het procentteken als operator voor “de rest bij deling”.
Zo’n overloop gebeurt stil. Er komt geen foutmelding, want een controle bij elke optelling zou de machine merkbaar vertragen.
Op 4 juni 1996 ging Ariane 5, vlucht V-88, zevenendertig seconden na de start verloren. Een snelheidswaarde werd van een kommagetal omgezet naar een geheel getal van \(16\) bits, paste daar niet in, en de besturing schakelde uit. De schade bedroeg meer dan een half miljard euro in hedendaags geld.
Python zelf loopt niet over. Gehele getallen groeien er mee met de waarde die ze moeten bevatten, wat gebruiksvriendelijk is en trager. Heel wat reken- en machinelearningbibliotheken voor Python zijn mede daarom in C of C++ geschreven, en daar ligt de breedte wel vast.
2 Als de adressen opraken
Elk toestel op het internet heeft een IP-adres, geschreven als vier bytes. Dit adres herken je misschien van je eigen router.
192 168 0 1
11000000 . 10101000 . 00000000 . 00000001Vier bytes van acht bits, samen \(32\) bits, en elk getal loopt van \(0\) tot \(255\). Dat geeft \(2^{32}\) IP-adressen, ruim vier miljard. Dat aantal ligt vast, dus vroeg of laat is het laatste adres uitgedeeld, en dat is intussen gebeurd. De oplossing is een ruimere notatie: IPv6 telt \(128\) bits per adres.
Toen het formaat van IPv4 werd afgesproken in de jaren zeventig, leek vier miljard eindeloos: er hingen een paar honderd machines aan het netwerk. In februari 2011 deelde de centrale beheerder zijn laatste blokken uit. Europa ging het jaar daarop op rantsoen. Sindsdien wordt er gedeeld: tientallen toestellen achter één publiek IP-adres.
IPv6 bestaat als norm sinds 1998 en is nog altijd niet overal ingevoerd. Een notatie vervangen die overal ingebakken zit, is moeilijker dan ze meteen ruim genoeg kiezen.
3 Cijfers na de komma
Tot hier ging het over gehele getallen. De regel uit de eerste les van deze reeks loopt nochtans gewoon door voorbij de komma, met negatieve exponenten. Decimaal staan daar de tienden, honderdsten en duizendsten. Binair staan daar de helften, kwarten en achtsten:
\[ 0{,}101_2 = 2^{-1} + 2^{-3} = \tfrac{1}{2} + \tfrac{1}{8} = 0{,}625 . \]
Probeer nu twee breuken zelf, op papier. De eerste is \(\tfrac{3}{4}\), en die lukt vlot, want \(\tfrac{3}{4} = \tfrac{1}{2} + \tfrac{1}{4} = 0{,}11_2\). De tweede is \(\tfrac{1}{5}\). Dat getal ligt tussen \(\tfrac{1}{8}\) en \(\tfrac{1}{4}\), dus je begint met \(0{,}001\), en daarna blijf je bezig. Wat je ook toevoegt, je komt er nooit precies uit.
Het verschil zit in de noemer. Een getal met eindig veel cijfers na de binaire komma is te schrijven als \(m / 2^{k}\), dus met een macht van twee als noemer. Voor \(\tfrac{3}{4}\) is dat het geval. Voor \(\tfrac{1}{5}\) niet, want \(5\) deelt geen enkele macht van twee. Een breuk heeft een eindige binaire notatie precies wanneer haar noemer, in laagste termen, een macht van twee is.
Decimaal is die voorwaarde ruimer, want \(10 = 2 \cdot 5\). Daar eindigen zowel de halven als de vijfden, en daarom ziet \(\tfrac{1}{5} = 0{,}2\) er zo onschuldig uit. Binair bestaat dat getal niet.
Dhahran, 25 februari 1991. Een Patriot-luchtafweersysteem hield de tijd bij in tienden van een seconde. Elke tik rondde af. Na honderd uur was de klok \(0{,}34\) seconde mis, en bij raketsnelheid is dat ruim een halve kilometer. Het systeem miste, en achtentwintig Amerikaanse soldaten kwamen om.
En \(\tfrac{1}{10}\) is gewoon \(0{,}1\), een getal dat je zonder nadenken opschrijft. Kijk dus eens wat een computer ervan maakt. x == 3 stelt de vraag of x gelijk is aan drie, en antwoordt True of False. De cel hieronder stelt dus een vraag waarvan het antwoord in de wiskunde vastligt. Noteer je voorspelling voor je op Run Code klikt.
Wiskundig is die gelijkheid vanzelfsprekend, en toch antwoordt de cel dat ze onwaar is. Dit is geen fout van Python. Vrijwel elke programmeertaal geeft hetzelfde antwoord, en dat is al decennia zo. De volgende twee secties leggen uit waarom, en wanneer het wel goed gaat.
4 Kommagetallen in een computer
Hoe krijg je zo’n getal in een vast aantal bits? Je zou een vaste komma kunnen afspreken: zoveel bits ervoor, zoveel erna. Dat werkt niet, want met één afspraak moet je zowel de massa van een elektron als de afstand tot de zon kunnen weergeven.
De oplossing is de wetenschappelijke notatie, in basis twee. Elk getal wordt
\[ \pm\, 1{,}m \cdot 2^{k} . \]
Voor de komma is afgesproken dat er altijd een \(1\) staat. Die hoeft dus niet opgeslagen te worden. Er blijven drie dingen over: het teken, de exponent \(k\) en de cijfers \(m\). Zo’n getal heet een float, naar floating point: de komma ligt niet vast maar schuift mee met de exponent.
Zo staat \(0{,}1\) in \(32\) bits.
teken exponent m
0 01111011 10011001100110011001101Eén bit voor het teken, acht voor de exponent, drieëntwintig voor \(m\). Hier is \(k = -4\), want \(0{,}1 = 1{,}6 \cdot 2^{-4}\). Hoe die acht bits precies \(-4\) voorstellen, laten we hier terzijde.
Voor \(m\) zijn er dus drieëntwintig plaatsen. De rij van \(0{,}1\) houdt daar niet op. Ze wordt afgekapt en afgerond. Wat er werkelijk staat is \(0{,}100000001490116119384765625\).
Python gebruikt \(64\) bits, met elf voor de exponent en tweeënvijftig voor \(m\). Dezelfde opbouw, een kleinere afwijking, maar de afwijking is nog steeds niet nul.
Met \(32\) bits zijn er \(2^{32}\) patronen, ruim vier miljard. Dat aantal ligt vast. Een geheel getal legt ze op een rij van ongeveer \(-2\) tot \(+2\) miljard, telkens één uit elkaar. Een float spreidt ze uit van het astronomisch grote tot het bijzonder kleine. Wat hij aan bereik wint, verliest hij in nauwkeurigheid. Rond \(1\) liggen de noteerbare getallen dicht bij elkaar, rond een miljard niet meer.
5 Terug naar de vraag
Bekijk \(0{,}1\) nu opnieuw. Als breuk is dat \(\tfrac{1}{10}\), en de noemer bevat de priemfactor \(5\). Volgens de voorwaarde hierboven eindigt de binaire ontwikkeling dus niet. Ze wordt periodiek:
\[ 0{,}1 = 0{,}0\overline{0011}_2 . \]
Er zijn eindig veel bits beschikbaar, dus wat opgeslagen wordt, is een benadering. Voor \(0{,}2\) geldt hetzelfde. Tel je die twee benaderingen op, dan is de som niet gelijk aan de benadering van \(0{,}3\). Vraag de som eens rechtstreeks op, zonder ze te laten beoordelen.
De cijferstaart achteraan is het verschil tussen wat er opgeslagen staat en \(0{,}3\). Daarop is de vergelijking hierboven stukgelopen.
Niet elke gelijkheid loopt verkeerd af.
Deze gaat wel op. \(\tfrac{1}{2}\) en \(\tfrac{1}{4}\) hebben een macht van twee als noemer, worden dus exact opgeslagen, en hun som \(\tfrac{3}{4}\) eveneens.
Daar valt weinig mee aan te vangen in een echt programma, want daar weet je zelden op voorhand welke getallen er precies uit een berekening komen. De praktische regel is daarom:
Test kommagetallen nooit op gelijkheid. Vergelijk in de plaats daarvan \(|x - y| < \varepsilon\), met \(\varepsilon\) een kleine drempel die past bij de nauwkeurigheid van de getallen waarmee je werkt.
6 Conclusie
Een notatie van vaste breedte heeft een grens. Je botst er op drie manieren tegenaan.
- Het getal is te groot: de bits die niet passen vallen weg, en de teller loopt rond.
- De patronen raken op: er is geen volgend adres meer te geven.
- Het getal past niet precies in basis \(2\): er wordt afgerond, hoeveel bits je er ook aan geeft.
Alleen de tweede merk je meteen. De andere twee leveren geen foutmelding op, en je programma rekent gewoon door met een verkeerd getal.
Daarom moet je weten met welke getallen je werkt. Tel je iets op dat de grens kan raken, gebruik dan een breder type of reken modulo. Vergelijk je kommagetallen, gebruik dan de regel hierboven.
En over de drie lessen heen: bits betekenen enkel wat je afspreekt dat ze betekenen. Hetzelfde patroon \(01000001_2\) is \(65\) als geheel getal, de letter A in ASCII-tekstcodering, een deel van een IP-adres, en een stuk van een instructie wanneer de processor het als code leest.
De afspraken rond kommagetallen staan in IEEE 754, de norm uit 1985 die vrijwel elke processor volgt. Daar vind je ook wat een computer doet met nul, met oneindig, en met een berekening die helemaal geen getal oplevert. Dat laatste heet NaN, van not a number, en het heeft de eigenaardige eigenschap dat het niet gelijk is aan zichzelf.
Voor de gehele getallen is er de stelling dat elk natuurlijk getal in elke basis precies één notatie heeft, op nullen vooraan na. Het herhaald delen uit de vorige les is die stelling in uitgevoerde vorm.
7 Begrippen
- overloop: wat er gebeurt wanneer een resultaat niet in het beschikbare aantal bits past. De bits die er niet meer bij passen, vallen weg. In het Engels overflow.
- modulo: rekenen waarbij enkel de rest bij deling telt. Een teller van \(n\) bits rekent modulo \(2^n\), in Python geschreven met de operator
%. - float: de notatie van een kommagetal als \(\pm 1{,}m \cdot 2^{k}\), waarbij de komma met de exponent meeschuift.
8 Oefeningen
Een teller in één byte staat op \(200\), en er komt \(100\) bij. Welke waarde bevat de byte daarna?
TipAntwoord\(200 + 100 = 300\), en dat past niet in acht bits. Er blijft \(300 \bmod 256 = 44\) over. De byte is over zijn grens gelopen zonder enige foutmelding.
Verklaar waarom \(0{,}1 + 0{,}2 = 0{,}3\) in de meeste programmeertalen onwaar is, terwijl \(0{,}5 + 0{,}25 = 0{,}75\) wel waar is.
TipAntwoordDe noemers van \(0{,}1\) en \(0{,}2\) bevatten de priemfactor \(5\), dus beide getallen worden afgerond opgeslagen. De som van die twee benaderingen is niet gelijk aan de benadering van \(0{,}3\). Bij \(\tfrac{1}{2}\) en \(\tfrac{1}{4}\) is de noemer wel een macht van twee, waardoor beide getallen en hun som exact zijn.
Een programma telt tienduizend keer \(0{,}1\) op bij een variabele die op \(0\) begint. Waarom staat er achteraf niet precies \(1000\), en hoe zou je het anders aanpakken?
TipAntwoordElke optelling voegt de afrondingsfout van \(0{,}1\) opnieuw toe, en die fouten stapelen zich op. Beter tel je tienduizend keer een geheel getal op en deel je pas op het einde één keer.