Différentes façons (et les plus rapides) de calculer les sinus (et cosinus) dans Arduino

9

J'utilise une carte Arduino Uno pour calculer les angles de mon système (bras robotique). Les angles sont en fait des valeurs de 10 bits (0 à 1023) de l'ADC, en utilisant toute la gamme de l'ADC. Je ne vais opérer que dans le 1er quadrant (0 à 90 degrés), où les sinus et les cosinus sont positifs, donc il n'y a pas de problème avec les nombres négatifs. Mes doutes peuvent s'exprimer en 3 questions:

  1. Quelles sont les différentes façons de calculer ces fonctions trigonométriques sur Arduino?

  2. Quel est le moyen le plus rapide de faire de même?

  3. Il y a les fonctions sin () et cos () dans l'IDE Arduino, mais comment l'Arduino les calcule-t-il réellement (car utilise-t-il des tables de recherche ou des approximations, etc.)? Ils semblent être une solution évidente, mais j'aimerais connaître leur mise en œuvre réelle avant de les essayer.

PS: Je suis ouvert au codage standard sur l'IDE Arduino et au codage d'assemblage, ainsi qu'à toute autre option non mentionnée. De plus, je n'ai aucun problème avec les erreurs et les approximations, qui sont inévitables pour un système numérique; cependant, si possible, il serait bon de mentionner l'étendue des erreurs possibles

Transistor Overlord
la source
Seriez-vous d'accord avec des valeurs approximatives?
sa_leinad
Oui en fait, mais j'aimerais connaître l'étendue de l'erreur des différentes méthodes. Ce n'est pas un produit de précision mais un de mes projets secondaires. En fait, les approximations sont inévitables pour presque tous les systèmes numériques (sinon tous) mettant en œuvre une fonction mathématique
Transistor Overlord
Je suppose que vous voulez travailler en degrés. Allez-vous vouloir saisir des nombres entiers ou décimaux pour l'angle?
sa_leinad
Degrés oui. Je pense qu'il serait plus facile d'écrire du code et de tester si nous utilisons des entiers, donc j'irais avec ça. Je mettrai des informations plus claires sur les modifications
Transistor Overlord
1
Pour seulement 90 degrés (entiers), une table de recherche à 90 entrées serait la plus rapide et la plus efficace. En fait, pour les 360 degrés complets, vous pouvez utiliser une table de recherche à 90 entrées. Il suffit de le lire à l'envers pour 90-179 et de l'inverser pour 180-269. Faites les deux pour 270-359.
Majenko

Réponses:

11

Les deux méthodes de base sont le calcul mathématique (avec polynômes) et les tables de recherche.

La bibliothèque mathématique d'Arduino (libm, partie de avr-libc) utilise la première. Il est optimisé pour l'AVR en ce qu'il est écrit avec un langage d'assemblage à 100%, et en tant que tel, il est presque impossible de suivre ce qu'il fait (il n'y a également aucun commentaire). Soyez assuré que ce sera le cerveau d'implémentation à flotteur pur le plus optimisé, bien supérieur au nôtre.

Cependant, la clé est flottante . Tout sur l'Arduino impliquant une virgule flottante va être lourd par rapport à un entier pur, et comme vous ne demandez que des entiers entre 0 et 90 degrés, une simple table de recherche est de loin la méthode la plus simple et la plus efficace.

Un tableau de 91 valeurs vous donnera tout de 0 à 90 inclus. Cependant, si vous créez une table de valeurs à virgule flottante entre 0,0 et 1,0, vous avez toujours l'inefficacité de travailler avec des flottants (accordé moins inefficace que le calcul sinavec des flottants), donc stocker une valeur à virgule fixe à la place serait beaucoup plus efficace.

Cela peut être aussi simple que de stocker la valeur multipliée par 1000, vous avez donc entre 0 et 1000 au lieu entre 0,0 et 1,0 (par exemple, sin (30) serait stocké comme 500 au lieu de 0,5). Plus efficace serait de stocker les valeurs comme, par exemple, une valeur Q16 où chaque valeur (bit) représente 1 / 65536e de 1,0. Ces valeurs Q16 (et les Q15, Q1.15, etc.) associées sont plus efficaces avec lesquelles travailler, car vous avez des puissances de deux avec lesquelles les ordinateurs aiment travailler au lieu de puissances de dix avec lesquelles ils détestent travailler.

N'oubliez pas non plus que la sin()fonction attend des radians, vous devez donc d'abord convertir vos degrés entiers en une valeur en radians à virgule flottante, ce qui rend l'utilisation sin()encore plus inefficace par rapport à une table de recherche qui peut fonctionner directement avec la valeur des degrés entiers.

Une combinaison des deux scénarios est cependant possible. L'interpolation linéaire vous permettra d'obtenir une approximation d'un angle à virgule flottante entre deux entiers. C'est aussi simple que de déterminer la distance entre deux points dans la table de recherche et de créer une moyenne pondérée basée sur cette distance des deux valeurs. Par exemple, si vous êtes à 23,6 degrés, vous prenez (sintable[23] * (1-0.6)) + (sintable[24] * 0.6). Fondamentalement, votre onde sinusoïdale devient une série de points discrets reliés entre eux par des lignes droites. Vous échangez la précision contre la vitesse.

Majenko
la source
J'ai écrit une bibliothèque il y a quelque temps qui utilisait un polynôme de Taylor pour sin / cos qui était plus rapide que la bibliothèque. Étant donné, j'utilisais des radians à virgule flottante comme entrée pour les deux.
tuskiomi
8

Il y a de bonnes réponses ici, mais je voulais ajouter une méthode qui n'a pas encore été mentionnée, une très bien adaptée au calcul des fonctions trigonométriques sur les systèmes embarqués, et c'est la technique CORDIC Entrée Wiki ici Elle peut calculer des fonctions trigonométriques en utilisant uniquement des décalages et ajoute et une petite table de consultation.

Voici un exemple grossier en C. En effet, il implémente la fonction atan2 () des bibliothèques C en utilisant CORDIC (c'est-à-dire trouver un angle avec deux composantes orthogonales). Il utilise des virgules flottantes, mais peut être adapté pour une utilisation avec l'arithmétique à virgule fixe.

/*
 * 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;
}

Mais essayez d'abord les fonctions natives d'Arduino trig - elles pourraient être assez rapides de toute façon.

Halzephron
la source
1
J'ai adopté une approche similaire dans le passé, sur stm8. cela prend deux étapes: 1) calculer le péché (x) et cos (x) à partir du péché (2x), puis 2) calculer le péché (x +/- x / 2) à partir du péché (x), le péché (x / 2) , cos (x) et cos (x / 2) -> grâce à l'itération, vous pouvez approcher votre cible. dans mon cas, j'ai commencé avec 45 degrés (0,707) et j'ai réussi à atteindre la cible. il est considérablement plus lent que la fonction standard IAR sin ().
dannyf
7

J'ai joué un peu avec le calcul des sinus et cosinus sur l'Arduino en utilisant des approximations polynomiales à virgule fixe. Voici mes mesures du temps d'exécution moyen et de l'erreur la plus défavorable, par rapport à la norme cos()et sin()à 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

Il est basé sur un polynôme du 6e degré calculé avec seulement 4 multiplications. Les multiplications elles-mêmes sont effectuées en assemblage, car j'ai trouvé que gcc les implémentait de manière inefficace. Les angles sont exprimés uint16_ten unités de 1/65536 de révolution, ce qui fait que l'arithmétique des angles fonctionne naturellement modulo d'une révolution.

Si vous pensez que cela peut convenir à votre facture, voici le code: trigonométrie à virgule fixe . Désolé, je n'ai toujours pas traduit cette page, qui est en français, mais vous pouvez comprendre les équations, et le code (noms de variables, commentaires ...) est en anglais.


Edit : Puisque le serveur semble avoir disparu, voici quelques informations sur les approximations que j'ai trouvées.

Je voulais écrire des angles en virgule fixe binaire, en unités de quadrants (ou, de manière équivalente, en virages). Et je voulais également utiliser un polynôme pair, car ceux-ci sont plus efficaces à calculer que les polynômes arbitraires. En d'autres termes, je voulais un polynôme P () tel que

cos (π / 2 x) ≈ P (x 2 ) pour x ∈ [0,1]

J'ai également demandé que l'approximation soit exacte aux deux extrémités de l'intervalle, pour garantir que cos (0) = 1 et cos (π / 2) = 0. Ces contraintes ont conduit à la forme

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

où Q () est un polynôme arbitraire.

Ensuite, j'ai cherché la meilleure solution en fonction du degré de Q () et j'ai trouvé ceci:

        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

Le choix parmi les solutions ci-dessus est un compromis vitesse / précision. La troisième solution donne plus de précision que ce qui est réalisable avec 16 bits, et c'est celle que j'ai choisie pour l'implémentation 16 bits.

Edgar Bonet
la source
2
C'est incroyable, @Edgar.
SDsolar
Qu'avez-vous fait pour trouver le polynôme?
TLW
@TLW: Je lui ai demandé d'avoir de "belles" propriétés (par exemple cos (0) = 1), qui étaient limitées à la forme (1 − x²) (1 + x²Q (x²)), où Q (u) est un arbitraire polynôme (c'est expliqué dans la page). J'ai pris un Q du premier degré (seulement 2 coefficients), trouvé les coefficients approximatifs par ajustement, puis réglé manuellement l'optimisation par essais et erreurs.
Edgar Bonet
@EdgarBonet - intéressant. Notez que cette page ne se charge pas pour moi, bien que la mise en cache fonctionne. Pourriez-vous s'il vous plaît ajouter le polynôme utilisé à cette réponse?
TLW
@TLW: a ajouté cela à la réponse.
Edgar Bonet
4

Vous pouvez créer quelques fonctions qui utilisent l'approximation linéaire pour déterminer le sin () et le cos () d'un angle particulier.

Je pense à quelque chose comme ceci: Pour chacun, j'ai divisé la représentation graphique de sin () et cos () en 3 sections et j'ai fait une approximation linéaire de cette section.
approximation linéaire

Idéalement, votre fonction vérifierait d'abord que la plage de l'ange est comprise entre 0 et 90.
Ensuite, elle utiliserait une ifelsedéclaration pour déterminer à laquelle des 3 sections il appartient, puis effectuerait le calcul linéaire correspondant (c.-à-d. output = mX + c)

sa_leinad
la source
Cela n'implique-t-il pas une multiplication en virgule flottante?
Transistor Overlord
1
Pas nécessairement. Vous pouvez l'avoir pour que la sortie soit mise à l'échelle entre 0-100 au lieu de 0-1. De cette façon, vous traitez avec des entiers, pas avec des virgules flottantes. Remarque: 100 était arbitraire. Il n'y a aucune raison que vous ne puissiez pas mettre à l'échelle la sortie entre 0-128 ou 0-512 ou 0-1000 ou 0-1024. En utilisant un multiple de 2, il vous suffit de faire les bons décalages pour réduire le résultat.
sa_leinad
Assez intelligent, @sa_leinad. Upvote. Je me souviens de l'avoir fait en travaillant avec la polarisation des transistors.
SDsolar
4

J'ai cherché d'autres personnes qui avaient approché cos () et sin () et je suis tombé sur cette réponse:

Réponse de dtb à "Fast Sin / Cos utilisant un tableau de traduction pré-calculé"

Fondamentalement, il a calculé que la fonction math.sin () de la bibliothèque mathématique était plus rapide que l'utilisation d'une table de recherche de valeurs. Mais d'après ce que je peux dire, cela a été calculé sur un PC.

Arduino a une bibliothèque mathématique incluse qui peut calculer sin () et cos ().

sa_leinad
la source
1
Les PC sont équipés de FPU qui le rendent rapide. Arduino ne le fait pas, ce qui le ralentit.
Majenko
La réponse est également pour C # qui fait des choses comme la vérification des limites du tableau.
Michael
3

Une table de recherche sera le moyen le plus rapide de trouver des sinus. Et si vous êtes à l'aise avec les nombres à virgule fixe (entiers dont le point binaire est ailleurs qu'à droite du bit-0), vos calculs ultérieurs avec les sinus seront également beaucoup plus rapides. Ce tableau peut alors être un tableau de mots, éventuellement en Flash pour économiser de l'espace RAM. Notez que dans vos calculs, vous devrez peut-être utiliser des longs pour de grands résultats intermédiaires.

JRobert
la source
1

généralement, table de correspondance> approximation -> calcul. ram> flash. entier> virgule fixe> virgule flottante. pré-calclation> calcul en temps réel. mise en miroir (sinus à cosinus ou cosinus à sinus) par rapport au calcul / recherche réel ...

chacun a ses avantages et ses inconvénients.

vous pouvez faire toutes sortes de combinaisons pour voir celle qui convient le mieux à votre application.

edit: j'ai fait une vérification rapide. en utilisant une sortie entière de 8 bits, le calcul de 1024 valeurs de sinistre avec la table de recherche prend 0,6 ms et 133 ms avec des flottants, ou 200 fois plus lentement.

dannyf
la source
1

J'avais une question similaire à OP. Je voulais créer une table LUT pour calculer le premier quadrant de la fonction sinus en tant qu'entiers 16 bits non signés à partir de 0x8000 à 0xffff. Et j'ai fini par écrire ceci pour le plaisir et le profit. Remarque: Cela fonctionnerait plus efficacement si j'utilisais des instructions «if». De plus, ce n'est pas très précis, mais serait suffisamment précis pour une onde sinusoïdale dans un synthétiseur de son

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)
}

Maintenant, pour récupérer les valeurs, utilisez cette fonction qui accepte une valeur de 0x0000 à 0x0800 et renvoie la valeur appropriée de la LUT

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

Rappelez-vous, ce n'est pas l'approche la plus efficace pour cette tâche, je n'arrivais pas à comprendre comment faire des séries Taylor pour donner des résultats dans la plage appropriée.

Arnadath
la source
Votre code ne compile pas: Imm_UI_Aest déclaré deux fois, a ;et certaines déclarations de variables sont manquantes et uLut_0doivent être globales. Avec les correctifs nécessaires, lu_sin()est rapide (entre 27 et 42 cycles CPU) mais très imprécis (erreur maximale ≈ 5.04e-2). Je ne peux pas comprendre ce que sont ces «polynômes Arnadathiens»: cela semble un calcul assez lourd, mais le résultat est presque aussi mauvais qu'une simple approximation quadratique. La méthode a également un coût de mémoire énorme. Il serait préférable de calculer la table sur votre PC et de la placer dans le code source sous forme de PROGMEMtableau.
Edgar Bonet du
1

Juste pour le plaisir, et pour prouver que cela peut être fait, j'ai terminé une routine d'assemblage AVR pour calculer les résultats sin (x) en 24 bits (3 octets) avec un bit d'erreur. L'angle d'entrée est en degrés avec un chiffre décimal, de 000 à 900 (0 ~ 90,0) pour le premier quadrant uniquement. Il utilise moins de 210 instructions AVR et fonctionne en moyenne sur 212 microsecondes, variant de 211us (angle = 001) à 213us (angle = 899).

Il a fallu plusieurs jours pour tout faire, plus de 10 jours (heures gratuites) en pensant simplement au meilleur algorithme pour le calcul, compte tenu du microcontrôleur AVR, sans virgule flottante, éliminant toutes les divisions possibles. Ce qui a pris plus de temps, c'était de faire les bonnes valeurs de passage pour les entiers, pour avoir une bonne précision, il faut passer des valeurs de 1e-8 aux nombres entiers binaires 2 ^ 28 ou plus. Une fois que toutes les erreurs responsables de la précision et de l'arrondi ont été trouvées, ont augmenté leur résolution de calcul de 2 ^ 8 ou 2 ^ 16 supplémentaires, les meilleurs résultats ont été obtenus. J'ai d'abord simulé tous les calculs sur Excel en prenant soin d'avoir toutes les valeurs comme Int (x) ou Round (x, 0) pour représenter exactement le traitement de base AVR.

Par exemple, dans l'algorithme, l'angle doit être en radians, l'entrée est en degrés pour faciliter la tâche de l'utilisateur. Pour convertir des degrés en radians, la formule triviale est rad = degrés * PI / 180, cela semble agréable et facile, mais ce n'est pas le cas, PI est un nombre infini - si l'utilisation de quelques chiffres crée des erreurs en sortie, la division par 180 nécessite Manipulation de bits AVR car il n'a pas d'instruction de division, et plus que cela, le résultat nécessiterait une virgule flottante car implique des nombres bien inférieurs à l'entier 1. Par exemple, Radian de 1 ° (degré) est 0,017453293. Puisque PI et 180 sont des constantes, pourquoi ne pas inverser cette chose pour une simple multiplication? PI / 180 = 0,017453293, multipliez-le par 2 ^ 32 et il en résulte une constante 74961320 (0x0477D1A8), multipliez ce nombre par votre angle en degrés, disons 900 pour 90 ° et décalons-le de 4 bits vers la droite (÷ 16) pour obtenir 4216574250 (0xFB53D12A), c'est-à-dire les radians du 90 ° avec une expansion de 2 ^ 28, ajustés en 4 octets, sans une seule division (sauf le 4 décalage de bit à droite). D'une certaine manière, l'erreur incluse dans une telle astuce est inférieure à 2 ^ -27.

Donc, tous les autres calculs doivent se rappeler qu'il est 2 ^ 28 plus élevé et pris en charge. Vous devez diviser les résultats en déplacement par 16, 256 ou même 65536 juste pour éviter qu'il n'utilise des octets de faim croissants inutiles qui n'aideraient pas la résolution. Ce fut un travail minutieux, il suffit de trouver la quantité minimale de bits dans chaque résultat de calcul, en maintenant la précision des résultats autour de 24 bits. Chacun des plusieurs calculs a été effectué en essai / erreur avec un nombre de bits supérieur ou inférieur dans le flux Excel, en regardant la quantité globale de bits d'erreur au résultat dans un graphique montrant 0-90 ° avec une macro exécutant le code 900 fois, une fois par dixième de degré. Cette approche Excel "visuelle" était un outil que j'ai créé, qui m'a beaucoup aidé à trouver la meilleure solution pour chaque partie du code.

Par exemple, en arrondissant ce résultat de calcul particulier 13248737.51 à 13248738 ou tout simplement perdre les décimales "0,51", dans quelle mesure cela affectera-t-il la précision du résultat final pour tous les 900 angles d'entrée (00,1 ~ 90,0) tests?

J'ai pu garder l'animal contenu dans 32 bits (4 octets) à chaque calcul, et je me suis retrouvé avec la magie pour obtenir une précision dans les 23 bits du résultat. Lors de la vérification des 3 octets du résultat, l'erreur est de ± 1 LSB, en suspens.

L'utilisateur peut saisir un, deux ou trois octets du résultat pour ses propres exigences de précision. Bien sûr, si un seul octet est suffisant, je recommanderais d'utiliser une seule table sin de 256 octets et d'utiliser l'instruction AVR 'LPM' pour la saisir.

Une fois que la séquence Excel a été fluide et nette, la traduction finale d'Excel vers l'assemblage AVR a pris moins de 2 heures, comme d'habitude, vous devriez penser plus en premier, travailler moins plus tard.

À ce moment-là, j'ai pu en serrer encore plus et réduire l'utilisation des registres. Le code réel (non définitif) utilise environ 205 instructions (~ 410 octets), exécute un calcul sin (x) en moyenne de 212us, horloge à 16 MHz. À cette vitesse, il peut calculer 4700+ sin (x) par seconde. Ce n'est pas important, mais il peut exécuter une sinusoïde précise jusqu'à 4700 Hz avec 23 bits de précision et de résolution, sans aucune table de recherche.

L'algorithme de base est basé sur la série Taylor pour sin (x), mais a beaucoup changé pour s'adapter à mes intentions avec le microcontrôleur AVR et la précision à l'esprit.

Même que l'utilisation d'une table de 2700 octets (900 entrées * 3 octets) serait une vitesse intéressante, quelle est l'expérience amusante ou d'apprentissage à ce sujet? Bien sûr, l'approche CORDIC a également été envisagée, peut-être plus tard, le point ici est de presser Taylor dans le cœur de l'AVR et de prendre l'eau d'une roche sèche.

Je me demande si Arduino "sin (78.9 °)" peut exécuter Processing (C ++) avec 23 bits de précision en moins de 212us et le code nécessaire plus petit que 205 instructions. Peut-être si C ++ utilise CORDIC. Les croquis Arduino peuvent importer du code d'assemblage.

Cela n'a aucun sens de publier le code ici, plus tard, je modifierai ce message pour y inclure un lien Web, peut-être sur mon blog à cette URL . Le blog est principalement en portugais.

Cette entreprise sans passe-temps était intéressante, repoussant les limites du moteur AVR de près de 16MIPS à 16MHz, sans instruction de division, multiplication uniquement en 8x8 bits. Il permet de calculer sin (x), cos (x) [= sin (900-x)] et tan (x) [= sin (x) / sin (900-x)].

Surtout, cela a aidé à garder mon cerveau de 63 ans poli et huilé. Quand les adolescents disent que les «vieux» ne savent rien de la technologie, je réponds «détrompez-vous, qui pensez-vous a créé les bases de tout ce que vous aimez aujourd'hui?».

À votre santé

Wagner Lip
la source
Agréable! Quelques remarques: 1. La sin()fonction standard a à peu près la même précision que la vôtre et est deux fois plus rapide. Il est également basé sur un polynôme. 2. Si un angle arbitraire doit être arrondi au multiple de 0,1 ° le plus proche, cela peut entraîner une erreur d'arrondi aussi élevée que 8,7e-4, ce qui annule en quelque sorte le bénéfice de la précision de 23 bits. 3. Pourriez-vous partager votre polynôme?
Edgar Bonet
1

Comme d'autres l'ont mentionné, les tables de recherche sont la voie à suivre si vous voulez de la vitesse. J'ai récemment étudié le calcul des fonctions trigonométriques sur un ATtiny85 pour l'utilisation de moyennes vectorielles rapides (vent dans mon cas). Il y a toujours des compromis ... pour moi, je n'avais besoin que d'une résolution angulaire de 1 degré, donc une table de recherche de 360 ​​int (mise à l'échelle de -32767 à 32767, ne fonctionnant qu'avec des int) était la meilleure solution. Récupérer le sinus est juste une question de fournir un index 0-359 ... donc très vite! Quelques chiffres de mes tests:

Temps de recherche FLASH (us): 0.99 (table stockée à l'aide de PROGMEM)

Temps de recherche RAM (us): 0,69 (table en RAM)

Lib time (us): 122.31 (en utilisant Arduino Lib)

Notez que ce sont des moyennes sur un échantillon de 360 ​​points pour chacun. Les tests ont été effectués sur un nano.

acicuc
la source