Paul Zimmermann, Loria, Nancy

Algorithmes efficaces sur les nombres, polynômes et séries

Pour un logiciel de calcul formel, il est crucial d'optimiser les op\'erations sur les objets de base que sont les nombres, polyn\^omes et s\'eries. On peut distinguer en fait deux classes d'objets~: les entiers et les polyn\^omes o\`u les op\'erations sont exactes, les flottants et les s\'eries o\`u seule la partie la plus significative du r\'esultat int\'eresse l'utilisateur. Nous pr\'esenterons les meilleurs algorithmes connus actuellement, dont la plupart sont r\'ecents (Karp/Markstein 93, Jebelean 97, Burnikel/Ziegler 98, Mulders 98, Hanrot/Zimmermann 99) pour les multiplications, divisions, racines carr\'ees sur des entiers ou flottants, en consid\'erant trois mod\`eles de complexit\'e (na\"{\i}f, Karatsuba, FFT). Nous donnerons \'egalement des temps de calcul obtenus avec des implantations de certains de ces algorithmes.