Dass ich die Wurzelfunktion mittels Heron-Verfahren berechnen kann ist mir bekannt. Meine Frage. Wie berechnet denn die sqrt-Funktion aus der C-Bibliothek math.h die Wurzel? Welche Algorithmen stecken da dahinter? Findet man das irgendwie raus? Grüße Jens
Jens B. schrieb: > Dass ich die Wurzelfunktion mittels Heron-Verfahren berechnen kann ist > mir bekannt. Meine Frage. Wie berechnet denn die sqrt-Funktion aus der > C-Bibliothek math.h die Wurzel? Welche Algorithmen stecken da dahinter? > Findet man das irgendwie raus? Am sichersten gehts immer, wenn man sich den Source Code der Runtime-Bibliothek besorgt. Für Wurzel gibt es viele Verfahren. Wenn du mal danach googelst, wirst du sicherlich einige finden. (In Ermangelung eines guten Gedächtnisses würde ich eine Newton Iteration für eine double Wurzel benutzen. Für Integer-Wurzeln gibt es aber bessere Verfahren)
Karl heinz Buchegger schrieb: > (In Ermangelung eines guten Gedächtnisses würde ich eine Newton > Iteration für eine double Wurzel benutzen. Für Integer-Wurzeln gibt es > aber bessere Verfahren)
1 | double mySqrt( double value ) |
2 | {
|
3 | double result; |
4 | double nextResult; |
5 | |
6 | //
|
7 | // nur um sicher zu gehen
|
8 | //
|
9 | if( value < 0.0 ) |
10 | value = value; |
11 | |
12 | //
|
13 | // die erste Schätzung
|
14 | //
|
15 | result = value; |
16 | nextResult = value / 2.0; |
17 | |
18 | //
|
19 | // mittels Newton verfeinern, bis die gewünschte Genauigkeit
|
20 | // erreicht ist
|
21 | //
|
22 | // Newton
|
23 | // gegeben: x^2 - a = 0 ( a ist die Zahl, deren Wurzel gesucht wird)
|
24 | // und gegeben eine Schätzung für xi, dann ist
|
25 | // xn = x - f(x) / f´(x)
|
26 | // ein besserer Wert für x, der die Gleichung löst
|
27 | //
|
28 | // f(x) = x^2 - a
|
29 | // f´(x) = 2*x
|
30 | //
|
31 | while( fabs( result - nextResult ) > 0.00001 ) |
32 | {
|
33 | result = nextResult; |
34 | nextResult = result - ( result * result - value ) / ( 2 * result ); |
35 | }
|
36 | |
37 | return nextResult; |
38 | }
|
Edit: nextResult = result - ( result * result - value ) / ( 2 * result ); ist eine ziemlich naive Umsetzung der Newton Formel. Die kann man noch mit arithmetischen Mitteln vereinfachen :-) nextResult = ( result + value / result ) / 2;
Jens B. schrieb: > ... > Findet man das irgendwie raus? > > Grüße > Jens Quelltext? Und dann hier kurz beschreiben?
nee. die Frage war nicht ganz richtig verstanden worden. Ich hab verstanden, wie ich die Wurzel selbst "zu Fuß" berechne, nämlich mit Newtoniteration was bei der Wurzel als Heron-Verfahren bezeichnet wird. ich würde gern wissen, wie die gängigen Compiler die Wurzel berechnen. z.B. gcc oder compiler von iar. Steckt da auch das Newton verfahren dahinter? wieviele Iterationen werden da berechnet? Hab von den Standardbibliotheken nix gescheites dazu im Netz gefunden. grüße jens PS mich würde noch das das Verfahren für Integer-Wurzeln interessieren, was k-h angedeutet hat. allerdings interessiere ich mich für den algorithmus, weniger für assembler-code. hast du da vl. Links parat?
Jens B. schrieb: > nee. die Frage war nicht ganz richtig verstanden worden. Ich hab > verstanden, wie ich die Wurzel selbst "zu Fuß" berechne, nämlich mit > Newtoniteration was bei der Wurzel als Heron-Verfahren bezeichnet wird. > > ich würde gern wissen, wie die gängigen Compiler die Wurzel berechnen. > z.B. gcc oder compiler von iar. Steckt da auch das Newton verfahren > dahinter? wieviele Iterationen werden da berechnet? avr-lib besorgen. Nachsehen. http://www.nongnu.org/avr-libc/ > PS mich würde noch das das Verfahren für Integer-Wurzeln interessieren, > was k-h angedeutet hat. allerdings interessiere ich mich für den > algorithmus, weniger für assembler-code. hast du da vl. Links parat? Google
Warum sollte die Math-Bibliothek oder der Compiler die Wurzel selbst berechnen ? Er lässt das den Prozessor tun, in dem er einen passenden Opcode (FSQRT 0xD9 0xFA) ausführt. http://developer.intel.com/design/pentium/manuals/24319101.pdf
Dann verwendet man Taylor-Reihenentwicklung http://en.wikipedia.org/wiki/Square_root http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4483493%2F4488527%2F04488594.pdf%3Farnumber%3D4488594&authDecision=-203 oder Cordic http://www.restena.lu/convict/Jeunes/Math/square_root_CORDIC.htm wenn ihm nicht Ganzzahlen reichen http://home.utah.edu/~nahaj/factoring/isqrt.c.html
sqrt Ähh... dazu schreibt das Referenzhandbuch: sqrt berechnet die positive Quadratwurzel des Arguments x. Für komplexe Zahlen x liefert sqrt(x) die komplexe Wurzel, deren arg (Winkel der Zahl in der komplexen Zahlenebene) arg(x)/2 beträgt. Die komplexe Version von sqrt ist definiert als: sqrt(z) = sqrt(abs(z)) (cos(arg(z)/2 + i sin(arg(z)/2)). Hmm, naja.
Zunächst wird die Wurzel (bzw. Mantisse) linear approximiert. Dies dient als Startwert für einige wenige Schritte der Newton-Iteration (aka. Heron-Verfahrens im Falle der Quadratwurzel): http://newlib.sourcearchive.com/documentation/1.15.0/s__sqrt_8c-source.html Taylor-Entwicklung ist nicht zu empfehlen. Johann
Borland schrieb: > sqrt(z) = sqrt(abs(z)) (cos(arg(z)/2 + i sin(arg(z)/2)). > > Hmm, naja. Jo, das geht auch ohne die trigonomatrischen Funktioenen und besser wie's Onkel Wicki beschreibt. Das kostet dann 3 reelle Quadratwurzeln:
Johann
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.