Hoe zou je getallen in een computergeheugen kunnen opslaan?
Een in de bankwereld vroeger veel gebruikte oplossing is de volgende: gebruik 4 bits voor een cijfer, en spreek af 0=0000, 1=0001, 2=0010, 3=0011, 4=0100, 5=0101, 6=0110, 7=0111, 8=1000, 9=1001. Dit is een handige oplossing als je bijna niet met de getallen hoeft te rekenen, maar je ze wel vaak moet afdrukken, zodat de conversie naar onze decimale schrijfwijze snel moet gaan. Nu wordt 1998 geschreven als 0001 1001 1001 1000.
Ons getal 1998 betekent eigenlijk 1 keer 1000 plus 9 keer 100 plus 9 keer 10 plus 8 keer 1, en de getallen 1000, 100, 10, 1 zijn machten van tien. Daarom heet deze manier om getallen te representeren het tientallig stelsel. We gebruiken het tientallig stelsel omdat we tien vingers hebben.
(Vroeger telden de Fransen en de Denen ook op hun tenen: er zijn duidelijke resten van een twintigtallig stelsel: in het Deens zeg je halvtreds, tres, halvfjerds, firs, halvfems voor 50, 60, 70, 80, 90: 50 is tweemaal twintig en nog de helft van het derde twintigtal, enz. Evenzo zijn 80, 90 in het Frans quatre-vingts en quatre-vingt-dix: 90 is vier maal twintig plus tien. Maar nu we schoenen hebben is het tellen op de tenen minder populair geworden.)
Maar er is niets bijzonders met het getal tien. In het zeventallig stelsel zou 123 het getal 1*49 + 2*7 + 3*1 = 66 voorstellen. En omgekeerd zou het tientallige 123 in het zeventallig stelsel 234 zijn.
Een woord in een computergeheugen is een lange rij bits, nullen en enen, en kan opgevat worden als getal in het tweetallig stelsel. Bijvoorbeeld zou 01100001 het getal 0*128 + 1*64 + 1*32 + 0*16 + 0*8 + 0*4 + 0*2 + 1*1 = 97 voorstellen. Zelfs betrekkelijk kleine getallen worden al lange rijen met bits, moeilijk te overzien voor het menselijk oog, en daarom gebruikt men in plaats van de binaire (tweetallige) voorstelling meestal een octale (achttallige) of hexadecimale (zestientallige) representatie. Ditzelfde getal zou achttallig 141 en zestientallig 61 luiden. Het is de ASCII code van de `a'. (In het tientallig stelsel hebben we tien cijfers nodig. In het zestientallig stelsel zestien, en daarvoor worden 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F gebruikt.)
Opgave Hoe schrijf ik 1998 in het honderdtallig stelsel? Hoeveel cijfers heeft dit getal in het honderdtallig stelsel?
Het voordeel van achttallig of zestientallig boven tientallig is dat geen berekening nodig is bij het converteren van en naar binair: Zestientallig 70A3F is binair 0111 0000 1010 0011 1111, dus 01110000101000111111, en om dit octaal te schrijven verdelen we het van achter af in groepjes van drie: 01 110 000 101 000 111 111, en lezen 1605077 af.
Opgave Welk tientallig getal is dit?
Je ziet dat conversie van en naar het tientallig stelsel veel rekenwerk kost; dat is de reden waarom BCD gebruikt werd als er vrijwel niet gerekend hoeft te worden, maar de decimale voorstelling vaak nodig is.
Of er voor achttallig of zestientallig gekozen wordt is vaak een kwestie
van cultuur. In de Digital wereld (DEC = Digital Equipment Corporation)
werd meestal octaal gewerkt, bij IBM (International Business Machines)
meestal hexadecimaal.
[Nu Unix en de taal C op DEC computers ontwikkeld zijn (PDP7, PDP11, VAX)
was er aanvankelijk alleen ondersteuning voor het gebruik van octaal:
begint een getal in een C programma met het cijfer 0 dan is het octaal.
Later is een notatie voor hexadecimaal toegevoegd: laat het getal voorafgaan
door 0x. Dus in een C programma stellen 97, 0141, 0x61 en 'a' dezelfde
constante voor. Een bekende rest van de oude octale cultuur is de
schrijfwijze van het argument van het Unix chmod commando.]
Tegenwoordig verdwijnt het octaal langzaam. Hexadecimale getallen zijn
korter, en dat is een groot voordeel bij lange getallen zoals ethernetadressen.
Een spel waarbij de tweetallige schrijfwijze van getallen van pas komt is Nim. Er zijn twee spelers en een aantal hoopjes lucifers. Beurtelings nemen de spelers wat lucifers weg van een hoopje (ten minste 1, hooguit het hele stapeltje). Vantevoren spreek je af of degene die de laatste lucifer pakt wint of verliest.
Als je wilt (en je browser Java kent) kun je dit spel nu meteen spelen.
Bijvoorbeeld: we spelen met stapeltjes van 6, 5, 4 en 3, en laatste lucifer wint. Ik begin met 4 lucifers van de stapel van 6 te pakken. Nu is de stand 2, 5, 4, 3. Jij pakt de hele stapel van 5. Dan is de stand 2, 4, 3. Ik pak 3 van de middelste stapel zodat het 2, 1, 3 wordt. Jij pakt een van de stapel van 2 (1, 1, 3) en ik de stapel van 3 (1, 1), jij 1 (1) en ik de laatste en win.
Dit is geen toeval - van het begin af aan was het duidelijk dat dit voor mij goed af zou lopen. De truuk is, de stapelgrootten binair te schrijven, en als binaire vectoren op te tellen (dus met 1+1=0). Als er 0 uitkomt verliest degene die aan zet is (bij de afspraak: laatste lucifer wint). In dit voorbeeld: 6, 5, 4, 3 is 110, 101, 100, 011 samen 100. Ik maak er 010, 101, 100, 011 van, samen 000. Enz.
Om te bewijzen dat dit een goede strategie is, moet ik laten zien: (1) Als jij stapels krijgt die samen 0 zijn, en je doet een zet, dan krijg ik stapels die samen niet 0 zijn. En (2) Als ik stapels krijg die samen niet 0 zijn, dan kan ik een zet doen met als resultaat dat de stapels samen weer 0 zijn. En inderdaad, (1) is duidelijk: je pakt een aantal lucifers, en in de binaire schrijfwijze van dit getal is er een bit dat niet 0 is. De bijbehorende kolom verandert, en was eerst in totaal 0, is nu dus in totaal 1. En ook punt (2) is duidelijk: kijk naar de som die ik krijg. Als dat bijvoorbeeld 1011 is, dan is er een bijdrage van 1... ergens, een stapel van minstens acht lucifers, zeg het was 11010, een stapel van 26. Om het totaal 0 te maken moet ik drie bits veranderen, en de stapel grootte 11010+01011=10001 geven, dus van 26 naar 17 gaan. Omdat het voorste bit dat verandert van 1 naar 0 gaat, is de nieuwe stapel kleiner dan de oude, dus is dit een legale zet.
Maar als de afspraak nu is dat de laatste lucifer verliest? Ik zou precies hetzelfde gespeeld hebben tot de stand (1, 1, 3) en dan niet alledrie maar slechts twee van de drie gepakt hebben; jij krijgt (1, 1, 1), ik krijg (1, 1), jij krijgt (1) en verliest. Het is duidelijk dat degene die bovenbeschreven winststrategie volgt degene is die uiteindelijk een stand krijgt met wat losse 1-en, en precies een grotere stapel. Op dat moment kan de keus gemaakt worden om de stand op een even of juist op een oneven aantal losse enen te brengen.
Tot zover Nim. Er is een uitvoerige theorie rond dit soort spelen ontstaan. Zie J.H. Conway `On numbers and games', en daarna Berlekamp, Conway & Guy `Winning Ways' (2 vols).
Hoe moeten negatieve getallen gerepresenteerd worden?
Soms zie je machines waar het teken als afzonderlijk bit voorgesteld wordt. Bijvoorbeeld +5 = 0 0101 en -5 = 1 0101. Dit is vreselijk onhandig in het rekenen, en wordt meestal alleen samen met BCD gebruikt.
Een redelijke oplossing is het complementeren van alle bits (elke 0 in 1 en elke 1 in 0 veranderen) en afspreken dat het voorste bit het tekenbit is. Dus +5 = 00101 en -5 = 11010. De opteller hoeft niets van deze afspraak te weten, behalve dan dat bij een carry ("1 onthouden" in de voorste positie) het antwoord nog met 1 verhoogd moet worden: -5+3 = 11010 + 00011 = 11101 = -2 en -5+6 = 11010 + 00110 = 00001 = 1. Bij een woordlengte van 5 bits is dit dus rekenen modulo 2^5 - 1 = 31. Een heel klein nadeel van deze oplossing is dat er maar 31 (in plaats van 32) verschillende getallen mogelijk zijn (namelijk -15, -14, ... , 15). Een klein nadeel van deze constructie is dat het optellen wat vertraagd wordt (na afloop van de `gewone' optelling moet nog naar het carry bit gekeken worden). Een groot nadeel is dat er twee voorstellingen van de 0 zijn: +0 = 00000 en -0 = 11111 stellen hetzelfde getal voor. Maar het komt heel vaak voor dat je wil kijken of iets nul is. Nu moet je met twee waarden vergelijken.
One's complement optelling (16-bits) wordt gebruikt voor de berekening van de checksum van een internet protocol (IP) pakket.
Daarom kiezen alle moderne computers voor de oplossing met ..., -5 = 11011, -4 = 11100, -3 = 11101, -2 = 11110, -1 = 11111, 0 = 00000, 1 = 00001, 2 = 00010, 3 = 00011, 4 = 00100, 5 = 00101, ... dwz het tegengestelde van een getal wordt verkregen door alle bits te complementeren en er 1 bij te tellen. (De PDP8 instructie CIA.) Bij een woordlengte van 5 bits is dit rekenen modulo 2^5 = 32. De opteller hoeft niet te weten of je met negatieve getallen werkt of niet: 11011 + 00011 = 11110 geldt, zowel als je denkt dat hier 27+3=30 staat, als wanneer je dit leest als -5+3 = -2. Is er een carry (overflow) bij het optellen, dan wordt dit bit gewoon weggegooid. Alle nadelen genoemd bij de One's complement arithmetic zijn nu vermeden. Er is een heel klein nadeel voor in de plaats gekomen: de 32 getallen die we kunnen voorstellen zijn -16, ..., 15, zodat -16 wel bestaat, maar +16 niet. Nu heeft de vergelijking x = -x dus twee oplossingen!
Opgave Welk getal heeft geen tegengestelde op de PDP8? En op een computer met 32-bit gehele getallen?
Op een PDP8 loop je al heel snel tegen de beperking aan dat 12 bits niet voldoende zijn om alle getallen die je nodig hebt te representeren. (Alles positief is dit 0..4095; met positieve en negatieve getallen -2048..2047.) Op een computer met 32-bit gehele getallen heb je 0..4294967295 of -2147483648..2147483647 beschikbaar. Meestal is dat wel voldoende, maar 2^32 bytes is 4 GB, en mijn schijven zijn groter, en 2^32 centen is bijna 43 miljoen gulden en sommige mensen hebben een groter banksaldo, dus zelfs als er fysieke dingen geteld worden dan is 32 bits niet altijd voldoende. Daarentegen is 64 bits wel "altijd" voldoende bij het tellen: als er elke nanoseconde een gebeurtenis geteld wordt dan duurt het meer dan 500 jaar voor het tellertje overloopt.
Dat was het tellen. Toch loopt een argeloze C programmeur al gauw tegen problemen aan vanwege de beperkte getalsgrootte. Tussenresultaten in berekeningen met een klein antwoord kunnen best groot zijn, en bij het uitrekenen van (a*b*c)/(p*q) gaat het al fout (in 32 bits) als a, b, c groter dan 2000 zijn.
Opgave Als ik A dingen uit N kies (met 0 <= A <= N), dan is dat 100*A/N procent. Hoe moet ik het aantal procent (afgerond op hele procenten) uitrekenen als A en N 32-bit gehele getallen zijn, en tussenresultaten ook 32-bit gehele getallen zijn? Eerst 100*A werkt niet als A groot is. Eerst A/N werkt al helemaal niet, want daar komt 0 uit (tenzij A = N).
Er bestaan programmabibliotheken om in dubbele precisie of meervoudige precisie of onbeperkte precisie te rekenen. Deze routines gebruiken meer dan één machinewoord om een getal op te slaan. Computeralgebrapakketten zoals Maple en Mathematica werken met gehele getallen van "onbeperkte" grootte - meestal zoveel als maar in het geheugen past. Onder Unix is er ook het rekenprogramma bc. De programmeertaal ABC wordt nog wel gebruikt in de cryptografische wereld omdat hij met gehele getallen van onbeperkte lengte werkt.
PDP8 voorbeeld van het optellen van dubbele lengte getallen: A1 en B1 zijn de voorkant (de eerste 12 bits) en A2 en B2 de achterkant (laatste 12 bits) van de 24-bits getallen A en B. We willen C = A + B uitrekenen.
0500 .... A1, ....
0501 .... A2, ....
0502 .... B1, ....
0503 .... B2, ....
0504 .... C1, ....
0505 .... C2, ....
0506 0000 TELOP, 0
0507 7300 CLA CLL /AC=0, L=0
0510 1201 TAD A2 /PAK ACHTERKANT A
0511 1203 TAD B2 /TEL ACHTERKANT B ERBIJ
0512 3205 DCA C2 /BERG OP IN ACHTERKANT C
0513 7004 RAL /ROTEER CARRY BIT VAN L NAAR AC
0514 1200 TAD A1 /TEL VOORKANT A ERBIJ
0515 1202 TAD B1 /TEL VOORKANT B ERBIJ
0516 3204 DCA C1 /BERG OP IN VOORKANT C
0517 5606 JMP I TELOP /KLAAR
Oefening Bereken 2^100000 = 99900...09376. Kan je machine ook 2^1000000 aan? (Het is 99006...09376.) Hoeveel cijfers hebben deze beide getallen precies? Wat zijn de eerste zes cijfers? Wat zijn de laatste zes cijfers? Wat zijn de laatste zes cijfers van 2^(10^100)? Waarom? Maple vertelt me (bij het commando `evalf(log(2)/log(10));') dat de 10-logaritme van 2 ongeveer .3010299957 is. Hoeveel van deze decimalen kun je voorspellen uit de waarde van 2^100000 ? Gebruik de machtreeks van log(1+x).
Discussie van bovenstaande oefening: Onder Unix kun je een aantal commando's aan elkaar knopen in een `pijplijn': de uitvoer van de eerste wordt de invoer van de tweede. Als nu echo gewoon herhaalt wat er gezegd wordt, en bc rekent, en wc -c telt hoeveel letters er in een bestand zitten dan levert het commando `echo 2^10 | bc | wc -c' het antwoord 5 (vier cijfers en een regelovergang; 2^10 = 1024). Grote getallen worden door bc over meer regels verdeeld:
% bc
2^1000
10715086071862673209484250490600018105614048117055336074437503883703\
51051124936122493198378815695858127594672917553146825187145285692314\
04359845775746985748039345677748242309854210746050623711418779541821\
53046474983581941267398767559165543946077062914571196477686542167660\
429831652624386837205668069376
Ik zou niet weten hoe ik onder DOS een commando zou moeten intypen dat me vertelt hoeveel cijfers 2^1000 heeft, en klikkend met de muis onder Windows lijkt me dit ook niet eenvoudig. Toch zit er ook in Windows een zakrekenapparaat ingebouwd.
Ik heb vrijwel geen ervaring met DOS/Windows, maar heb sterk de indruk dat als je iets wilt waar de ontwerper niet aan gedacht heeft, je dat vaak met het aan elkaar knopen van wat Unix commando's eenvoudig voorelkaar krijgt terwijl het met DOS zelden lukt. Voorts, dat als je iets wilt waar de ontwerper wel aan gedacht heeft, en het staat voor je klaar in een Windows menuutje, maar je wilt het duizend keer doen, er onder Windows vaak niets anders opzit dan duizend keer dat menuutje aan te klikken, waar de Unix shell een eenvoudig for statement toelaat.
In de cryptografie ben je geïnteresseerd in een aantal onderwerpen zoals (i) het versturen van geheime boodschappen, d.w.z. het versleutelen en ontsleutelen van informatie; (ii) het bewijzen dat je bent wie je zegt te zijn (authenticatie); (iii) het produceren van niet-vervalsbare handtekeningen onder een niet-vervalsbare brief, enz.
Al dit soort systemen berust er op dat iemand over privéinformatie beschikt. Een heel slecht idee is om lichaamskenmerken te willen gebruiken: vingerafdruk, lijntjes op de iris, dynamisch patroon van schrijven tijdens het zetten van een handtekening, eigenschappen van het timbre van de stem. Slecht omdat in veel verschillende contexten cryptografie nodig is, en als ik bijvoorbeeld mijn vingerafdruk heb afgegeven bij de systeembeheerder om op een computer te kunnen inloggen, en bij de bank om geld te kunnen opnemen, dan beschikt de systeembeheerder over de informatie nodig om mijn geld op te nemen, wat vast niet de bedoeling was.
Dus, in plaats van dit soort kenmerken wordt de kennis van een codewoord, een sleutel, een pincode, een password gebruikt. Als je zo verstandig bent om in iedere context een verschillende sleutel te kiezen en een systeembeheerder kent je password, dan kent hij nog niet je pincode.
Toch blijft dit soort systemen onbevredigend. Als ik inlog over ethernet, en iemand anders luistert alle pakketjes af die op het ethernet langskomen, dan vangt zij ook mijn password.
Oefening
Zoek of schrijf een programma voor je laptop om het ethernet
af te luisteren. Onder Linux zou dat bijvoorbeeld tcpdump kunnen zijn.
Ben je alleen geïnteresseerd in passwords dan kun je tcpdump sterk
kortwieken, en alles weggooien behalve wat komt als een reactie op de
vraag `Password:'.
Eigenlijk wil ik te allen tijde mijn privéinformatie voor mezelf houden, en bewijzen dat ik over die informatie beschik zonder die informatie zelf af te geven.
Daar zijn allerlei methoden voor, en cryptografie is een wetenschap op zichzelf geworden, maar laat ik hier heel kort een voorbeeld geven van een systeem met openbare sleutel. Eerst een klein beetje getaltheorie.
(Waarom denk ik nu aan cryptografie? Omdat dit het meest voorkomende onderwerp is waarbij mensen willen rekenen met getallen van vele honderden cijfers; de best bekende toepassing van meervoudige lengte aritmetiek.)
Ik schrijf a == b (mod m) als a en b dezelfde rest hebben bij deling door m. Bijvoorbeeld 11 == 5 (mod 3). (Het gangbare symbool is drie streepjes boven elkaar, maar dat heb ik hier niet in voorraad, vandaar ==. Het wordt uitgesproken als `is congruent met' of gewoon `is'. De mod wordt uitgesproken als `modulo'. Heel vaak wordt ook gewoon = geschreven in plaats van ==.)
Laat phi(m) het aantal getallen tussen de 1 en de m zijn die geen factor groter dan 1 gemeen hebben met m. (Dit heet de Euler phi-functie. Ik heb hier geen Griekse letter phi in voorraad, daarom maar uitgeschreven.) Bijvoorbeeld: phi(12) = 4 want 1, 5, 7, 11 hebben niets gemeen met 12, terwijl 2, 4, 6, 8, 10, 12 een factor 2 gemeen hebben met 12, en 3 en 9 een factor 3. En phi(11) = 10. En phi(10) = 4. En phi(1) = 1.
De kleine stelling van Fermat zegt dat als a geen factor gemeen heeft met m, dan is a^phi(m) == 1 (mod m). Bijvoorbeeld: als een getal geen factor met 10 gemeen heeft (dus op 1 of 3 of 7 of 9 eindigt) dan eindigt a^4 op een 1. En inderdaad: 1^4 = 1 en 3^4 = 81 en 7^4 = 2401 en 9^4 = 6561.
En dit betekent, dat als ik a^N (mod m) wil weten, ik N mag reduceren modulo phi(m). Bijvoorbeeld, als ik het laatste cijfer van 3^666 wil weten dan mag ik 666 reduceren modulo 4. Maar 666 = 2 (mod 4), dus het laatste cijfer van 3^666 is hetzelfde als het laatste cijfer van 3^2 kortom, is 9.
(We hebben phi(100) = 40, dus de laatste twee cijfers van 3^666 zijn dezelfde als de laatste twee cijfers van 3^26 = 2541865828329, kortom 3^666 eindigt op ...29.)
Maar dit betekent weer dat als d*e == 1 (mod phi(m)) dan is a^(d*e) == a (mod m). (Voortdurend is onze aanname dat a en m geen factor gemeen hebben, oftewel ggd 1 hebben.) Bijvoorbeeld, 3*27 == 1 (mod 40), dus als ik eerst b = a^3 (mod 100) uitreken, dan is a = b^27 (mod 100). Inderdaad, 7^3 = 343 = 43 (mod 100) en 43^27 = 126954558834210268249846442662975710502469107 = 7 (mod 100).
Dit is bruikbaar in de cryptografie: we zouden ^3 kunnen gebruiken om te coderen, en ^27 om te decoderen.
Alice wil vertrouwelijk kunnen communiceren met de buitenwereld. Daartoe kiest ze twee grote priemgetallen p en q (van een paar honderd cijfers) en houdt die streng geheim, alleen het product m = p*q openbaart ze (via een advertentie in de Telegraaf, of door m op haar www thuispagina te zetten). Natuurlijk kun je p en q in principe terugvinden als je m weet: als m = 8611 dan leert enig proberen dat p en q gelijk aan 79 en 109 moeten zijn. Maar vandaag kan nog niemand getallen van vierhonderd cijfers (die het product van twee heel grote priemgetallen zijn) in factoren ontbinden - dat kost miljoenen jaren rekenwerk - dus in werkelijkheid blijven p en q geheim, ook al is p*q bekend. Zelf kan ze phi(m) = (p-1)*(q-1) = m-p-q+1 uitrekenen, maar niemand anders kan dat. Nu zoekt ze twee getallen d en e zo dat d*e == 1 (mod phi(m)), en maakt ook e bekend, maar houdt d streng geheim. (De letters d en e staan voor decryptie en encryptie: ontsleutelen en versleutelen of ook ontcijferen en vercijferen.)
Als nu Bob een vertrouwelijke brief aan Alice wil sturen, met boodschap b, dan zoekt hij eerst Alice's openbare getallen m en e op, en berekent vervolgens b^e (mod m), en stuurt haar dit op. Niemand kan dit lezen, want het is niet duidelijk hoe je b zou kunnen terugvinden uit b^e (mod m). Maar Alice kan dit wel, want die kent haar geheime getal d, en berekent (b^e)^d = b^(d*e) = b^1 = b (mod m).
Probleem Vind twee grote getallen p en q, van ongeveer 200 cijfers, die waarschijnlijk priem zijn. Hoe ga je na of een getal waarschijnlijk priem is? Vind twee getallen, bijvoorbeeld e = 3 en d = ? zo dat d*e = 1 (mod phi(p*q)). Verzin een mededeling van 100 bytes, versleutel die (met behulp van e en m), en ontcijfer hem weer (met behulp van d en m). Hoe kan je eigenlijk een getal tot een gigantisch hoge macht verheffen zonder dat het uren (of eeuwen) rekentijd kost?
Al dit gereken met heel grote getallen is wat onhandig en langzaam en meestal wil je dat alleen aan het begin doen, om een sleutel voor de onderlinge communicatie af te spreken. Daarna kun je verder gaan met een veel efficiënter systeem, dat van deze gemeenschappelijke geheime sleutel gebruik maakt.
Laten Alice en Bob allebei een geheim getal A en B kiezen. Voorts kiest een van beiden nog een grondtal K (bijvoorbeeld 2) en een heel groot getal p, waarschijnlijk priem. Alice stuurt aan Bob K^A (mod p), en Bob stuurt aan Alice K^B (mod p). Nu zijn A en B nog steeds geheim, want er is geen algoritme bekend dat het `discrete logaritme' probleem oplost: vind A als K en p en K^A (mod p) bekend zijn. Een afluisteraar kent nu K^A (mod p) en K^B (mod p), maar Alice en Bob gebruiken voor hun geheime communicatie de sleutel S = (K^A)^B = (K^B)^A (mod p) die ze allebei kennen, maar die de afluisteraar niet kan reconstrueren.
Als je weet hoe gehele getallen voorgesteld moeten worden, dan is het duidelijk wat je met breuken doet: afzonderlijk teller en noemer bewaren. Hoe zit het met decimale breuken? Een getal als 3.14159 kun je bewaren als 314159/100000, maar als je noemers altijd machten van tien zijn hoef je alleen de exponent te onthouden, en heb je hier het paar getallen (314159, 5). Als de noemer altijd hetzelfde is hoef je de noemer helemaal niet te onthouden, dan ligt die vast volgens afspraak. Bij prijzen kun je bijvoorbeeld f 12,95 onthouden als 1295; de vaste noemer betekent hier gewoon het kiezen van een andere eenheid: centen in plaats van guldens, zodat de getallen weer geheel zijn.
In computerverband zijn de noemers geen machten van tien, maar machten van twee. Weer heb je `fixed point numbers', waarbij de binaire punt op een afgesproken plaats ligt, en `floating point numbers', waarbij je ook moet aangeven waar de binaire punt ligt. Een drijvende-kommagetal is een paar (M,E) dat het getal M * 2^E voorstelt, M voor mantisse, E voor exponent, waarbij de binaire punt helemaal vooraan in M ligt. Dus (1101, 11) stelt .1101 * 2^3 voor (kortom 6.5 = zeseneenhalf) in een hopelijk begrijpelijke mengeling van binair en decimaal. Dit getal hadden we ook (01101, 100) kunnen schrijven, maar dan zijn meer bits nodig. De schrijfwijze heet genormaliseerd als het voorste bit van de mantisse 1 is. (En als je toch afspreekt dat het voorste bit 1 zal zijn, dan hoef je dat bit niet meer op te schrijven, dat spaart weer een bit.)
Veel computers kennen hardware instructies voor floating point optelling en vermenigvuldiging. De hardware verwacht dan natuurlijk een welgedefinieerde representatie (hoeveel bits mantisse? hoeveel bits exponent? waar staan deze in de getallen die bewerkt worden?) Vroeger waren er allerlei verschillende conventies, maar tegenwoordig houdt iedereen zich aan de IEEE 754 standaard. (IEEE = Institute of Electrical and Electronics Engineers, uitgesproken I-triple-E) Een 32-bit floating point getal bestaat uit de volgende 32 bits: 0) s, 1 bit, het tekenbit. 1-8) e, een 8-bit getal dat iets met de exponent te maken heeft. 9-31) m, een rij van 23 bits die iets met de mantisse te maken heeft. Het getal e kan kennelijk de waarden 0..255 aannemen. Als e=255 en m=0 dan stelt dit getal +oneindig of -oneindig voor (afhankelijk van het tekenbit s). Als e=255 en m is niet nul, dan stelt dit getal NaN (`not a number') voor. Als 0 < e < 255 dan is e = E + 127, zodat exponenten tussen -126 en 127 kunnen voorkomen. In deze gevallen is de mantisse M de string van 24 bits die ontstaat door een 1 voor m te zetten. Als e = 0 en m is niet nul, dan is dit een niet-genormaliseerde representatie van een getal met E = -126 en M de 24-bit string die ontstaat door een 0 voor m te zetten. Als e = 0 en m = 0 dan is het getal 0 (kennelijk met twee representaties: +0, -0).
Een 64-bit floating point getal bestaat op dezelfde manier uit 1+11+52 bits, dus met een 53-bit mantisse M en een exponent tussen -1022 en 1023.
Opgave Wat zijn de in absolute waarde grootste en kleinste niet-nul getallen in 32-bits? In 64-bits? Geef de binaire voorstelling en de decimale waarde.
De IEEE standaard vertelt niet alleen hoe floating point getallen opgeslagen moeten worden, maar ook wat het resultaat van rekenkundige bewerkingen moet zijn, d.w.z. op welke manier er afgerond moet worden, zodat het resultaat van een berekening 100% vast ligt, en twee computers die zich aan dezelfde standaard houden dezelfde antwoorden vinden bij een berekening.
Een klein detail dat veel verdriet veroorzaakt is de vraag: welk uiteinde van een getal schrijf ik het eerst? Als bij een computer met 4-bit geheugencellen het getal 0001 1101 (negenentwintig) opgeslagen wordt, heeft dan 0001 het laagste adres of juist 1101? In het eerste geval heet de computer `big endian' (`big end first'), in het laatste geval `little endian', en beide komen voor.
Zolang je op één computer werkt (en je programmeert in een hogere taal) hoef je je dit nooit af te vragen, en het is dan ook heel dom om te weten hoe dat bij je eigen computer is. (Een Intel PC is little endian.) Het is dom om dit te weten, omdat, als je dit weet er het gevaar bestaat dat je deze kennis impliciet toepast in een programma. Maar dan werkt dat programma niet meer op andere computers.
Wat er meestal fout gaat is hetzij dat iemand getallen naar schijf schrijft, en ze later weer ergens anders inleest, en onzin vindt omdat de delen van een getal op die andere computer in een andere volgorde staan (of misschien ook omdat het floating point getallen waren en die andere computer een heel andere floating point representatie hanteert), hetzij dat iemand bijvoorbeeld een pointer naar een getal bewaart en denkt dat hij kan testen of het getal even of oneven is door te kijken naar het laatste bit van het byte waar die pointer heenwijst. Ik heb mensen weken zien zoeken in een programma van honderdduizend regels naar precies deze fout. Programmeren is tijdrovend en dus duur. En fouten vinden in oude programma's is nog veel tijdrovender, en veel duurder. Feiten van je computer weten die niet in de definitie van de gebruikte programmeertaal staan is tijd en geld weggooien.