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.
union
Float_t
{
Float_t(float
num =
0.0
f) : 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és 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 :
void
TestFunction()
{
Float_t num(1.0
f);
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 :
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 flottant à 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.
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}finkitxmlcodelatexdvpdonc 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.