Algorithme SLZ - Résultats

L'algorithme SLZ est un nouvel algorithme pour trouver les pires cas pour l'arrondi correct d'une fonction mathématique à une variable. Le problème et l'algorithme sont décrits dans les articles suivants:

• Damien Stehlé, Vincent Lefèvre et Paul Zimmermann. Searching Worst Cases of a One-Variable Function Using Lattice Reduction. IEEE Transactions on Computers, 54(3):340–346, mars 2005.
• Damien Stehlé, Vincent Lefèvre et Paul Zimmermann. Worst cases and lattice reduction. Dans Jean-Claude Bajard and Michael Schulte, éditeur, Proceedings of the 16th IEEE Symposium on Computer Arithmetic, pages 142–147, Santiago de Compostela, Espagne, 2003. IEEE Computer Society Press, Los Alamitos, CA.

Cet algorithme a été implémenté par Paul Zimmermann pour trouver les pires cas de la fonction 2^x entre 1/2 et 1 dans un système à virgule flottante en base 2. Télécharger le programme (distribué sous la GNU General Public License).

Ce programme a été utilisé pour trouver les pires cas dans un système avec 64 bits de mantisse (il s'agit de la précision étendue sur les processeurs x86). Il a été lancé avec les 4 premiers arguments suivants (voir la documentation): 128 64 56 24. Le 64 correspond à la taille de la mantisse, nous avons cherché les pires cas avec au moins 56 bits identiques suivant le bit d'arrondi (cf les résultats ci-dessous), et le 24 n'est qu'un paramètre d'optimisation, trouvé en essayant différentes valeurs sur un petit intervalle. La recherche a été effectuée entre 0 et 2⁶³ = 9223372036854775808.

Les résultats obtenus sont donnés dans les tableaux ci-dessous. Cette recherche exhaustive a demandé 37227 heures sur un cluster de l'INRIA Rocquencourt, 22945 heures sur un cluster du Centre Charles Hermite, 5628 heures sur le cluster de notre projet SPACES, 3305 heures sur un cluster du LIP, et 274 heures sur des machines du centre de calcul MEDICIS, du 21 mars 2004 au 10 janvier 2005.

Donnons d'abord quelques explications sur les notations. Pour x nombre machine, on considère la mantisse de la valeur exacte 2^x; on peut écrire 2⁶³ 2^x = Y + F, où Y est un entier vérifiant 2⁶³ ≤ Y < 2⁶⁴ et la partie fractionnaire F s'écrit en binaire: 0.rfff...fff..., i.e. elle est formée d'un bit quelconque r (appelé bit d'arrondi) suivi d'une succession de bits identiques f. On note m ce nombre maximum de bits identiques; si x n'est pas un entier, alors m est fini. Si m est suffisamment grand (par exemple, m ≥ 56), alors on dit que x est un pire cas. Dans la suite, on considère les pires cas entre 1/2 et 1, et on note x = 1/2 + t/2⁶⁴, où t est un entier vérifiant 0 ≤ t < 2⁶³.

---

Dernière modification: 2005-11-10 17:21:53.
Retour à la première page