Springen naar inhoud

Vergelijken van doubles


  • Log in om te kunnen reageren

#1

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 18 januari 2011 - 15:08

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.

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:
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?
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 18 januari 2011 - 16:46

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).
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#3

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 18 januari 2011 - 16:59

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 Bericht bekijken

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.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#4

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 18 januari 2011 - 23:43

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.
Een computertaal is voor mensen, niet voor de computer.

#5

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 19 januari 2011 - 01:33

- 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 :P 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.
In theory, there's no difference between theory and practice. In practice, there is.

#6

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 19 januari 2011 - 08:47

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.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#7

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 19 januari 2011 - 11:05

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 :P
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+15 relevant kunnen worden.

Je kunt voor dit geval trouwens ook checken of (abs(a)+abs(b))<epsilon.
In theory, there's no difference between theory and practice. In practice, there is.

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 19 januari 2011 - 12:27

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!
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures