Algorithmique et programmation

Travaux dirigés, 27 octobre 1999

Louis Granboulan

1   Arithmétique flottante

  1. Étude théorique
    On se donne quatre entiers : une base B, une longueur de mantisse n et deux exposants extrémaux Emin et Emax. Habituellement, B³2, n³2 et Emin<0<Emax. L'écriture en virgule flottante d'un réel x est ex . x0,x1...xn-1 Bex avec ex = ±1, Emin£ ex £ Emax et 0£ xi<B, si on a x = ex(åi=0n-1xiB-i)Bex. On appelle mantisse la valeur fx = åi=0n-1xiB-i.
    1. Bien évidemment, tous les réels ne sont pas représentables exactement. Calculer quels sont le plus petit et le plus grand réels positifs représentables exactement.
    2. L'addition, soustraction, multiplication, ... de deux réels exactement représentables n'est pas toujours un réel exactement représentable. On décide par exemple d'arrondir au plus grand réel exactement représentable inférieur au résultat.

      Que donne l'algorithme suivant ? On suppose que Emax est suffisamment grand pour éviter les overflow.
      • a ¬ 1.0     b ¬ 1.0
      • tant que ((a + 1.0) - a) - 1.0 == 0 faire a ¬ a + a
      • tant que ((a + b) - a) - b <> 0 faire b ¬ b + 1.0
      • imprimer b
  2. Norme IEEE 754
    Cette norme étend la notation précédente comme suit : la base B=2 et on note fx = åi=1n xi 2-i. L'exposant ex peut varier dans l'intervalle [Emin-1, Emax+1].
    Exposant Mantisse Valeur
    Emin-1 fx=0 ±0
    Emin-1 fx¹0 ± fx 2Emin
    Emin£ ex £ Emax   ± (1+fx) 2ex
    Emax+1 fx=0 ±¥
    Emax+1 fx¹0 NaN
    float double
    32 bits 64 bits
    n = 23 n = 52
    Emin=-126 Emin=-1022
    Emax=+127 Emax=+1023
    Les arrondis des opérations peuvent se faire de plusieurs façons : au plus proche, vers 0, vers le haut ou vers le bas.
    1. Comparer cette représentation avec la représentation précédente.

2   Calcul d'une somme

  1. Série harmonique
    1. On définit la suite u0=0 et un=un-1+1/n Montrer que le calcul de cette suite en représentation flottante converge.
    2. Trouver une astuce pour calculer assez précisément ån=1N 1/n. Évaluer la précision du résultat.
  2. Encadrement du résultat
    1. Décrire des techniques de calcul d'un encadrement de ån=1N an.
    2. En déduire quelques considérations sur la représentation d'un réel par un intervalle.
  3. Double précision
    On représente un réel par une somme de deux flottants. On veut normaliser A + B sous la forme X + x de telle sorte que la valeur absolue de x soit la plus petite possible. On suppose que les opérations sur les flottants sont arrondies au plus proche.
    1. Exprimer la condition de normalisation sous la forme |x|£ 1/2a(X).
    2. Trouver comment faire cette normalisation en six opérations dans le cas général et en trois opérations (additions et soustractions) si |B| est suffisamment petit.
    3. En déduire comment faire une addition en vingt opérations.
    4. Étudier, dans cette représentation, les autres opérations habituelles.

This document was translated from LATEX by HEVEA.