Daily Archives: 16 mai 2010

Comment calcule une calculatrice ?

Posted on by
Reply

Naïvement, je pensais qu’une calculatrice (ou tout logiciel de calcul scientifique) utilisait les développements en série pour calculer les fonctions usuelles : trigonométriques (sinus, cosinus, tangente), exponentielle, logarithme, etc. En fait, il n’en est rien et on utilise des astuces bien précises qui diminuent fortement la complexité des calculs.

Par exemple, on utilise l’algorithme CORDIC (COordinate Rotation DIgital Computer) inventé en 1959 par Jack E. Volder. Détaillons-le sommairement.

On se donne un angle en radian \alpha (que l’on suppose compris entre 0 et \pi/2, on peut toujours s’y ramener par des formules trigonométriques du genre \sin(x+\pi/2)=\cos(x), etc…). On va calculer par itération un vecteur v_n qui représente un point sur le cercle unité. Pour cela, on lui fait subir des rotations d’angles \gamma_n choisis judicieusement, par exemple tels que \tan \gamma_n= 2^{-n}. L’avantage est qu’en binaire la multiplication par 2^{-n} revient à un simple décalage de virgule. Le vecteur v_n, d’angle correspondant \alpha_n, convergera alors vers la valeur exacte v, d’angle correspondant \alpha.

On a donc une relation de récurrence du type

\displaystyle v_{n+1}=\begin{pmatrix} \cos \gamma_{n} & -\sin \gamma_{n} \\ \sin \gamma_{n} & \cos \gamma _{n}\end{pmatrix}v_n

d’où en factorisant par \cos \gamma_n

\displaystyle v_{n+1}=\cos(\arctan(2^{-n}))\begin{pmatrix} 1 & -\sigma_{n} 2^{-n} \\ \sigma_{n} 2^{-n} & 1 \end{pmatrix}v_n

où \sigma_n = \pm 1 (sens de la rotation). On le calcule en regardant le signe de l’angle actuel \alpha_{n+1}=\alpha_n-\sigma_n \arctan2^{-n}.

Il suffit alors d’avoir en mémoire les différentes valeurs de \arctan2^{-n} (on peut même utiliser l’approximation \arctan2^{-n} \sim 2^{-n} pour n un peu grand) pour se retrouver avec un algorithme qui n’utilise que des additions, des décalages de virgules et une seule multiplication finale par

\displaystyle\prod_{n=0}^{N-1} \cos(\arctan(2^{-n})) = \prod_{n=0}^{N-1} \frac{1}{\sqrt{1 + 2^{-2n}}},

valeurs que l’on peut aussi stocker à l’avance. Malin, non?

On peut généraliser ce genre de procédés. Pour plus d’informations : http://en.wikipedia.org/wiki/CORDIC