L'algorithme CORDIC
ou comment les calculatrices calculent les fonctions trigonométriques ?

 

Contrairement à ce que beaucoup de personnes pensent, les calculatrices n'utilisent ni développement en série ni approximation polynômiale pour calculer un cosinus, un sinus ou une tangente.
Rappelons à ce sujet les développements en séries entières des fonctions cosinus et sinus :


Si on peut utiliser le polynôme comme approximation de sin x, on évitera cependant cette méthode. En effet, celle-ci utilise beaucoup trop de multiplications ce qui demande un temps machine trop important. On préfera donc l'algorithme suivant appelé algorithme CORDIC (COrdiante Rotation DIgital Computer) développé par J.E. Volder en 1959.

L'idée de cet algorithme consiste pour calculer tan q , à faire subir à un vecteur de coordonnées
(X ; Y) des rotations d'angles de plus en plus proche de 0 et dont la somme est égale à
q. Le quotient Y/X est alors une approximation de tan q.

Détaillons un peu :

Prenons 0 < q < p/2 et des qi tels que avec .
Si le point M0 a pour coordonnées (X0, Y0), le point M1, image de M0 par la rotation de centre O et d'angle
q0 , a pour coordonnées (X1, Y1) vérifiant :
X1 = X0 × cos
q0 - Y0 × sin q0 et
Y1 = X0 × sin
q0 + Y0 × cos q0

Ce que l'on peut écrire en terme de matrices :
est la matrice de rotation d'angle
q0 et de centre O.
On obtient de même en faisant subir au point M1 une rotation d'angle
q1 les coordonnées de M2 :

Pour passer de M0 à M2, il suffit alors de faire le produit de matrices

×, ce qui donne :

(*)


On continue alors à faire des rotations d'angles
qi pour passer de M2 à M3, M3 à M4, ..., pour au final arriver à Mn un point proche de M.

Mais où est tan q dans tout cela ?

Pour le trouver, on va choisir arbitrairement des coordonnées pour M0. On prendra par exemple X0 = K et Y0 = 0 où K est un nombre arbitraire (par exemple 1).
On obtient alors, si X et Y sont les coordonnées de M, X = Kcos
q et Y = Ksin q.
D'où Y/X = tan q. La valeur de K a alors peu d'importance.
Ainsi par exemple dans l'égalité (*) si
q0 + q1 est une approximation de q, on a Y2/X2 ~ tan q.

Il suffit donc de calculer, si on fait n rotations, les n coordonnées (Xi, Yi) afin d'avoir une approximation de tan q.
Oui, mais voilà, pour calculer (Xi, Yi) il faut calculer cos
qi et sin qi et cela on ne sait pas faire (rappelons que l'algorithme étudié sert justement à pouvoir calculer les cosinus et sinus d'un angle).
On va donc transformer la matrice de rotation en

Pour passer de M0 à Mn, on aura donc à effectuer le produit de ces matrices qui va nous donner le nombre K = cos q0 × cos q1 ×...×cos qn (qui ne sera pas génant si on l'oublie -puisqu'il apparaitra de la même manière dans X et Y) multiplié par des matrices de la forme .

Donc pour calculer tan q, il faudra savoir calculer les tan qi.

Choisir les qi.

C'est là qu'intervient le choix des qi. En effet, on va choisir les qi de manière à ce que tan qi = 10-i. Ainsi le passage de Mi à Mi+1 s'obtient en faisant :

Xi + 1 = Xi - 10-i ×Yi et Yi + 1 = Yi + 10-i × Xi .

C'est là toute la puissance de cet algorithme : on passe d'un point au suivant à l'aide uniquement d'additions ou de soustractions et de multiplications par des puissances de 10 (donc de simples décalages de virgules).

Il faudra bien sûr stocker en mémoire les différents qi, bien que l'on puisse se contenter de stocker les 6 premiers et d'utiliser pour les autres le fait que pour des angles très petits tan q soit pratiquement égal à q. Ainsi pour i > 5, on pourra prendre qi = 10-i (voir le tableau en fin de page).

On obtient alors l'algorithme suivant pour calculer tan q :

  I = 0 On initialise les variables I, X et Y.
  X = K K constante arbitraire (peut être prise égale à 1)
  Y = 0  
  E = 10-15  
  Tant que (q > E) si l'angle q est devenu assez petit on arrête
  Tant que (q < atan(10-I) ) si q > qi on passe. qi = atan(10-i) à stocker quelque part
  I = I + 1  
  Fin tant que  
  q = q - atan(10-I) On enlève à q l'angle qi
  temp = X On fait la rotation d'angle qi
  X = X - 10-I ×Y  
  Y = Y + 10-I × temp  
  Fin tant que  
  Z = Y/X Z est égale à tan q !! (enfin une valeur approchée)

Attention cependant ! Bien que Y/X soit une valeur approchée de tan q, n'allons pas conclure trop rapidement que Y et X sont des valeurs approchées de sin q et cos q !!
Souvenons nous qu'il y a un produit de cosinus K que l'on a volontairement oublié. Aussi si au lieu de poser X = 1 et Y = 0, on pose X = K et Y = 0 avec K = cos
q0 × cos q1 ×...×cos qn, on obtiendra en plus X ~ cos q et Y ~ sin q . Mais il faudra en plus stocker en mémoire les différentes valeurs des cos q0, cos q1, ..., cos qn.
On modifiera alors l'algorithme précédent en rajoutant les lignes suivantes après la ligne
E = 10-15 :

  theta = q afin de ne pas modifier la valeur de q
  K = 1  
  Tant que (theta > E) si l'angle q est devenu assez petit on arrête
  Tant que (theta < atan(10-I) ) si q > qi on passe. qi = atan(10-i) à stocker quelque part
  I = I + 1  
  Fin tant que  
  theta = theta - atan(10-I) On enleve à q l'angle qi
  K = K ×cos (atan(10-I)) Si on a pu enlever l'angle qi à q, on multiplie K par cos qi
  Fin tant que  

Bien que certaines lignes se ressemblent, on ne peut mélanger le calcul de K et l'algorithme précédent car celui-ci doit être initialisé avec la bonne valeur de K.

Et sin q et cos q ?

Si on ne veut utiliser que l'algorithme précédent (c'est-à-dire avec K = 1), on obtiendra cos q et sin q à l'aide des formules :

et .

Une remarque pour finir : Cet algorithme n'est valable que pour des angles q compris entre 0 et p/2. Aussi pour les autres angles, on se ramènera à l'intervalle [-p ; p] en ajoutant des multiples de 2p. Puis on se ramènera dans l'intervalle [0 ; p/2] en utilisant les formules trigonométriques :
cos (-x) = cos x ; cos (
p - x) = - cos x ; ....

Ci-dessous, le tableau donnant les valeurs des qi à stocker en mémoire :

i 10-i qi = atan(10-i)
0 1 0,7853981633974480
1 0,1 0,0996686524911620
2 0,01 0,0099996666866652
3 0,001 0,0009999996666669
4 0,0001 0,0000999999996667
5 0,00001 0,0000099999999997
6 0,000001 0,0000010000000000
...    
13 10-13 10-13
14 10-14 10-14
15 10-15 10-15