Algorithmes pour la conception de circuits arithm\'etiques rapides

L'expos\'e sera ax\'e sur deux th\`emes : l'arithm\'etique ``en ligne'' (c'est un mode de calcul dans lequel les op\'erandes circulent en s\'erie, poids forts en t\^ete, et sont repr\'esent\'es dans un syst\`eme redondant d'\'ecriture des nombres), et les algorithmes ``de type Cordic'' de calcul des fonctions \'el\'ementaires. L'arithm\'etique ``en ligne'' est un moyen de calcul qui permet d'atteindre de hautes performances en permettant un ``pipe-line'' au niveau du chiffre. Le sens de circulation ``poids forts en t\^ete'' des chiffres est plus naturel que le sens ``poids faibles en t\^ete'', car il correspond \`a la notion de continuit\'e (on va du grossier au pr\'ecis), de surcro\^{\i}t, le sens ``poids faibles en t\^ete'' ne permettrait pas d'effectuer des divisions ou de calculer des fonctions \'el\'ementaires. On donnera quelques algorithmes et quelques r\'esultats de complexit\'e. Les algorithmes ``de type Cordic'', bien qu'assez anciens (le premier algorithme de cette classe a trois si\`ecles et a \'et\'e invent\'e par Briggs, un contemporain de Neper, pour construire la premi\`ere table de logarithmes), sont un des moyens de calcul des fonctions \'el\'ementaires (sinus, exponentielle, logarithme, ...) les plus employ\'es (on trouve des algorithmes de ce type dans la plupart des calculatrices, et dans des coprocesseurs comme l'Intel 8087 ou le Motorola 68881). On montre que de petites modifications de ces algorithmes permettent l'utilisation de syst\`emes redondants d'\'ecriture des nombres, et autorisent ainsi d'excellentes performances de calcul. On peut notamment utiliser ces algorithmes modifi\'es pour calculer ``en ligne''.