Wie funktioniert sqrt

[Jens B. (meddle)]

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

[Karl H. (kbuchegg)]

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 H. (kbuchegg)]

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)

double mySqrt( double value )
{
  double result;
  double nextResult;

  //
  // nur um sicher zu gehen
  //
  if( value < 0.0 )
    value = value;
  
  //
  // die erste Schätzung
  //
  result = value;
  nextResult = value / 2.0;
  
  //
  // mittels Newton verfeinern, bis die gewünschte Genauigkeit
  // erreicht ist
  //
  // Newton
  //    gegeben:    x^2 - a = 0    ( a ist die Zahl, deren Wurzel gesucht wird)
  //    und gegeben eine Schätzung für xi, dann ist
  //    xn = x - f(x) / f´(x)
  //    ein besserer Wert für x, der die Gleichung löst
  //
  //    f(x) = x^2 - a
  //    f´(x) = 2*x
  //
  while( fabs( result - nextResult ) > 0.00001 )
  {
    result = nextResult;
    nextResult = result - ( result * result - value ) / ( 2 * result );
  }
  
  return nextResult;
}

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;

[Klaus W. (mfgkw)]

Jens B. schrieb:
> ...
> Findet man das irgendwie raus?
>
> Grüße
> Jens


Quelltext?
Und dann hier kurz beschreiben?

[Jens B. (meddle)]

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?

[Karl H. (kbuchegg)]

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

[MaWin (Gast)]

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

[sqrtf (Gast)]

nur haben die meisten mikrocontroller keinen passenden sqrt befehl

[MaWin (Gast)]

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

[Borland (Gast)]

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.

[Johann L. (gjlayde)]

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

[Johann L. (gjlayde)]

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:

$$\sqrt{z} = \sqrt{x+iy} = \operatorname{sign}(y) \sqrt\frac{|z|+x}{2} + i\cdot\sqrt\frac{|z|-x}{2}$$

Johann