2013-11-22 15 views
5

Let, x ist eine ganze Zahl und y = x * x.C++ sqrt-Funktionspräzision für volle Quadrate

Dann ist es garantiert, dass sqrt(y) == x?

Zum Beispiel kann ich sicher sein, dass sqrt(25) oder sqrt(25.0)5.0 zurückkehren, nicht 5.0000000003 oder 4.999999998?

+3

Wenn 5 nicht genau dargestellt werden kann, wie könnte es? Das Beste, auf das Sie hoffen können, ist, dass es auf 5 gekürzt wird. – chris

+0

Wie 5 ist eine ganze Zahl, sollte es nicht genau dargestellt werden? Ich habe irgendwo gelesen, dass double genau die Werte im ganzzahligen Bereich speichern kann. –

+2

@RafiKamal: Ein 64-Bit-IEEE-754-Float mit doppelter Genauigkeit kann den gesamten Bereich von 32-Bit-Ganzzahlen mit und ohne Vorzeichen ohne Verlust genau darstellen. Das regelt nur Typumwandlungen in genau diesem Fall.Es regelt nicht die Genauigkeit der Fließkomma-Bibliothek, die 'sqrt (x)' berechnet. –

Antwort

4

Nein, das kann nicht garantiert werden. Für Integer und ihre Quadrate, die in den dynamischen Bereich der Fließkomma-Mantisse passen (2^53 für ein typisches C/C++ double), sind Sie wahrscheinlich OK, aber nicht unbedingt garantiert.

Sie sollten Gleichheitsvergleiche zwischen Gleitkommawerten und exakten Werten vermeiden, insbesondere exakte ganzzahlige Werte. Fließkomma-Rundungsmodi und andere solche Dinge können Ihnen wirklich in die Quere kommen.

Sie möchten entweder einen "Vergleichsbereich" verwenden, um ein "ungefähr gleich" -Ergebnis zu akzeptieren, oder Ihren Algorithmus in Ganzzahlen umwandeln. Es gibt mehrere StackOverflow-Fragen, die Gleichheitsvergleiche für Gleitkommazahlen abdecken. Ich schlage vor, Sie suchen nach ihnen und lesen.

Für eine bestimmte Klasse von Problem, habe ich hier eine alternative Lösung gefunden: Find n-th root of all numbers within an interval

Diese Lösung einen anderen Ansatz hat als auf kniffliger Gleitkomma-Arithmetik zu verlassen.

8

Eine Implementierung, die dem IEEE-754-Standard für zulässige Fehler für grundlegende Operationen entspricht (von denen sqrt ein Beispiel ist) erfordert, dass die Werte korrekt gerundet werden.
Dies bedeutet, dass der Fehler weniger als 1/2 ULP (Einheit an der letzten Stelle) oder grundsätzlich so nah wie möglich an der tatsächlichen Antwort liegt.

Um Ihre Frage zu beantworten, wenn die tatsächliche Antwort ist genau darstellbar durch eine double dann erhalten Sie die genaue Antwort.

Hinweis: Dies wird nicht vom C++ - Standard garantiert, sondern vom IEEE-754-Standard, der für die meisten Benutzer wahrscheinlich kein Problem darstellt.

Letztlich soll ein einfacher Test für Ihre Zwecke ausreichend sein:

for(int i = 0; i < (int)std::sqrt(std::numeric_limits<int>::max()); i++) 
    { 
     assert((int)(double)i == i);//Ensure exactly representable, because why not 
     assert(std::sqrt((double)i*i) == i); 
    } 

Wenn dies passiert, ich sehe keinen Grund zur Sorge.

1

Sie sollten Brute-Force-Suche alle Werte bis zu 2^26 ziemlich leicht, aber ich glaube, die Antwort ist ja. Nach dieser Nummer, nein.

Der digitalisierte Lehrbuchalgorithmus für Quadratwurzel endet mit Rest == 0, was genaue Ergebnisse liefert. Wenn eine Fließkomma-Bibliothek die ieee-754-Konformität beansprucht, wird sie diesen Wert ebenfalls auf andere Weise angeben.