www.mikrocontroller.net

Forum: Compiler & IDEs sinus berechnen


Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hi leute,

kurzer umriss:
ich suche nach einer alternative zur gnu bibliothek... ich brauche eine 
implementierung, die schneller rechnet... und auf die 4te 
nachkommastelle noch genau ist...

für eine tabelle ist nicht genug platz im speicher...

...daher meine frage, kennt jemand einen schnellen algorhitmus oder gar 
eine bibliothek die ich verwenden könnte??

(GNU-C)

vielen dank mal :)

Autor: Tom Ekman (tkon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo,

also ich denk mal wenn'st den vollen Sinus (0-45 Grad wegen Symmetrie) 
brauchst, wirst kaum eine Chance haben etwas merklich schnelleres zu 
finden da es dafür etablierte Standardverfahren gibt die praktisch 
überall eingesetzt werden und sehr schnell konvergieren.

Wie sieht es mit Speicherplatz für eine Tabelle aus? Vielleicht wär es 
möglich die zu komprimieren wenn es nur ein wenig an Platz fehlt

gr

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast wrote:

> implementierung, die schneller rechnet... und auf die 4te
> nachkommastelle noch genau ist...

Binär oder Dezimal? **g**

> für eine tabelle ist nicht genug platz im speicher...

Algorithen bekommst du auch nicht für lau.

> ...daher meine frage, kennt jemand einen schnellen algorhitmus oder gar
> eine bibliothek die ich verwenden könnte??

Wo du nie dran vorbei kommst ist die Normierung auf einen kleinen 
Argumentbereich, also erstmal mod 2pi, mod pi, mod pi/2 oder mod pi/4 
rechnen.

Für den sin selber gibt's 3 Ideen:

1) Taylor um 0
2) Taylor um pi/4 oder pi/8 (dann auch den cos um pi/8)
3) Approximation durch ein Polynom, z.b. 4. Grades.

Ansatz ist

Das Polynom wird so gewählt, daß
was also eine Optimierungsaufgabe für die 5 Koeffizienten von p 
darstellt. Da es sich um ein Polynom handelt, ist es unangenehm, für 
Argumente die betragsmäßig größer als 1 sind, auswerten zu müssen. Soll 
der Bereuch daher auf 0..pi/4 beschränkt werden, kommt noch eine analoge 
Aufgabe für den Cosinus hinzu bzw. man zwelegt das Intervall der Länge 
pi/2 in 2 der Länge pi/4 und nimmt 2 Polynome, eines für jedes 
Teilintervall.

Als Maß bietet sich an
oder

Das ganze dürfte auf ne Taylor-Entwicklung rauslaufen, deren 
Entwicklungspunkt etwa in der Intervallmitte ist.

Allerdings ist die Funktion per Konstruktion wegen der Minimalität der 
Norm optimal geeignet für den Zweck.

Für die Arithmetik:

Wie wär's mit Q-Format in Assembler? Also erst mal checken, welches 
Q-Format passen würde. 1.15 ist zwar recht easy zu implementieren, 
allerdings bleiben die (Zwischen)Werte nicht im Invervall (-1,1). Genehm 
wäre ein 3.29 Q-Format, das immerhin (-4,4) darstellen kann. Bei 3.13 
reichen die Nachkommastellen wohl nicht für die Genauigkeit aus. 
Speziell für den Sinus hatte ich ein 16-er Q-Format mal implementiert, 
aber wo...?

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
da kommen wir doch schon näher :)

Q-format ist gut... weiss nicht wie sinnvoll, aber dachte an 1.15

aber implementiert die libc des gcc nicht eh schon die 
taylor-approximation?

ich dachte an CORDIC in Q

aber ich raff den CORDIC nich, bin zu doof :(

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast wrote:

> aber implementiert die libc des gcc nicht eh schon die
> taylor-approximation?

Doch. Aber deren Entwicklungspunkt ist 0, wie gesagt.

Stell dir einfach vor, du willst den sin durch ein Polynom 1. Grades 
(also eine Gerade) annähern. Bei Taylor mit Entwicklungspunkt 0 ist das 
p(x)= x. Wenn du die Gerade so legen kannst, daß zB der über alle Werte 
genommene Fehler (in der gewählten Norm) minimal ist, bekommst du sowas 
wie ne Bestgerade an sin in [0, pi/2]. Das approximiert besser und ist 
aber auch nur ein Polynom ersten Grades.

Daran sieht man (entgegen meiner obigen Vermutung) daß diese 
Approximation keine Taylor-Entwicklung ist, weil sie keine Tangente an 
sin liefert.

Oben ist das Verfahren eben für ein Polynom höheren Grades gemacht. Der 
sin hat den Vorteil, daß die geraden Terme wegfallen. Die Approximation 
hat den Vorteil, daß sie sich nicht auf den Punkt 0 fixiert und mit 
roher Gewalt ;-) so lange rechnet, bis der Fehler/Restterm klein genug 
ist, sondern der Fehler per Konstruktion klein ist. Ob das im Endeffekt 
besser/schneller ist, muss man sich anschauen.

Zudem implementiert die libc in float und nicht in Q-Format, was 
aufwändig ist. Des weiteren muss sie sich nicht im NaNs etc kümmern und 
die floats aus- und einpacken und ist nicht in asm geschrieben.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hmmmm....

in welche richtung empfielt sich nun zu gehen?

Q-format steht fest, aber soll ich in Q nun taylorreihen verfolgen oder 
soll ich mich weiter in CORDIC einlesen (hier soll der geschwindigkeits 
vorteil in der ausschliesslichen verwendung von additionen und shifts 
liegen)...

ich bewege mich nur im bereich 0..PI/2

danke soweit mal für die infos

Autor: dvh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man Stützstellen bei 30 und 60 Grad (zwischen 0 und 90) nimmt, dann 
ist dies eine Naeherung  auf besser als 1.0E-6:
wenn z.B. x=75.0*pi/180.0 dann ist 60° zu verwenden
mit dx=x-x60 (x60=60.0*pi/180.0) gilt dann:
sin(x)=sin(x60)*cos(dx)+cos(x60)*sin(dx)
mit sin(x60)=sqrt(3)/2 und cos(x60)=0.5.
Für die kleinen Werte dx gilt in der 1.0E-6 Naeherung
sin(dx)=dx*(1-1/6*dx^2*(1-1/20*dx^2)) und
cos(dx)=1-1/2*dx^2*(1-1/12*dx^2)
(Taylorentwicklung)
ich bekomme zB. bei 75°
s60*(1.0-dx**2*0.5*(1.0-dx**2/12.0))+c60*( 
dx*(1.0-1.0/6.0*dx**2*(1.0-0.05*dx**2)))-sin(x)=3.9514708150001354e-07

Autor: Alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier mal die Implementierung aus einer von mir genutzten fixed point 
(16.16 Format) Klasse.
    Fxp32 Fxp32::sineInternal(Fxp32 Value)
    {
        // Polynomial length is chosen such that theoretical error < 2*10^(-4)
        // Matlab code:
        // x  = 0:.001:pi/2;
        // y  = sin(x);
        // xn = x ./ pi; %normalize x from (0, pi/2) to (0, .5)
        // p = polyfit(xn, y, 4);
        // p = p * 2^16; % convert to 16.16 format
        const UInt8 PolyLength = 5;
        const Int32 PolyCoeff[PolyLength] = { 0x0000000FL,  //  15.137052889215985
                                              0x0003209AL,  //   2,049535691178602e+05
                                              0x000034CAL,  //   1.351355002615320e+04
                                              0xFFF9AE1CL,  //  -4.141804497187611e+05                                             
                                              0x0002CA0FL   //   1.827989287236855e+05
                                            };

        Fxp32 Temp;
        Fxp32 Result;
        Fxp32 Exp;
        Int8  i;
        bool IsNeg = false;

        // Use identity sin(x) = -sin(-x) and make make Value positive, remember sign
        if (Value < Fxp32(0))
        {
            Value = -Value;
            IsNeg = !IsNeg;
        }

        // Use identity sin(x) = -sin(-x) to map 3rd and 4th quadrant to 1st and 2nd
        if (Value.m_Value & ConversionFactor)
        {
            IsNeg = !IsNeg;
        }

        // Normalize to range (0, 1]
        Value.m_Value &= 0x0000FFFFL;

        // Now m_Value maps to the first positive half wave
        // Check if 1st or 2nd quadrant, if 2nd use identity sin(pi/2+x) = sin(pi/2-x)
        if (Value.m_Value & HalfIncrement)
        {
            // This means value >= 0.5, i.e. 2nd quadrant => map to 1st
            Value.m_Value = (ConversionFactor - Value.m_Value);
        }

        // Polynom evaluation in this way:
        // Result = X*(X*(A*X+B)+C)+D
        // (requires less multiplications)
        // Constant term
        Result.m_Value = PolyCoeff[PolyLength-1];
        Result        *= Value;
        Temp.m_Value   = PolyCoeff[PolyLength-2];
        Result        += Temp;

        // Use polynom to approximate sine
        for (i=PolyLength-3; i>=0; i--)
        {
            Temp.m_Value = PolyCoeff[i];
            Result      *= Value;
            Result      += Temp;
        }

        if (IsNeg)
        {
            Result = -Result;
        }

        return Result;
    }

    Fxp32 Fxp32::sine(Fxp32 Value)
    {
        Fxp32 Temp;

        // Normalize Value by dividing by PI (map interval +/-Pi to +/-1)
        Temp.m_Value = PiInverse;
        Value       *= Temp;

        return sineInternal(Value);
    }

Autor: Werner Grimmel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ohne alles obige im Detail gelesen zu haben:

Google mal nach "Bezierkurven" oder "Beziersplines". Das ist nichts 
anderes als ein Polynom (Bernsteinpolynome etc...). Du betrachtest den 
Sinus als Graph in einem kartesischen Koordinatensystem und rechnest 
also die x/y Koordinaten aus für alle Werte bis Pi/2. Der Rest ist ja 
symmetrisch.

Du musst für einen Bezierspline einen Startpunkt und einen Endpunkt 
festlegen
(also z.B. (0,0) und (Pi/2,1)). Jetzt benötigst du Stützstellen. Die 
Stützstellen liegen hier aber NICHT auf der Sinuskurve, sondern sind 
Punkte im Koordinatensystem die den Verlauf des Graphen beeinflussen.

Du nimmst einen Algorithmus zur Berechnung des Splines auf Basis von 
Additionen und Shifts und fertig. Keine explizite Multiplikation nötig.

Ist sehr sehr einfach, ganz wenig Code und recht schnell da keine 
Multiplikation nötig. Genauigkeit theoretisch beliebig erweiterbar durch 
Umsaklieren des Koordinatensystems oder Einführung zusätzlicher 
Stützstellen.

google Stichwörter:

- Satz von de Casteljau
- Fadenkonstruktion Parabel
- Bernsteinpolynome
- Bezierspline

--> Mal eines der zahlreichen Java-Applets zu den Splines im Internet 
ansehen! Es ist fantastisch was man mit diesen Kurven alles machen 
kann!! Und superleicht!!

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
das mit dem splining ist interessant, aber wenn ich dann meinen punkt 
auf dem sinusähnliche gebilde habe, bin ich noch immer nicht bei dem 
gesuchten winkel... (asin())

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast wrote:
> das mit dem splining ist interessant, aber

Auch nur Polynome, die es auszuwerten gilt.

> wenn ich dann meinen punkt
> auf dem sinusähnliche gebilde habe, bin ich noch immer nicht bei dem
> gesuchten winkel... (asin())

Wenn du sin willst, dann berechne sin.
Wenn du asin willst, dann berechne asin.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Wenn du sin willst, dann berechne sin.
>Wenn du asin willst, dann berechne asin.

der weg ist mein ziel ;)

ich danke allen für eure infos, ist alles sehr wertvoll für mich... 
danke :)

Autor: Hans-jürgen Herbert (hjherbert) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ein Polynom 4. Ordnung sollte reichen fuer Genauigkeit 200 ppm

Und wenns schneller gehen soll siehst Du da
Beitrag Beitrag "float arithmetic"

(Jene Programme verzichen auf Behandlung von Sonderfällen)

Autor: Dennis (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Blöd gefragt:

Externen Sinusgenerator auf den ADC anschliessen und Meßwert 
verarbeiten...

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ist das schneller? Wie lange muss man warten, wenn man sin(1000) will?

Autor: Dennis (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sin(1000) = sin(280), höher als 360 macht es eh kein Sinn...

Ob es schneller ist? Kommt auf die Frequenz und Anwendung an.

Vorteil: SW in 10 Min geschrieben, ext. Sinusgenerator kann evtl. auch 
getriggert werden (Anwendungsabhängig). Wie im vorigen Beitrag gesagt: 
blöde Idee, aber es kann evtl. auch funktionieren. Wurde uns im Studium 
nicht jeden Tag eingebläut, auch mal "unübliche" Wege zu gehen, wenn sie 
den einfacher/besser/störfester/wasauchimmer sind?

Gruss:

Dennis

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
danke für die anregung....

ich suche etwas extrem schnelles

Je Sekunde muss ich 20000 mal je einen sin() einen cos(mit anderem 
winkel) und einen arccos ausfürhen...

(un jede menge anderes)

denke ich muss dann doch 4kb flash opfern für eine tabelle...

danke euch allen soweit :)

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.