mikrocontroller.net

Forum: Projekte & Code atan2 Funktion mit lookup table für arm


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Erik H. (agutanus)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Da ich in der arm dsp-library keine optimierte atan2_f32 -Funktion 
finden konnte, habe ich mir nun selber eine geschrieben:

f32 arm_atan2_f32(f32 y, f32 x);

mathematisch: atan2( y, x ) = atan( y / x )

Ausgehend von der arm_sin_f32() Funktion habe ich in excel eine LUT 
(lookup table, size: 64) erstellt und ein paar Fallunterscheidungen in 
der Funktion durchgeführt.
Da eine atan2 LUT eigentlich die Eingangswerte im Bereich von [0 ... 
inf] abdecken müssten, wird zu Beginn geprüft, welcher Eingangswert 
betragsmäßig größer ist und dann der kleinere durch den größeren Wert 
dividiert.
Dadurch muss die LUT lediglich Eingangswerte von [0 ... 1] abdecken.
Negative Eingangswerte werden ebenfalls durch Fallunterscheidungen 
berücksichtigt.

Im Vergeich zur standard-C-Funktion atan2(y, x); benötigt diese auf 
einem Cortex M3 lediglich 48% der Rechenzeit und wich nur in einer von 9 
Testrechnungen in der letzten (6.) Nachkommastelle ab.

(für meine Zwecke mehr als ausreichend, da sie zur Auswertung von 
Sensormesswerten genutzt wird, die maximal 3 Dezimalstellen sicher 
messen)

Falls jemand noch Fehler oder Optimierungsmöglichkeiten findet: her 
damit! :-)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Erik H. schrieb:
> Da ich in der arm dsp-library keine optimierte atan2_f32 -Funktion
> finden konnte, habe ich mir nun selber eine geschrieben:
>
> f32 arm_atan2_f32(f32 y, f32 x);
>
> mathematisch: atan2( y, x ) = atan( y / x )
>
> Ausgehend von der arm_sin_f32() Funktion habe ich in excel eine LUT
> (lookup table, size: 64) erstellt und ein paar Fallunterscheidungen in
> der Funktion durchgeführt.
> Da eine atan2 LUT eigentlich die Eingangswerte im Bereich von [0 ...
> inf] abdecken müssten, wird zu Beginn geprüft, welcher Eingangswert
> betragsmäßig größer ist und dann der kleinere durch den größeren Wert
> dividiert.
> Dadurch muss die LUT lediglich Eingangswerte von [0 ... 1] abdecken.
> Negative Eingangswerte werden ebenfalls durch Fallunterscheidungen
> berücksichtigt.
>
> Im Vergeich zur standard-C-Funktion atan2(y, x); benötigt diese auf
> einem Cortex M3 lediglich 48% der Rechenzeit und wich nur in einer von 9
> Testrechnungen in der letzten (6.) Nachkommastelle ab.

hmmm. Wenn die LUT "nur" doppelt so schnell ist, lohn sich diese 
Optimierung dann überhaupt? Bist duso knapp mit der Zeit, oder ist's 
eher eine kosmetische Optimierung?

> (für meine Zwecke mehr als ausreichend, da sie zur Auswertung von
> Sensormesswerten genutzt wird, die maximal 3 Dezimalstellen sicher
> messen)
>
> Falls jemand noch Fehler oder Optimierungsmöglichkeiten findet: her
> damit! :-)

Was ich nicht verstehe ist die Interpolante:

Die Interpolate für das Intervall x+Δ wird erhalten durch ein Polynom 3. 
Grades, das an x-Δx, x, x+Δ und x+2·Δx die gleichen Funktionswerte hat 
wie atan. Solche Polynome neigen bekanntermassen dazu, zwischen den 
Stützstellen aufzuschwingen und nicht gut zu interpolieren.

Wird zB linear interpoliert, dann ergibt sich als Maximalfehler ca. 2E-5 
was knapp 5 Dezimalen sind. Ein Polynom 3. Grades zu berechnen lohnt 
also nicht wirklich. Der Maximalfehler tritt übrigens wie erwartet in 
der Mitte des Intervalls auf, in dem 0.57 ≈ 1/sqrt(3) liegt, also in der 
Nähe der Nullstelle der 3. Ableitung von atan.

Wird hingegen mit Béziers 3. Ordnung interpoliert, was pro Auswertung 
nur 7 Multiplikationen kostet, reicht eine Tabelle mit 64 Werten (also 
32 Stützen) für eine Genauigkeit von 8 Dezimalen.

Weitere Möglichkeit ist eine Approximation nach Remez-Algorithmus wie 
von Yalu hier demonstriert:

Beitrag "Re: Suche speichersparende Möglichkeit für exp10()"

Da atan braver ist als das dortige exp10 dürfte die Formel für atan noch 
einfacher werden.

Autor: Erik H. (agutanus)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johann L. schrieb:

> hmmm. Wenn die LUT "nur" doppelt so schnell ist, lohn sich diese
> Optimierung dann überhaupt? Bist duso knapp mit der Zeit, oder ist's
> eher eine kosmetische Optimierung?

Ich fand das Ergebnis gar nicht schlecht, da die originalen arm_math 
Funktionen (sin, cos) in f32 lediglich etwa 30% Zeitersparnis bringen.


> Was ich nicht verstehe ist die Interpolante

Mit der Interpolation habe ich mich nicht näher beschäftigt, da ich von 
der arm_sin_f32() Funktion ausgegangen bin. Ich habe die dort verwendete 
kubische Interpolation 1zu1 übernommen, da sie mir recht sinnvoll 
erschien.
Ich kann das ganze ja nochmal mit linearer Interpolation (geringster 
Rechenaufwand) basteln... Dann dürfte es noch wesentlich schneller sein.

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.