Trigonometrische Funktionen auf uC

[ragnar]

Hallo,

Ich möchte gerne auf einem Mikrocontroller trigonometrische Funktionen berechnen (also sin, cos, tan, arctan). Aus Effizienzgründen möchte ich mit Fixpunktzahlen arbeiten (keine floats). Die Genauigkeit muß ausreichend hoch sein, auf jeden Fall besser als bei einer 256-Byte lookup table.
Ich gehe im Moment davon aus, dass ich 32-bit zur Verfügung haben werde.

Gibts dazu irgendeine fertige Bibliothek (am besten in C) die ich verwenden kann ?

ciao,
Georg

[SprinterSB]

Wen du ein GCC benutzt: da kannst du einfach die libm benutzen. Einfach gcc-Schalter -lm und die Prototypen hast du via #include <math.h>
Allerdings implementiert die libm den ieee-Standard, was einen gewissen Overhead beinhaltet, weil auch NANs (NAN steht für Not A Number, also zB Infinity, etc) korrekt bekandelt werden. Kleinen µC sprengt das den Flash, und von der Laufzeit ginge es bestimmt auch besser.
Lookup-Tabellen sind ja so schlecht nicht, wenn du zwischen den Stützstellen interpolierst (zB linear oder quadratisch).
Was evtl auch gut funktionieren könnte, ist eine Lookup und 1 oder 2 Schritte mit Newton nachzuiterieren (bei sin und cos). tan auf sin, cos zurückführen.
Zudem ist eine Lookup nicht aud 256 Byte oder 8bit-Werte beschränkt. Da würde ich eher die Bitbreite der Werte genauer machen als mehr Werte in die Tabelle zu nehemn und anschauen, wie man gescheit interpoliert (Bronstein-Semendjajew)

[cavegn]

@sprinter: sind die funktionen in der math.h nicht auf doubles ausgelegt?

cu

chris

[SprinterSB]

oops :oops:, sorry, hatte das "Fixpunkt" gelesen, aber wohl gleich wieder verdrängt...

Die libm arbeitet natürlich mit doubles (oder mit floats, wenn man sie entsprechend generiert) .

[sep]

Du brauchst 32-Bit Fixpunkt Werte? Wieviele davon als Nachkommastellen?

Ich behaupte ja dass nur eine Potenzreihenentwicklung (spart ROM) oder eine Interpolation (spart Zeit) in Frage kommen.

sin(x) = x - 1/3! * x^3 + 1/5! * x^5 -1/7! x^5 ...

Oder du leitest dir den Sinus aus einer e-Funktion her, was aber auf dasselbe hinausläuft. (Ist nur universeller)
Und den Cosinus kannst du ja als "verschobenen" Sinus betrachten.
Was brauchst du noch?

Und: Warum muß es so genau sein? Was willst du damit machen? Vielleicht reichen ja einfache Näherungen?

[ragnar]

@SprinterSB:
Ich nehme an, doubles und floates werden vom AVR-GCC entsprechend emuliert, oder ? Trotzdem danke für den Tip mit dem Nachinterpolieren. Die Möglichkeit hatte ich schon wieder ganz vergessen.

@sep:
Potenzreihenentwicklung ist viel zu langsam. Das ist wäre nur interessant, um die Tabelle initial im Ram anzulegen und nicht einzucompilieren.

Nur: wie kann ich sin aus e herleiten ?
Und vor allem: wie kann ich den arctan (also tan^(-1)) vernünftig in eine Tabelle quetschen ?

Was ich damit machen will ? Roboterintelligenz natürlich ;-)
Im Wesentlichen möchte ich eine Markov/MonteCarlo-Lokalisation machen. Dafür muss ich ziemlich viele Positionen ständig neu berechnen, von Polar- in Kartesische Koordinaten umrechnen, etc. Das soll vor allem schnell gehen.

ciao, Georg

[sep]

Wenn du das ein bisschen geschickt machst, musst du nicht ständig hin und her rechnen... dan reicht auch eine geringere Genauigkeit.

Vielleicht kannst du dir auch eine schlanke Fließkomma-Engine bauen?

exp(i * phi) = cos(phi) + i sin(phi)
=> sin(phi) = (exp(i * phi) - exp(-i* phi))/2i

[SprinterSB]

@SprinterSB:
Ich nehme an, doubles und floates werden vom AVR-GCC entsprechend emuliert, oder ? Trotzdem danke für den Tip mit dem Nachinterpolieren. Die Möglichkeit hatte ich schon wieder ganz vergessen.
Klaro, ne FPU gibt's ja nicht bei AVR.


Nur: wie kann ich sin aus e herleiten ?
Und vor allem: wie kann ich den arctan (also tan^(-1)) vernünftig in eine Tabelle quetschen ?

Was willst du mit exp(). Über C zu rechnen macht dir nur Overhead. Du weisst doch, daß deine Werte in R liegen. Für eine Multiplikation in C brauchst du immerhin 3 Multiplikationen über R.

Für atan() hast du

atan(x) = Pi/2 - atan(1/x)
atan(x) = -atan(-x)

was schon mal das Intervall auf [0,1] begrenzt. Falls du über die Taylorreihe um 0 von atan() gehen willst ist das schlecht, denn am Rande des Konvergenzradius ist die Konvergenz echt mies.
Evtl hilft das Additionstheorem
atan x + atan y = atan ((x+y)/(1-xy)), |x| << 1, |y| << 1
also
atan x = 1/2 * atan (2x / (1-x^2)) mit |x| << 1
oder so ähnlich ;-)
Wenn man das wiederholt anwendet und den atan() um 0 linearisiert, also atan x = x nimmt, bekommt man den atan() ebenfalls raus. Allerdings muss man Wurzeln ziehen, wenn ich mich recht erinnere. Ne Wurzel zu ziehen wiederum ist nicht viel mehr Aufwand als ein paar Divisionen.

Noch ein Tipp:
Wenn du 2 Zahlen multipliziertst, etwa 2 16-bit-Werte in 8-bit-Darstellung, dann musst du auswerten
P = (B*a1+a0)*(B*b1+b0)
Dabei ist B die Basis (hier 2^8) und a1, a0, b1, b0 sind die Ziffern zur Basis B.
Das auszumultiplizieren:
P = B^2*a1*b1 + B*(a1*b0 + a0*b1) + a0*b0
= B^2*c2 + B*c1 + c0
So gerechnet, kostet das 4 Multiplikationen, und die sind teuer. (Multiplikation mit der Basis ist trivial).
Wenn du hinschreibst
ck = (a1+a0)*(b1+b0) = a1*b1 + a1*b0 + a0*b1 + a0*b0
c2 = a1*b1
c0 = a0*b0
hast du
P = B^2*c2 + B*(ck-c2-c0) + c0,
was dich nur noch Multiplikationen kostet. Die Idee -- allerdings für große Zahlen mit mehreren hundert Stellen -- stammt von Karatsuba. Allerdings musst du etwas Acht geben, weil die Koeffizienten noch nicht auf 0 <= B < ci normiert sind.

[sep]

Was willst du mit exp(). Über C zu rechnen macht dir nur Overhead. Du weisst doch, daß deine Werte in R liegen. Für eine Multiplikation in C brauchst du immerhin 3 Multiplikationen über R.

Ja aber für die e-Funktion kann man vielleicht eine gute Interpolation bauen und sich den Rest aus dieser holen... Sinus, Cosinus und Tangens sind ja direkt möglich. Für den arkustangens bräuchte man dann den ln ... den man sich vielleicht aus der e-Funktion bauen könnte?

Aber vermutlich ist es einfacher eine Spline-Interpolation o.ä. der Funktionen zu machen.

Macht C eigentlich diese Optimierung, wie du sie beschreibst, für mehr-Bytige Variablen automatisch oder muss man sich da eigene Operatoren bauen?

[SprinterSB]

Macht C eigentlich diese Optimierung, wie du sie beschreibst, für mehr-Bytige Variablen automatisch oder muss man sich da eigene Operatoren bauen?
Ob eine solche Optimierung sinnvoll ist, sieht man leider oft erst, nachdem man sie implementiert hat, denn sie ist von vielen Faktoren abhängig: wie teuer ist eine Multiplikation gegen eine Addition, etc.
Wie gcc mit doubles und floates umgeht siehst du in den Quellen von gcc in
gcc/libgcc2.c
gcc/config/avr/libgcc.S
gcc/config/avr/avr.md
Solche Optimierungen macht avr-gcc AFAIK nicht und IMHO würd ich eher versuchen gute Routinen für die zu berechnenden Funktionen zu finden als an den Basics rumzuschrauben.

tan würde ich nicht direkt implementieren, sonder als tan=sin/cos wegen der Pole von tan.

Den atan via ln zu berechnen ginge dann weiter ins Complexe zu artanh, weil ln grottig konvergiert.

Der OP hat auch nix darüber gesagt, auf welcher Maschine er überhaupt ist. "auf einem uC" kann ja alles sein...

[ragnar]

Vielen Dank für die zahlreichen Antworten. Ich werde mich mal wieder melden wenns fertig ist, wird aber wohl noch eine geraume Weile dauern.

Georg