3. Schnelle Rundungsfunktion

Schnelle Rundungsfunktion

  • ?

    Hi,

    bisher benutze ich zum Runden von double's folgendes Macro:

    MY_ROUND(inVal,numDig) (((double)(int)((inVal)*pow((double)10,numDig)+CNCO_SIGN(inVal)*0.5))/pow((double)10,numDig))

    inVal ist der zu rundende Wert, numDig legt die Anzahl der Nachkommastellen fest, auf die gerundet werden soll.

    Dank der pow()'s und Divisionen ist das Makro natürlich nicht sehr schnell. Deswegen meine Frage: welche Alternativen gibt es hier? Eventuell eine schnelle Funktion aus dem C++-Standard? Oder ein besserer Ersatz für mein Macro?

    Danke!

    0
  • ?

    Da mit CNCO_SIGN unbekannt ist, habe ich einfach mal danach gesucht. Google findet lustigerweise genau einen Treffer - nämlich genau dieselbe Frage auf SO: https://stackoverflow.com/questions/39368809/fast-rounding-function-with-variable-precision

    Mir fallen Fragen ein:
    a) warum nicht als Funktion statt als Macro?
    b) dieses ganze rumgecaste: was, wenn der int-Wert nicht in double passt?
    c) was soll eigentlich genau erreicht werden? Was soll der Ausgabetyp sein? Etwa double, der ggf. das gerundete Ergebnis nicht exakt darstellen kann?

    0
  • ?

    Argh, b) war natürlich auch umgekehrt gültig: was, wenn der double-Wert nicht in int passt? Welche Typen/Werte sollen überhaupt für inVal und numDig eingesetzt werden?

    0
  • W

    stellt sich noch die Frage: warum überhaupt im Dezimalsystem runden. Dies ist nämlich für einen beliebiegen double i.A. gar nicht möglich. So ist z.B. die Zahl 0,1 im Binärsystem mit endlicher Anzahl von Nachkommastellen gar nicht darstellbar.
    Wenn Du schreibst

    double a = 0.1;

    so enthält 'a' einen Wert von etwa 0.10000000000000001. Die nächst kleinere Zahl im Bereich double (8 Byte) müßte so bei 0.099999999999999992 liegen. Dazwischen gibt es schlicht nichts. Was willst Du da also runden?

    Wenn das Runden nur die Ausgabe betrifft, so greife auf die Mittel zurück, die die Ausgabefunktionen bieten. Das ist dann auch viel schneller.

    0
  • D

    Warum nicht so?

    #include <cmath>

#include <iostream>

constexpr double operator "" _digits(unsigned long long n)
{
	return std::pow(10., n);
}

constexpr double round(double n, double factor)
{
	return std::round(n * factor) / factor;
}

int main()
{
	double const almost_pi = 3.1415927;
	std::cout << round(almost_pi, 2_digits) << std::endl;
	return 0;
}

    Generell auch zu dem Makro:
    pow (bzw. std::pow) könnte ab C++11 constexpr sein,
    auch wenn ich dazu auf cppreference nichts finden konnte...
    Der GCC macht es jedenfalls 🙂
    Damit kann bei einer zur Compile-Time bekannten Rundung schonmal das potenzieren rausoptimiert und durch einen konstanten Wert ersetzt werden.

    Danach hast du eigentlich nur noch Multiplikationen und Divisionen.
    Die fliegen auch raus, wenn dein Eingabewert auch zur Compile-Time bekannt ist.

    Davon abgesehen ist die moderne Variante trotzdem aus mehreren Gründen zu bevorzugen:

    • Kein Makro! (Makros haben keinen direkten Scope und verschmutzen im Grunde die ganze Übersetzungseinheit)
    • Dein Makro wertet seine Parameter mehrfach aus, was besonders doof ist, wenn jemand als Parameter sowas wie "foo++" angibt.
    • Durch den nutzerdefinierten Literal wird auch direkt deutlich, was die Parameter tun: 1. welcher Wert gerundet wird, 2. auf wie viele Nachkommastellen
    0
  • ?

    Um das mal zu erklären: ich verwende die Rundungsfunktion, um z.B. Vergleiche mit begrenzter Genauigkeit durchzuführen.

    Wenn z.B. zwei double-Werte 6.12349684731 und 6.12348874662 vorkommen, so sind diese nicht gleich. Jetzt benötige ich aber nur eine Genauigkeit von 4 Nachkommastellen, also runde ich die beiden Werte nach 6.1235 und 6.1235 -> sie sind gleich. Wenn mir double auf Grund seiner Beschränkungen da jetzt aber beispielsweise 6.12349999999 und 6.12349999999 draus macht, ist mir das auch egal, weil der Vergleich in dem Falle auch wieder ergibt, dass sie gleich sind.

    0
  • ?

    Was spricht dann dagegen, einfach die Differenz zu bilden?

    auto d1 = 6.12349684731;
auto d2 = 6.12348874662;
std::abs(d1-d2)
(double) 8.10069e-06
std::abs(d1-d2) < 0.0001
(bool) true
    0
  • D

    Die Genauigkeit hängt nicht von den Nachkommastellen1 ab, sondern von den signifikanten Stellen.

    1Bei der Exponentialschreibweise kann man die Nachkommstellen betrachten.

    0
  • Mod

    Das was DirkB sagt. Aber noch mit der Ergänzung, dass auch das nicht reicht. Die dumme 0 macht alles kaputt und es gibt noch weitere mögliche Komplikationen. Das ganze Thema ist schwierig (und zwar sehr viel schwieriger, als der TE denkt!) und es gibt leider keine zufriedenstellenden Lösungen, die wirklich alle Fälle abdecken. Siehe hier für eine Abhandlung:
    https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/

    Noch eine interessante Lösung technischer Art: Nach IEEE 754 ist die Integer-Repräsentation von Fließkommazahlen geordnet. Wenn man sich also darauf verlassen kann, dass die Maschine diesen Standard benutzt (kann man zu 99.9999%) und man hat Zugriff auf diese Repräsentation (in C++ kein Problem), dann kann man sich ausrechnen, um wie viele float-"Schritte" sich zwei Werte unterscheiden und danach ein Vergleichskriterium bauen. Das Problem mit der 0 bleibt jedoch bestehen 😞

    0
  • W

    Morom schrieb:

    Wenn z.B. zwei double-Werte 6.12349684731 und 6.12348874662 vorkommen, so sind diese nicht gleich. Jetzt benötige ich aber nur eine Genauigkeit von 4 Nachkommastellen, also runde ich die beiden Werte nach 6.1235 und 6.1235 -> sie sind gleich.

    nach dem Verfahren wären 6.12346 und 6.12354 gleich, aber 6.12346 und 6.12344 wären nicht gleich, obwohl ihre Differenz nur 1/4 von der Differenz des ersten Zahlenpaars ausmacht.

    0

  • Vergleiche mit begrenzter Genauigkeit

    Wie wärs damit?

    bool is_almost_equal(double a, double b, double prec=0.0001)
{
    return abs(a-b) <= prec; // ?
}
    0
  • Mod

    Ist halt die Frage, ob 1e-7 und 1e-17 wirklich als gleich gelten sollen, obwohl 10 Größenordnungen (und ca 1.5e17 potentielle double-Werte) dazwischen liegen.

    Oder ob 1.00001 und 1000002 wirklich als gleich gelten sollen, während 100000000000001 und 100000000000002 als verschieden gelten (obwohl da nur 64 andere Werte zwischen gehen!).

    0

  • Ja, das ist alles nicht so einfach.
    Ich weiss auch gar nicht ob man überhaupt eine richtig schnelle (und gleichzeitig schlaue) Epsilon-Equals Funktion machen kann. Also z.B. eine wo Epsilon ein vielfaches der "Unit in the Last Place" (ULP) ist.
    Wenn's auch langsam sein darf, dann ist es nicht so schwer. ULP der grösseren Zahl ermitteln, mit Konstante multiplizieren, und dann gucken ob die Differenz der beiden Zahlen betragsmässig kleiner ist.

    @Morom
    Muss dein Test auf "Gleichheit" transitiv sein?
    Wenn nein, dann bietet sich eine Epsilon-Equals Funktion mit manuellem Epsilon an, so wie wob bzw. HarteWare es vorgeschlagen haben.

    Und wenn du eine transitive Funktion brauchst, dann ist vermutlich Runden eh die beste Lösung. Nur würde ich, wenns geht, auf binäre Stellen runden und nicht auf dezimale.

    0
  • Mod

    hustbaer schrieb:

    Ja, das ist alles nicht so einfach.
    Ich weiss auch gar nicht ob man überhaupt eine richtig schnelle (und gleichzeitig schlaue) Epsilon-Equals Funktion machen kann. Also z.B. eine wo Epsilon ein vielfaches der "Unit in the Last Place" (ULP) ist.
    Wenn's auch langsam sein darf, dann ist es nicht so schwer. ULP der grösseren Zahl ermitteln, mit Konstante multiplizieren, und dann gucken ob die Differenz der beiden Zahlen betragsmässig kleiner ist.

    Die schnelle Methode dafür habe ich doch schon genannt. Nach int casten, Differenz bilden, mit Vorgabe vergleichen. Funktioniert auf jeder IEEE 754 Maschine. Eventuell noch Sonderbehandlung für NaN, inf, usw. einführen.

    Problem ist halt, dass solch ein flexibler epsilon-Vergleich nicht mit der häufig gewünschten Funktionalität kompatibel ist, unter einer gewissen Schranke alles als 0 anzusehen. Da muss man dann wieder eine Sonderprüfung einbauen.

    0

  • hustbaer schrieb:

    so wie wob bzw. HarteWare es vorgeschlagen haben.

    Ach, ich Blindfisch! Habe diesen kleinen Code-Snippet voll übersehen. War natürlich nicht meine Absicht alles zwei Mal zu sagen.

    0

  • @SeppJ
    Womit wir wieder beim Thema "scheiss strict aliasing" wären 😃

    0
Anmelden zum Antworten