Implementieren die Quadratwurzel Methode durch sukzessive Approximation

Question

die Quadratwurzel durch sukzessive Approximation Bestimmen des folgenden Algorithmus implementiert:

1. Begin durch Erraten, daß die Quadratwurzel x/2. Anruf, die g erraten.

2. Die tatsächliche Quadratwurzel muss zwischen g und x/g liegen. Erzeugen Sie bei jedem Schritt in der sukzessiven Approximation eine neue Schätzung durch Mittelwertbildung von g und x/g.

3. Wiederholen Sie Schritt 2, bis die Werte von g und x/g so nah beieinander liegen, wie es die Präzision der Hardware zulässt. In Java ist der beste Weg, um nach dieser Bedingung zu suchen, zu testen, ob der Durchschnittswert gleich einem der Werte ist, die verwendet wurden, um ihn zu erzeugen.

Was mich wirklich verwirrt, ist die letzte Anweisung der Stufe 3. ich es wie folgt interpretiert:

private double sqrt(double x) { 
    double g = x/2; 
    while(true) { 
     double average = (g + x/g)/2; 
     if(average == g || average == x/g) break; 
     g = average; 
    } 

    return g; 
} 

Dies scheint nur eine Endlosschleife zu verursachen. Ich folge dem Algorithmus genau, wenn der Durchschnitt entweder g oder x/g ist (die zwei Werte, die verwendet wurden, um ihn zu erzeugen), dann haben wir unsere Antwort?

Answer 1

Niemals Gleitkommawerte für Gleichheit vergleichen. Das Ergebnis ist nicht zuverlässig.

ein epsilon Verwenden Sie wie folgt:

if(Math.abs(average-g) < 1e-7 || Math.abs(average-x/g) < 1e-7) 

Sie können die Epsilon-Wert ändern, was Sie brauchen. Wahrscheinlich am besten ist etwas mit dem Original x.

Answer 2

Um zu überprüfen, ob g und x/g so nah sind wie die HW erlauben, sehen Sie sich den relativen Unterschied an und vergleichen Sie mit dem Epsilon für Ihr Gleitkommaformat. Wenn es innerhalb eines kleinen ganzzahligen Vielfachen von Epsilon ist, sind Sie in Ordnung.

Relative Differenz von x und y, ist etwa 1.0E-7 https://en.wikipedia.org/wiki/Relative_change_and_difference

Das epsilon für 32-Bit-IEEE-Floats sehen, wie sie in eine der anderen Antworten hier, aber diese Antwort verwendet, um die absoluten und nicht den relative Differenz.

In der Praxis bedeutet, dass so etwas wie:

Math.abs(g-x/g)/Math.max(Math.abs(g),Math.abs(x/g)) < 3.0e-7