Algorithme de Cordic

L'algorithme de Cordic (pour COordinate Rotation DIgital Computer, « calcul numérique par rotation de coordonnées ») est un algorithme créé en 1957 par un ingénieur américain, Jack Volder, et qui permet de calculer des valeurs approchées des fonctions trigonométriques. Cet algorithme a notamment été utilisé sur les premières calculatrices.

L'idée de l'algorithme est le suivant. Soit $\theta\in[0,\pi/2]$ dont on souhaite calculer le cosinus et la tangente. Soit $M=(\cos\theta,\sin\theta)$ le point correspondant sur le cercle trigonométrique. On va construire une suite $M_n=(x_n,y_n)$ de points du cercle trigonométrique qui converge vers $M$ en partant du point $M_0=(1,0)$ et en lui appliquant des rotations. Pour cela, on va fixer une famille $\alpha_n$ d'angles de plus en plus petits. Si on note $\theta_n$ l'angle obtenu après $n$ itérations, on pose $\theta_{n+1}=\theta_n+\alpha_n$ si $\theta_n<\theta$ et $\theta_{n+1}=\theta_n-\alpha_n$ si $\theta_n\geq\theta$. Si les angles $(\alpha_n)$ sont bien choisis, alors $\theta_n$ tend vers $\theta$.

Notons $\sigma_n=1$ si on fait une rotation d'angle $\alpha_n$ et $\sigma_n=-1$ si on fait une rotation d'angle $-\alpha_n$. Dans tous les cas, on fait donc une rotation d'angle $\sigma_n \alpha_n$. Rappelons d'autre part que la matrice d'une rotation d'angle $\beta$ est $$\begin{pmatrix} \cos(\beta)&-\sin(\beta)\\ \sin(\beta)&\cos(\beta) \end{pmatrix}.$$ On a donc $$ \begin{pmatrix} x_{n+1}\\ y_{n+1} \end{pmatrix}= \begin{pmatrix} \cos(\sigma_n \alpha_n)&-\sin(\sigma_n\alpha_n)\\ \sin(\sigma_n \alpha_n)&\cos(\sigma_n \alpha_n) \end{pmatrix}\begin{pmatrix} x_n\\ y_n\end{pmatrix}.$$ Pour pouvoir effectivement calculer les coordonnées successives $\begin{pmatrix}x_n\\y_n\end{pmatrix}$, il suffit de partir d'une suite d'angles $\alpha_n$ dont on connait effectivement le cosinus et le sinus. Pour simplifier, on va factoriser par $\cos(\alpha_n)$ dans la relation précédente, et, en utilisant les propriétés du sinus et du cosinus, on a : $$ \begin{pmatrix} x_{n+1}\\ y_{n+1} \end{pmatrix}=\cos(\alpha_n) \begin{pmatrix} 1&-\sigma_n\tan(\alpha_n)\\ \sigma_n\tan(\alpha_n)&1 \end{pmatrix}\begin{pmatrix} x_n\\ y_n\end{pmatrix}.$$ On choisit alors pour $\alpha_n$ les angles tels que $\tan(\alpha_n)=2^{-n}$. Ainsi, $\alpha_0=\pi/4$, mais le calcul des autres valeurs de $\alpha_n$ nécessite un calcul à réaliser une fois pour toutes et à stocker dans la mémoire de la calculatrice. Notons alors $(x'_n)$ et $(y'_n)$ les suites définies par $x'_0=1$, $y'_0=1$ et la relation de récurrence $$ \begin{pmatrix} x'_{n+1}\\ y'_{n+1} \end{pmatrix}= \begin{pmatrix} 1&-\sigma_n 2^{-n}\\ \sigma_n 2^{-n}&1 \end{pmatrix}\begin{pmatrix} x'_n\\ y'_n\end{pmatrix}.$$ Ces suites sont faciles à calculer, particulièrement sur une calculatrice puisque la division par deux correspond juste à un décalage de virgule en binaire. De plus on a $$\begin{pmatrix} x_n\\ y_n \end{pmatrix}=\prod_{j=0}^{n-1}\cos(\alpha_j)\begin{pmatrix} x'_n\\ y'_n \end{pmatrix}.$$ Si on réalise toujours le même nombre $n$ d'itérations, on peut donc en déduire une valeur approchée de $x_n$ et de $y_n$, et donc de $\cos\theta$ et $\sin\theta$, si on stocke en plus des valeurs de $\alpha_0,\dots,\alpha_{n-1}$ une fois pour toutes une valeur approchée de $$\prod_{j=0}^{n-1}\cos(\arctan(2^{-j}))=\prod_{j=0}^{n-1}\frac{1}{\sqrt{1+2^{-2j}}}.$$

Contrairement à ce qu'on pourrait imaginer au premier abord, cet algorithme permet à une calculatrice de calculer une valeur approchée de $\cos(\theta)$ et $\sin(\theta)$ beaucoup plus efficacement que si elle utilisait la formule de Taylor (qui nécessite de plus des multiplications, ce qui est plus difficile pour une calculatrice).

Une variante de cet algorithme permet également de calculer des valeurs approchées du logarithme d'un réel $x\in [1,10]$ en stockant simplement la valeur d'un nombre fini de logarithmes. Supposons par exemple que l'on connaisse avec une grande précision les valeurs de $\ln(10)$, $\ln(2)$, $\ln\left(1+\frac 1{10}\right)$,...,$\ln\left(1+\frac1{10^N}\right)$. Il existe alors des entiers $\alpha_0$, $\alpha_1$,..., $\alpha_N$ compris entre $0$ et $10$ tels que $$2^{\alpha_0}\left(1+\frac 1{10}\right)^{\alpha_1}\cdots \left(1+\frac 1{10^N}\right)^{\alpha_N}\leq \frac{10}{x} \leq 2^{\alpha_0}\left(1+\frac 1{10}\right)^{\alpha_1}\cdots \left(1+\frac 1{10^N}\right)^{\alpha_N} \left(1+\frac 1{10^N}\right).$$ De plus, ces entiers $\alpha_i$ sont faciles à déterminer par des multiplications et des divisions par $10$. Alors, en utilisant les propriétés fonctionnelles du logarithme et l'inégalité $\ln(1+x)\leq x,$ on obtient $$\alpha_0\ln2+\alpha_1\ln\left(1+\frac 1{10}\right)+\cdots+\alpha_N\ln\left(1+\frac 1{10^N}\right) \leq \ln(10)-\ln(x)$$ $$\leq \alpha_0\ln2+\alpha_1\ln\left(1+\frac 1{10}\right)+\cdots+\alpha_N\ln\left(1+\frac 1{10^N}\right)+\frac1{10}^N.$$ Ainsi, $$\ln(10)-\alpha_0\ln2-\alpha_1\ln\left(1+\frac 1{10}\right)-\cdots-\alpha_N\ln\left(1+\frac 1{10^N}\right)$$ est une approximation à $10^{-N}$ de $\ln x$.

L'origine de l'algorithme de Cordic est à chercher dans des algorithmes mis au point par Briggs au XVIIè siècle pour établir des tables de logarithmes.