Papers we love: What every computer scientist should know about floating-point arithmetic

 
15 mei 2017

Een van de meest onderschatte onderwerpen uit ons vakgebied zijn wat mij betreft ‘getallen’ of ‘cijfers’. Er zijn bijna geen onderwerpen te vinden waar de samenhang tussen geschiedenis, abstracties en technische beperkingen je zo hard om de oren slaat: signed en unsigned numbers , underflow , overflows, containers als BigInteger etc. Voor de mensen onder ons die een computer science en/of software engineering achtergrond hebben zal herinneren dat er menig college aan dit soort onderwerpen geweid is terwijl er voor veel mensen van de acadamy geldt dat zij hier proefondervindelijk het een en ander van hebben geleerd. Om iedereen nog eens op het hart te drukken hoe lastig iets conceptueel eenvoudigs als een getal kan zijn heb ik voor deze maand gekozen om dit onderwerp nader te belichten.

Een subset van de rationele getallen drukken wij in software uit als zogenaamde floating point getallen. Het gaat hierbij dus om getallen als 0.25, 0.2 maar ook 1/3. De eerste twee zijn relatief eenvoudig omdat ze eindig zijn. Voor het getal 1/3 is dat echter niet zo, afhankelijk van de hoeveelheid gevraagde precisie krijg je meer decimalen achter de komma. Dit levert hiermee ook een soft-, en hardware probleem op: hoeveel bits gebruik je voor deze precisie? Theoretisch betekent dit namelijk dat mogelijk oneindig veel bits nodig hebt om het getal juist op te slaan. Kortom, een situatie die in de praktijk niet kan werken.

Over een oplossing die wel bruikbaar is kun je deze maand wat lezen in een paper genaamd What every computer scientist should know about floating-point arithmetic. In deze paper uit begin jaren 90 wordt het probleem van fracties in wiskundige, technische maar ook software engineering termen uitgelegd. Dit is gebaseerd op een standaard genaamd IEEE 754 [1, 2] en beschrijft dus fractionele getallen in een eindig aantal bits kun opslaan. Hieronder kun je een afbeelding zien van een genormaliseerde floating point representatie (via wikipedia).

Hier kun je dus goed zien dat de significand, of mantisse, wordt vermenigvuldigd met een base (β) en een exponent (e). De precisie (p in de paper) van het getal (en daarmee dus de afwijking op de ‘echte’ waarde) wordt bepaald door het aantal bits wat wordt gereserveerd voor de verschillende getallen. Met het voorbeeld hierboven zullen 1.23451 en 1.23459 beiden als het hierboven afgebeelde getal worden opgeslagen. Dit laatste houdt in dat er 1 unit in the last place (ulp) aan precisie is verloren. Naast deze absolute beschrijving kun je deze drift ook nog relatief uitdrukken door $ulp / $getal = $relatieve_fout% te berekenen. Hierdoor kun je redeneren over de precisie van de berekeningen en verschillende situaties met elkaar vergelijken.

Lastig wordt het wanneer er gerekend moet gaan worden met deze getallen. Wat gebeurt er dan? Wat is de betekenis van een berekeningen die is gebaseerd op twee verschillende floating point numbers die beiden ook deze rounding errors hebben? Het antwoord is, zoals gebruikelijk, niet erg eenvoudig maar is wel uitgebreid beschreven in de paper en de standaard. Om te laten zien hoe je hier last van kunt hebben wil ik wel een voorbeeld van David Goldberg laten zien. Hij geeft als voorbeeld een bankrekening waar iedere dag 100$ in wordt gestort. Je krijgt hier een jaarlijkse rente van 6% over, die iedere dag wordt samengesteld. Dit betekend dat je de balans aan het einde van het jaar kunt berekenen met de formule 100[(1 + i/n)n – 1]/(i/n) als we stellen dat n = 365 en i = 0.6. Het exacte getal wat hier uit dient te komen is 37614.05, maar als je dit uitrekent met single precision floats kom je uit op 37615.45. Dit verschil van 1.40$ wordt veroorzaakt door het serieel uitvoeren van de machtsverheffing met een getal wat oorspronkelijk al een afrondingsfout heeft. Hierdoor vergroot je als het ware het effect van de afronding.

Nu zal, afhankelijk van de programmeertaal, dit voorbeeld wel of niet standaard hetzelfde resultaat hebben. Dit hangt namelijk af hoeveel bits er worden gereserveerd voor de precisie. Er zijn hier verschillende keuzes in; single precision (float), double precision (double) en extended double (long double) zijn de meest gangbare definities. Naarmate de precisie ook groter wordt is de impact natuurlijk ook kleiner. Daarnaast kan er door te schuiven met precisie (p) ook enorm bereik van een floating point getal worden gerealiseerd. Hierdoor onstaat echter weer een nieuw probleem: het rekenen met twee floating point getallen is erg lastig. Een float met een hoge precisie van een float met een lage precisie aftrekken kan resulteren in een effectieve no-op als het eerste getal kleiner is dan de precisie van het tweede.

Berekeningen brengen nog een ander probleem met zich mee: je kunt excepties krijgen. Deze excepties zijn bijvoorbeeld delingen door 0, over-, of underflows, Not a Number (NaN), ∞ etc. Om hiermee op een flexibele manier om te kunnen gaan zijn er twee technieken die gezamenlijk worden gebruikt door de code die de berekeningen uitvoert: status flags en traps. De eerste laat de code die een floating point berekening uit heeft laten voeren controleren of er bijvoorbeeld een overflow heeft plaatsgevonden. Dit is krachtig in combinatie met trap handlers: hierin kan een exceptionele berekening worden afgevangen, waarna men kan reageren en een nieuw resultaat kan teruggeven, eventueel in combinatie met het zetten van een of meerdere status flags. In hetzelfde voorbeeld kun je bijvoorbeeld bijhouden hoevaak iets overflowed, waarna je alsnog een goede benadering kunt geven van de uitgevoerde berekening.

Ik redeneer nu op een ontzettend kort-door-de-bocht manier over floating point getallen en de bijbehorende implementatie details, maar de details zijn veel te verregaand voor een nieuwsbrief artikel als dit. Mocht je het interessant vinden kan ik je aanraden om even de Wikipedia pagina [3,4] of de paper door te nemen. Het werkt heel verhelderend om te zien waarom dit nu zulke complexe materie is en geeft daarnaast nog op een interessante manier een historisch perspectief op de ontwikkeling van ‘rekenchips’ van vroeger.

Om dan af te sluiten: waarom moeten we dit weten? Wees je bewust van het type operatie dat je aan het uitvoeren bent en bepaal of een floating point getal, met variabele precisie, hiervoor geschikt is.

Meestal zal het antwoord hierop ‘ja’ zijn, maar in sommige scenario’s is dit zeker niet zo. Van alles wat bijvoorbeeld met financiële administratie te maken heeft kun je je afvragen of dit met een floating point kan worden uitgedrukt. Wees je hier van bewust en maak een weloverwogen keuze is het devies!


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Gave Technologie


Plaats een reactie

Jouw emailadres wordt nooit gepubliceerd of gedeeld. Benodigde velden zijn met * gemarkeerd.