Verschiedene (und schnellste) Methoden zur Berechnung von Sinus (und Cosinus) in Arduino

9

Ich verwende ein Arduino Uno-Board, um die Winkel meines Systems (Roboterarm) zu berechnen. Die Winkel sind tatsächlich 10-Bit-Werte (0 bis 1023) vom ADC, wobei der gesamte Bereich des ADC verwendet wird. Ich werde nur im 1. Quadranten (0 bis 90 Grad) arbeiten, wo sowohl Sinus als auch Cosinus positiv sind, also gibt es kein Problem mit negativen Zahlen. Meine Zweifel können in 3 Fragen ausgedrückt werden:

  1. Welche verschiedenen Methoden gibt es, um diese trigonometrischen Funktionen auf Arduino zu berechnen?

  2. Was ist der schnellste Weg, um dasselbe zu tun?

  3. Es gibt die Funktionen sin () und cos () in der Arduino-IDE, aber wie berechnet der Arduino sie tatsächlich (wie in verwenden sie Nachschlagetabellen oder Näherungen usw.)? Sie scheinen eine offensichtliche Lösung zu sein, aber ich würde gerne ihre tatsächliche Implementierung erfahren, bevor ich sie ausprobiere.

PS: Ich bin sowohl offen für die Standardcodierung in der Arduino IDE und der Assemblycodierung als auch für alle anderen Optionen, die nicht erwähnt werden. Ich habe auch keine Probleme mit Fehlern und Annäherungen, die für ein digitales System unvermeidlich sind; Wenn möglich, ist es jedoch gut, das Ausmaß möglicher Fehler zu erwähnen

Transistor Overlord
quelle
Würden Sie mit ungefähren Werten einverstanden sein?
sa_leinad
Ja eigentlich, aber ich möchte das Ausmaß des Fehlers verschiedener Methoden wissen. Dies ist kein Präzisionsprodukt, sondern ein Nebenprojekt von mir. Tatsächlich sind Annäherungen für fast jedes (wenn nicht jedes) digitale System, das eine mathematische Funktion implementiert, unvermeidlich
Transistor Overlord
Ich gehe davon aus, dass Sie in Abschlüssen arbeiten möchten. Möchten Sie Ganzzahlen oder Dezimalzahlen für den Winkel eingeben?
sa_leinad
Grad ja. Ich denke, es wäre einfacher, Code zu schreiben und zu testen, wenn wir ganze Zahlen verwenden, also würde ich damit anfangen. Ich werde klarere Informationen über Änderungen
Transistor Overlord
1
Für nur 90 (ganzzahlige) Grad wäre eine Nachschlagetabelle mit 90 Einträgen am schnellsten und effizientesten. Tatsächlich können Sie für die vollen 360 Grad eine Nachschlagetabelle mit 90 Einträgen verwenden. Lesen Sie es einfach für 90-179 rückwärts und invertieren Sie es für 180-269. Machen Sie beides für 270-359.
Majenko

Antworten:

11

Die beiden grundlegenden Methoden sind mathematische Berechnungen (mit Polynomen) und Nachschlagetabellen.

Die Mathematikbibliothek des Arduino (libm, Teil von avr-libc) verwendet die erstere. Es ist für den AVR optimiert, da es mit 100% Assemblersprache geschrieben ist und daher fast unmöglich zu verfolgen ist, was es tut (es gibt auch keine Kommentare). Seien Sie versichert, es wird das optimierteste Pure-Float-Implementierungsgehirn sein, das unserem weit überlegen ist.

Der Schlüssel dort ist jedoch float . Alles auf dem Arduino, was Gleitkomma beinhaltet, wird im Vergleich zu reinen Ganzzahlen schwergewichtig sein, und da Sie nur Ganzzahlen zwischen 0 und 90 Grad anfordern, ist eine einfache Nachschlagetabelle bei weitem die einfachste und effizienteste Methode.

Eine Tabelle mit 91 Werten gibt Ihnen alles von 0 bis einschließlich 90. Wenn Sie jedoch eine Tabelle mit Gleitkommawerten zwischen 0,0 und 1,0 sinerstellen, haben Sie immer noch die Ineffizienz, mit Gleitkommazahlen zu arbeiten (die nicht so ineffizient sind wie die Berechnung mit Gleitkommazahlen), sodass das Speichern eines Festkommawertes weitaus effizienter wäre.

Das kann so einfach sein wie das Speichern des mit 1000 multiplizierten Werts, sodass Sie zwischen 0 und 1000 statt zwischen 0,0 und 1,0 haben (zum Beispiel würde sin (30) als 500 statt 0,5 gespeichert). Effizienter wäre es, die Werte beispielsweise als Q16-Wert zu speichern, wobei jeder Wert (Bit) 1/65536. von 1,0 darstellt. Mit diesen Q16-Werten (und den zugehörigen Q15-, Q1.15- usw.) kann effizienter gearbeitet werden, da Sie über Zweierpotenzen verfügen, mit denen Computer gerne arbeiten, anstatt über Zehnerpotenzen, mit denen sie nicht gerne arbeiten.

Vergessen Sie nicht auch , dass die sin()Funktion Radiant erwartet, so dass Sie zunächst Ihre ganze Zahl Grad in einen Floating - Point - Radiant - Wert umwandeln müssen, so dass die Verwendung von sin()noch ineffizient im Vergleich zu einer Referenztabelle , die direkt mit dem ganzzahligen Grad Wert arbeiten kann.

Eine Kombination der beiden Szenarien ist jedoch möglich. Durch lineare Interpolation können Sie einen Gleitkommawinkel zwischen zwei ganzen Zahlen approximieren. Es ist so einfach wie herauszufinden, wie weit Sie zwischen zwei Punkten in der Nachschlagetabelle liegen, und einen gewichteten Durchschnitt basierend auf dem Abstand der beiden Werte zu erstellen. Zum Beispiel, wenn Sie bei 23,6 Grad sind, nehmen Sie (sintable[23] * (1-0.6)) + (sintable[24] * 0.6). Grundsätzlich wird Ihre Sinuswelle zu einer Reihe diskreter Punkte, die durch gerade Linien miteinander verbunden sind. Sie tauschen Genauigkeit gegen Geschwindigkeit.

Majenko
quelle
Ich habe vor einiger Zeit eine Bibliothek geschrieben, die ein Taylor-Polynom für sin / cos verwendete, das schneller als die Bibliothek war. Gegeben, ich habe Gleitkomma-Bogenmaß als Eingabe für beide verwendet.
Tuskiomi
8

Hier gibt es einige gute Antworten, aber ich wollte eine Methode hinzufügen, die noch nicht erwähnt wurde, eine, die sich sehr gut für die Berechnung trigonometrischer Funktionen auf eingebetteten Systemen eignet, und das ist die CORDIC-Technik. Wiki-Eintrag hier Sie kann Triggerfunktionen nur mit Verschiebungen und berechnen fügt hinzu und eine kleine Nachschlagetabelle.

Hier ist ein grobes Beispiel in C. Tatsächlich implementiert es die atan2 () - Funktion der C-Bibliotheken mit CORDIC (dh einen Winkel mit zwei orthogonalen Komponenten finden). Es verwendet Gleitkommawerte, kann jedoch für die Verwendung mit Festkomma-Arithmetik angepasst werden.

/*
 * Simple example of using the CORDIC algorithm.
 */

#include <stdio.h>
#include <math.h>

#define CORDIC_TABLE_SIZE  16

double cordic_table[CORDIC_TABLE_SIZE];

void init_table(void);
double angle(double I, double Q);

/*
 * Given a sine and cosine component of an
 * angle, compute the angle using the CORIDC
 * algoritm.
 */
double angle(double I, double Q)
{
    int L;
    double K = 1;
    double angle_acc = 0;
    double tmp_I;

    if (I < 0) {
        /* rotate by an initial +/- 90 degrees */
        tmp_I = I;
        if (Q > 0.0) {
            I = Q;           /* subtract 90 degrees */
            Q = -tmp_I;
            angle_acc = -90;
        } else {
            I = -Q;          /* add 90 degrees */
            Q = tmp_I;
            angle_acc = 90;
        }
    } else {
        angle_acc = 0;
    }

    /* rotate using "1 + jK" factors */
    for (L = 0, K = 1; L <= CORDIC_TABLE_SIZE; L++) {
        tmp_I = I;
        if (Q >= 0.0) {
            /* angle is positive: do negative roation */
            I += Q * K;
            Q -= tmp_I * K;
            angle_acc -= cordic_table[L];
        } else {
            /* angle is negative: do positive rotation */
            I -= Q * K;
            Q += tmp_I * K;
            angle_acc += cordic_table[L];
        }
        K /= 2.0;
    }
    return -angle_acc;
}

void init_table(void)
{
    int i;
    double K = 1;

    for (i = 0; i < CORDIC_TABLE_SIZE; i++) {
        cordic_table[i] = 180 * atan(K) / M_PI;
        K /= 2.0;
    }
}
int main(int argc, char **argv)
{
    double I, Q, A, Ar, R, Ac;

    init_table();

    printf("# Angle,    CORDIC Angle,  Error\n");
    for (A = 0; A < 90.0; A += 0.5) {

        Ar = A * M_PI / 180; /* convert to radians for C's sin & cos fn's */

        R = 5;  // Arbitrary radius

        I = R * cos(Ar);
        Q = R * sin(Ar);

        Ac = angle(I, Q);
        printf("%9f, %9f,   %12.4e\n", A, Ac, Ac-A);
    }
    return 0;
}

Aber probieren Sie zuerst die nativen Arduino-Triggerfunktionen aus - sie sind möglicherweise trotzdem schnell genug.

Halzephron
quelle
1
Ich habe in der Vergangenheit einen ähnlichen Ansatz gewählt, auf stm8. Es dauert zwei Schritte: 1) Berechne sin (x) und cos (x) aus sin (2x) und dann 2) berechne sin (x +/- x / 2) aus sin (x), sin (x / 2) , cos (x) und cos (x / 2) -> durch Iteration können Sie sich Ihrem Ziel nähern. In meinem Fall habe ich mit 45 Grad (0,707) angefangen und mich zum Ziel herausgearbeitet. Es ist erheblich langsamer als die Standardfunktion von IAR sin ().
Dannyf
7

Ich habe ein bisschen mit der Berechnung von Sinus und Cosinus auf dem Arduino unter Verwendung von Festpunkt-Polynom-Approximationen gespielt. Hier sind meine Messungen der durchschnittlichen Ausführungszeit und des Worst-Case-Fehlers im Vergleich zum Standard cos()und sin()von avr-libc:

function    max error   cycles   time
-----------------------------------------
cos_fix()   9.53e-5     108.25    6.77 µs
sin_fix()   9.53e-5     110.25    6.89 µs
cos()       2.98e-8     1720.8   107.5 µs
sin()       2.98e-8     1725.1   107.8 µs

Es basiert auf einem Polynom 6. Grades, das mit nur 4 Multiplikationen berechnet wurde. Die Multiplikationen selbst werden in Assembly durchgeführt, da ich festgestellt habe, dass gcc sie ineffizient implementiert hat. Die Winkel werden uint16_tin Einheiten von 1/65536 einer Umdrehung ausgedrückt , wodurch die Arithmetik der Winkel natürlich modulo eine Umdrehung funktioniert.

Wenn Sie der Meinung sind, dass dies zu Ihrer Rechnung passt, finden Sie hier den Code: Festpunkttrigonometrie . Entschuldigung, ich habe diese Seite, die auf Französisch ist, immer noch nicht übersetzt, aber Sie können die Gleichungen verstehen, und der Code (Variablennamen, Kommentare ...) ist auf Englisch.


Bearbeiten : Da der Server verschwunden zu sein scheint, finden Sie hier einige Informationen zu den Annäherungen, die ich gefunden habe.

Ich wollte Winkel im binären Festkomma, in Quadranteneinheiten (oder äquivalent in Windungen) schreiben. Und ich wollte auch ein gerades Polynom verwenden, da diese effizienter zu berechnen sind als beliebige Polynome. Mit anderen Worten, ich wollte ein Polynom P (), so dass

cos (π / 2 x) ≈ P (x 2 ) für x ∈ [0,1]

Ich forderte auch, dass die Näherung an beiden Enden des Intervalls genau ist, um sicherzustellen, dass cos (0) = 1 und cos (π / 2) = 0. Diese Einschränkungen führten zur Form

P (u) = (1 - u) (1 + uQ (u))

wobei Q () ein beliebiges Polynom ist.

Als nächstes suchte ich nach der besten Lösung in Abhängigkeit vom Grad von Q () und fand diese:

        Q(u)              degree of P(x²)  max error
─────────────────────────┼─────────────────┼──────────
          0                       2         5.60e-2
       0.224                     4         9.20e-4
0.2335216 + 0.0190963 u          6         9.20e-6

Die Wahl unter den oben genannten Lösungen ist ein Kompromiss zwischen Geschwindigkeit und Genauigkeit. Die dritte Lösung bietet mehr Genauigkeit als mit 16-Bit erreichbar, und ich habe sie für die 16-Bit-Implementierung ausgewählt.

Edgar Bonet
quelle
2
Das ist unglaublich, @Edgar.
SDsolar
Was haben Sie getan, um das Polynom zu finden?
TLW
@TLW: Ich verlangte, dass es einige „schöne“ Eigenschaften hat (z. B. cos (0) = 1), die auf die Form (1 - x²) (1 + x²Q (x²)) beschränkt sind, wobei Q (u) beliebig ist Polynom (wird auf der Seite erklärt). Ich nahm ein Q ersten Grades (nur 2 Koeffizienten), fand die ungefähren Koeffizienten durch Anpassung und stimmte dann die Optimierung durch Versuch und Irrtum von Hand ab.
Edgar Bonet
@ EdgarBonet - interessant. Beachten Sie, dass diese Seite für mich nicht geladen wird, obwohl zwischengespeichert funktioniert. Könnten Sie bitte das zu dieser Antwort verwendete Polynom hinzufügen?
TLW
@ TLW: fügte das der Antwort hinzu.
Edgar Bonet
4

Sie können einige Funktionen erstellen, die mithilfe der linearen Approximation die sin () und cos () eines bestimmten Winkels bestimmen.

Ich denke ungefähr so: Für jeden habe ich die grafische Darstellung von sin () und cos () in drei Abschnitte unterteilt und eine lineare Annäherung an diesen Abschnitt vorgenommen.
Lineare Näherung

Ihre Funktion würde idealerweise zuerst prüfen, ob der Bereich des Engels zwischen 0 und 90 liegt.
Dann würde sie eine ifelseAnweisung verwenden, um zu bestimmen, zu welchem ​​der 3 Abschnitte sie gehört, und dann die entsprechende lineare Berechnung durchführen (dh output = mX + c)

sa_leinad
quelle
Wird dies nicht eine Gleitkomma-Multiplikation beinhalten?
Transistor Overlord
1
Nicht unbedingt. Sie könnten es haben, damit die Ausgabe zwischen 0-100 statt 0-1 skaliert wird. Auf diese Weise haben Sie es mit ganzen Zahlen zu tun, nicht mit Gleitkommazahlen. Hinweis: 100 war willkürlich. Es gibt keinen Grund, warum Sie die Ausgabe nicht zwischen 0-128 oder 0-512 oder 0-1000 oder 0-1024 skalieren konnten. Wenn Sie ein Vielfaches von 2 verwenden, müssen Sie nur nach rechts verschieben, um das Ergebnis wieder zu verkleinern.
sa_leinad
Ziemlich klug, @sa_leinad. Upvote. Ich erinnere mich, dass ich dies getan habe, als ich mit der Vorspannung von Transistoren gearbeitet habe.
SDsolar
4

Ich suchte nach anderen Leuten, die cos () und sin () angenähert hatten, und stieß auf diese Antwort:

dtbs Antwort auf "Fast Sin / Cos mit einem vorberechneten Übersetzungsarray"

Grundsätzlich berechnete er, dass die Funktion math.sin () aus der Mathematikbibliothek schneller war als die Verwendung einer Nachschlagetabelle mit Werten. Aber soweit ich das beurteilen kann, wurde dies auf einem PC berechnet.

Arduino enthält eine Mathematikbibliothek , mit der sin () und cos () berechnet werden können.

sa_leinad
quelle
1
In PCs sind FPUs integriert, die es schnell machen. Arduino tut es nicht, und das macht es langsam.
Majenko
Die Antwort ist auch für C #, das Dinge wie das Überprüfen von Array-Grenzen erledigt.
Michael
3

Eine Nachschlagetabelle ist der schnellste Weg, um Sinus zu finden. Und wenn Sie mit Festkommazahlen (Ganzzahlen, deren Binärpunkt nicht rechts von Bit-0 liegt) rechnen können, sind Ihre weiteren Berechnungen mit den Sinuswerten ebenfalls viel schneller. Diese Tabelle kann dann eine Worttabelle sein, möglicherweise in Flash, um RAM-Speicherplatz zu sparen. Beachten Sie, dass Sie in Ihrer Mathematik möglicherweise Longs für große Zwischenergebnisse verwenden müssen.

JRobert
quelle
1

im Allgemeinen Nachschlagetabelle> Annäherung -> Berechnung. ram> flash. Ganzzahl> Festpunkt> Gleitkomma. Vorberechnung> Echtzeitberechnung. Spiegeln (Sinus zu Cosinus oder Cosinus zu Sinus) vs. tatsächliche Berechnung / Nachschlagen ....

Jeder hat seine Vor- und Nachteile.

Sie können alle möglichen Kombinationen vornehmen, um festzustellen, welche für Ihre Anwendung am besten geeignet ist.

edit: Ich habe eine schnelle Überprüfung durchgeführt. Bei Verwendung einer 8-Bit-Ganzzahlausgabe dauert die Berechnung von 1024 sin-Werten mit der Nachschlagetabelle 0,6 ms und mit Floatern 133 ms oder 200x langsamer.

dannyf
quelle
1

Ich hatte eine ähnliche Frage an OP. Ich wollte eine LUT-Tabelle erstellen, um den ersten Quadranten der Sinusfunktion als vorzeichenlose 16-Bit-Ganzzahlen von 0x8000 bis 0xffff zu berechnen. Und am Ende habe ich das aus Spaß und Gewinn geschrieben. Hinweis: Dies würde effizienter funktionieren, wenn ich 'if'-Anweisungen verwenden würde. Es ist auch nicht sehr genau, aber es wäre genau genug für eine Sinuswelle in einem Klangsynthesizer

void sin_lut_ctor(){

//Make a Look Up Table for 511 terms of the sine function.
//Plugin in some polynomials to do some magic
//and you get an aproximation for sines up to π/2.
//

//All sines yonder π/2 can be derived with math

const uint16_t uLut_d = 0x0200; //maximum LUT depth for π/2 terms. 
uint16_t uLut_0[uLut_d];        //The LUT itself.
//Put the 2 above before your void setup() as global variables.
//This coefficients will only work for uLut_d = 511.

uint16_t arna_poly_0 = 0x000a; // 11
uint16_t arna_poly_1 = 0x0001; // 1
uint16_t arna_poly_2 = 0x0007; // 7
uint16_t arna_poly_3 = 0x0001; // 1   Precalculated Polynomials
uint16_t arna_poly_4 = 0x0001; // 1   
uint16_t arna_poly_5 = 0x0007; // 7
uint16_t arna_poly_6 = 0x0002; // 2
uint16_t arna_poly_7 = 0x0001; // 1

uint16_t Imm_UI_0 = 0x0001;              //  Itterator
uint16_t Imm_UI_1 = 0x007c;              //  An incrementor that decreases in time

uint16_t Imm_UI_2 = 0x0000;              //  
uint16_t Imm_UI_3 = 0x0000;              //              
uint16_t Imm_UI_4 = 0x0000;              //
uint16_t Imm_UI_5 = 0x0000;              //
uint16_t Imm_UI_6 = 0x0000;              //  Temporary variables
uint16_t Imm_UI_7 = 0x0000;              //
uint16_t Imm_UI_8 = 0x0000;              //
uint16_t Imm_UI_9 = 0x0000;              //
uint16_t Imm_UI_A = 0x0000;
uint16_t Imm_UI_B = 0x0000;

uint16_t Imm_UI_A = uLut_d - 0x0001;     //  510

uLut_0[0x0000] = 0x8000;        //Assume that the middle point is 32768 (0x8000 hex)
while (Imm_UI_0 < Imm_UI_A) //Construct a quarter of the sine table
  {
Imm_UI_2++;                                   //Increase temporary variable by 1

Imm_UI_B = Imm_UI_2 / arna_coeff_0;           //Divide it with the first coefficient (note: integer division)
Imm_UI_3 += Imm_UI_B;                         //Increase the next temporary value if the first one has increased up to the 1st coefficient
Imm_UI_1 -= Imm_UI_B;                         //Decrease the incrementor if this is the case
Imm_UI_2 *= 0x001 - Imm_UI_B;                 //Set the first temporary variable back to 0

Imm_UI_B = Imm_UI_3 / arna_poly_1;           //Do the same thing as before with the next set of temporary variables
Imm_UI_4 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_3 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_4 / arna_poly_2;           //And again... and again... you get the idea.
Imm_UI_5 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_4 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_5 / arna_poly_3;
Imm_UI_6 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_5 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_6 / arna_poly_4;
Imm_UI_7 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_6 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_7 / arna_poly_5;
Imm_UI_8 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_7 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_8 / arna_poly_6;
Imm_UI_9 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_8 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_9 / arna_poly_7          //the last set won't need to increment a next variable so skip the step where you would increase it.
Imm_UI_1 -= Imm_UI_B;
Imm_UI_9 *= 1 - Imm_UI_B;

uLut_0[Imm_UI_0] = (uLut_0[Imm_UI_0 - 0x0001] + Imm_UI_1); //Set the current value as the previous one increased by our incrementor
Imm_UI_0++;              //Increase the itterator
  }   
  uLut_0[Imm_UI_A] = 0xffff; //Lastly, set the last value to 0xffff

  //And there you have it. A sine table with only one if statement (a while loop)
}

Verwenden Sie diese Funktion, um die Werte wiederherzustellen. Sie akzeptiert einen Wert von 0x0000 bis 0x0800 und gibt den entsprechenden Wert von der LUT zurück

uint16_t lu_sin(uint16_t lu_val0)
{
  //Get a value from 0x0000 to 0x0800. Return an appropriate sin(value)
  Imm_UI_0 = lu_val0/0x0200; //determine quadrant
  Imm_UI_1 = lu_val0%0x0200; //Get which value
  if (Imm_UI_0 == 0x0000)
  {
    return uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0001)
  {
    return uLut_0[0x01ff - Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0002)
  {
    return 0xffff - uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0003)
  {
    return 0xffff - uLut_0[0x01ff - Imm_UI_1];
  }
}// I'm using if statements here but similarly to the above code block, 
 //you can do without. just with integer divisions and modulos

Denken Sie daran, dies ist nicht der effizienteste Ansatz für diese Aufgabe. Ich konnte einfach nicht herausfinden, wie man Taylor-Serien erstellt, um Ergebnisse im richtigen Bereich zu erzielen.

Arnadath
quelle
Ihr Code wird nicht kompiliert: Imm_UI_Awird zweimal deklariert, a ;und einige Variablendeklarationen fehlen und uLut_0sollten global sein. Mit den notwendigen Korrekturen lu_sin()ist schnell (zwischen 27 und 42 CPU-Zyklen) aber sehr ungenau (maximaler Fehler ≈ 5.04e-2). Ich kann den Punkt dieser „Arnadathschen Polynome“ nicht verstehen: Es scheint eine ziemlich schwere Berechnung zu sein, aber das Ergebnis ist fast so schlecht wie eine einfache quadratische Näherung. Das Verfahren hat auch enorme Speicherkosten. Es wäre viel besser, die Tabelle auf Ihrem PC zu berechnen und als PROGMEMArray in den Quellcode einzufügen.
Edgar Bonet
1

Nur zum Spaß und um zu beweisen, dass dies möglich ist, habe ich eine AVR-Assemblierungsroutine abgeschlossen, um sin (x) -Ergebnisse in 24 Bit (3 Byte) mit einem Fehlerbit zu berechnen. Der Eingabewinkel wird in Grad mit einer Dezimalstelle angegeben, von 000 bis 900 (0 ~ 90,0) nur für den ersten Quadranten. Es verwendet weniger als 210 AVR-Anweisungen und läuft durchschnittlich 212 Mikrosekunden, die von 211us (Winkel = 001) bis 213us (Winkel = 899) variieren.

Es dauerte mehrere Tage, um alles zu erledigen, mehr als 10 Tage (freie Stunden), nur um über den besten Algorithmus für die Berechnung nachzudenken, wenn man bedenkt, dass der AVR-Mikrocontroller kein Gleitkomma ist und alle möglichen Unterteilungen eliminiert. Was mehr Zeit in Anspruch nahm, war die Erstellung der richtigen Aufwärtswerte für Ganzzahlen. Um eine gute Genauigkeit zu erzielen, müssen die Werte von 1e-8 auf binäre Ganzzahlen 2 ^ 28 oder mehr erhöht werden. Sobald alle Fehler gefunden wurden, die für Präzision und Aufrundung verantwortlich sind, und die Berechnungsauflösung um zusätzliche 2 ^ 8 oder 2 ^ 16 erhöht wurden, wurden die besten Ergebnisse erzielt. Ich habe zuerst alle Berechnungen in Excel simuliert und darauf geachtet, dass alle Werte Int (x) oder Round (x, 0) sind, um genau die AVR-Kernverarbeitung darzustellen.

Im Algorithmus muss der Winkel beispielsweise im Bogenmaß angegeben werden. Die Eingabe erfolgt in Grad, um dem Benutzer die Arbeit zu erleichtern. Um Grad in Bogenmaß umzuwandeln, lautet die Trivialformel rad = Grad * PI / 180, es scheint nett und einfach zu sein, aber es ist nicht so, PI ist eine unendliche Zahl - wenn nur wenige Ziffern verwendet werden, entstehen Fehler am Ausgang, die Division durch 180 erfordert AVR-Bitmanipulation, da es keinen Teilungsbefehl gibt, und darüber hinaus würde das Ergebnis Gleitkomma erfordern, da Zahlen weit unter der Ganzzahl 1 enthalten sind. Beispielsweise beträgt der Radian von 1 ° (Grad) 0,017453293. Da PI und 180 Konstanten sind, können Sie diese Sache für eine einfache Multiplikation umkehren. PI / 180 = 0.017453293, multiplizieren Sie es mit 2 ^ 32 und es ergibt sich eine Konstante 74961320 (0x0477D1A8), multiplizieren Sie diese Zahl mit Ihrem Winkel in Grad, Nehmen wir 900 für 90 ° und verschieben Sie es um 4 Bit nach rechts (÷ 16), um 4216574250 (0xFB53D12A) zu erhalten, dh das Bogenmaß der 90 ° mit 2 ^ 28 Erweiterung, das in 4 Bytes ohne eine einzige Division passt (mit Ausnahme der 4) Bitverschiebung nach rechts). In gewisser Weise ist der in einem solchen Trick enthaltene Fehler kleiner als 2 ^ -27.

Alle weiteren Berechnungen müssen sich also daran erinnern, dass es 2 ^ 28 höher ist und sich darum gekümmert hat. Sie müssen die Ergebnisse für unterwegs durch 16, 256 oder sogar 65536 teilen, um zu vermeiden, dass unnötig wachsende Hungerbytes verwendet werden, die die Auflösung nicht verbessern würden. Das war eine mühsame Aufgabe, nur die minimale Anzahl von Bits in jedem Berechnungsergebnis zu finden und die Ergebnisgenauigkeit bei 24 Bit zu halten. Jede der verschiedenen Berechnungen wurde in Versuch / Irrtum mit höherer oder niedrigerer Bitanzahl im Excel-Fluss durchgeführt, wobei die Gesamtmenge der Fehlerbits am Ergebnis in einem Diagramm beobachtet wurde, das 0-90 ° mit einem Makro zeigt, das den Code 900 Mal ausführt. einmal pro Zehntelgrad. Dieser "visuelle" Excel-Ansatz war ein von mir erstelltes Tool, das mir sehr geholfen hat, die beste Lösung für jeden einzelnen Teil des Codes zu finden.

Wenn Sie beispielsweise dieses spezielle Berechnungsergebnis 13248737.51 auf 13248738 aufrunden oder nur die Dezimalstellen "0,51" verlieren, wie stark wirkt sich dies auf die Genauigkeit des Endergebnisses für alle 900 Eingabewinkel-Tests (00.1 ~ 90.0) aus?

Ich war in der Lage, das Tier bei jeder Berechnung innerhalb von 32 Bit (4 Bytes) zu halten, und endete mit der Magie, innerhalb von 23 Bit des Ergebnisses eine Genauigkeit zu erzielen. Bei der Überprüfung der gesamten 3 Bytes des Ergebnisses beträgt der Fehler ± 1 LSB (ausstehend).

Der Benutzer kann ein, zwei oder drei Bytes aus dem Ergebnis für seine eigenen Genauigkeitsanforderungen abrufen. Wenn nur ein Byte ausreicht, würde ich natürlich empfehlen, eine einzelne 256-Byte-Sin-Tabelle zu verwenden und die AVR-Anweisung 'LPM' zu verwenden, um sie abzurufen.

Sobald die Excel-Sequenz reibungslos und ordentlich lief, dauerte die endgültige Übersetzung von Excel zu AVR weniger als 2 Stunden. Wie üblich sollten Sie zuerst mehr überlegen und später weniger arbeiten.

Zu dieser Zeit war ich in der Lage, noch mehr zu quetschen und die Verwendung von Registern zu reduzieren. Der tatsächliche (nicht endgültige) Code verwendet ungefähr 205 Befehle (~ 410 Bytes) und führt eine sin (x) -Berechnung im Durchschnitt von 212us bei einem Takt von 16 MHz durch. Bei dieser Geschwindigkeit können 4700+ sin (x) pro Sekunde berechnet werden. Nicht wichtig, aber es kann eine präzise Sinuswelle bis zu 4700 Hz mit 23 Bit Genauigkeit und Auflösung ohne Nachschlagetabellen ausführen.

Der Basisalgorithmus basiert auf der Taylor-Reihe für sin (x), wurde jedoch stark modifiziert, um meine Absichten hinsichtlich des AVR-Mikrocontrollers und der Präzision zu erfüllen.

Selbst wenn die Verwendung einer 2700-Byte-Tabelle (900 Einträge * 3 Byte) schnell attraktiv wäre, was ist der Spaß oder die Lernerfahrung dabei? Natürlich wurde auch der CORDIC-Ansatz in Betracht gezogen, vielleicht geht es hier darum, Taylor in den AVR-Kern zu drücken und Wasser aus einem trockenen Gestein zu entnehmen.

Ich frage mich, ob Arduino "sin (78.9 °)" Processing (C ++) mit 23 Bit Genauigkeit in weniger als 212us und dem erforderlichen Code kleiner als 205 Anweisungen ausführen kann. Kann sein, wenn C ++ CORDIC verwendet. Arduino-Skizzen können Assembly-Code importieren.

Es macht keinen Sinn, den Code hier zu posten. Später werde ich diesen Beitrag bearbeiten, um einen Weblink dazu aufzunehmen, möglicherweise in meinem Blog unter dieser URL . Der Blog ist hauptsächlich in Portugiesisch.

Dieses Hobby-No-Money-Unternehmen war interessant und hat die Grenzen der AVR-Engine von fast 16MIPS bei 16MHz ohne Divisionsanweisung und Multiplikation nur in 8x8 Bit überschritten. Es erlaubt die Berechnung von sin (x), cos (x) [= sin (900-x)] und tan (x) [= sin (x) / sin (900-x)].

Vor allem half dies, mein 63 Jahre altes Gehirn poliert und geölt zu halten. Wenn Teenager sagen, dass die 'alten Leute' nichts über Technologie wissen, antworte ich: "Überlegen Sie noch einmal, wer hat Ihrer Meinung nach die Grundlagen für alles geschaffen, was Sie heute genießen?".

Prost

Wagner Lip
quelle
Nett! Einige Bemerkungen: 1. Die sin()Standardfunktion hat etwa die gleiche Genauigkeit wie bei Ihnen und ist doppelt so schnell. Es basiert auch auf einem Polynom. 2. Wenn ein beliebiger Winkel auf das nächste Vielfache von 0,1 ° gerundet werden muss, kann dies zu einem Rundungsfehler von bis zu 8,7e-4 führen, was den Vorteil der 23-Bit-Genauigkeit irgendwie zunichte macht. 3. Würde es Ihnen etwas ausmachen, Ihr Polynom zu teilen?
Edgar Bonet
1

Wie bereits erwähnt, sind Nachschlagetabellen der richtige Weg, wenn Sie Geschwindigkeit wünschen. Ich habe kürzlich die Berechnung von Triggerfunktionen auf einem ATtiny85 für die Verwendung schneller Vektormittelwerte (in meinem Fall Wind) untersucht. Es gibt immer Kompromisse ... für mich brauchte ich nur eine Winkelauflösung von 1 Grad, daher war eine Nachschlagetabelle mit 360 Ints (Skalierung von -32767 bis 32767, nur Arbeiten mit Ints) der beste Weg. Das Abrufen des Sinus ist nur eine Frage der Angabe eines Index 0-359 ... also sehr schnell! Einige Zahlen aus meinen Tests:

FLASH-Suchzeit (us): 0,99 (mit PROGMEM gespeicherte Tabelle)

RAM-Suchzeit (us): 0,69 (Tabelle im RAM)

Lib Zeit (us): 122.31 (Verwenden von Arduino Lib)

Beachten Sie, dass dies jeweils Durchschnittswerte für eine 360-Punkte-Stichprobe sind. Die Tests wurden an einem Nano durchgeführt.

acicuc
quelle