Quadratwurzel mittels Funktionswert der Quadratfunktion

[TimoN11]

Hey,
Die Aufgabe lautet:


Leider verstehe ich nicht wie man mit der Quadratfunktion die Wurzel herausbekommt.
Zudem verstehe ich auch nicht wie man eine binäre Suche für die Quadratfunktion erstellt -> Werte in ein Array füllen? Aber wie groß muss der x Wert dann sein.
Zudem muss das ganze rekursiv laufen.

Kann eventuell jemand die Aufgabe erklären?
Finde sie einfach zu ungenau formuliert.

Grüße,

 

[ImmerDieseKinder]

Ist auch nicht leicht zu verstehen, aber du kannst es so machen

Spoiler

    public static double qw2(double qw, double d) {
        // System.out.println(qw + " " + d);
        if (Math.abs(qw * qw - d) < 1.0e-8) {
            return qw;
        }
        return qw2((qw + d / qw) / 2, d);
    }

    public static double qw1(double d) {
        return qw2(d - 1, d);
    }

    public static void main(String[] args) {
        for (int i = 2; i < 101; i++) {
            System.out.println(qw1(i));
        }
    }

 

[fhoffmann]

Ist auch nicht leicht zu verstehen, aber du kannst es so machen

Das ist aber keine binäre Suche mit Hilfe der Quadrierung.

Die Idee ist folgende:
Um beispielsweise die Wurzel von 8 zu berechnen, probierst du eine Zahl aus, die zu klein ist (z.B. 0), und eine Zahl aus, die zu groß ist (z.B. 10 - welche du hier wählst, musst du dir selber überlegen).
Dann stellst du fest:
0 * 0 = 0 < 8
10 * 10 = 100 > 8
Die Wurzel von 8 muss also zwischen 0 und 10 liegen.
Dann probierst du die Mitte aus, also 5:
5 * 5 = 25 > 8
Die Wurzel von 8 muss also zwischen 0 und 5 liegen.
Dann probierst du die Mitte aus, also 2,5:
2,5 * 2,5 = 6,25 < 8
Die Wurzel von 8 muss also zwischen 2,5 und 5 liegen.
...

 

[ImmerDieseKinder]

binäre Suche

Das hatte ich auch zuerst, aber iwas wollte bei der Intervallhalbierung nicht funktionieren. Danke dass du die Bedingung nochmal aufgezeigt hast. Jetzt ist es ja easy.

 

[TimoN11]

Das ist aber keine binäre Suche mit Hilfe der Quadrierung.

Die Idee ist folgende:
Um beispielsweise die Wurzel von 8 zu berechnen, probierst du eine Zahl aus, die zu klein ist (z.B. 0), und eine Zahl aus, die zu groß ist (z.B. 10 - welche du hier wählst, musst du dir selber überlegen).
Dann stellst du fest:
0 * 0 = 0 < 8
10 * 10 = 100 > 8
Die Wurzel von 8 muss also zwischen 0 und 10 liegen.
Dann probierst du die Mitte aus, also 5:
5 * 5 = 25 > 8
Die Wurzel von 8 muss also zwischen 0 und 5 liegen.
Dann probierst du die Mitte aus, also 2,5:
2,5 * 2,5 = 6,25 < 8
Die Wurzel von 8 muss also zwischen 2,5 und 5 liegen.
...

Hey, danke hab es jetzt umgesetzt.
Bei Werten wie 9, 18, 64, 25, 101 kriege klappt es wunderbar.
Aber bei Werten wie z.B. 5, 1011 kriege ich ein Stack Overflow.
Kannst du vielleicht über mein Code drüber schauen?

public class Aufgabe2 {
public static double Quadratwurzel(double a){
if(a < 0) return Double.NaN;
else{
    double anfang = 0;
    return binaereSuche(a,anfang, a);
}
}
public static double binaereSuche(double a, double anfang, double ende){
    if((anfang*anfang) == a || (ende*ende) == a){
        if((anfang*anfang) == a) return anfang;
        else if((ende*ende) == a) return ende;
    }else{
        double mitte = (anfang+ende)/2;
        if(mitte*mitte == a) return mitte;
        else if (mitte*mitte > a) return binaereSuche(a,anfang,mitte);
        else if (mitte*mitte < a) return binaereSuche(a,mitte,ende);
    }
    return 0;
}

 

[TimoN11]

Gibt es eine Möglichkeit das return 0; am Ende von der binaereSuche Methode wegzulassen? Wenn ich den weglasse spuckt mit der Compiler ein Error raus, obwohl im else Bereich bereits return enthalten sind.

 

[fhoffmann]

- Beim rechnen mit double können immer kleine Fehler auftreten. Das kann dazu führen, dass die Bedingung anfang*anfang) == a || (ende*ende) == a nie erfüllt ist. Du solltest hier besser abfragen ende - anfang < 0.000001.

- Das return kannst du dir sparen, wenn du nach dem letzen else das if weglässt.

 

[Blender3D]

Gibt es eine Möglichkeit das return 0; am Ende von der binaereSuche Methode wegzulassen? Wenn ich den weglasse spuckt mit der Compiler ein Error raus, obwohl im else Bereich bereits return enthalten sind.

Der Code funktioniert so nicht teste einmal die Wurzel aus 2. Das führt zu einem Stackoverflow da sich der Zielwert zu langsam annähert.
Du benötigst eine Rekursionsbeschränkung.
[CODE lang="java" title="Wurzel Binär" highlight="16-20, 3-6"]public class SquareRoot {
public static void main(String[] args) {
double[] value = { 0, 2, 1, 1000, 9, 3.141, -1 };
for (int i = 0; i < value.length; i++)
System.out.println(
(i + 1) + "\t rootOf(" + value + ")\t-> " + sqrt(value) + "\t(" + Math.sqrt(value) + ")");
}

public static double sqrt(double value) {
if (value < 0)
return Double.NaN;
return sqrt(value, 0, value, 1000);
}

private static double sqrt(double value, double min, double max, int stepLimit) {
double middle = min + (max - min) / 2;
double square = middle * middle;
if (square == value || stepLimit == 0)
return middle;
return value > square ? sqrt(value, middle, max, stepLimit - 1) : sqrt(value, min, middle, stepLimit - 1);
}
}[/CODE]

 

[fhoffmann]

Bei einer Zahl, die kleiner als 1 ist, ist die Wurzel größer als die Zahl!
Hier funktioniert es also nicht, die Zahl selbst anfangs als "ende" bzw. "max" zu nehmen.

 

[ImmerDieseKinder]

@Blender3D kleiner Tipp:

    public static double sqrt(double value) {
        if (value < 0) // + value >= Double.MAX_VALUE-1 ...
            return Double.NaN;
        return sqrt(value, -1, value + 1, 1000);
    }

    private static double sqrt(double value, double min, double max, int stepLimit) {
        double mid = (min + max) / 2.0;
        double sqr = mid * mid;
        if (sqr == value || stepLimit == 0)
            return mid;
        return value > sqr ? sqrt(value, mid, max, stepLimit - 1) : sqrt(value, min, mid, stepLimit - 1);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 101; i++) {
            System.out.println(sqrt(i / 10.0));
        }
        System.out.println(sqrt(10_000));
    }