1
L’ALGORITHME CORDIC
(Christophe.Devalland@ac-rouen.fr)
Utiliser sa calculatrice pour déterminer la valeur d’un cosinus, d’un logarithme ou d’une
racine carrée est un geste devenu tellement banal que plus personne ne se demande pourquoi et
comment cela marche. Mais, pour reprendre une formule bien connue, a-t-on vraiment besoin de
soulever le capot de sa voiture et de comprendre le fonctionnement du moteur pour s’en servir ?
Evidemment non. Pourtant, un jour en classe de première, un élève de ma femme un peu curieux
a été fier d’expliquer à ses camarades comment on pouvait extraire une racine carrée à la main. A
cette occasion, il s’est ensuite demandé si la calculatrice utilisait la même méthode pour calculer
une racine carrée. Nous nous sommes également posé cette question sans pouvoir y répondre. On
pourrait même aller plus loin en se demandant comment la calculatrice peut donner la valeur
d’un sinus ou d’un logarithme avec autant de précision.
Quand il s’agit d’opérations simples telles que l’addition ou la multiplication, on peut
assez bien imaginer comment elle procède parce que nous savons faire ces opérations à la main.
Mais pour les autres fonctions, comment fait-elle réellement ? Utilise-t-elle des développements
limités, des approximations de fonctions, ou d’autres mécanismes plus complexes ? C’est en
fouillant à droite et à gauche que j’ai trouvé quelques réponses qui m’ont servies de base pour cet
article. Je me suis par ailleurs amusé à programmer certains algorithmes sur ma calculatrice
pour vérifier que, malgré leur simplicité, ils donnent de bons résultats.
Un peu d’histoire
A la fin des années 50, les calculateurs électroniques sont en plein essor. Les domaines où
ils interviennent sont de plus en plus variés et on les trouve par exemple dans les avions où ils
servent d’assistants à la navigation aérienne. De ce fait, les besoins de calculs en temps réel se
font de plus en plus sentir, notamment pour les calculs trigonométriques. Ainsi, en 1959, Jack E.
Volder met au point un algorithme qui permet d’approximer des fonctions trigonométriques à
partir d’opérations élémentaires (additions, soustractions et multiplications). Cet algorithme
appelé « algorithme CORDIC » (pour Coordinate Rotation DIgital Computer) repose, comme son
nom l’indique, sur le calcul des coordonnées de vecteurs auxquels on applique une rotation bien
choisie. Très vite, grâce à sa mise en œuvre matérielle très simple (l’ingéniosité de l’algorithme
permet en effet un câblage électronique extrêmement simple), l’algorithme CORDIC est repris
dans des domaines très diverses tels que : le traitement de signaux radars, les coprocesseurs
mathématiques (intel i8087 par exemple) ou les calculatrices scientifiques (toutes marques
confondues). Un autre avantage non négligeable de cet algorithme est qu’il permet d’obtenir une
précision déterminée à l’avance en effectuant un nombre d’itération donné. Mais pour être certain
du résultat, il faut restreindre l’intervalle d’utilisation au domaine de convergence de
l’algorithme, comme on le verra plus bas (il existe toutefois des techniques permettant de
contourner cette limitation).
Première approche
J’ai repris ici un article de Yves Suprin paru dans le bulletin n°10 de novembre 1996 de la
régionale de Haute−Normandie. Il s’agit en fait d’un devoir à la maison proposé en classe de 1
ère
S dont l’objectif est de permettre le calcul d’une valeur approchée du sinus d’un angle a
appartenant à l’intervalle [0 ; π/2[ en s’inspirant de l’algorithme CORDIC.
L’idée est la suivante : a peut se décomposer en une somme a
1
+a
2
+a
3
+...+a
n
. Les angles a
i
étant
de plus en plus petits, et suffisamment, pour assurer la convergence ; un angle a
i
pouvant être
utilisé plusieurs fois dans cette décomposition. On converge alors vers l’angle a de la
façon suivante :