[GELÖST] C Wurzel errechnen?

Übersicht Sonstiges Smalltalk

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen

 

CO2

ehemals "SirMO"

Betreff: [GELÖST] C Wurzel errechnen?

BeitragMi, Feb 22, 2012 15:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,
Ich möchte eine Funktion in C schreiben, welche mir die Wurzel aus einer Zahl zieht. Ich weiß, das es die Funktion schon in der stdlib gibt, möchte sie aber selber schreiben.
Über ein paar Internet-Recherchen habe ich herausgefunden, das die einfachste Wurzelformel Code: [AUSKLAPPEN]
Zahl ^ 0.5 = Wurzel aus Zahl
ist. Das problem ist allerdings, das es in C kein ^ - Zeichen gibt.
Also habe ich mir eine Funktion geschrieben, welche eine Zahl potenziert. So sieht sie aus:
Code: [AUSKLAPPEN]
float Potenziere(float fZahl, int iPotenz)
{
    int ix;
    float ferg = 1;
    for(ix = 0; ix < iPotenz; ix++)
    {
        ferg = ferg * fZahl;
    }
    return ferg;
}

Damit kann man aber immernoch keine Zahl hoch 0.5 rechnen, da der Zähler iPotenz erstens vom typ integer ist, und weil die for-schleife halt immer 1 auf die Zahl aufrechnet...
meine Frage: Wie kann man so eine Funktion in C schreiben, die also die Wurzel aus einer Zahl zieht?
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti
  • Zuletzt bearbeitet von CO2 am Sa, Feb 25, 2012 0:16, insgesamt einmal bearbeitet

Xeres

Moderator

BeitragMi, Feb 22, 2012 15:55
Antworten mit Zitat
Benutzer-Profile anzeigen
Würde eine nummerische Berechnung machen, so wie es in Wikipedia beschrieben ist.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

CO2

ehemals "SirMO"

BeitragMi, Feb 22, 2012 16:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Zitat:
Mit dem Startwert y = 2 erhält man:

Wie bekomme ich den startwert, bzw. die anzahl der zu berechnenden Schritte heraus?
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

BtbN

BeitragMi, Feb 22, 2012 18:49
Antworten mit Zitat
Benutzer-Profile anzeigen
in cmath: double pow(double x, double y);

Eingeproggt

BeitragMi, Feb 22, 2012 19:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Zitat:
Wie bekomme ich den startwert, bzw. die anzahl der zu berechnenden Schritte heraus?


Uiui, Konvergenz von unendlichen Reihen is schon wieder über ein Jahr her bei mir... Aber soweit ich mich erinnern kann, geht es mit jedem Startwert. Nur "unterschiedlich gut". Und die Anzahl der Schritte bestimmst du. Rechne einfach so lange bis dir dein Ergebnis genau genug ist, sprich es sich nicht mehr merkbar ändert (siehe Beispiel auf Wikipedia, da ändert sich nach Schritt 4 schon kaum mehr was).

mfG, Christoph.
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Vertex

BeitragMi, Feb 22, 2012 20:27
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi, das geht mit Newton-Raphson:

Gesucht ist sqrt(y):
Code: [AUSKLAPPEN]
y = x² | - x²
y - x² = 0


Das neue Problem ist also für die Funktion f(x) = y - x² eine Nullstelle zu finden (wobei y Konstant ist).

Dann sucht man einen Startpunkt x_0 und berechnet alle weiteren x_i wie folgt:
Code: [AUSKLAPPEN]
x_(i + 1) = x_i - f(x_i) / f'(x_i)


Wobei hier f'(x) = -2x ist also:

Code: [AUSKLAPPEN]
x_(i + 1) = x_i - (y - x_i²) / (-2x_i)


Hier die Quadratwurzel aus 25:
Code: [AUSKLAPPEN]
Local y# = 25
Local xi#, xi1# = y

Const EPS# = 0.000001


Repeat
   xi = xi1
   Print xi
   
   xi1 = xi - (y - xi*xi) / (-2 * xi)
Until Abs(xi - xi1) <= EPS

WaitKey
vertex.dreamfall.at | GitHub

Midimaster

BeitragDo, Feb 23, 2012 0:04
Antworten mit Zitat
Benutzer-Profile anzeigen
man könnte es auch durch Näherung machen. Ist ein derber Weg, aber gut zu kapieren:

die Wurzel aus X liegt irgendwo zwischen 0 und X

Unten=0
Oben=X
Die Mitte M dieser beiden Werte ist (0+x)/2
Mitte=(Unten+Oben)/2

nun errechne ich M*M und sehe nach, ob es größer als X ist oder kleiner


wenn M*M größer ist als X dann liegt der gesuchte Wert zwischen 0 und M und das Spiel geht mit diesen beiden Werten von vorne los.

Unten=0
Oben=Mitte
Die Mitte M dieser beiden Werte ist (U+M)/2
Mitte=(Unten+Oben)/2



wenn aber M*M kleiner ist als X dann liegt der gesuchte Wert zwischen M und X und das Spiel geht mit diesen beiden Werten von vorne los

Unten=Mitte
Oben=X
Die Mitte M dieser beiden Werte ist (M+X)/2
Mitte=(Unten+Oben)/2

Man hört auf, wenn der Fehler zwischen M*M und X klein genug geworden ist.
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe
  • Zuletzt bearbeitet von Midimaster am Do, Feb 23, 2012 11:58, insgesamt 3-mal bearbeitet

Vertex

BeitragDo, Feb 23, 2012 2:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Das Verfahren, was Midimaster beschreibt, ist das sogenannte Heron-Verfahren: http://de.wikipedia.org/wiki/Heron-Verfahren. Wenn man unter "Geometrische Veranschaulichung des Heron-Verfahrens" schaut, dann lässt sich das auch gut verstehen.
Die FPUs implementieren anscheinend den CORDIC-Algorithmus: http://de.wikipedia.org/wiki/CORDIC
vertex.dreamfall.at | GitHub

Midimaster

BeitragDo, Feb 23, 2012 12:36
Antworten mit Zitat
Benutzer-Profile anzeigen
@Vertex: Heron ist etwas anderes als mein Verfahren! Das Heron-Verfahren ist viel schneller und effizienter... aber auch schon ein wenig schwieriger zu verstehen:

die Wurzel aus X liegt irgendwo zwischen X und X/Ergebnis

Die Formel dazu :

Ergebnis = (Ergebnis + X/Ergebnis)/2

(zunächst wird für das Ergebnis (ist auch gleichzeitig die "Mitte") einfach X eingesetzt.)

Start:
Wert 1 : X
Wert 2 : X/Ergebnis also X/X also "1"

Das neue Ergebnis dieser beiden Werte ist


Mitte = (Mitte + X/Mitte)/2

nun wird nicht Mitte*Mitte berechnet und es gibt keine Entscheidung
sonder das Ergebnis wandert in die selbe Rechung:


Mitte = (Mitte + X/Mitte)/2


Man hört auf, wenn der Fehler zwischen Mitte und X/Mitte klein genug geworden ist.
  • Zuletzt bearbeitet von Midimaster am Do, Feb 23, 2012 13:30, insgesamt 2-mal bearbeitet

Eingeproggt

BeitragDo, Feb 23, 2012 12:49
Antworten mit Zitat
Benutzer-Profile anzeigen
Man verzeihe wenn ich mit der höheren Mathematik nicht ganz mitkomme, aber:

Zitat:
die Wurzel aus X liegt irgendwo zwischen X und X/Ergebnis

Ich würde sagen die Wurzel aus X ist genau X/Ergebnis?

X² ist bekanntlich X*X. Will ich nun die Wurzel daraus ziehen wäre das genau X (Achtung! Damit ist "ein anderes X" gemeint als bei dir, Midimaster). Also umständlich ausformuliert: Sqrt(X²)=X²/X
Oder zurück zu deiner meiner ersten Frage: Die Wurzel einer Zahl ist die Zahl durch die Wurzel.

mfG, Christoph.

Nachtrag: Hmm, oder wolltest du mit deinem posting nur dein "Näherungsverfahren" von gestern erklären?
Gewinner des BCC 18, 33 und 65 sowie MiniBCC 9

Midimaster

BeitragDo, Feb 23, 2012 13:26
Antworten mit Zitat
Benutzer-Profile anzeigen
@eingeproggt: Nein, ich beschreibe ein neues Verfahren, dass Vertex ins Spiel gebracht hat.

Bei solchen Näherungsverfahren ist das Ergebnis leider nie die math. richtige Lösung und daher gilt in diesem Verfahren tatsächlich der Satz:

"Das Ergebnis liegt zwischen sich und dem X/sich"

beispiel Wurzel aus 10:
=>
Das Ergebnis liegt zwischen 10 und 1 (aus 10/10)


(10 + 10/10)/2 =5.5
=>
Das Ergebnis liegt zwischen 5.5 und 1.8 (aus 10/5.5)


nächste Runde:

(5.5 + 10/5.5)/2 = 3.6
=>
Das Ergebnis liegt zwischen 3.6 und 2.7 (aus 10/3.6)


nächste Runde:
(3.6 + 10/3.6)/2 = 3.19
=>
Das Ergebnis liegt zwischen 3.19 und 3.13 (aus 10/3.19)


usw....
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Vertex

BeitragDo, Feb 23, 2012 14:49
Antworten mit Zitat
Benutzer-Profile anzeigen
Midimaster, du hast Recht. Hatte vermutet, die Folge {Mitte_i} sei monoton steigend und konvergiert gegen Sqrt(x). Ich wollte damit zeigen, dass es wie das Heronverfahren arbeitet, bei dem das der Fall ist (Beweis über (x + y)/2 >= Sqrt(x * y)). Die Folge Deines Verfahrens ist aber weder monoton steigend noch monoton fallend, konvergiert aber tatsächlich gegen Sqrt(x):

BlitzBasic: [AUSKLAPPEN]
Local x# = 25.0
Local unten#, mitte#, oben#
Local quadrat#

Const EPS# = 0.0001

unten = 0.0
oben = x

Repeat
mitte = (unten + oben) / 2.0
quadrat = mitte * mitte
If quadrat > x Then
oben = mitte
ElseIf quadrat < x Then
unten = mitte
EndIf
Print(mitte)
Until Abs(quadrat - x) <= EPS

WaitKey()


Wäre mal interessant zu beweisen, warum der Fixpunkt bei Sqrt(x) liegt.
vertex.dreamfall.at | GitHub
 

CO2

ehemals "SirMO"

BeitragFr, Feb 24, 2012 18:43
Antworten mit Zitat
Benutzer-Profile anzeigen
So, erstmal entschuldigung das ich jetzt erst zurückschreibe.

Dann ist hier mal die Lösung die ich gewählt habe:
Code: [AUSKLAPPEN]
float Potenziere(float fZahl, int iPotenz) //Potenzieren Funktion
{
    int ix; //Zähler
    float ferg = 1; //Ergebnis
    for(ix = 0; ix < iPotenz; ix++) //Solange Zähler kleiner als Potenz
    {
        ferg = ferg * fZahl; //Rechne Ergebnis mal Zahl
    }
    return ferg; //Ergebnis returnen
}

float Wurzel(float fZahl) //Wurzel Funktion
{
    float fStart = 1; //Startwert
    float fErg = 0; //Ergebnis
    const int iGenauigkeit = 5; //je größer desto genauer die berechnung
    int ix; //Zähler
    fStart = (Potenziere(fStart, 2) + fZahl) / (2 * Potenziere(fStart, 1)); //1. Berechnung.
    for(ix = 0; ix < iGenauigkeit; ix++) //Nach 5 durchläufen (6 Rechnungen) Genau genug ;)
    {
        fStart = (Potenziere(fStart, 2) + fZahl) / (2 * Potenziere(fStart, 1)); //Berechnen
    }
    fErg = fStart; //Zuweisung
    return fErg; //return
}


Ich danke allen, die Halfen.

Bevor irgendwer meint, ich würde andere Vorschläge ignorieren: Dieses Verfahren schien mir das einfachste zu sein, und da ich kein Mathematik-Professor bin, habe ich sie auch genommen. Nichts desto trotz danke ich auch den anderen für die Hilfsbereitschaft.
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Vertex

BeitragFr, Feb 24, 2012 20:26
Antworten mit Zitat
Benutzer-Profile anzeigen
Öhm, funktioniert das denn?
Habs mal mit BB ausprobiert, und bin der Meinung, dass meine Funktion das selbe berechnet wie Deine:
BlitzBasic: [AUSKLAPPEN]
Print Sqrt(25.0)
WaitKey

Function Sqrt#(radicand#)
Local xi# = 1
Local i

For i = 1 To 7
xi = (xi^2 + xi) / (2 * xi^1)
Next

Return xi
End Function


Es wird "1" != "5" ausgegeben.
vertex.dreamfall.at | GitHub

Midimaster

BeitragFr, Feb 24, 2012 20:37
Antworten mit Zitat
Benutzer-Profile anzeigen
BlitzBasic: [AUSKLAPPEN]
xi = (xi^2 + xi) / (2 * xi^1)


....ist nicht richtig umgesetzt. Es muss so lauten:

BlitzBasic: [AUSKLAPPEN]
xi = (xi^2 + radicand) / (2 * xi^1)


und das ganze ist ganz schön aufgebläht....
Kürzt man ein wenig darin herum, dann wird dies draus und es geht immer noch:
BlitzBasic: [AUSKLAPPEN]
xi = (xi + radicand/xi) /2


und jetzt kommt schon keine Quadratfunktion mehr drin vor und jetzt genau ist es auch der "Heron"!

Klein, Schön, Schnell!


und in C:

Code: [AUSKLAPPEN]
float Wurzel(float fZahl) //Wurzel Funktion
{
    float fStart = 1; //Startwert
    const int iGenauigkeit = 5; //je größer desto genauer die berechnung
    int ix; //Zähler
    for(ix = 0; ix < iGenauigkeit; ix++)
    {
        fStart =  (fStart + fZahl/fStart) / 2
    }
    return fStart; //return Ergebnis
}


die andere Funktion wird gar nicht gebraucht!
  • Zuletzt bearbeitet von Midimaster am Fr, Feb 24, 2012 20:52, insgesamt einmal bearbeitet

Vertex

BeitragFr, Feb 24, 2012 20:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Alles klar, so funktioniert es. Danke Midimaster!

CO2, wie heißt dieses Verfahren bzw. woher kennst Du es?

Edit: Ahh, Midimaster hat den Beweis schon erbracht, dass es sich um das Heron-Verfahren handelt.
vertex.dreamfall.at | GitHub

Midimaster

BeitragFr, Feb 24, 2012 20:53
Antworten mit Zitat
Benutzer-Profile anzeigen
heron! siehe updates meines letzten beitrags!
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Propellator

BeitragFr, Feb 24, 2012 21:11
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]
#include <stdio.h>

float fsqr( float n ) {
   float result;
   __asm__("fld %0;"
         "fsqrt;"
         "fstp %1;"
          :: "f" (n), "m" (result));
   return result;
}

int main() {
   printf("%f", fsqr(2.0));
   return 0;
}


Benutzt nicht die stdlib Funktion, und läuft am schnellsten. Razz
Propellator - Alles andere ist irrelephant.
Elefanten sind die Könige der Antarktis.

Arrangemonk

BeitragFr, Feb 24, 2012 21:34
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]
double fastpow(double x, double y)
{
   double a = 1.0 - y;
   double b = x - 1.0;
   double c = 0.5 * b *b;
   double d = b - c
   return x /((1.0 + (a * d)) + (0.5* (d * d * a*a));   
}


is nicht korrekt aber für lichtberechnungen ganz annehmbar
ingeneur
 

CO2

ehemals "SirMO"

BeitragSa, Feb 25, 2012 0:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Dann nochmal danke für alle Antworten!

@ Midimaster:
Die Potenzieren - Funktion brauchte ich eh, aber trotzdem danke für die gekürzte Funktion. Wink

@ Propellator:
Shocked Das habe ich ja noch nie gesehen... Naja, bin auch nicht der erfahrendste in C Embarassed

Da das Thema nun geklärt ist, werde ich den Thread als "[GELÖST]" taggen.
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen


Übersicht Sonstiges Smalltalk

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group