Programming FAQ - Getallen en talstelsels

[RobIII]

FAQ: Talstelsels en getallen Inhoudsopgave 1: Inhoudsopgave 2: Inleiding 3: Decimaal talstelsel 4: Binair talstelsel 5: Hexadecimaal talstelsel 6: Overige talstelsels 7: Notatie 8: En waarom al die talstelsels? 9: Representatie en opslag 10: Decimaal teken en cijfergroeperingssymbool 11: Datums 12: Signed / Unsigned, MSB en LSB 13: Floats (ook wel drijvende komma of zwevende komma getallen) 14: Floats en afronding 15: Fixed point getallen « · ^ Inleiding Hoe een getal in een computer wordt opgeslagen weet zo'n beetje iedereen wel; het is een verzameling van enen en nullen. Echter, hoe het precies in zijn werk gaat wil nog wel eens een klok en klepel verhaal zijn. Vandaar deze FAQ over getallen, talstelsels en hun representatie. We gaan eerst even kort op herhaling van basisschool stof: « · ^ Decimaal talstelsel Als je tot 150 telt begin je bij 0, 1, 2, 3 en zodra je door alle cijfers heen bent, bij 9 dus, begin je weer opnieuw met een tiental ervoor. Zo kom je dus bij 10, 11, 12, ... 20, 21, ... 98, 99 en dan herhaal je het trucje; echter nu niet met een tiental maar met een honderdtal. 98, 99, 100, 101 etc. Het getal 2756 in het decimale stelsel kun je dus ontleden als: 6 x 1 ofwel: 6 x 10[sup]0[/sup] = 6 5 x 10 ofwel: 5 x 10[sup]1[/sup] = 50 7 x 100 ofwel: 7 x 10[sup]2[/sup] = 700 2 x 1000 ofwel: 2 x 10[sup]3[/sup] = 2000 ---- + 2756 « · ^ Binair talstelsel Het binaire stelsel, dat enkel de cijfers 1 en 0 kent, werkt in feite hetzelfde als het decimale stelsel; enkel hebben we nu maar 2 cijfers tot onze beschikking. De term binair komt dan ook van het feit dat het een tweetallig talstelsel is. De reeks 0, 1, 2, 3, 4 tellen we binair als volgt: 000, 001, 010, 011, 100. Ook hier geldt weer; als je geen cijfers meer hebt plaats je een nieuw getal ervoor en begin je opnieuw. Het wordt duidelijker als je het getal ontleedt: We nemen het getal 2756 (binair geschreven als 101011000100) weer als voorbeeld: 0 x 2[sup]0[/sup] = 0 0 x 2[sup]1[/sup] = 0 1 x 2[sup]2[/sup] = 4 0 x 2[sup]3[/sup] = 0 0 x 2[sup]4[/sup] = 0 0 x 2[sup]5[/sup] = 0 1 x 2[sup]6[/sup] = 64 1 x 2[sup]7[/sup] = 128 0 x 2[sup]8[/sup] = 0 1 x 2[sup]9[/sup] = 512 0 x 2[sup]10[/sup] = 0 1 x 2[sup]11[/sup] = 2048 ---- + 2756 « · ^ Hexadecimaal talstelsel Het hexadecimale talstelsel is weinig verschillend van voorgaande talstelsels; echter nu hebben we 16 getallen tot onze beschikking. Dit zijn de cijfers 0, 1, 2, 3 ... 8, 9 en de letters A, B, C, D, E en F. Na het getal 9 komt nu dus geen 10 want we hebben nog 6 letters tot onze beschikking en we tellen na 9 dus vrolijk door: ... 7, 8, 9, A, B, C, D, E, F. En dan zijn we door onze cijfers heen. Geen nood want we herhalen gewoon wat de andere talstelsels doen: we plaatsen er een cijfer voor: ...C, D, E, F, 10, 11, 12, ..., 19, 1A, 1B, ...1F, 20, 21... We ontleden wederom het getal 2756 (hexadecimaal geschreven als AC4): 4 x 16[sup]0[/sup] = 4 x 1 = 4 C x 16[sup]1[/sup] = 12 x 16 = 192 A x 16[sup]2[/sup] = 10 x 256 = 2560 ---- + 2756 « · ^ Overige talstelsels In de computerwereld komen we ook nog wel eens octaal tegen; het 8-tallig talstelsel. Hierbij heb je dus beschikking over de cijfers 0 t/m 7. Er zijn nog andere talstelsels (en je kunt ze met behulp van voorgaande regels zelfs zelf verzinnen) die je wel eens kunt tegenkomen; deze zijn echter relatief zeldzaam. Op al deze talstelsels zijn dezelfde regels van pas. Als je dus gelukkig wordt van een 71-tallig talstelsel: leef je uit! Wel is het zo dat de meeste programmeertalen vaak enkel voorgaande (of zelfs maar 1 of 2 van voorgaande) talstelsels ondersteunen. « · ^ Notatie Vaak zie je in code een notatie als 0x0AC4. De "0x" geeft in dit geval aan dat het om een hexadecimaal getal gaat. Octale getallen worden vaak voorzien van een voorloop 0 of van de letter o en binaire getallen met de letter b. Afhankelijk van de taal die je gebruikt kan de notatie verschillen (de letters h en q worden ook gebruikt, evenals andere leestekens) dus het is even de moeite waard je hier in te verdiepen als je er nog niet mee bekend bent in je favoriete taal. « · ^ En waarom al die talstelsels? Hexadecimaal wordt vaak gebruikt omdat ieder hexadecimaal getal (0 tot F dus) overeenkomt met 4 bits. Een byte (8 bits) komt dan overeen met 2 hexadecimale getallen (00 tot FF). Bij het octale talstelsel komt elk getal (0 tot 7 dus) overeen met 3 bits. Omdat de notatie niet afdoet aan de waarde die het getal representeert is het dus ook gewoon een kwestie van smaak; voor het systeem blijft de waarde uiteindelijk toch bestaan uit enen en nullen (of wel spanning/geen spanning). De compiler, interpreter of assembler zetten dus het getal uit notatie X toch om naar de logische waarde. « · ^ Representatie en opslag We hebben gezien dat het getal 275610 hetzelfde is als AC416 en 1010110001002 (waarbij de kleine cijfers het talstelsel aangeven). De betekenis is dus hetzelfde, enkel de representatie is verschillend. Het getal 00275610 is ook hetzelfde als 275610 of 00001010110001002; het enige verschil zijn de voorloopnullen. Deze worden vaak gebruikt in bijvoorbeeld klantnummers, ordernummers of andere zaken waarbij het de voorkeur heeft om een 'vaste lengte' getal te hebben. In de binaire notatie heeft het de voorkeur om altijd getallen te noteren in de lengte van een veelvoud van 8 bits (dus bijvoorbeeld 8, 16 of 32 bits). Deze voorloopnullen worden dus doorgaans, als je integers hanteert voor je klantnummers, door de applicatie toegevoegd; intern worden deze voorloopnullen niet opgeslagen. De applicatie zorgt dan voor de formattering van je klantnummer op bijvoorbeeld je factuur of op het scherm. Het is dan ook af te raden om getallen als 'strings' te bewaren omdat anders de voorloopnullen 'verloren' zouden gaan. « · ^ Decimaal teken en cijfergroeperingssymbool Hetzelfde geldt voor cijfergroeperingssymbool en decimaalteken (1.323.382,00): deze worden door de applicatie op het moment dat het getal wordt weergegeven of afgedrukt in het getal geplaatst en worden dus niet in de 'enen en nullen' opgeslagen. Op deze manier kan je OS of platform aan de hand van de door de gebruiker als voorkeur gekozen notatie hanteren en kan je applicatie dus bijvoorbeeld in de VS datzelfde getal presenteren als 1,323,382.00) « · ^ Datums Je zult begrijpen dat de notatie (c.q. representatie) van de getallen niet van invloed is op de betekenis. Datzelfde kom je ook vaak tegen bij datums. De datum 2-12-1977 is hetzelfde als 12/2/1977; waarbij bij de eerste notatie de d-m-y wordt gehanteerd en bij de tweede de notatie m/d/y. Hierin schuilt echter een gevaar; de datum 2-12-1977 kan zonder kennis van welke notatie wordt gebruikt, niet met zekerheid worden vastgesteld. Het kan immers 2 december zijn maar ook 12 februari. Een veilige notatie die deze problemen voorkomt is de ISO 8601 y-m-d notatie; de meeste RDBMS'en ondersteunen deze notatie en dat is maar goed ook. Maar al te vaak gaat een query die op server A prima werkt compleet de mist in op server B omdat deze een verschil heeft in de regionale/landinstellingen. Overigens is het gebruik van parametrized queries nog altijd aanbevolen boven deze manier. Zodoende wordt de juiste notatie automatisch gehanteerd door de driver die het SQL statement voedt met je gegevens. Maar ook bij het interpreteren van invoer van gebruikers kan het nodig zijn om zeker te weten welke datumnotatie gebruikt is. De datum 31-12-1977 is natuurlijk niet verkeerd te interpreteren maar de voorgenoemde datum 2-12-1977 kan voor behoorlijke hoofdpijn zorgen als je applicatie in een andere locale wordt gestart dan de locale waarin je je applicatie hebt ontwikkeld. Zorg er daarom altijd voor dat je gebruikers duidelijk maakt welke notatie je verwacht, je datums controleert op geldigheid, en bij voorkeur dat je applicatie 'locale-aware' is; dus dat de applicatie 'weet' welke notatie waarschijnlijk gebruikt wordt door de gebruiker. Achter de schermen, als de notatie eenmaal is vastgesteld, geldt natuurlijk hetzelfde als voor getallen. De datum wordt opgeslagen als een aantal enen en nullen en bij het weergeven daarvan maakt het dus niet (meer) uit welke representatie gekozen wordt; het is enkel een voor mensen leesbare weergave van de enen en nullen. Of dat dan d-m-y of m-d-y is; dat kan je applicatie, maar bij voorkeur het OS, bepalen. Je kunt dus ook veilig datums vergelijken zolang je zorgt dat de daadwerkelijke data consistent is. « · ^ Signed / Unsigned, MSB en LSB Omdat we niet alleen positieve getallen maar ook negatieve getallen willen opslaan en gebruiken wordt er onderscheid gemaakt tussen signed en unsigned integers. Bij een signed integer is er 1 bit gereserveerd om aan te geven of het getal positief danwel negatief is. Wanneer alle 8 bits 1 zouden zijn zou de waarde 255 het hoogste getal zijn dat een byte kan opslaan. Als we deze byte echter signed zouden maken houden we effectief nog maar 7 bits over, waardoor we nu maximaal het getal 127 kunnen opslaan in de byte; echter kunnen we nu wel getallen opslaan van -128 t/m 127 in tegenstelling tot de unsigned variant; 0 t/m 255. Het bereik is in beiden 256 waardes. Wanneer we van links naar rechts naar een byte kijken (bijvoorbeeld 001110112 dus 5910) dan is de linkse bit de MSB ofwel Most Significant Bit en de rechtse bit de LSB; Least Significant Bit. Dit is makkelijk te onthouden: wanneer je de rechtse bit zou wijzigen is het verschil hooguit 1. Wanneer je de linkse bit zou veranderen is het verschil 128, en dus veel significanter. Bij een signed variant wordt de MSB gebruikt voor het teken. Wanneer de MSB 1 is is het getal negatief; Het getal 100000002 is dan de laagst mogelijke waarde, 100000012 de één na laagste enzovoorts, totdat we bij 111111112 komen, welke nu dus -110 betekent. Deze methode wordt het "Two's complement" genoemd. Bits worden overigens van rechts naar links geteld, beginnend bij 0. De LSB is dus bit 0 en de MSB is bit 31 in een 32 bits getal. « · ^ Floats (ook wel drijvende komma of zwevende komma getallen) We hebben tot nu toe gezien hoe een integer, een getal uit de verzameling Z, wordt opgeslagen in een computer. Onder de gehele getallen verstaan we de natuurlijke getallen {0, 1, 2, ... } en de negatieve vorm ervan {-1, -2, ...}. Maar hoe zit het nu met rationale getallen, ofwel de 'breuk' c.q. decimale breuken (en dus de verzameling Q)? Deze worden opgeslagen in een float(ing point), real, single of double; afhankelijk van de programmeertaal. Tussen twee hele getallen liggen een oneindig aantal breuken; zo is er tussen 0 en 1 de breuk 0.5 maar ook 0.05, 0.005, 0.0005 en 0.0000012387287. Omdat computers bij voorkeur werken met een vast aantal bits (meestal 32 of 64, maar andere varianten zijn ook mogelijk) is het onmogelijk om al die breuken op te slaan in het aantal beschikbare bits. Een float is dan ook altijd een benadering van de breuk. Doorgaans onderscheiden we de single precision float en de double precision float (32 en 64 bits respectievelijk, maar afhankelijk van het platform kan dit veschillen). Het IEEE (Institute of Electrical and Electronics Engineers) heeft de meestgebruikte standaard voor floating points vastgelegd in IEEE 754. De complete uitleg hiervan is te lang voor deze FAQ, zie daarvoor de volgende bronnen: » YouTube: Floating Point - Computerphile « Wikipedia: Floating point Wikipedia: Single precision Wikipedia: Double precision http://babbage.cs.qc.edu/IEEE-754/Decimal.html « · ^ Floats en afronding Door de manier waarop een float wordt opgeslagen kan (bijvoorbeeld) het getal 0.1 niet (exact) opgeslagen worden; enkel een (hele goede) benadering. Berekeningen die je met een float uitvoert zullen dan ook altijd een benadering zijn. Mits goed toegepast zal dit geen probleem zijn en is het resultaat enkel marginaal "fout"; Je kunt je voorstellen dat als je de afstand tussen 2 sterren berekent dat die 7 centimeter die je er langs zit op een afstand van miljarden kilometers niet significant (genoeg) is. Desondanks dien je toch op te passen voor een aantal 'verrassingen' die floats voor je in petto kunnen hebben; als je bijvoorbeeld een berekening hebt gedaan met floats die de uitkomst 110 geeft en je vergelijkt dit met de integer 110 dan kan deze expressie naar false evalueren; de 'uitkomst' kan dan bijvoorbeeld 110.000000000024892 zijn vanwege de afrondingen die in de floating point berekening zijn toegepast. Een van de bekendste floating point "ooops"-en waarbij er zelfs doden en gewonden vielen is die van de patriot raket in 1991 die doel mistte vanwege deze afrondingen. Zorg dus dat je goed weet waar je mee bezig bent! Meer hierover lees je (o.a.) op: » YouTube: Floating Point - Computerphile « Wikipedia: Floating point - Accuracy problems Wikipedia: Floating point - Minimizing the effect of accuracy problems The pitfalls of verifying floating-point computations (PDF) What Every Computer Scientist Should Know About Floating-Point Arithmetic. « · ^ Fixed point getallen Een fixed point getal heeft, in tegenstelling tot een floating point getal, de komma op een vaste plek in het getal, in de vorm xxxx.xxxx (het aantal x-en voor en na de komma kan per type variëren en de juiste keuze is afhankelijk van je probleemdomein). Dit heeft als gevolg dat je niet hele kleine (bijv 0,0000000123) of hele grote (bijv. 1230000000) getallen in hetzelfde type kunt opslaan, maar het voordeel is dat afrondingsfouten voorspelbaar zijn, wat bijvoorbeeld belangrijk is bij het opslaan van geldbedragen, waar de komma op de plek van een macht van tien wordt geplaatst (meestal voor de laatste twee decimalen). Fixed point getallen kun je doorgaans gewoon opslaan in een integer. 1234,56 wordt dan bijvoorbeeld gewoon 123456. Dit heeft als voordeel dat je gewoon kunt optellen en aftrekken. Voorbeeld: 1234,56 <=> 123456 4328,57 <=> 432857 -------+ ------+ 5563,13 <=> 556313 Voor de daadwerkelijke representatie van het getal hoef je alleen maar te delen door de "waarde" van de komma in de plek in het getal. Zo staat hij in bovenstaand voorbeeld voor de laatste twee decimalen, dus die waarde is 102 = 100. Ook bij vermenigvuldigen en delen moet je naderhand compenseren voor de verschoven plek - na vermenigvuldigen moet je in dit voorbeeld delen door 100, en na delen moet je juist vermenigvuldigen (of eigenlijk éérst vermenigvuldigen, omdat bij een deling op een integer vaak wordt afgerond naar hele getallen). Naast geldbedragen werden fixed point getallen in het verleden veel gebruikt als een sneller alternatief voor floating point getallen. Het getal is dan feitelijk een integer, waarbij de onderste n bits zich achter de komma bevinden. Een 32 bits getal werd op die wijze vaak onderverdeeld in 16 bits voor de komma en 16 bits erachter (wat vaak wordt aangeduid met de notatie 16.16 of 16:16). Omdat de plek van de komma een macht van twee is, kunnen de delingen en vermenigvuldigingen, die ter compensatie gedaan moeten worden, worden vervangen door shifts. Dit was echter in de tijd dat floating point operaties een stuk langzamer waren dan operaties op integers, wat tegenwoordig niet meer opgaat. Overigens hebben moderne programmeertalen vaak speciale typen voor het exact opslaan van getallen met decimale representatie, zoals 'decimal' of 'currency'. Deze zijn echter wel 'duurder' in het gebruik; d.w.z. dat de CPU meer werk heeft om er mee te kunnen werken omdat het geen datatypen zijn welke door de CPU zélf worden ondersteund.

[ Voor 255% gewijzigd door RobIII op 07-01-2015 09:33 ]