Programme de l’UE

L’arithmétique des ordinateurs s’intéresse à la fois à la conception d’opérateurs arithmétiques, et à leur utilisation fine pour réaliser des fonctions plus complexes.

Ce cours présente un panorama des représentations utilisées en machine pour manipuler les nombres entiers, les réels et les polynômes, ainsi que l’algorithmique associée à chaque représentation pour réaliser les opérations de base (addition, multiplication, division, racine carrée… ) et calculer des fonctions « élémentaires » (logarithme, exponentielle, fonctions trigonométriques, etc.).

On s’intéressera d’abord à la manipulation de nombres en « précision fixée » (entiers, virgule flottante, norme IEEE 754) ainsi qu’à diverses techniques permettant d’augmenter ou de garantir la précision des calculs: on montrera ainsi qu’une arithmétique « approchée » comme la virgule flottante permet de faire des calculs exacts.

On étudiera ensuite la complexité et l’algorithmique des opérations de base sur les polynômes (multiplication, division, évaluation, interpolation), en arithmétique exacte.

Enfin, nous aborderons la question du calcul sur les polynômes en arithmétique approchée. Cela permettra d’une part de présenter les notions fondamentales de conditionnement d’un problème et de stabilité d’un algorithme et, d’autre part, de comprendre pourquoi l’évaluation polynomiale est de plus en plus souvent au coeur des implantations (logicielles ou matérielles) d’opérateurs arithmétiques de base comme la division ou la racine carrée.

Intervenants

  • Jean Michel Muller, DR CNRS (http://perso.ens-lyon.fr/jean-michel.muller/)
  • Claude Pierre Jeannerod, CR INRIA (http://perso.ens-lyon.fr/claude-pierre.jeannerod/)

Quelques ouvrages de référence

  • Ercegovac et Lang, Digital Arithmetic, The Morgan Kaufmann Series in Computer Architecture and Design, 2004
  • D.E. Knuth, The Art of Computer Programming, Volume 2, Addison Wesley 1997
  • Muller, Arithmétique des Ordinateurs, Masson, 1989 (texte intégral accessible à http://prunel.ccsd.cnrs.fr/ensl-00086707)
  • J. von zur Gathen et J. Gerhard, Modern Computer Algebra, Cambridge 2003.
  • Muller, Elementary functions, algorithms and implementation, 2ème édition, Birkhauser, 2006
  • P. Burgisser, M. Clausen, et M.A. Shokrollahi, Algebraic Complexity Theory, Springer 1997.
  • Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Seconde édition, Août 2002
  • Muller, Brisebarre, de Dinechin, Jeannerod, Lefèvre, Melquiond, Revol, Stehlé et Torrès, Handbook of Floating-Point Arithmetic, Birkhauser, 2010