Entwickler-Ecke :: Thema anzeigen - Wurzel ausrechnen nach dem Heronverfahren

kabuco - Mo 12.12.05 16:07
Titel: Wurzel ausrechnen nach dem Heronverfahren

Habe hier einen Algorithmus, der euch sicherlich interressieren sollte:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure TForm1.Button1Click(Sender: TObject);
var A,X : real;
begin
A := StrToFloat(Edit1.Text);
X := A;
repeat
X := (X+A/X)/2;
until abs(X-A/X)<0.000001;
Label2.Caption := 'Die Wurzel aus '+Edit1.Text+' ist '+FloatToStr(X);
end;

Ich setze mit diesem Code Voraus, das ihr ein Edit1 Feld habt und ein Label namens Label2. Und nartürlich einen Button.
Dieser Algorithmus berechnet die Wurzel aus A bis zur 5. Stelle nach dem Komma genau!

MFG
kab

kabuco - Di 13.12.05 14:31

Es ghet ja einfach nur darum, das man mal einen Algorithmus zur Wurzelbestimmung hat. Klar kann man das einfacher bekommen, aber das ist für alle Matheinterressierten unter uns!

delfiphan - Di 13.12.05 21:57

Dass es einen Algorithmus gibt, der das kann, ist ja nicht so erstaunlich.
Interessant wäre wenn schon dann die Herleitung. Ausserdem sollte man angeben unter welchen Bedingungen der Algorithmus konvergiert - und wieso die Sache dann bis auf 5 Stellen genau ist.

delfiphan - Di 13.12.05 22:19

@unforgiven: "Intervallschachtelung" ist nur ein Begriff und keine Erklärung. Was ich meinte war ein mathematischer Beweis, wieso gerade sqrt() rauskommt. Und: Als Abbruchkriterium kommt es wohl nicht gut raus, wenn du 1. eine absolute Toleranz setzst und 2. wenn diese noch so weit unter der Maschinengenauigkeit liegt.

Ich meinte eher so, zeigen, dass mit x'=f(x) für Fixpunkt x'=x gerade die Wurzel rauskommt, dann noch zeigen, wieso der Fixpunktsatz gilt. Dann noch eine obere Schranke für den Fehler angeben.

PS: Ich sehe ein, wir sind nicht bei den FAQs. Aber so bringt der Beitrag nicht sehr viel. Kein theoretisches Verständnis und kein praktischer Nutzen.

unforgiven - Di 13.12.05 23:13

nun ja, was wir hier mit der schleife bzw dem algorithmus machen is einfach eine intervallannährung...das heronverfahren ist ein nährungsverfahren

hier ist es gut beschrieben [http://home.schule.at/member/kimathe/wurzel_kurz5.htm]

PS.: dieses verfahren geht übrigens für alle wurzeln...egal wir groß der radikant und wie groß der wurzelexponent ist...mann müsste nur den algorithmus ein bisschen umschreiben...aber im großen und ganzen, kann man diesen algortihmus für alle qurzel nehmen...gut ist das für zB einen funktionsplotter...

bockwurst - Mi 14.12.05 17:02

Ich habe mir mal die Mühe gemacht,
diesen Algorithmus und den "normalen" Sqrt nach Geschwindigkeit zu testen.

Wer ist schneller?
Ich habe mit verschiedenen Werten eine große Schleife durchlaufen und mit Hilfe von GetTickCount die Zeit gemessen.

Der normale Sqrt war etwa um den Faktor 11 schneller !!!
(Compiler ohne Optimierung)

unforgiven - Mi 14.12.05 17:08

na ja, wobei das bei schnellen rechnern keinen großen unterschied hat...

große unterschiede werden nur bei komplexen berechnungen mit rekursiven methoden deutlich...da is iterativ oft schneller...

ich würde mal die function von sqrt sehen, wie die das gelöst haben...

Alstar - Mi 14.12.05 22:02

Ich glaube, dass das keinem weh tut, wenn ich hier den Stück Source aus der System.pas poste:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

function Sqrt(const X: Extended): Extended;
asm
        FLD     X
        FSQRT
        FWAIT
end;

Alstar

delfiphan - Do 15.12.05 01:33

@Alstar: Die Funktion wird nicht wirklich aufgerufen. Das geschieht in Delphi via "Compiler Magic"; d.h. der Compiler schreibt das grad direkt in den Code rein (geinlinet) und lässt den Funktionsaufruf einfach weg. Bei neueren Delphi Versionen zu mindest.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!