Pourquoi l’algorithme CORDIC occupe gratuitement une place dans mon cœur
Éviter les nombres à virgule flottante en utilisant le point fixe
- Utiliser le point fixe plutôt que la virgule flottante permet de représenter des nombres réels
- Utiliser un entier 32 bits en séparant les 16 bits de poids fort pour la partie entière et les 16 bits de poids faible pour la partie fractionnaire
- Cela permet de représenter environ de -32768.99997 à 32767.99997
- Le programmeur peut ajuster la précision en choisissant la position du point fixe
- Pour convertir un float en point fixe, il faut multiplier par 2^16 puis caster en
int32_t
- Pour convertir un point fixe en float, il faut diviser par 2^16
- L’addition et la soustraction fonctionnent telles quelles, tandis que la multiplication et la division nécessitent d’ajuster le facteur d’échelle
Vue d’ensemble de l’algorithme CORDIC
- CORDIC est l’acronyme de "Co-ordinate Rotation Digital Computer", développé au milieu des années 1950
- Il s’agit d’une méthode qui calcule les valeurs du sinus et du cosinus en faisant tourner progressivement un vecteur sur le cercle unité par petits angles
- Comme dans une recherche binaire, on se rapproche de l’angle cible en avançant d’abord par grands angles, puis en réduisant de moitié l’angle de rotation dans le sens horaire ou antihoraire jusqu’à convergence
- L’angle maximal de rotation est fixé à 90 degrés (
π/2 radians), et 16 itérations permettent de converger vers l’angle cible
- Une fois convergé, la valeur de
y du vecteur vaut approximativement sin(a) et celle de x vaut approximativement cos(a)
Simplifier la matrice pour n’utiliser que des multiplications par des constantes
- La matrice de rotation contient des fonctions sinus, cosinus et tangente, ce qui rend le calcul complexe
- Comme la fonction tangente correspond à une rotation d’angle fixe, ses valeurs peuvent être précalculées et stockées dans une table (environ 64 octets)
- Le terme en cosinus apparaît à chaque itération, mais comme sa valeur de convergence est une constante (environ 0.6366), il suffit de le multiplier une seule fois à la fin
Utiliser uniquement des opérations Shift et Add
- Les angles utilisés dans la fonction tangente sont choisis via la fonction arctangente sous la forme de valeurs
2^-i
- Cela permet de remplacer les multiplications par des décalages de bits
- La valeur de convergence du terme en cosinus est recalculée et devient environ 0.60725, puis définie comme valeur initiale de
x du vecteur
- Chaque itération de l’algorithme CORDIC se simplifie alors comme suit
- si
z est supérieur ou égal à 0, rotation dans le sens antihoraire (soustraire y>>i à x, ajouter x>>i à y)
- si
z est inférieur à 0, rotation dans le sens horaire (ajouter y>>i à x, soustraire x>>i de y)
- mise à jour de
z en soustrayant ou ajoutant la valeur d’angle issue de la table
- On peut ainsi calculer des fonctions trigonométriques uniquement à l’aide de multiplications par des constantes, de décalages de bits et d’additions
L’avis de GN⁺
- CORDIC semble être un algorithme particulièrement utile dans des environnements aux ressources matérielles limitées, comme les systèmes embarqués ou les FPGA. C’est notamment une approche à envisager en l’absence de support pour les opérations en virgule flottante.
- L’idée de choisir stratégiquement les angles de la fonction tangente pour remplacer les multiplications par des décalages de bits est impressionnante. C’est un bon exemple de combinaison entre intuition mathématique et compréhension de l’architecture informatique.
- Il est également intéressant de noter qu’il peut servir non seulement au calcul des fonctions trigonométriques, mais aussi à celui des logarithmes, exponentielles, racines carrées et d’autres fonctions. L’algorithme apparenté BKM mérite aussi qu’on s’y intéresse.
- Il faut toutefois garder à l’esprit que le matériel moderne intègre souvent déjà une FPU et que l’utilisation du point fixe peut entraîner une perte de précision, ce qui demande de la prudence lors de l’adoption de cette approche.
- Dans un système qui doit effectuer un grand nombre de calculs similaires, on peut aussi envisager une conception matérielle dédiée à CORDIC.
1 commentaires
Avis Hacker News
L’algorithme CORDIC peut être utilisé non seulement avec les FPGA, mais aussi dans le développement de jeux ou les simulations physiques distribuées. Les calculs en virgule flottante garantissent difficilement un comportement déterministe entre plateformes, donc implémenter un moteur physique en virgule fixe et les fonctions trigonométriques avec CORDIC peut constituer une solution.
CORDIC peut servir non seulement pour le sinus et le cosinus, mais aussi pour les logarithmes, exponentielles, racines carrées, normes de vecteurs, conversions entre coordonnées polaires et cartésiennes, rotations de vecteurs, etc. Avec des quaternions, il semble possible d’effectuer des opérations basées sur CORDIC de façon plus efficace et plus précise.
Partage d’une expérience personnelle : dans un cours de pré-calcul au lycée, l’auteur a appris comment les fonctions trigonométriques étaient implémentées dans une calculatrice, puis a découvert qu’il ne s’agissait pas d’une série de Taylor mais en réalité de CORDIC, avant d’en faire lui-même une implémentation en TI Basic.
En 2023, même des MCU bon marché comme le STM32G4 intègrent une FPU, ce qui permet d’utiliser librement la virgule flottante au lieu de la virgule fixe. Mais le G4 dispose aussi d’un périphérique CORDIC implémenté en matériel dédié, apparemment pour éviter les pertes de précision en virgule flottante.
Il semble y avoir une erreur dans l’explication selon laquelle une rotation de 22,75° équivaut à une rotation de 45° suivie d’une rotation de -22,5°. Cela devrait probablement être 22,5°.
Le système d’octree de Meagher a été implémenté uniquement avec des opérations entières, sans multiplication ni division entières. Cela facilitait la création d’un matériel d’accélération graphique VLSI rapide et sur mesure pour représenter les octrees.
CORDIC peut être vu comme un concept proche de la suite de Farey pour les angles, ou du mediant, c’est-à-dire une somme naïve de fractions.
CORDIC a aussi été implémenté sur des calculatrices HP programmables vintage équipées d’un CPU 4 bits. Il est également possible d’y programmer une méthode d’approximation utilisant le développement de Taylor du sinus.
Si cet article vous a plu, cela vaut aussi la peine de lire le grand classique de Donald Knuth, "The Art of Computer Programming", qui explique des algorithmes mathématiques avec des exemples.
CORDIC est un algorithme qui a connu un grand succès autrefois dans le domaine du DSP.
C’est un excellent algorithme, qui semble utile pour exécuter des réseaux de neurones sur du matériel peu performant.