Annuaire
Webmail
Intranet
Lorsque l'on cherche à améliorer la qualité des calculs en machine
(on vise des calculs plus précis, plus fiables, plus rapides, moins
coûteux en mémoire ou même en silicium), il arrive fréquemment que
l'on soit amené à modéliser la question posée à l'aide d'outils de
théorie (algorithmique) des nombres. On illustrera ce phénomène à
l'aide de deux exemples :
1) quand on implante des fonctions en machine, on utilise presque
toujours des approximations polynomiales. Dans la plupart des cas,
le polynôme qui approche le mieux (pour une norme et un intervalle
donnés) une fonction a des coefficients qui ne sont pas exactement
représentables sur un nombre fini de bits. Or, les polynômes
que nous devons utiliser doivent satisfaire des contraintes du type :
si $n$ désigne le degré maximal des polynômes considérés,
le $i$-ème coefficient, pour $i = 0, \ldots,\, n$, de l'approximant doit être
un nombre rationnel de dénominateur $2^{m_i}$, où $(m_i)_{i = 0, ...,
\, n}$ est une suite d'entiers donnée ou à déterminer, suivant
l'application considérée. Nous présenterons une méthode heuristique
utilisant l'algorithmique des réseaux euclidiens et notamment
l'algorithme LLL qui permet de produire une très bonne (voire la
meilleure) approximation polynomiale sous ce type de contraintes
quand la norme considérée est la norme sup. Des techniques similaires
fonctionnent pour la norme $L^2$.
[Travaux de B., Chevillard, Hanrot, Muller, Tisserand et Torres]
2) l'évaluation en machine d'une fonction nécessite un arrondi. Le fait de garantir
que l'on obtient toujours l'arrondi correct (on expliquera
cette notion) est un problème difficile que l'on peut le ramener à la résolution
d'inégalités diophantiennes. On présentera l'état actuel, très partiellement
satisfaisant, des méthodes de résolution de ces inégalités, qui s'appuient sur
l'algorithme d'Euclide ou sur des techniques dues à Don Coppersmith pour déterminer des
racines entières de polynômes modulo un entier. [Travaux de Lefèvre, Muller, Stehlé,
Zimmermann]
