Die Rekursion und der Kopfknoten (Heron)

[naequs]

Irgendwie tu' ich mich gerade schwer die annaeherung der quadratwurzel mittels der heronreihe xn+1=0.5*(xn+a/xn)
zu berechnen.
fuer a==1 und a==0 sind die abbruchbedingung ja klar.
wie ist das mit xn ? das ist ja die gewuenschte genauigkeit ..

die funktion wuerde dann ja irgendwie so aussehen:

double hsqrt(double a,double xn) {
if(a==0) return 0;
else if(a==1) return 1;
else if(xn>0) return 0.5*(xn+a/xn)+numsqrt(a, xn-1);
}

was aber so noch nicht richtig ist

 

[Hasentod]

Wenn du in jedem Iterationsschritt eins subtrahierst, kann das auch nix werden und addieren braucht man dort auch nichts.

xn ist nicht die Genauigkeit, sondern das derzeitige approximierte Ergebnis, dass weiter verfeinert wird.
Die Genauigkeit gibst du vor, indem du sie selbst als Abbruchkriterium definierst (siehe unten, als Differenz von x_n und x_n+1), oder die maximale Iterationstiefe beschränkst. Aufgrund der quadratischen Konvergenzrate des Newtonverfahren geht das recht flott und du bist nach wenigen Schritten unterhalb der Maschinengenauigkeit.

double hsqrt(double a, double xn){
	if (a == 0) return 0;
	if (a == 1) return 1;
		
	double xn1 = 0.5 * (xn+a/xn);
		
	if (abs(xn1-xn) < 0.000001) return xn1;
	else return hsqrt(a, xn1);
}

 

[Anapäst]

Read this line and do whatever it says twice.

 

[claus]

Abbruchbedingung ist wenn |x_n-a/x_n| (den Betrag kann man weglassen, weil nach dem ersten Schritt das Vorzeichen im Betrag gleich bleibt, weiß nur spontan nicht ob + oder -) unter der Zielgenauigkeit liegt (Ein Rechteck mit Seiten x_n und a/x_n hat Fläche a, weshalb die Wurzel von a zwischen beiden Seitenlängen liegen muss. Der Abstand zweier Iterierter ist nicht wirklich sinnvoll!), Ausgabe x_n.

Für 1 braucht man denke ich kein extra Abbruchkriterium (Kriegt man unter Umständen nur einen Näherungswert, aber irgendwo muss man sowieso eine Grenze ziehen, weil man nicht für alle Quadrate von natürlichen Zahlen if Fälle machen kann.)
Vor allem würde ich 0 und 1 wenn dann vorher prüfen und nicht bei jedem Schritt. (eventuell vor der eigentlichen Funktion negative Zahlen ausfiltern)

 

[Deaddy]

Read this line and do whatever it says twice.

Ich hasse Dich, hätte ich kein SIGINT bekommen wäre ich jetzt wohl verhungert.