Algorithmes pour l'arithmétique
Cours de base (30 h de cours, 30h de TD)
Cours : Florent de Dinechin (Florent.de.Dinechin)
TD : ?? (??)
Ce cours est une introduction à la complexité et à l'algorithmique
des opérations de base sur les nombres le plus souvent implantés
en machine (entiers, nombres flottants, éléments d'un corps fini).
Voici un plan indicatif:
- Représentation des nombres et opérations de bases. Représentation de position, représentations logarithmiques, représentations redondantes, addition et multiplication. Complexité en temps et en espace.
- Entiers, polynômes et séries.
Principaux paradigmes pour accélérer les calculs
(FFT et Karatsuba pour multiplier, Newton pour diviser).
Réduction entre problèmes et complexité des fonctions algébriques.
- Arithmétique "réelle" et continue.
Représentation des nombres (virgule fixe, virgule flottante, norme IEEE 754).
Exemple d'algorithmes (division et racine carrée, fonctions élémentaires).
- Corps finis.
Différentes représentations des corps finis.
Algorithmes pour la multiplication, la division et l'exponentiation rapide.
Bibliographie
-
M.D. Ercegovac and T. Lang, Digital Arithmetic, Morgan Kaufmann 2004.
- D.E. Knuth, The Art of Computer Programming, Volume 2, Addison Wesley 1997.
- J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge 2003.
- N. Higham, Accuracy and stability of numerical algorithms, SIAM 2002.
- M. Overton, Numerical Computing with IEEE Floating Point Arithmetic, SIAM 2001.