Warum der CORDIC-Algorithmus kostenlos in meinem Herzen wohnt
Floating Point mit Fixed Point vermeiden
- Mit Fixed Point statt Floating Point lassen sich reelle Zahlen darstellen
- Mit einem 32-Bit-Integer werden die oberen 16 Bit als Ganzzahlteil und die unteren 16 Bit als Nachkommateil verwendet
- Damit lassen sich ungefähr Werte von -32768.99997 bis 32767.99997 darstellen
- Der Programmierer kann die Position des Dezimalpunkts festlegen und so die Genauigkeit anpassen
- Um
float in Fixed Point umzuwandeln, mit 2^16 multiplizieren und anschließend nach int32_t casten
- Um Fixed Point in
float umzuwandeln, durch 2^16 teilen
- Addition und Subtraktion funktionieren unverändert, bei Multiplikation und Division muss der Scaling Factor angepasst werden
Überblick über den CORDIC-Algorithmus
- CORDIC ist die Abkürzung für "Co-ordinate Rotation Digital Computer" und wurde Mitte der 1950er Jahre entwickelt
- Eine Methode zur Berechnung von Sinus- und Kosinuswerten, bei der ein Vektor auf dem Einheitskreis schrittweise um kleine Winkel rotiert wird
- Ähnlich wie bei der binären Suche wird zunächst mit großen Winkeln in Richtung des Zielwinkels bewegt und dann durch halbierte Drehungen im Uhrzeigersinn oder gegen den Uhrzeigersinn zur Lösung konvergiert
- Der maximale Rotationswinkel ist 90 Grad (
π/2 rad), und nach 16 Iterationen konvergiert der Wert in die Nähe des Zielwinkels
- Der y-Wert des konvergierten Vektors ist ungefähr
sin(a), der x-Wert ungefähr cos(a)
Vereinfachung der Matrix, sodass nur konstante Multiplikation verwendet wird
- Die Rotationsmatrix enthält Sinus-, Kosinus- und Tangensfunktionen, was die Berechnung aufwendig macht
- Da die Tangensfunktion bei einer festen Rotationsfolge verwendet wird, können die Werte vorab berechnet und in einer Tabelle gespeichert werden (etwa 64 Byte)
- Der Kosinus-Term tritt in jeder Iteration auf, aber da sein Konvergenzwert konstant ist (etwa 0.6366), muss er nur einmal am Ende multipliziert werden
Nur Shift- und Add-Operationen verwenden
- Die für die Tangensfunktion verwendeten Winkel werden mithilfe der Arkustangensfunktion als
2^-i gewählt
- Dadurch kann Multiplikation durch Bit-Shift-Operationen ersetzt werden
- Der Konvergenzwert des Kosinus-Terms wird erneut berechnet und ergibt ungefähr 0.60725; dieser wird als x-Wert des initialen Vektors gesetzt
- Jede Iteration des CORDIC-Algorithmus vereinfacht sich damit wie folgt
- Wenn
z größer oder gleich 0 ist, gegen den Uhrzeigersinn drehen (bei x y>>i subtrahieren, zu y x>>i addieren)
- Wenn
z kleiner als 0 ist, im Uhrzeigersinn drehen (zu x y>>i addieren, von y x>>i subtrahieren)
- Den Winkelwert aus der Tabelle subtrahieren oder addieren und so
z aktualisieren
- Dadurch lassen sich trigonometrische Funktionen nur mit konstanter Multiplikation, Bit-Shifts und Additionen berechnen
Meinung von GN⁺
- CORDIC wirkt wie ein nützlicher Algorithmus für Umgebungen mit begrenzten Hardware-Ressourcen, etwa Embedded-Systeme oder FPGAs. Besonders wenn Gleitkommaoperationen nicht unterstützt werden, ist das ein erwägenswerter Ansatz.
- Die Idee, die Winkel der Tangensfunktion strategisch zu wählen und Multiplikationen so durch Bit-Shifts zu ersetzen, ist beeindruckend. Ein gutes Beispiel für das Zusammenspiel von mathematischer Einsicht und Verständnis von Computerarchitektur.
- Interessant ist auch, dass sich der Ansatz nicht nur für trigonometrische Funktionen, sondern auch für Logarithmen, Exponentialfunktionen, Quadratwurzeln und andere Berechnungen nutzen lässt. Der verwandte BKM-Algorithmus ist in dem Zusammenhang ebenfalls einen Blick wert.
- Allerdings ist in moderner Hardware oft bereits eine FPU integriert, und bei Fixed-Point-Arithmetik kann es zu Präzisionsverlusten kommen, weshalb man den Einsatz sorgfältig abwägen sollte.
- In Systemen, die viele ähnliche Berechnungen durchführen, könnte man auch über dedizierte CORDIC-Hardware nachdenken.
1 Kommentare
Hacker-News-Kommentare
Der CORDIC-Algorithmus kann nicht nur auf FPGAs eingesetzt werden, sondern auch in der Spieleentwicklung oder in verteilten Physiksimulationen. Fließkommaberechnungen garantieren plattformübergreifend nur schwer deterministisches Verhalten; eine mögliche Lösung ist daher die Implementierung einer Fixed-Point-Physik-Engine und die Umsetzung trigonometrischer Funktionen mit CORDIC.
CORDIC lässt sich nicht nur für Sinus und Kosinus nutzen, sondern auch für Logarithmen, Exponentialfunktionen, Quadratwurzeln, Vektorbeträge, Umrechnungen zwischen Polarkoordinaten und kartesischen Koordinaten sowie für Vektorrotationen. Mit Quaternionen könnten CORDIC-basierte Berechnungen offenbar noch effizienter und genauer durchgeführt werden.
Jemand berichtet, im Precalculus-Unterricht an der Highschool gelernt zu haben, wie Taschenrechner trigonometrische Funktionen implementieren, und später festgestellt zu haben, dass es in Wirklichkeit CORDIC und nicht die Taylor-Reihe war, woraufhin die Person es selbst in TI Basic implementierte.
Stand 2023 besitzen selbst günstige MCUs wie der STM32G4 eine integrierte FPU, sodass sich Fließkomma statt Fixed-Point problemlos verwenden lässt. Der G4 verfügt jedoch auch über ein dediziertes CORDIC-Peripheriegerät in Hardware, offenbar um Präzisionsverluste bei Fließkomma zu vermeiden.
In der Erklärung, dass eine Rotation um 22,75° einer Rotation um 45° gefolgt von einer Rotation um -22,5° entspreche, scheint ein Fehler zu sein. Vermutlich ist 22,5° gemeint.
Meaghers Octree-System wurde ausschließlich mit Ganzzahloperationen und ohne Ganzzahlmultiplikation oder -division implementiert. Das erleichterte die Entwicklung schneller, maßgeschneiderter VLSI-Grafikbeschleuniger-Hardware für Octree-Darstellungen.
CORDIC kann als ein Konzept betrachtet werden, das der Farey-Folge für Winkel ähnelt, oder dem Mediant beziehungsweise der naiven Addition von Brüchen.
CORDIC wurde sogar in programmierbaren HP-Vintage-Rechnern mit 4-Bit-CPU implementiert. Auch Näherungsverfahren auf Basis der Taylor-Entwicklung der Sinusfunktion lassen sich programmieren.
Wer diesen Artikel mochte, sollte vielleicht auch Donald Knuths Standardwerk "The Art of Computer Programming" lesen, das mathematische Algorithmen anhand von Beispielen erklärt.
CORDIC war früher ein sehr populärer Algorithmus im DSP-Bereich.
Ein großartiger Algorithmus, der sich nützlich für die Ausführung neuronaler Netze auf leistungsschwacher Hardware anfühlen könnte.