Les nombres flottants et leurs pièges

La série d'articles de Bruce Dawson aborde en détail les problématiques liées à la représentation des nombres à virgule flottante. Ce premier article pose les bases et explore le monde étrange et merveilleux des mathématiques à virgule flottante.
Retrouvez l'ensemble des articles de cette série sur la page d'index.

N'hésitez pas à commenter cet article ! 12 commentaires Donner une note à l'article (5)

Article lu   fois.

Les deux auteurs

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction

Il y a quelques années, j'ai écrit un article expliquant comment comparer des nombres à virgule flottante en utilisant des comparaisons d'entiers. Cet article a été plutôt populaire (il est fréquemment cité et les exemples de code ont été utilisés par nombre d'entreprises) et ça me fait un peu peur, parce que l'article a quelques défauts. Je ne vais pas donner de lien vers l'article : je veux le remplacer, et donc ne pas envoyer les gens le lire.

Aujourd'hui, je vais commencer par poser les bases en expliquant comment et pourquoi cette astuce fonctionne, tout en explorant le monde étrange et merveilleux des mathématiques à virgule flottante.

Il y a beaucoup de références qui expliquent la disposition binaire et le décodage des nombres à virgule flottante. Dans ce billet, je vais présenter l'organisation binaire et expliquer comment fonctionne le procédé de décodage par des expérimentations et de la rétroconception.

II. Norme IEE 754-1985

Le standard IEEE 754-1985 spécifie le format des nombres à virgule flottante de 32 bits, type connu sous le nom float dans de nombreux langages. La version 2008 du standard ajoute de nouveaux formats, mais ne modifie pas les existants, qui sont standardisés depuis plus de 25 ans.

Un flottant (1) de 32 bits consiste en un champ d'un bit pour le signe, un champ de 8 bits pour l'exposant et un champ de 23 bits pour la mantisse. L'union ci-dessous montre la disposition des bits d'un tel flottant. Cette union nous sera très utile pour explorer et travailler sur la représentation interne des nombres à virgule flottante. Je ne recommanderais pas d'utiliser cette union pour du code de production (elle est en violation des règles d'aliasing (2) établies par certains compilateurs et ceux-ci vont donc probablement générer du code inefficace), mais elle nous sera utile pour apprendre. Ces articles sur l'aliasing et l'undefined behavior (comportement indéfini) proposent des détails supplémentaires.

 
Sélectionnez
union Float_t
{
    Float_t(float num = 0.0f) : f(num) {}
    // extraction portable des composants
    bool Negative() const { return (i >> 31!= 0; }
    int32_t RawMantissa() const { return i & ((1 << 23) - 1); }
    int32_t RawExponent() const { return (i >> 23) & 0xFF; }

    int32_t i;
    float f;
#ifdef _DEBUG
    struct
    {   
        // Champs de bits pour l'exploration. Ne pas utiliser en production.
        uint32_t mantissa : 23;
        uint32_t exponent : 8;
        uint32_t sign : 1;
    } parts;
#endif
};

Le format des nombres flottants de 32 bits a été attentivement conçu pour leur permettre d'être réinterprété comme un entier et l'aliasing de i et f devrait fonctionner sur la majorité des plates-formes (si, comme gcc et VC++, elles autorisent l'aliasing par les unions), avec le bit de signe de l'entier et du flottant occupant la même position.

La disposition des champs de bits est dépendante du compilateur, donc la structure à champs de bits parts, qui est dans l'union, peut ne pas fonctionner sur toutes les plates-formes. Cependant, ceci fonctionne avec Visual C++ sur x86 et x64, ce qui est suffisant pour ce que je souhaite tester. Sur des systèmes big endian (3) comme SPARC et PPC, l'ordre dans la structure à champs de bits est inversé.

III. Représentation de quelques nombres

Afin de vraiment comprendre les flottants, il est important d'explorer et d'expérimenter. Une façon d'explorer est d'écrire du code comme ceci, en compilant en mode « debug » afin que le débogueur ne le retire pas en l'optimisant :

 
Sélectionnez
void TestFunction()
{
    Float_t num(1.0f);
    num.i -= 1;
    printf("Valeur flottante, representation, signe, exposant, mantisse\n");
    for (;;)
    {
        // point d'arrêt ici
        printf("%1.8e, 0x%08X, %d, %d, 0x%06X\n",
            num.f, num.i,
            num.parts.sign, num.parts.exponent, num.parts.mantissa);
    }
}

Placez un point d'arrêt sur la ligne du printf, puis ajoutez les différents composants de num à votre fenêtre de débogueur et examinez-les, ce qui pourra donner cela par exemple :

Image non disponible

Vous pouvez alors commencer à faire des tests interactifs, comme incrémenter la mantisse ou l'exposant, incrémenter num.i, ou inverser le bit de signe. En faisant cela, observez num.f afin de voir de quelle façon il évolue. Ou bien, assignez différentes valeurs de flottants à num.f et regardez comment les autres champs changent. Vous pouvez soit observer les résultats dans la fenêtre du débogueur, soit appuyer sur Run après chaque changement, afin que le printf s'exécute et affiche des résultats joliment formatés.

Allez-y. Placez Float_t et le code d'exemple dans un projet et jouez avec pendant quelques minutes. Découvrez les valeurs minimum et maximum des valeurs flottantes. Expérimentez avec les valeurs minimum et maximum de mantisse dans des combinaisons variées. Pensez aux conclusions. Ceci est la meilleure façon d'apprendre. J'attendrai.

Image non disponible

J'ai placé quelques-uns des résultats que vous pouvez rencontrer pendant ces expériences dans le tableau ci-dessous :

Valeur du flottant Représentation entière Signe Exposant Mantisse
0.0 0×00000000 0 0 0
1.40129846e-45 0×00000001 0 0 1
1.17549435e-38 0×00800000 0 1 0
0.2 0x3E4CCCCD 0 124 0x4CCCCD
1.0 0x3F800000 0 127 0
1.5 0x3FC00000 0 127 0×400000
1.75 0x3FE00000 0 127 0×600000
1.99999988 0x3FFFFFFF 0 127 0x7FFFFF
2.0 0×40000000 0 128 0
16,777,215 0x4B7FFFFF 0 150 0x7FFFFF
3.40282347e+38 0x7F7FFFFF 0 254 0x7FFFFF
Infini positif 0x7f800000 0 255 0

Avec ces informations nous pouvons commencer à comprendre le décodage des flottants. Les flottants utilisent un format en écriture scientifique base 2, donc nous pouvons nous attendre à ce que le décodage soit mantisse × 2^exposant. Cependant, dans l'encodage de 1.0 et 2.0 la mantisse est nulle, donc comment ceci peut-il fonctionner ? Ça fonctionne grâce à une astuce. Les nombres normalisés en notation scientifique base 2 sont toujours de la forme :

kitxmlcodelatexdvp1.xxxx × 2^{exposant}finkitxmlcodelatexdvp

donc stocker le chiffre 1 initial est inutile. En l'omettant, on gagne un bit supplémentaire de précision – le champ de 23 bits d'un flottant gère en fait 24 bits de précision car il y a un 1 implicite avec une valeur de 0x800000.

L'exposant pour 1.0 devrait être nul mais le champ exposant vaut en fait 127. C'est parce que exposant est stocké sous une forme augmentée de 127. Pour convertir la valeur dans le champ exposant en la valeur de l'exposant, vous devez simplement soustraire 127.

Les deux exceptions à cette règle de calcul de l'exposant sont quand le champ exposant vaut 255 ou 0. 255 est une valeur pour exposant qui indique que le flottant est soit l'infini soit un NaN (« Not-a-Number »), une mantisse contenant zéro indiquant l'infini. 0 est une valeur spéciale pour exposant, qui indique qu'il n'y a pas de chiffre 1 initial sous-entendu, ce qui signifie que ces nombres ne sont pas normalisés. C'est nécessaire afin de représenter exactement la valeur zéro. La valeur de l'exposant dans ce cas vaut -126, ce qui est la même valeur que lorsque le champ exposant vaut 1.

Pour clarifier les règles d'exposant, j'ai ajouté une colonne « valeur de l'exposant » qui montre l'exposant binaire réel correspondant au champ exposant.

Valeur flottante Représentation entière Signe Champ exposant Valeur de l'exposant Mantisse
0.0 0×00000000 0 0 -126 0
1.40129846e-45 0×00000001 0 0 -126 1
1.17549435e-38 0×00800000 0 1 -126 0
0.2 0x3E4CCCCD 0 124 -3 0x4CCCCD
1.0 0x3F800000 0 127 0 0
1.5 0x3FC00000 0 127 0 0×400000
1.75 0x3FE00000 0 127 0 0×600000
1.99999988 0x3FFFFFFF 0 127 0 0x7FFFFF
2.0 0×40000000 0 128 1 0
16,777,215 0x4B7FFFFF 0 150 23 0x7FFFFF
3.40282347e+38 0x7F7FFFFF 0 254 127 0x7FFFFF
Infini positif 0x7f800000 0 255 Infini! 0

Bien que ces exemples ne le montrent pas, les nombres négatifs sont gérés en mettant 1 dans le champ de signe, ce qui est appelé une forme signe-et-magnitude (« sign-and-magnitude »). Tous les nombres, même zéro et l'infini, ont des versions négatives.

Les nombres dans ce tableau ont été choisis afin de démontrer diverses choses :

  • 0.0 : il est utile que zéro soit représenté par tous les bits à 0. Cependant, il y a aussi un zéro négatif qui a le bit de signe activé. Le zéro négatif est égal au zéro positif ;
  • 1.40129846e-45 : ceci est le plus petit flottant positif et sa représentation entière est le plus petit entier positif ;
  • 1.17549435e-38 : ceci est le plus petit flottant avec un chiffre 1 initial sous-entendu, le plus petit nombre avec un exposant non-zéro, le plus petit flottant normalisé. Ce nombre correspond aussi à FLT_MIN (4). Notez que FLT_MIN n'est pas le plus petit flottant. Il y a en fait à peu près 8 millions de flottants positifs plus petits que FLT_MIN ;
  • 0.2 : ceci est un exemple d'un des nombreux nombres décimaux qui ne peuvent pas être représentés précisément avec un format binaire en virgule flottante. La mantisse devrait répéter C à l'infini ;
  • 1.0 : notez l'exposant et la mantisse et mémorisez la représentation entière au cas où vous la verriez dans des captures hexadécimales ;
  • 1.5 et 1.75 : juste quelques nombres un peu plus grands pour montrer la mantisse qui change alors que l'exposant reste identique ;
  • 1.99999988 : ceci est le plus grand flottant qui a le même exposant que 1.0 et le plus grand flottant qui est plus petit que 2.0 ;
  • 2.0 : notez que exposant est incrémenté de 1 par rapport à 1.0 et que la représentation entière et l'exposant sont tous deux plus grands que ceux de 1.99999988 ;
  • 16777215 : ceci est le plus grand flottant impair. Le flottant suivant a une valeur d'exposant de 24, ce qui signifie que la mantisse est déplacée assez vers la gauche pour que les nombres impairs soient impossibles. Notez que ça signifie qu'au-dessus de 16777215, un flottant a moins de précision qu'un entier ;
  • 3.40282347e+38 : FLT_MAX. Le plus grand flottant fini, avec l'exposant (non « infini ») maximum et la mantisse maximum ;
  • infini positif : le papa ours des flottants.

Nous pouvons maintenant décrire comment décoder le format des flottants :

  • si le champ exposant vaut 255, alors le nombre est infini (si la mantisse est nulle), ou NaN (si la mantisse n'est pas nulle) ;
  • si le champ exposant vaut entre 1 et 254, alors l'exposant vaut entre -126 et 127, il y a un chiffre 1 initial sous-entendu et la valeur du flottant est :
    kitxmlcodeinlinelatexdvp(1.0 + champ-mantisse / 0×800000) * 2^(champ-exposant - 127)finkitxmlcodeinlinelatexdvp ;
  • si le champ exposant est nul, alors l'exposant est -126, il n'y a pas de chiffre 1 initial implicite et la valeur du flottant est :
    kitxmlcodeinlinelatexdvp(champ-mantisse / 0×800000) * 2^{-126}finkitxmlcodeinlinelatexdvp
  • si le bit de signe est placé alors la valeur du flottant est l'opposé.

L'exposant sous la forme incrémentée de 127 et le chiffre 1 initial omis mènent à quelques caractéristiques très utiles des flottants, mais j'ai beaucoup de choses à dire dessus, donc souvenez-vous-en pour le prochain billet !

IV. Remerciements

Cet article est une traduction autorisée de Tricks With the Floating-Point Format par Bruce Dawson.

Merci à LittleWhite, à oodini, à Luc Hermitte, à Flob90, à Davidbrcz et à screetch pour leur relecture technique, à Torgar et à _Max_ pour sa relecture orthographique.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   


Note de traduction : par abus de langage, l'auteur utilise régulièrement le terme « flottant » à la place de « nombre à virgule flottante ».
Note de traduction : on parle d'aliasing quand deux objets de deux types différents sont à la même adresse mémoire. Voir Wikipédia - Aliasing (computing) pour plus de détails.
Note de traduction : big endian se traduit par « gros-boutiste » et définit la représentation mémoire des nombres. Il dépend du processeur. Voir Wikipédia - Endianness pour plus de détails.
Note de traduction : utiliser std::numeric_limits‹float>::min() est une façon plus « C++ » de récupérer la même valeur que FLT_MIN. De même pour std::numeric_limits‹float>::max() et FLT_MAX.

  

Copyright © 2012 Bruce Dawson. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.