algorithme CORDIC

Une calculatrice doit parfois trouver un logarithme sans disposer d'une table infinie de résultats. Dans le modèle simplifié présenté ici, on utilise des facteurs positifs dont quelques logarithmes sont déjà connus : multiplier ces facteurs revient alors à additionner leurs logarithmes. Cette reconstruction n'est valable que si le choix des facteurs permet d'approcher l'entrée avec une erreur contrôlée ; elle n'est pas, à elle seule, une description générale de CORDIC.

Concrètement, la procédure part d'un produit courant, le compare au nombre visé, puis choisit parmi les facteurs disponibles celui qui réduit l'écart logarithmique. Après chaque choix, elle vérifie l'erreur restante : si celle-ci est inférieure à la précision fixée, elle s'arrête ; sinon, elle recommence. Ce geste décrit seulement la stratégie du modèle simplifié, sous l'hypothèse qu'elle atteint le seuil en un nombre fini d'étapes.

CORDIC, acronyme de COordinate Rotation for DIgital Computer, désigne un algorithme numérique mis au point en 1959 par l'Américain Volder. Dans le cadre décrit ici, il évalue le logarithme népérien d'un nombre réel positif à une précision choisie, en utilisant un nombre fini de valeurs de logarithmes supposées connues.

Dans le modèle multiplicatif simplifié retenu pour cette fiche, et non comme description générale de CORDIC, le calcul exploite la transformation d'un produit en somme. Pour deux nombres positifs nommés x et y, la relation est : $\ln (xy)=\ln (x)+\ln (y)\backslash ln(xy)=\backslash ln(x)+\backslash ln(y)$. Lorsqu'un jeu de facteurs et une stratégie garantissent que leur produit approche l'entrée avec une erreur logarithmique contrôlée, cette décomposition ramène son logarithme à une addition de valeurs disponibles. Le nombre d'opérations est fini seulement si la stratégie atteint le critère d'erreur fixé en un nombre fini d'étapes.

La source limite ce calcul aux entrées positives qui ne sont ni trop grandes ni trop petites. CORDIC appartient à la lignée des méthodes décrites par Briggs, co-inventeur des logarithmes avec Neper, et intervient dans les calculatrices pour évaluer efficacement des fonctions transcendantes.

Dans le modèle multiplicatif simplifié, soit un réel positif à traiter, dans la plage admise, et soit une précision fixée. On dispose de facteurs positifs dont les logarithmes sont connus. À chaque étape, on compare le produit courant à l'entrée, puis on sélectionne un facteur qui réduit l'erreur logarithmique résiduelle ; la multiplication de ce facteur correspond à l'addition de son logarithme. On répète ce choix jusqu'à ce que l'erreur résiduelle, ajoutée aux erreurs cumulées des logarithmes connus, ne dépasse pas la précision demandée. La somme obtenue donne alors l'approximation recherchée, sous l'hypothèse que cette stratégie atteint le critère en un nombre fini d'étapes.

L'entrée doit être un nombre réel strictement positif et appartenir à la plage de valeurs que la procédure accepte. La précision attendue doit être fixée avant le calcul. Dans le modèle multiplicatif simplifié de cette fiche, on suppose aussi disponibles des facteurs positifs dont les logarithmes sont connus, ainsi qu'une stratégie qui garantit, pour l'entrée considérée, d'atteindre en un nombre fini d'étapes la précision annoncée. Le critère d'arrêt doit borner à la fois l'écart logarithmique entre l'entrée et le produit obtenu et les erreurs cumulées des valeurs connues ; la seule finitude du jeu de facteurs ne suffit pas.

Une entrée nulle ou négative bloque ce calcul du logarithme népérien réel : la propriété utilisée exige ici des facteurs positifs. De même, un nombre trop grand ou trop petit sort du domaine annoncé par la source ; il faut alors employer une adaptation qui ramène d'abord l'entrée dans la plage admise, si cette adaptation est disponible.

On cherche une approximation de ln(1,8) avec deux valeurs supposées connues : ln(1,5) ≈ 0,405465 et ln(1,2) ≈ 0,182322. Cet exemple illustre le principe multiplicatif ; il ne détaille pas l'implémentation complète d'une calculatrice.

1. On décompose exactement le nombre : $\mathrm{1,8}=\mathrm{1,5}\times \mathrm{1,2}1\{,\}8=1\{,\}5\backslash times1\{,\}2$.

2. La multiplication devient une addition : $\ln (\mathrm{1,8})=\ln (\mathrm{1,5})+\ln (\mathrm{1,2})\backslash ln(1\{,\}8)=\backslash ln(1\{,\}5)+\backslash ln(1\{,\}2)$.

3. On additionne les valeurs disponibles : $\mathrm{0,405465}+\mathrm{0,182322}=\mathrm{0,587787}0\{,\}405465+0\{,\}182322=0\{,\}587787$. On obtient donc ln(1,8) ≈ 0,587787, arrondi à six décimales.

Le contrôle refaisable consiste à vérifier d'abord que 1,5 × 1,2 = 1,8, puis à refaire l'addition des deux approximations. La précision finale dépend de celle des valeurs connues.

Dans une calculatrice, une mise en œuvre de CORDIC évalue efficacement des fonctions transcendantes en exécutant un nombre d'étapes déterminé par sa garantie de convergence et la précision demandée. L'utilisateur choisit cette précision par l'intermédiaire de l'affichage ou du calcul demandé, puis la machine enchaîne les opérations prévues.

Pour savoir ce que fait la machine, on peut distinguer deux cas. Si le logarithme demandé figure déjà parmi les valeurs connues, une consultation directe suffit. Sinon, le modèle simplifié enchaîne les facteurs retenus et additionne leurs logarithmes jusqu'au critère d'arrêt. L'exemple de 1,8 permet de contrôler ce second cas lorsque la décomposition est exacte.

Avant tout calcul réel, le signe de l'entrée se vérifie : une valeur nulle ou négative appelle un autre cadre mathématique, pas cette procédure sur les réels positifs.

CORDIC et le logarithme népérien. Le logarithme est la fonction à évaluer ; CORDIC est une procédure de calcul. Pour une entrée comme 1,8, ln(1,8) désigne une valeur, tandis que l'algorithme décrit les opérations qui permettent de l'approcher.

Valeur exacte et valeur approchée. L'identité ln(xy) = ln(x) + ln(y) est exacte pour des réels positifs. En revanche, 0,587787 est ici une approximation de ln(1,8), car les logarithmes additionnés ont eux-mêmes été arrondis.

À zéro et sous zéro. Le logarithme népérien réel n'est pas défini pour une entrée inférieure ou égale à 0. Le symptôme est immédiat : aucune décomposition en facteurs réels positifs ne peut produire cette entrée. Il faut changer de domaine mathématique ou conclure que le calcul réel demandé n'existe pas.

Entrée hors plage. La source précise que les nombres ne doivent être ni trop grands ni trop petits, sans donner de seuil universel. Ce seuil dépend donc de la procédure mise en œuvre ; une entrée refusée doit être ramenée dans la plage admise par une adaptation explicitement prévue.

Précision mal interprétée. Fixer six décimales ne rend pas chaque résultat exact. Dans l'exemple, 0,587787 est obtenu à partir de deux valeurs arrondies ; il faut conserver le signe ≈ et contrôler la propagation des arrondis.

La fiche fonction transcendante situe la famille de fonctions que les calculatrices évaluent notamment à l'aide de procédures comme CORDIC.