Calcul informatique des fonctions trigonométriques

L'algorithme CORDIC – COordinate Rotation DIgital Computer – permet de calculer efficacement la tangente d'un angle.
 

Nous allons nous intéresser dans cette activité à la méthode qu'utilisent les calculatrices pour calculer les fonctions trigonométriques.

Présentation de l'algorithme

Contrairement à l'opinion commune, la grande majorité des calculatrices et des logiciels de calcul formel n'utilisent ni développement en série ni approximation polynomiale pour calculer les fonctions trigonométriques.

Rappelons avant toute chose les développements en séries entières de Taylor des fonctions trigonométriques :

Développement limité du cosinus


Développement limité du sinus


Développement limité de la tangente.

La série de Taylor de la fonction tangente est plus compliquée que celle des fonctions cosinus et sinus puisque les nombres de Bernoulli Bk interviennent dans le calcul des coefficients cherchés ; à partir de n = 3, le n-ième nombre impair de Bernoulli est nul. À ce propos, les premiers nombres de Bernoulli sont :

Premiers nombres de Bernoulli.

Bien que l'on puisse utiliser les formules de Taylor – convergentes – qui donnent par ailleurs de très bonnes approximations, cette technique est évitée car elle nécessite un grand nombre de multiplications assez coûteuses en temps. C'est pourquoi l'algorithme CORDIC – acronyme de COordinate Rotation DIgital Computer –, développé par Jack Volder en 1959, est préféré. L'idée remonterait cependant au mathématicien anglais Henri Briggs (1561-1630), l'un des inventeurs du logarithme décimal, encore appelé « logarithme briggsien ».

Une synthèse très intéressante consacrée à l'architecture CORDIC sur les calculatrices de poches est accessible sur une page rédigée par feu Jacques Laporte (ayons une pensée pour lui).

Principe de l'algorithme

Comme son nom l'indique, l'idée de l'algorithme CORDIC est de calculer tan(θ) en faisant subir à un vecteur de coordonnées (X;Y) des rotations d'angles de plus en plus petits, tendant vers 0, et dont la somme est égale à θ. Le quotient Y/X est alors clairement une approximation de tan(θ) par définition de la tangente.

Dessin expliquant l'algorithme CORDIC

Considérons un angle θ tel que theta dans ]0; pi/2[ et une suite décroissante de θk, c'est-à-dire telle que Suite décroissante d'angles, avec Somme des angles, où n est un entier naturel.
Soit le point M0 de coordonnées (X_0;Y_0). Alors le point M1, image de M0 par la rotation de centre O et d'angle θ0, a pour coordonnées (X_1;Y_1) vérifiant :

Relations de départ.

En effet, si l'on identifie R^2 au plan complexe d'Argand-Cauchy et que l'on utilise alors les affixes des points dans ce plan, M0(z0) a pour image M1(z1) avec z1 défini grâce aux formules de transformation de coordonnées par rotation pure :

Calcul de z_1.

Démontrons maintenant par récurrence sur l'entier k que :

Relations de récurrence.

On a vu le résultat pour k = 1. Le résultat est d'ailleurs aussi valable pour k = 0 étant donné qu'une somme d'aucun élément est l'élément neutre 0, d'où le résultat avec cos(0) = 1 et sin(0) = 0.

Soit maintenant k > 1. Si l'on note zk-1 et zk les affixes respectives de Mk-1 et de Mk, et theta', Mk est le transformé de Mk-1 par la rotation de centre O et d'angle θk-1. D'où la relation :

Démonstration.

On a donc démontré le résultat annoncé par récurrence.

Remarquons alors que :

Tangente exacte trouvée.

Amélioration du calcul de la tangente

Ainsi, tan(θ) ne dépend pas de la coordonnée X0 initiale. On pourra donc prendre X0 = 1 dans un premier temps. Et comme Somme des angles, il suffit de calculer les n+1 coordonnées des points Mk afin d'obtenir la valeur de tan(θ). Or, pour calculer ces coordonnées, il suffit de savoir calculer les cos(θk) et les sin(θk), ce que nous ne savons pas faire puisque l'algorithme sert précisément à pouvoir les calculer ! L'astuce consiste à transformer nos relations sur les affixes des points de manière à faire apparaître des tangentes.

On a donc :

Expression de z_1

et l'on montre par récurrence sur l'entier k que :

Expression de z_k.

En effet, par hypothèse de récurrence, on peut écrire :

Démonstration

si bien que, par simplification dans les coordonnées (X_k;Y_k) obtenues, il ne reste plus que le rapport de la partie imaginaire sur la partie réelle de l'expression :

Nouvelle expression plus sympathique.

Simplification judicieuse du calcul

Cette relation ne fait intervenir plus que les tan(θk). Pour calculer tan(θ), il suffit donc de savoir calculer les tan(θk).

Par conséquent, il s'agit de choisir les tan(θk) judicieusement. Nous allons en fait prendre les θk de manière à ce que tan(θk) = 10-k. Dès lors, le passage de Mk à Mk+1 s'obtient uniquement à l'aide de calculs très élémentaires puisque :

Simplification de la relation de récurrence.

D'où les relations simples :

Relations de récurrence simples.

De tels calculs sont extrêmement rapides à mettre en œuvre informatiquement étant donné qu'ils ne nécessitent que des additions, des soustractions et de simples décalages de virgules.

Il faut cependant avoir préalablement en mémoire les premières valeurs possibles des θk. Pour k > 6, nous pourrons bien évidemment prendre θk = 10-k d'après l'équivalent de la fonction tangente en 0 : Équivalent de la fonction tangente en 0.

Le tableau ci-dessous donne les premières valeurs à choisir pour θk, à 10-20 près, exprimé en radians :

Table de valeurs à choisir pour les angles θk.
k 10-k θk = Arctan(10-k)
010,78539816339744830962
10,10,099668652491162027378
20,010,0099996666866652382063
30,0010,00099999966666686666652
40,00010,000099999999666666668667
50,000010,0000099999999996666666667
60,0000010,00000099999999999966666667

Calcul des autres fonctions trigonométriques

Néanmoins, bien que Y/X soit une valeur approchée de tan(θ), Y et X ne sont guère les valeurs approchées respectives de sin(θ) et de cos(θ) puisqu'il existe un produit de cosinus et de X0 que nous avons laissé de côté depuis le début.

En fait, il suffit d'utiliser les formules peu coûteuses :

Relations fondamentales entre les fonctions trigonométriques.

Notons enfin que l'algorithme n'est valable que pour des angles θ tels que theta dans ]0; pi/2[. Pour les autres angles, on se ramène à cet intervalle à l'aide de relations issues de la symétrie des courbes trigonométriques, comme cos(–θ) = cos(θ) ou sin(π–θ) = sin(θ).

Pseudo-code de l'algorithme

Présentons tout d'abord un pseudo-code de l'algorithme, c'est-à-dire le détail des opérations à effectuer sans syntaxe propre à un langage.

  1. Initialisation des variables utilisées :

  2. Tant que theta plus grand qu'epsilon :

  3. On renvoie Y/X, valeur de tan(θ).

Il ne reste plus qu'à implémenter ce pseudo-code dans un langage de programmation.

Implémentation de l'algorithme en PHP

Vous pouvez dès maintenant tester l'algorithme CORDIC que j'ai implémenté en PHP sur TrigoFACILE.

Il vous suffit d'indiquer l'angle en degrés dont vous désirez calculer la tangente dans la case ci-dessous :

(par exemple « 30 », « 841,274 », « -57 », etc.)

 

↑ Retour au haut de cette page

Pages connexes
  • Calcul informatique des fonctions trigonométriques

← Retour au menu précédent