Algorithmes pour l’arithmétique

Cours de base (30 h de cours, 30h de TD)

Cours : Florent de Dinechin (Florent.de.Dinechin) TD : Sylvain Chevillard (Sylvain.Chevillard)

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 entiers et opérations de bases. Représentation de position, représentations logarithmiques, représentations redondantes, addition et multiplication. Complexité en temps et en espace.
• Grands entiers, polynômes et séries. Principaux paradigmes pour accélérer les calculs (Karatsuba et FFT pour multiplier, Newton pour diviser).
• 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). Analyse d’erreur.
• 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.