[C++] doubles naar stream schrijven zonder precisieverlies?

[MrBucket]

Ik werk momenteel met CGAL, een template library voor geometrische datatypes en datastructuren. Nu wil ik mijn data uit zo'n datastructuur wegschrijven naar een stream, en gelukkig biedt die daar ondersteuning voor middels de bekende << en >> iostream overloads.

Uiteindelijk bestaat de weggeschreven data uit doubles, waarin de coordinaten van punten uitgedrukt worden. Echter, het is absoluut noodzakelijk dat ik de coordinaten zonder precisieverlies weg kan schrijven; zelfs bij hele kleine verschillen kan mijn algoritme al vastlopen als ik de volgende keer de data weer inlees.

Dus, wie kan me vertellen hoe ik de stream moet configureren om doubles zonder precisieverlies weg te schrijven? Kan het uberhaupt?

Ik heb al gekeken naar het gebruik van de setprecision en scientific manipulators, maar ik vraag me af hoeveel decimalen ik dan als precision in moet stellen? Volgens <limits> kan een double tot 15 decimalen precisie aan, maar dat garandeerd dan toch alleen dat de 15 weggeschreven decimalen ook echt de 15 decimalen zijn die je aan zo'n double hebt toegekend? (M.a.w. er zijn dus ook nog bits die niet weggeschreven worden).

Wie weet raad?

[Domokoen]

Ikzelf zou daarvoor overstappen op het 'wegschrijven' van het geheugen van de double. Een double neemt een x aantal bytes in in het geheugen, en door het met reinterpret_cast<unsigned char*>(&mijnDouble) te casten kan je erbij en dan x bytes wegschrijven, waarbij je voor x sizeof(double) gebruikt.
Dat gaat alleen niet zomaar met de << en >> operatoren, daarvoor moet je over op read/write methodes.

[Verwijderd]

Je kan hem ook in een int converteren

C:

int main() {
        double d_bla=123.456;
        int * i_bla=&d_bla;
        double * d_blub;
        d_blub=(double *)i_bla;
        printf("%d %f\n", *i_bla, *d_blub);
}

Output:
446676599 123.456000

Je kan niet het getal zelf casten, want dan gooit hij alles achter de komma gewoon weg. Bij een pointer casten wordt het getal zelf niet veranderd.

[MrBucket]

@Sjord:
Dit is ong. dezelfde oplossing als die Mr.Chinchilla aandraagt. Overigens is sizeof(double) 8 bytes, terwijl sizeof(int) 4 bytes geeft. Je zou dus 2 ints moeten serializen om een double op te slaan

@Mr.Chinchilla & Sjord:

Ik had er zelf ook al aan gedacht om de geheugen-representatie van doubles weg te schrijven in plaats van zijn getalsrepresentatie (als ints, of als een hex-string van die 8 bytes). Hier zitten echter twee nadelen aan:
• Ik kan de code die de datastructuur naar de ostream stuurt niet aanpassen, omdat het onderdeel is van die library. Dit betekent dat ik mijn eigen stream-class moet afleiden die een geoverloade <<-operator heeft voor doubles. Dit is niet erg flexibel en/of elegant, liever wil ik een oplossing die met de standaard iostream-functionaliteit te realiseren is.
• Het weggeschreven formaat is niet te lezen door mensen, en (wat erger is) ook niet door andere programma's die ascii-fileformaten ondersteunen. Ik weet bijvoorbeeld dat MilkShape het .asc-fileformaat van 3D Studio ondersteunt, en deze slaat doubles ook op als platte tekst. Omdat ik mijn data o.a. door MilkShape wil kunnen laten inlezen om het zo te kunnen bewerken, heb ik er weinig aan als ik mijn data voor mijn eigen programma in een alternatief formaat opsla, omdat ik dan voor MilkShape alsnog mijn toevlucht moet zoeken tot een inexact platte-tekst formaat.

Vandaar dat ik mijn doubles het liefst gewoon als leesbare tekst wegschrijf, met genoeg decimalen om het resultaat exact te houden.

Any ideas?

Ow, misschien een belangrijk detail: de getallen die ik opsla liggen in de range (-2000, 2000). Ik hoef dus geen belachelijk grote exponenten weg te kunnen schrijven, maar wel belachelijk kleine getallen...

[ Voor 8% gewijzigd door MrBucket op 20-02-2005 20:44 ]

[Macros]

Zoek even online hoeveel decimalen een double kan representeren, kan best 15 zijn ofzo, weet het niet uit mijn hoofd.
Maar.. doubles zijn altijd maar een benadering van het echte getal, als bij jou een 15de decimaal significant is voor je algoritme zou ik nog eens achter je oren krabben of je algoritme wel ideaal is. Want fouten hopen zich zowiezo op, ook als je de hele precisie van je doubles behoudt.

[MrBucket]

Macros schreef op zondag 20 februari 2005 @ 20:46:
Zoek even online hoeveel decimalen een double kan representeren, kan best 15 zijn ofzo, weet het niet uit mijn hoofd.

Klopt, maar volgens mij houdt die 15 dus in dat je in een double gegarandeerd een getal van 15 decimalen kan gieten, en als je die double afdrukt dat je dezelfde 15 decimalen te zien krijgt. Dit is volgens mij iets anders als: als ik mijn double wegschrijf als een getal van 15 decimalen, krijg ik na het inlezen weer dezelfde binaire representatie van die double.

Maar.. doubles zijn altijd maar een benadering van het echte getal, als bij jou een 15de decimaal significant is voor je algoritme zou ik nog eens achter je oren krabben of je algoritme wel ideaal is. Want fouten hopen zich zowiezo op, ook als je de hele precisie van je doubles behoudt.

Nou, eigenlijk is het niet mijn algoritme wat dan in de soep loopt, maar meer die van CGAL (die library waar ik mee werk). Tijdens het opbouwen van die datastructuur ben ik er bijvoorbeeld van gegarandeerd dat, als ik opgeef dat drie punten op 1 lijn moeten liggen, dat ik dan doubles terugkrijg waarvan CGAL vindt dat ze op 1 lijn liggen. Tijdens het inlezen van de datastructuur uit een stream wordt dit ook gecontroleerd. En als ik dus precisie-verlies oploop tijdens het wegschrijven/inlezen, dan kan CGAL nog wel eens tot de conclusie komen dat die 3 punten nu niet meer op 1 lijn liggen.

Dus eigenlijk wil ik gewoon CGAL tevreden houden

[ Voor 1% gewijzigd door MrBucket op 20-02-2005 20:55 . Reden: Iets verduidelijkt ]

[Hielko]

Wellicht dat je dan toch beter kan kiezen voor een iets ander algoritme/andere datastructuur. Het algoritme dat je nu gebruikt lijkt me niet erg robuust en een oplossing waarbij rekening gehouden wordt met het feit dat punten vanwege afrondingsfouten niet meer exact op 1 lijn liggen is toch het netste.

Ik weet niet wat je exact wil doen, maar blijkbaar is op een gegeven moment bekent dat 3 punten op een lijn liggen. Sla dan bijv. ergens op dat deze punten op een lijn liggen oid, of ontwerp een algoritme dat niet crasht wanneer een punt niet gevonden wordt op een lijn.

[Soultaker]

Een 64-bits double precision floating point number heeft 52 mantissa bits. Bit N (beginnend bij 1) representeert het getal 2^-N, als je dat uitschrijft krijg je dus:
• bit 1: 0,5₁₀ (1 decimaal)
• bit 2: 0,25₁₀ (2 decimalen)
• bit 3: 0,125₁₀ (3 decimalen)
• bit 4: 0,0625₁₀ (4 decimalen)
Elk bit is exact representabel met een eindig aantal decimalen en als je ze optelt wordt het vereiste aantal decimalen uiteraard niet hoger. Ook zie je dat je voor elke volgende bit een extra decimaal nodig hebt; dat is ook logisch natuurlijk, want 0,5 eindigt op een vijf en als je die deelt krijgt je 0,25, wat weer op een 5 eindigt, en die 5 blijft op die manier elke keer staan natuurlijk.

Hieruit volgt dat je om de 52 binaire cijfers achter de komma (binalen ) weer te geven ook 52 decimalen nodig hebt. Het probleem daarmee is dan weer dat dit alleen werkt als er geen exponent gebruikt wordt.

[MSalters]

Soultaker: een IEEE 64 bits double. Dat is gangbaar, maar niet universeel. VC++ is bijvoorbeeld in de meeste modes op x86 niet IEEE-compliant. Nou valt dat met het aantal bits wel mee, maar zo'n berekening over punten op een lijn is blijkbaar kritischer. Daar kan de optimizer setting zo een of twee bits schelen.

Je redenering is verder incorrect, omdat je berekent hoeveel decimalen er nodig zijn voor een precieze representatie. Dat was niet de vraag. Voorbeeld: met 2 bits heb ik aan één decimaal genoeg { 0,0 0,2, 0,5, 0,8 1,0 } om de 2 bits te reconstrueren. Het correcte antwoord is dat je kleinste weergegeven eenheid in het doel-stelsel kleiner moet zijn als de kleinste weergegeven eenheid in het bron-stelsel. Dus bij 2 bits is dat een kwart, en de eerste kleinere decimale eenheid is een tiende. Ook 3 bits kunnen dus nog in één decimaal (0.125 > 0.1 ) maar voor 4 bits heb je twee decimalen nodig (0.0625 > 0.01)

52 bits is ongeveer 4 * 10¹⁵, 2^-52 is dus ongeveer 2 * 10^-16 en je hebt dus 16 decimalen nodig. Het eerder gegeven antwoord van 15 decimalen is de andere kant op. In 52 bits passen 15 decimalen. (52 bits is in feite 15,65 decimalen)

[ Voor 13% gewijzigd door MSalters op 20-02-2005 23:45 ]

[Domokoen]

Er was een soort vuistregeltje om aantal bits beschikbaar om te rekenen naar 10-tallig stelsel.
Volgens mij: 52 mantissa bits * log(2)/log(10) = 52 * 0.3 = 15,6. Dus ongeveer 15 decimalen, maar om 'veilig' te zitten is 16 minimaal nodig.

Edit: MSalters heeft het inmiddels ook in zijn ge-editte post ingevoegd

[ Voor 17% gewijzigd door Domokoen op 20-02-2005 23:51 ]

[Soultaker]

Klopt inderdaad, zo had ik het niet bekeken. Neemt niet weg dat je op die manier wel afhankelijk bent van de manier waarop je afrond bij het inlezen: maak je van 0,3 nu 0,250 of 0.375? Maar goed, dat is een kwestie van consistent definiëren bij het wegschrijven en inlezen en dan komt dat wel goed.

[PrinsEdje80]

Kun je ze niet binair wegschrijven? Niet in een ascii bestand zoals je nu doet (althans, zo lijkt het mij)... Volgens mij dump je als het ware het getal in binaire code als je het wegschrijft en neemt dus ook een stuk minder ruimte in beslag.

[MrBucket]

Goed, ik ben ff aan het experimenteren geslagen, en het blijkt dat het volgende stukje code doubles zonder precisieverlies kan wegschrijven en weer inlezen:

C++:

int main(){
    //Seed the random number generator
    srand((unsigned)time( NULL ) );

    char acBuff[48];
    for(int x=0; x<500000; x++){
        double d, d2;
        d = generateDouble();

        sprintf(acBuff, "%.16E", d);
        d2 = atof(acBuff);
        assert(d == d2);
    }

    std::cout << "Done!";
    _getch();
    return 0;
}

Het blijkt dus idd dat je 16 decimalen precisie nodig hebt, bij 15 decimalen loop je wel precisieverlies op. Het nadeel is alleen dat zowel sscanf() als std::istream weigeren meer dan 15 decimalen te lezen; je hebt dus echt atof() nodig om het weggeschreven getal weer te parsen.

Goed, nu nog proberen om dan toch maar een afgeleide iostream-klasse te schrijven die zijn doubles wegschrijft en inleest in dit formaat.