4. Vergleich zweier Double Zahlen

Vergleich zweier Double Zahlen

  • L

    Hallo Leute,

    First of all: Mir ist klar, dass der folgende Code "falsch" ist. Mir ist klar, dass ich zwei Double Zahlen nicht einfach so vergleichen kann, weil deren Genauigkeit beschränkt ist und ich den Vergleich über ein δ machen müsste. Ich suche nur eine exemplarische Lösung - also nichts, was man in einem Programm verwenden würde, das man auf die Menschheit loslässt. Okay, ich habe folgenden Code hier:

    #include <stdio.h>

int main (void)
{
  double j;

  for( j = 0.0; j < 5.0; j += 0.1 )
    if( j == 2.0 )
      printf( "Habs\n" );

  return 0;
}

    Jedem von uns ist klar, dass das Programm unter normalen Umständen niemals "Habs" ausgeben wird. Gehen wir aber das Programm einmal formal durch. Ich habe eine terminierende Schleife und eine Überprüfung, ob j = 2 ist. In dem Fall findet eine Ausgabe statt, da j bei jeder Iteration erhöht wird, kann dies nur ein Mal passieren.

    Rein logisch betrachtet, kann man aus dem Programm auch folgendes machen:

    #include <stdio.h>

int main (void)
{
  printf( "Habs\n" );
  return 0;
}

    Der Compiler versucht natürlich die Programme zu optimieren, gibt es eine Möglichkeit, dass der Compiler das am Anfang genannte Programm zu dem zuletzt genannten "Optimiert"?

    0
  • ?

    Vielleicht kann der Compiler ein Loop unwinding durchführen.

    Es ergibt sich dann aus:

    for( j = 0.0; j < 5.0; j += 0.1 )
    if( j == 2.0 )
      printf( "Habs\n" );

    Folgendes:

    if (0.0 == 2.0) goto PRINT;
if (0.1 == 2.0) goto PRINT;
if (0.2 == 2.0) goto PRINT;
if (0.3 == 2.0) goto PRINT;
if (0.4 == 2.0) goto PRINT;
[...]

goto NOPRINT:

PRINT:
printf("Habs\n");
NOPRINT:

    Wie man sieht kann dieser Code dann ohne Probleme ausgewertet werden. Alle Aussagen, die nicht wahr sind fallen heraus. Es bleibt:

    if (2.0 == 2.0) goto PRINT;

goto NOPRINT:

PRINT:
printf("Habs\n");
NOPRINT:

    Diesen Code kann er wieder optimieren:

    goto PRINT
goto NOPRINT:

PRINT:
printf("Habs\n");
NOPRINT:

    Da das goto nun keine Existenzberechtigung mehr hat, kann der Code also schlussendlich auch so geschrieben werden:

    printf("Habs\n");
    0
  • J

    floating-point werte kann man *nie* auf "==" vergleichen!
    Du musst zum Vergleichen immer ein "Epsilon" angeben...

    Verwende z.B. sowas:

    #include <float.h>
bool AreSame(double a, double b) 
{ 
    return fabs(a - b) < DBL_EPSILON; 
}

    und in C++ ist vermutlich dies richtig:

    #include <cmath> 
#include <limits> 
bool AreSame(double a, double b) { 
    return fabs(a - b) < std::numeric_limits<double>::epsilon(); 
}
    0
  • A

    Jochen Kalmbach schrieb:

    floating-point werte kann man *nie* auf "==" vergleichen!

    Ja, wird aber z.T. auch in DirectX Header-Dateien praktiziert. Das ist mir hier aufgefallen: http://www.c-plusplus.net/forum/viewtopic-var-t-is-257817.html
    Kann später (wenn ich unter Windows bin) die Stellen in den Header-Dateien posten, falls Interesse besteht...

    Macht der MS Compiler daraus vielleicht automatisch einen Vergleich mit einem "Epsilon"?

    0
  • L

    Hallo Jochen,

    mir geht es bei meiner Frage nicht darum, dass tatsächlich ein Vergleich zweier Float Werte stattfindet, sondern dass der Compiler den Code optimiert und die Stelle so aussieht, wie löklöklö es in seinem Beitrag beschrieben hat.

    0
  • Z

    LL0rd schrieb:

    Der Compiler versucht natürlich die Programme zu optimieren, gibt es eine Möglichkeit, dass der Compiler das am Anfang genannte Programm zu dem zuletzt genannten "Optimiert"?

    Nein, du kannst das Ergebnis der Optimierung nicht vorhersagen, weil
    Optimierungsmethode und -Strategien von Compiler unterschiedlich gewählt und implementiert sein können.

    Leichteres Beispiel:

    Ein For-Schleife die zum Selbstzweck irgendetwas hoch zählt aber sonst keine Prüfungen oder Aktionen durchführt wird vom fast jeden C++ Compiler wegrationalisiert.

    0
  • ?

    Zeus schrieb:

    LL0rd schrieb:

    Der Compiler versucht natürlich die Programme zu optimieren, gibt es eine Möglichkeit, dass der Compiler das am Anfang genannte Programm zu dem zuletzt genannten "Optimiert"?

    Nein, du kannst das Ergebnis der Optimierung nicht vorhersagen, weil
    Optimierungsmethode und -Strategien von Compiler unterschiedlich gewählt und implementiert sein können.

    Leichteres Beispiel:

    Ein For-Schleife die zum Selbstzweck irgendetwas hoch zählt aber sonst keine Prüfungen oder Aktionen durchführt wird vom fast jeden C++ Compiler wegrationalisiert.

    Ich denke, es ging ihm ums Prinzip: Er wollte wissen, ob eine solche Optimierung möglich ist und wie der Compiler vorgehen könnte. Auch hat er darauf hingewiesen, dass in der "Realität" vergleiche mit Fließkommazahlen gefährlich sind und es sich um eine theoretische Frage handelt.

    0
  • R

    Der Compiler kann die Floatingpointoperationen ja simulieren und dann zum gleichen Ergebnis kommen, als wäre das Programm ausgeführt worden. Der GCC hat zB extra MPFR dabei, um so etwas zu simulieren.

    Jochen Kalmbach schrieb:

    floating-point werte kann man *nie* auf "==" vergleichen!
    Du musst zum Vergleichen immer ein "Epsilon" angeben...

    Verwende z.B. sowas:

    #include <float.h>
bool AreSame(double a, double b) 
{ 
    return fabs(a - b) < DBL_EPSILON; 
}

    und in C++ ist vermutlich dies richtig:

    #include <cmath> 
#include <limits> 
bool AreSame(double a, double b) { 
    return fabs(a - b) < std::numeric_limits<double>::epsilon(); 
}

    Nö.

    http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

    0
  • ?

    Mal was Anderes, die Zahlen wären doch sogar darstellbar, die Mantisse ist dual mit Impliziter Eins:
    z.B.:
    1.5 = 2^0 * 1.1000... (dual, dezimal 1,5)
    2.0 = 2^1 * 1.0000...
    3.5 = 2^1 * 1.1100... (1.11 dual = 1.75 dezimal)
    5.0 = 2^2 * 1.0100...

    Also könnte das Programm doch sogar laufen.

    Bei Zehnerschritten (j += 0.1) wärs natürlich was anderes.
    0.1 = 2^-4 * 1.1001100110011... dual unendlich

    Ist zwar hier belanglos, aber es sollte doch gehen, oder?

    0
  • K

    rüdiger schrieb:

    Der Compiler kann die Floatingpointoperationen ja simulieren und dann zum gleichen Ergebnis kommen, als wäre das Programm ausgeführt worden. Der GCC hat zB extra MPFR dabei, um so etwas zu simulieren.

    Jochen Kalmbach schrieb:

    floating-point werte kann man *nie* auf "==" vergleichen!
    Du musst zum Vergleichen immer ein "Epsilon" angeben...

    Verwende z.B. sowas:

    #include <float.h>
bool AreSame(double a, double b) 
{ 
    return fabs(a - b) < DBL_EPSILON; 
}

    und in C++ ist vermutlich dies richtig:

    #include <cmath> 
#include <limits> 
bool AreSame(double a, double b) { 
    return fabs(a - b) < std::numeric_limits<double>::epsilon(); 
}

    Nö.

    http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

    [/quote]

    🕶
    1. Die Lösung mit fabs() funktioniert auf jeden Fall.

    2. Es bleibt natürlich die einfache Lösung, die am Anfang gezeigte for-Schleife einfach in zwei aufzuteilen und so den Wert 2 auszuklammern.

    3. Es sollte einmal gesagt werden: man kann auch float's und double's mit Konstanten per == vergleichen! Das geht sicher allerdings nur in dem Spezialfall, dass die gleiche Konstante zugewiesen wurde und dann keinerlei Rechenoperation oder Typumwandlung durchgeführt wurde. Das kann nützlich sein, wenn man z.B. den Maximalwert von Datentypen als "ungueltiger Wert" definert und das im DEBUG Compile Modus massenhaft geprüft wird.

    /*! @brief  "Ungueltiger" Wert für eingebaute Datentypen.
*/
template<typename T>
inline T invalid() {
  assert(isFundamental(T()));
  return std::numeric_limits<T>::max();
}

// Spezialisierungen
template<>  inline unsigned char      invalid() { return UCHAR_MAX; }
template<>  inline char               invalid() { return CHAR_MAX;  }
template<>  inline unsigned short     invalid() { return USHRT_MAX; }
template<>  inline          short     invalid() { return SHRT_MAX;  }
template<>  inline unsigned int       invalid() { return UINT_MAX;  }
template<>  inline          int       invalid() { return INT_MAX;   }
template<>  inline unsigned long      invalid() { return ULONG_MAX; }
template<>  inline          long      invalid() { return LONG_MAX;  }
template<>  inline          float     invalid() { return FLT_MAX;   }
template<>  inline          double    invalid() { return DBL_MAX;   }

/*! @brief  Enthaelt die Variable einen "ungueltigen" Wert?
 *
 *  Diese Templatefunktion definiert den maximalen Wert des verwendeten
 *  Typs als ungueltig. Diese Definition wird beispielsweise benoetigt, um
 *  Ergebnisse von Schnittberechnungen als ungueltig zu deklarieren, wenn
 *  kein Schnittpunkt auftrat (z.B. bei parallelen Geraden).
 *
 * @note Auch bei Gleitkomma-Datentypen kann direkt mit numeric_limits<T>::max()
 *       d.h. FLT_MAX UND DBL_MAX verglichen werden, da keine Rechenoperationen
 *       durchgefuehrt wurden, sondern nur eine einfache Zuweisung in setInvalid().
 *       Das spart Rechenzeit.
 *
 * @see http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
 * @see http://hal.archives-ouvertes.fr/hal-00128124/en/
 *
 * @note Diese Funktion wird vor allem im DEBUG Fall extrem oft aufgerufen
*
 * @note Eigentlich waere   value != invalid<T>()  der Test, aber um eine
 *       "remark" Meldung des icc bei sehr hohen Warning-Levels zu vermeiden,
 *       verwenden wir      value <  invalid<T>(), das ist anscheinend gleich
 *       schnell. Allerdings erfasst das auch eventuell auftretende "NAN" Werte,
 *       z.B. bei Aufruf von acosf( 1.001 ).
 *
 * @author Michael Kohnen / Karsten Burger
 *
 * @param v   Variable eines fundamentalen Datentyps
 */
template<typename T>
inline bool isValid(const T& v ) { return v < invalid<T>();}

// Spezialisierung, weil es so haeufig aufgerufen wird (hilft bei -O0)
template<>
inline bool isValid(const float& v ) { return v < FLT_MAX;}
template<>
inline bool isValid(const long& v ) { return v < LONG_MAX;}

/*! @brief  Setze die Variable auf "ungueltig".
 *
 *  Diese Definition wird beispielsweise benoetigt, um Ergebnisse von
 *  Schnittberechnungen als ungueltig zu deklarieren, wenn kein Schnittpunkt
 *  auftrat (z.B. bei parallelen Geraden).
 * @author Michael Kohnen
 * @param[out] v
 */
template<typename T>
inline void setInvalid(T& v) { v = invalid<T>();}
    0
  • K

    First of all: Mir ist klar, dass der folgende Code "falsch" ist. Mir ist klar, dass ich zwei Double Zahlen

    Na dann multipliziert doch einfach mit 10 und nehmt int, anstatt einen Disput ueber das richtige Vergleichen von Fliesskommazahlen loszutreten. Waehle auch deinen Threadtitel entsprechend, wenn es dir nicht um den Vergleich, sondern um die Optimierung geht.

    gibt es eine Möglichkeit, dass der Compiler das am Anfang genannte Programm zu dem zuletzt genannten "Optimiert"?

    Tja, wahrscheinlich nicht bei der Sprache C (oder C++ oder Java oder ..). "Reasoning" ist sehr schwer fuer imperative Sprachen. Auch ist das wohl von Compiler zu Compiler verschieden. Hier ein Beispiel fuer Haskell mit LLVM: http://donsbot.wordpress.com/2010/03/01/evolving-faster-haskell-programs-now-with-llvm/

    It quickly drops down to the llvm -O3 plateau, then marches past that to turn the loop into a constant.

    Und bevor hier weiter spekuliert wird: Niemand hat sich den generierten Assemblercode angesehen. Geht hin und schaut selbst!

    0
Anmelden zum Antworten