Wie funktioniert sqrt

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

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