Codage d’un nombre réel décimal avec une virgule flottanteCette 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 :
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
Les avantages de cette représentation sont multiples :
Multiplication de deux flottantsC’est l’opération flottante la plus simple. Si un nombre flottant
binaire x est représenté de la manière suivante L’algorithme est très simple et se divise en trois parties :
Calcul de l’exposantLe 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 flottantLa 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 :
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éeOn 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 :
Après n étapes, le produit se trouve dans les registres P et A, avec les poids faibles dans A. Addition de deux flottantsOn 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 :
Division de deux flottantsTransformer 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 : AlgorithmeL’algorithme se divise donc en trois parties :
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éeOn 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 " :
Comparaison de deux flottantsLes 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émentationCette 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 calculLes 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
ConclusionCette unité de calcul permet de calculer en haute précision. La précision se fait au détriment du temps de calcul. |