Codage d’un nombre réel décimal avec une virgule flottante

Cette section est issue d'un rapport de stage. Les codes source ne sont pas mis sen ligne mais je peux les fournir. Il manque aussi les références bibliographiques que je mettrai en ligne dès que je le pourrai.

Un réél de type double est le plus souvent codé sur 64 bits (au moment de la rédaction sur Pentium ou assimilés), le but des quelques algorithmes présentés ici permet de créer une nouvelle catégorie de nombres réels dont la précision est plus importante. L’ouvrage [12] décrit la norme IEEE qui est à la base de la standardisation du calcul sur ordinateur.

Bien que la norme IEEE ne soit pas explicite en ce qui concerne le codage des flottants dont la taille est supérieure à 80 bits, nous allons suivre ses spécifications pour coder un nombre en virgule flottante sur quatre mots machine, soit 128 bits répartis de la manière suivante :

  Signe 1   bit  
  Exposant 11   bits  
  Mantisse 116   bits  
 
 
  Total 128   bits  

 

Sous cette forme, la valeur absolue du nombre décimal correspondant est : (1+mantisse).2exposant

La mantisse représente un nombre non signé codé sur 116 bits, elle offre une précision d’au moins 34 chiffres décimaux significatifs. La mantisse d’un nombre non nul est normalisée et compactée, c’est-à-dire que l’on a enlevé le bit de poids fort qui est toujours à un, ainsi la mantisse est toujours inférieure strictement à un. Pour tous les calculs, il faudra prendre en compte ce bit.

L’exposant est un nombre signé codé par excès. Cet excès vaut 1023 (=210-1).

Nous avons gardé un codage de l’exposant sur 11 bits afin de rester compatible avec celui d’un double (il nous fallait un nombre de bits au moins égal à celui d’un double).

Le nombre représentable le plus petit possible a pour exposant Emin= -1022, le plus grand Emax=1023.

 

Représentation et avantages

 

Exposant Partie fractionnaire Représente
e = Emin –1 f = 0 ± 0
e = Emin –1 f ¹ 0 0,f x 2Emin
Emin £ e £ Emax - 1,f x 2e
e = Emax + 1 f = 0 ± ¥
e = Emax + 1 f ¹ 0 NaN

 

Les avantages de cette représentation sont multiples :

  1. Zéro est représenté par un nombre constitué uniquement de zéros.
  2. Les nombres non négatifs sont ordonnés de la même manière que les entiers.
  3. Les valeurs spéciales NaN (Not A Number), + ¥ , - ¥ sont utilisables.
  4. Les nombres plus petits que 1.0x2Emin ou dénormalisés, sont représentés avec des mantisses inférieures à un. On appelle ce phénomène le sous-dépassement progressif.

Multiplication de deux flottants

C’est l’opération flottante la plus simple. Si un nombre flottant binaire x est représenté de la manière suivante , le produit de deux nombre vaut :

L’algorithme est très simple et se divise en trois parties :

  1. multiplication des deux mantisses décompactées avec une multiplication entière non signée,
  2. arrondi de la mantisse,
  3. calcul de l’exposant.

Calcul de l’exposant

Le calcul de l’exposant est relativement simple : on utilise la formule suivante :

Normalement, nous ne serons pas amené à gérer le débordement, c’est-à-dire avoir à coder soit un nombre trop petit, soit un nombre trop grand.

 

Arrondi d’un flottant

La norme IEEE propose quatre types d’arrondi. Par défaut, on arrondit au plus proche, ou plus précisément, au nombre pair le plus proche. Mais on peut aussi arrondir vers zéro, vers plus ou moins l’infini. Le tableau suivant rappelle les différentes règles d’arrondi possibles :

Arrondi Signe du résultat positif Signe du résultat négatif
- ¥   +1 si r Ú s
+ ¥ +1 si r Ú s  
0    
Au plus proche +1 si r Ù p0 ou r Ù s +1 si r Ù p0 ou r Ù s

Soit S la valeur absolue du résultat intermédiaire. Les cases vides signifient que les n bits les plus significatifs de S sont les vrais bits du résultat. Si la condition dans la case est vraie, ajouter un au nième bit le plus significatif de S. Les symboles r et s représentent les bits d’arrondi et persistant alors que p0 est le nième bit le plus significatif de S. r est en fait le n+1ème bit le plus significatif de S et le bit persistant répond à la question : existe-t-il un bit non nul après le bit d’arrondi ?

Multiplication entière non signée

On dispose de trois registres A, B et P de n bits chacun. On désire affecter à P le produit A*B.

Initialement, P est nul.

Chaque étape de la multiplication de divise en deux parties :

  1. Si le bit de poids faible de A est un, alors on ajoute B à P, sinon on ajoute zéro.
  2. Les registres P et A sont décalés à droite. La retenue de la somme précédente est injectée dans le bit de poids fort de P. Tandis que le bit de poids faible de P est transféré dans le registre A. Le bit de poids faible de A qui n’est pas utilisé sort du registre.

Après n étapes, le produit se trouve dans les registres P et A, avec les poids faibles dans A.

Addition de deux flottants

On va additionner les nombres flottants a1 et a2. On note si leurs mantisses et ei leurs exposants. L’algorithme détaillé d’addition est le suivant :

  1. Si e1 < e2, permuter les opérandes de telle sorte que les exposants satisfassent la relation d = e1 – e2 ³ 0. L’exposant du résultat est supposé être e1.
  2. Si les signes de a1 et a2 sont différents, remplacer s2 par son complément à deux.
  3. Placer s2 dans un registre à p bits et le décaler de d positions vers la droite (en entrant des uns si s2 a été complémenté dans l’étape précédente). Des bits qui sortent du registre, prendre g à partir du bit le plus significatif, r à partir du bit suivant et le bit persistant à partir du OU des bits restants.
  4. Calculer une mantisse préliminaire S = s1 + s2 en ajoutant s1 au registre de p bits contenant s2. Si les signes de a1 et a2 sont différents, le bit le plus significatif de S est un et qu’il n’y a pas de retenue sortante, alors S est négatif. Remplacer S par son complément à deux. Ceci ne peut intervenir que lorsque d est nul.
  5. Décaler S de la manière suivante. Si les signes de a1 et a2 sont les mêmes et qu’il y a eu une retenue sortante dans l’étape (iv), alors décaler S d’une position vers la droite en remplissant le bit de poids fort avec un un (la retenue sortante). Autrement, le décaler à gauche jusqu’à ce qu’il soit normalisé. Quand on décale à gauche, sur le premier décalage, on fait rentrer g dans le bit de poids faible. Après cela, faire entrer des zéros par décalage. Ajuster l’exposant du résultat en fonction des décalages.
  6. Ajuster r et s. si S a été décalé à droite dans l’étape (v), égaler r et le bit de poids faible de S avant le décalage, égaler s :=g OU r OU s. S’il n’y a pas eu de décalage, faire r :=g, s :=r OU s. S’il y a eu deux décalage à gauche ou plus, faire r :=s :=0. (Dans le dernier cas, deux décalages ou plus ne peuvent intervenir que lorsque a1 et a2 ont des signes opposés et le même exposant, auquel cas le calcul s1+s2 à l’étape (iv) est exact).
  7. Arrondir S en utilisant la figure 31. Cela revient, si une entrée de la table est non vide, à ajouter un au bit de poids faible de S. Si le fait d’arrondir provoque une retenue sortante, décaler S à droite et ajuster l’exposant. C’est la mantisse du résultat.
  8. Calculer le signe du résultat. Si a1 et a2 sont de même signe, c’est le signe du résultat. Si a1 et a2 ont des signes différents, alors le signe du résultat dépend des cas suivants : a1 ou a2 négatif, permutation ou non à l’étape (i), remplacement ou non de S par son complément à deux dans l’étape (iv). La figure 32 résume ces différents cas.

 

Permutation Complément Signe de a1 Signe de a2 Signe du résultat
OUI   + - +
OUI   - + -
NON NON + - +
NON NON - + -
NON OUI + - -
NON OUI - + +

 

Division de deux flottants

Transformer l’algorithme de division entière en flottant est similaire à la conversion de l’algorithme de multiplication entière en flottant. Il faut utiliser la formule suivante :

Algorithme

L’algorithme se divise donc en trois parties :

  1. calcul de s1/s2,
  2. calcul de l’exposant,
  3. calcul de l’arrondi.

A l’étape (i), il faut charger s2 en B et s1 en P, A n’est pas nécessaire. Il faut aussi sauter le premier décalage à gauche. En ce qui concerne l’arrondi, il faut une étape de calcul supplémentaire car le premier bit de quotient peut être nul (mais pas le deuxième).

Le registre P doit aussi être suffisamment grand pour permettre de traiter de l’arithmétique signée (n+1 bits ou un bit de " débordement ").

L’algorithme est dit linéaire car il produit un bit de résultat à chaque itération.

Division entière non signée

On dispose de trois registres A, B et P de n bits chacun. On désire effectuer la division A/B. Au final (après n itérations), A contiendra le quotient et P le reste.

Initialement, P est nul.

Nous allons présenter l’algorithme de division dit " avec restauration " :

  1. Décaler les registres (P, A) à gauche. Le bit de poids fort de A remplace le bit de poids faible de P.
  2. Soustraire le contenu de B du registre P en rangeant le résultat dans P.
  3. Si le résultat de l’étape précédente est négatif, mettre le bit de poids faible de A à zéro, sinon le mettre à un.
  4. Si le résultat de l’étape (ii) est négatif, restaurer l’ancien contenu de P en ajoutant le contenu de B à P.

Comparaison de deux flottants

Les tests entre les flottants sont très simples si l’on respecte la norme IEEE. Il suffit de voir les nombres positifs comme des entiers (il n’est pas nécessaire de comparer les exposants puis les mantisses).

Implémentation

Cette classe de réels flottants en haute précision est implémentée dans CFlottant (en C++). Deux autres classes permettent la calcul matriciel. La classe CMatriceFlottant (voir [13]) définit les matrices et CCalculMatriciel propose la solution d’un système linéaire avec la méthode de Gauss. (décrite à l’annexe A.3)

On a utilisé l’assembleur intégré au studio de développement (Visual Studio) pour manipuler les expressions bit à bit et gagner en vitesse (voir [14]).

 

Tests de l’unité de calcul

Les tests de cette unité de calcul ont été peu poussés. En effet, pour vérifier les opérations élémentaires (calculs ou tests), il a été choisit au hasard des nombres en double précision et le résultat a été comparé à l’opération en double précision. Ces tests semblent être suffisants dans la mesure où, si le début du calcul est correct, on peut supposer que la fin l’est aussi, à un arrondi près. Dans tous les cas, il était impossible de vérifier tous les chiffres significatifs.

Le programme de test se trouve à l’annexe E.

Améliorations possibles

  • Les algorithmes ne sont pas optimisés (ils sont linéaires) alors qu’il est possible d’obtenir plus d’un bit de résultat à chaque itération.
  • Il n’y a pas de système de trappe ou de gestion des erreurs, de gestion du débordement (sous-dépassement en particulier)
  • Il n’y a pas d’arrondi, seule la troncature est utilisée.

 

Conclusion

Cette unité de calcul permet de calculer en haute précision. La précision se fait au détriment du temps de calcul.