wurzel ziehen nicht möglich - Freescale

[Cimbom G. (cimbomgs)]

Hallo,

ich programmiere einen Freescale Mikrocontroller und brauche für meine 
Rechung eine Wurzel-Funktion. Habe in Library nichts finden können :-(

Im Anhang sieht man die Funktion, die berechnet werden soll.

Für "quadratische Zahlen" (wurzel(25)=5, wurzel(16)=4,...) existiert 
eine Library-Funktion aber damit kann ich nicht anfangen.

Was kann ich machen?
Gibt es andere Möglichkeiten um Wurzel zu ziehen, bzw. Wurzel umgehen?
Oder weiß jemand ob man es vielleicht doch bei Freescale-Mikrocontroller 
realisieren kann?

Danke

ps. obwohl ich math.h includiere, kann ich die sqrt()-Funktion nicht 
benutzen. Der Compiler meckert dass es kein Prototyp existiert

[Jankey (Gast)]

__inline int JSqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5f;

    x2 = number * 0.5f;
    y  = number;
    i  = * (long *) &y;      // evil floating point bit level hacking
    i  = 0x5f3759df - (i >> 1);             // what the fugg?
    y  = * (float *) &i;
    y  = y * (threehalfs - (x2  y  y));   // 1st iteration
    //y  = y * ( threehalfs - ( x2  y  y ) );   // 2nd iteration, this 
can be removed

    return (int) (1/y);
}

[Cimbom G. (cimbomgs)]

Hallo Jankey, danke für die Antwort.

Kannst du auch etwas dazu sagen? Was macht die Funktion genau?

was macht das:

i  = * (long *) &y; // evil floating point bit level hacking
i  = 0x5f3759df - (i >> 1); // what the fugg?
y  = * (float *) &i;
y  = y * (threehalfs - (x2  y  y));

warum wird int zurückgegeben?

[Gast (Gast)]

Slm

also ich kenne mich mit Freescale uC nicht aus und in C habe ich auch 
noch nie programiert aber wenn der math.h exp(x) und ln(x) unterstützt 
kannst du die n-te wurzel aus x so ziehen:

x^1/n=exp(ln(x)/n)

[Karl H. (kbuchegg)]

Gast wrote:
> Slm
>
> also ich kenne mich mit Freescale uC nicht aus und in C habe ich auch
> noch nie programiert aber wenn der math.h exp(x) und ln(x) unterstützt
> kannst du die n-te wurzel aus x so ziehen:
>
> x^1/n=exp(ln(x)/n)


Wobei es eigentlich keinen wirklichen Grund gibt, warum
eine Implementierung zwar keine Wurzel aber ln und exp
unterstützen sollte.

sqrt kann man mit einer Newton Iteration ziemlich einfach
berechnen. Dazu braucht man lediglich Gleitkommaoperationen
Addition, Multiplikation und Division.

> ps. obwohl ich math.h includiere, kann ich die sqrt()-Funktion nicht
> benutzen. Der Compiler meckert dass es kein Prototyp existiert

Kannst du das mal näher ausführen

#include <math.h>

int main()
{
  double x, y;

  x = 28.3;
  y = sqrt( x );
}

sollte ohne Probleme und ohne Fehler compilieren.

[Michael G. (linuxgeek)]

Jupps... Wurzeln ziehen kann man auch iterativ, aber Du hast doch eine 
C-Library, oder nicht?

[Cimbom G. (cimbomgs)]

> sqrt kann man mit einer Newton Iteration ziemlich einfach
> berechnen. Dazu braucht man lediglich Gleitkommaoperationen
> Addition, Multiplikation und Division.

oje es ist lange her, dass wir bei der Wurzel-Herleitung in der Schule 
mit Addition, Multiplikation und Division gearbeitet haben. Ich kann 
micht garnicht mehr daran erinnern, wie wir es gamacht haben :-(


>> ps. obwohl ich math.h includiere, kann ich die sqrt()-Funktion nicht
>> benutzen. Der Compiler meckert dass es kein Prototyp existiert
> Kannst du das mal näher ausführen

naja wie gesagt, wenn ich versuche zu debuggen und mein Code compiliere, 
wird mir Linker-Fehler angezeigt. Ich vermute die math.h-Header besitzt 
die Funktion garnicht, daher die Fehlermeldung.

>
>

> #include <math.h>
> 
> int main()
> {
>   double x, y;
> 
>   x = 28.3;
>   y = sqrt( x );
> }
>

>
> sollte ohne Probleme und ohne Fehler compilieren.

nicht unter CodeWarrior. Nach dem ausführen kommt Fehlermeldung "kein 
Prototyp der Funktion sqrt() vorhanden"

[Michael G. (linuxgeek)]

Hast Du math.h includiert?
Nachtrag:

Um Quadratwurzel von a zu berechnet, iteriere gemaesz:

$$x_{n+1}=\frac{x_n + \frac{a}{x_n}}{2}$$

[Cimbom G. (cimbomgs)]

Michael G. wrote:
> Jupps... Wurzeln ziehen kann man auch iterativ, aber Du hast doch eine
> C-Library, oder nicht?

ich vermute eine unvollständige C-Library.

[Cimbom G. (cimbomgs)]

Michael G. wrote:
> Hast Du math.h includiert?

math.h ist includiert

[Michael G. (linuxgeek)]

Ok siehe oben... ;) Du brauchst uebrigens garnicht soviele Schritte, das 
konvergiert recht schnell. Kommt drauf an wieviele sichere Stellen Du 
brauchst.

[Gast (Gast)]

@   Karl heinz Buchegger (kbuchegg)
>Wobei es eigentlich keinen wirklichen Grund gibt, warum
>eine Implementierung zwar keine Wurzel aber ln und exp
>unterstützen sollte.

wie gesagt habe nch nie in C programmiert. ich denke das QUADRAT WURZEL 
also sqrt(x) in fast jeder Programmiersprache in irgend einer Form 
existiert aber er hat ja nach der N-te Wurzel gefragt und das gibt es 
icht immer als Standart.

> sqrt kann man mit einer Newton Iteration ziemlich einfach
> berechnen. Dazu braucht man lediglich Gleitkommaoperationen
> Addition, Multiplikation und Division.

da hast du recht, wusste aber niht mehr wie das ging.

[Cimbom G. (cimbomgs)]

Michael G. wrote:
> Ok siehe oben... ;) Du brauchst uebrigens garnicht soviele Schritte, das
> konvergiert recht schnell. Kommt drauf an wieviele sichere Stellen Du
> brauchst.

naja 2-3 Nachkommestellen reichen völlig aus

[Michael G. (linuxgeek)]

Naja die k-te Wurzel kannste auch berechnen, indem Du das 
Newton-Verfahren mit

$$f(x) = x^2 - k$$

 anwendest.

[Cimbom G. (cimbomgs)]

das n-te Wurzel brauche ich nicht, ich will nur das Quadrat-Wurzel.

o man das ist ja super, dann wäre damit mein Problem geklärt :-D

>Um Quadratwurzel von a zu berechnet, iteriere gemaesz:
>x_{n+1}=\frac{x_n + \frac{a}{x_n}}{2}

nach wievielen Schritten bekommt man 2-3 richtige Nachkommastellen?

[Falk B. (falk)]

@ Gast (Gast)

>also sqrt(x) in fast jeder Programmiersprache in irgend einer Form
>existiert aber er hat ja nach der N-te Wurzel gefragt und das gibt es
>icht immer als Standart.

Aber AFAIK gibt es eine allgemeine Potenzfunktion pow(x,y) welche

$$x^y$$

berechnet. Und wer in Mathematik nicht nur Kreide holen war, weiss

$$\sqrt[y]{x}=x^{\frac{1}{y}}$$

sprich pow(x, 1/y);

MfG
Falk

[Michael G. (linuxgeek)]

OK, also fuer 3 Nachkommastellen duerften 4 Iterationen ausreichen, das 
Verfahren konvergiert quadratisch. Ich gebe Dir mal ein Beispiel.

Wenn Du z.B.

$$\sqrt 9 = 3$$

 berechnen willst:

$$a=9$$

 und

$$x_0=1$$

$$x_1=\frac{1 + \frac{9}{1}}{2} =\frac{10}{2}=5$$

$$x_2=\frac{5 + \frac{9}{5}}{2} =\frac {\frac {34}{5}} {2} =\frac{34}{10} = 3{,}4$$

$$x_3=\frac{\frac{34}{10} + \frac{9}{\frac{34}{10}}}{2} =\frac{\frac{34}{10} + \frac{90}{34}}{2} =\frac{257}{85} \approx3{,}0235$$

$$x_4=\frac{\frac{257}{85} + \frac{9}{\frac{257}{85}}}{2} =\frac{\frac{257}{85} + \frac{765}{257}}{2} =\frac{65537}{21845} \approx3{,}00009 .$$

Du kannst natuerlich komplett numerisch Rechnen, also nicht mit 
rationalen Zahlen wie in diesem Beispiel. Solltest eventuell noch achten 
dass Du Dir keine Ausloeschungsprobleme einfaengst dabei. Das ergebnis

$$x_{n+1}$$

 verwendet immer

$$x_n$$

, also das Ergebnis der vorherigen Iteration, siehe oben.

Falls Du eine allgemeine Potenzfunktion hast geht es natuerlich auch so. 
Dann liegt es aber nahe dass Du die Wurzelfunktion auch zur Verfuegung 
hast.

[Karl H. (kbuchegg)]

#include <stdio.h>
#include <math.h>

double MySqrt( double a )
{
  double Xn = a / 2.0;
  double Xnn = 0.0;

  while( fabs( Xn - Xnn ) > 0.01 ) {
    Xnn = Xn;
    Xn = Xn / 2.0 + a / ( 2 * Xn );
  }

  return Xn;
}

int main()
{
  double y = MySqrt( 26.0 );

  printf( "%lf %lf\n", y, y*y );
}

Wenn du den Aufwand mit der While Schleife nicht brauchst,
sollte es (je nach Zahlenbereich von a) ausreichen einfach

double MySqrt( double a )
{
  double Xn = a / 2.0;

  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );

  return Xn;
}

Wenn das nicht reicht, dann iterierst du ganz einfach noch mal :-)

  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );

Und wenn das dann immer noch nicht reicht, dann halt noch ein 4.tes
mal:

  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );
  Xn = Xn / 2.0 + a / ( 2 * Xn );

Du kannst beliebig oft iterieren, jedesmal wird das Ergebnis
genauer.

[Cimbom G. (cimbomgs)]

Waow das ist klasse, super vielen Dank.

Habt vielen dank für eure Hilfe.

Ps. jetzt kann ich mich wieder an die Schulzeit erinnern :-). Genau so 
haben wir es die Wurzel-Funktion hergeleitet und für das n-te Wurzel gab 
es mehrere Möglichkeiten. Einer von den war das Newton-Verfahren

Nochmals Dankeschön

[Gast (Gast)]

@  Falk Brunner (falk)
>Aber AFAIK gibt es eine allgemeine Potenzfunktion pow(x,y) welche

siehe oben:
>also ich kenne mich mit Freescale uC nicht aus und in C habe ich auch
noch nie programiert

noch mal siehe oben:
>wie gesagt habe nch nie in C programmiert.

aus beiden aussagen kann man herleiten das ich nicht wissen kann ob 
einer power in C implementiert ist.

>Und wer in Mathematik nicht nur Kreide holen war,

siehe oben:
>x^1/n=exp(ln(x)/n)
ist das nicht das selbe pow(x,1/n)=x^1/n?

[Michael G. (linuxgeek)]

Bidde bidde... das Wurzelziehen auf die Art nennt sich uebrigens 
Heronverfahren, ist aber nur ein Spezialfall des Newton-Verfahrens.

Gruss,
Michael