Vergelijken van doubles

[jhnbk]

De meesten onder jullie weten hopelijk dat het vergelijken van twee variabelen van het type double (of float) risico's met zich meebrengt als deze variabelen afkomstig zijn van berekeningen. Met invoer en initialisatie lukt het nog net om waarden te vergelijken.

In volgende voorbeeld wordt dit op eenvoudige wijze getoond en al een oplossing gegeven met de statisch methode gelijk.

Code: Selecteer alles

public class Nauwkeurigheid {

public static double epsilon=10e-40;

public static void main(String[] args) {

double a=0.3;

double b=0.2;

double c=0.1;

System.out.println(c+b+a);

System.out.println(c+b+a == 0.6);

System.out.println(gelijk(c+b+a,0.6));

System.out.println();

System.out.println(a+b+c);

System.out.println(a+b+c ==0.6);

System.out.println(gelijk(a+b+c,0.6));

}

public static boolean gelijk(double a, double b){

return Math.abs(a-b)<epsilon;

}

}

Met uitvoer:

Code: Selecteer alles

0.6000000000000001

false

false

0.6

true

true

Nu komt het wel eens vaker voor dat getest moet worden of doubles eenzelfde waarde hebben. Echter, de grootte orde van deze waarden verschil van programma tot programma en zelfs in de programma's. De keuze van de waarde epsilon ligt dan ook niet voor de hand.

De vraag is dus als volgt:

- Wat zijn de richt waarden van epsilon zo al?

- zijn er beter methoden om gelijkheid van doubles te controleren.

- doubles hebben een eindige precisie. Is er een interval waarin de berekeningen met een optimale nauwkeurigheid kunnen gebeuren?

[317070]

De vraag is dus als volgt:

- Wat zijn de richt waarden van epsilon zo al?

- zijn er beter methoden om gelijkheid van doubles te controleren.

- doubles hebben een eindige precisie. Is er een interval waarin de berekeningen met een optimale nauwkeurigheid kunnen gebeuren?

Normaal gezien als je doubles op gelijkheid test, doe je iets verkeerd

Maar die epsilon is de standaardmethode om het te doen, als je het toch zou doen.

Verder werkt double op een exponentiële schaal (ongeveer...), dus deel je beide getallen door elkaar, en stelt dat het dan 0.01% van 1 mag afwijken (dat is de richtwaarde die ik gebruik), ga je vrijwel geen vals-negatieven hebben. (zie ook MSDN)

Door die exponentiële schaal is er ook geen 'beste' interval. (Uiteraard moet je WEL over- en underflow voorkomen).

[jhnbk]

Normaal gezien als je doubles op gelijkheid test, doe je iets verkeerd

An sich wel maar ik heb 6 gigantisch formules (en dan bedoel ik echt gigantisch) die ik kan vereenvoudigen als a=b=0 en dit zijn uiteindelijk doubles. Ik weet zeker dat ik daar met een simpele if de rekentijd van die formule tot ongeveer 1/5 zal kunnen brengen en alle kleine beetjes helpen.

Maar die epsilon is de standaardmethode om het te doen, als je het toch zou doen.

Verder werkt double op een exponentiële schaal (ongeveer...), dus deel je beide getallen door elkaar, en stelt dat het dan 0.01% van 1 mag afwijken (dat is de richtwaarde die ik gebruik), ga je vrijwel geen vals-negatieven hebben. (zie ook Door die exponentiële schaal is er ook geen 'beste' interval. (Uiteraard moet je WEL over- en underflow voorkomen).

Spreekt voor zich. Het was gewoon een vraag aangezien ik met het aanpassen van eenheden ineens de range waarin de berekeningen uitgevoerd worden kan aanpassen.

[Schwartz]

Men kan twee doubles testen door de opslag van de doubles te testen op byte nivo.

Door de 0.3333333 en 1/3 opgave goed te formuleren komt men een heel eind.

Men test of de cijfers achter de komma gelijk zijn. (dit is een aparte byte of meer bytes afhankelijk van de opslag)

En dan test men de rest waarbij men eventueel eerst de laatste bits op nul zet zodat men een andere precisie bekomt.

en dan is 333`33+(bit aan) en 333`33+(bit uit) gelijk aan elkaar.

En ook de - en + eerst testen...

Bij een gehele getal opgave doet men deze methode dan niet want anders hangt men zich op.

Je kunt het pas toepassen indien de double voorbij zijn precisie is.

(dan is het onbekend wat er allemaal achter de komma is)

De laatste bit is dan feitelijk random en die schakelt men uit door de laatste bit op 0 te zetten.

[Rogier]

- Wat zijn de richt waarden van epsilon zo al?

Ruwweg kun je er vanuit gaan dat een double een 64-bits IEEE floating point is, wat inhoudt dat er 53 bits voor de mantissa (het getal voor de exponent) gebruikt wordt. Verschillen kleiner dan 2^-53 1e-16 keer het getal vallen daardoor buiten de precisie.

Ik ga zelf altijd uit van ongeveer 1e-10 keer de orde van grootte van de getallen die ik wil vergelijken. Met die 1e-40 in je voorbeeld (om getallen van 0.6 te vergelijken) zat je dus veel te laag.

Als die orde van grootte op een bepaalde plek in je programma heel sterk uiteen kan lopen, zou je epsilon daar nog van kunnen laten afhangen, bijvoorbeeld door iets als epsilon=min(abs(a),abs(b))*1e-10 te nemen, maar dat zou dan niet altijd kloppen als a of b nul kan zijn.

Je schreef dat je je formule kan optimaliseren als a=b=0. Als a of b niet nul is, enig idee in welk gebied ze dan in jouw praktijksituatie liggen?

- zijn er beter methoden om gelijkheid van doubles te controleren.

Die abs + epsilon methode werkt op zich uitstekend, mits je een geschikte epsilon kiest (1e-10 maal de orde van grootte van de doubles is prima).

- doubles hebben een eindige precisie. Is er een interval waarin de berekeningen met een optimale nauwkeurigheid kunnen gebeuren?

De precisie is in verhouding tot het getal zelf altijd even groot.

Omdat het een exponentiële representatie is, is in absolute zin de precisie rondom 0 het grootst (dat wil zeggen als bijvoorbeeld p=1e-12, dan zijn er veel meer verschillende doubles tussen 0 en p dan tussen 1 en 1+p), maar daar heb je in de praktijk natuurlijk niks aan.

[jhnbk]

Ik heb geen idee van de grootte ordes van a en b. Een standaard epsilon die in meeste van de gevallen dan a=b=0 detecteert zal wel in orde zijn aangezien de extra berekening wel tijdrovend is maar met eenzelfde resultaat (hopelijk )

Te onthouden dus als richtlijn:

1e-10 maal de orde van grootte van de doubles is prima).

Bedankt iedereen voor de toelichtingen!

@Schwartz: beslissen of een getal kleiner of groter is kan uiteraard op byte niveau omdat deze ook de sortering respecteren als ik het goed voor heb.

Wat jij voorstelt om gelijkheid te testen lijkt mij niet ideaal aangezien beide getallen van een berekening kunnen komen.

[Rogier]

aangezien de extra berekening wel tijdrovend is maar met eenzelfde resultaat (hopelijk )

Dan zou ik even nagaan waar dat ongeveer geldt, en dan epsilon van die grens laten afhangen

Als je geen idee hebt van de orde van grootte, zou het dus kunnen dat het resultaat met a=b=10^-20 al significant anders is dan met a=b=0, maar de verschillen zouden ook pas vanaf a=b=10⁺¹⁵ relevant kunnen worden.

Je kunt voor dit geval trouwens ook checken of (abs(a)+abs(b))<epsilon.

[jhnbk]

Na mijn examens zal ik de grootte ordes eens uitzoeken. Voorlopig stelt het probleem zich niet echt aangezien de invoer a en b meestal direct wordt ingegeven als 0.0

Bedankt!