mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Wie funktioniert sqrt


Autor: Jens B. (meddle)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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;

Autor: Klaus Wachtler (mfgkw)
Datum:

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


Quelltext?
Und dann hier kurz beschreiben?

Autor: Jens B. (meddle)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/...

Autor: sqrtf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
nur haben die meisten mikrocontroller keinen passenden sqrt befehl

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Borland (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Taylor-Entwicklung ist nicht zu empfehlen.

Johann

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.