En continuant à étudier le problème de la précision décimale à l'aide de l'arithmétique binaire, qui a commencé dans les articles précédents [1,2,3,4], j'ai pu développer des algorithmes de calcul de nombres réels présentés au format de nombres décimaux à virgule flottante, qui donnent le même résultat exact que si les calculs seraient effectués manuellement.
Ces algorithmes utilisent l'arithmétique binaire, régulée par la norme IEEE754. Pour tester le fonctionnement des algorithmes, un programme de test en C ++ a été développé qui implémente une calculatrice décimale 18 bits.
Étant donné que le volume du matériel dépasse le format de la publication, j'ai exposé les principaux points sous forme de résumés. Nous appellerons cet article les thèses de mai :(.
Alors.
On sait que
L'arithmétique familière à l'utilisateur est l'arithmétique décimale.
Il existe également une arithmétique b-aire, où b est la base du système numérique, prenant toute valeur non nulle [5].
Pour afficher les nombres à différentes échelles, nous utilisons la notation des nombres à virgule flottante sous la forme d'un produit de la mantisse et d'un certain degré de base arbitraire. Il s'agit de la notation dite exponentielle.
Si le degré du nombre est fixe et que la mantisse du nombre est un entier, alors ce format est appelé format à virgule fixe. Un cas particulier du format à virgule fixe est un nombre dans lequel le degré est nul. Ce format est un format entier.
Si la mantisse est un nombre fractionnaire dans le système numérique b-aire avec la partie entière c ≠ 0 et c <b, alors un tel nombre est appelé normalisé.
Malgré le fait que, par leur nature physique, les nombres sont approximatifs, pour un appareil informatique, ce sont des nombres exacts et l'appareil doit effectuer des opérations sur eux avec une précision spécifiée par l'utilisateur.
Des calculs précis en arithmétique signifient l'obtention d'un résultat avec un nombre donné de chiffres significatifs valides après le point [6].
Tous les calculs dans l'ordinateur sont effectués sous forme binaire. Pour eux, la base est b = 2.
Étant donné que les systèmes de nombres binaires et décimaux sont incommensurables, lors de la conversion de nombres réels décimaux en code binaire, nous obtenons le plus souvent la valeur approximative de l'équivalent binaire du nombre décimal. Par conséquent, lors de la conversion de nombres décimaux en binaires, des erreurs de représentation se produisent.
Les nombres décimaux qui ont l'équivalent binaire exact sont appelés représentables.
Les nombres décimaux qui n'ont pas l'équivalent binaire exact sont appelés non représentatifs.
Tous les nombres décimaux entiers sont représentables si le nombre de chiffres significatifs dans leur équivalent binaire ne dépasse pas la grille de bits de la zone de mot machine dans laquelle ils sont écrits.
Plus il y a de chiffres binaires, l'équivalent binaire du nombre est représenté, plus l'erreur de présentation est petite. Cela explique la volonté d'augmenter constamment la capacité du registre opérationnel du processeur.
Tout nombre décimal dont l'équivalent binaire contient le nombre de chiffres significatifs qui dépasse la grille de bits d'un mot machine ne peut être représenté qu'environ.
Les opérations arithmétiques, qui entraînent un résultat avec dépassement de la profondeur de bits de la mantisse du mot machine, renvoient un nombre approximatif.
Les nombres approximatifs peuvent contenir des nombres vrais, douteux et incorrects.
Des nombres incorrects dans les calculs affectent la précision et peuvent parfois conduire à des résultats complètement incorrects [3].
Conformément à la théorie des calculs approximatifs, pour obtenir des résultats corrects, les nombres approximatifs sont arrondis de manière à exclure les nombres incorrects [6].
La précision que l'utilisateur souhaite ou peut obtenir dans les calculs est déterminée par le nombre de chiffres valides fournis par l'algorithme de calcul.
Tout nombre binaire peut être arrondi au nombre spécifié de chiffres binaires, en supprimant les bits supplémentaires.
De même, tout nombre décimal peut être arrondi au nombre requis de chiffres décimaux, en supprimant les chiffres supplémentaires.
Vous ne pouvez pas simplement supprimer des chiffres binaires supplémentaires dans un nombre binaire pour arrondir son équivalent décimal à un nombre donné de chiffres décimaux, car la diminution de la profondeur de bits de l'équivalent binaire d'un nombre décimal augmentera le nombre de chiffres invalides dans son équivalent décimal.
Tout nombre réel exprimé sous la forme d'une fraction décimale peut être représenté avec précision sous la forme d'un nombre à virgule flottante (TFT), dans lequel la mantisse est un entier. L'exposant au CNT indiquera la position du point dans ce numéro.
Si le nombre est présenté sous la forme d'un NTC avec une mantisse entière, alors la mantisse et l'exposant de ce nombre peuvent être convertis avec précision en code binaire.
Nouveau
Un format dans lequel la mantisse TNT décimale est représentée par l'équivalent binaire de la mantisse entière décimale et l'exposant est l'équivalent binaire de la puissance de 10 (base b = 10), sera appelé format décimal-binaire mixte (SDDF).
La différence entre le SDDF et le format TFT binaire est que l'exposant dans le SDDF est égal au degré de base b = 10, tandis que l'exposant du format TFT binaire est égal au degré de base binaire b = 2. En conséquence, pour SDDF, le nombre sera présenté
et pour la CNC, dans la norme IEEE754, comme
.
La différence entre le SDDF et le format décimal binaire (DDF ou BCD) du CTT est que dans le DDF la mantisse et l'exposant sont des nombres décimaux entiers dans lesquels chaque chiffre est écrit comme un octet ou une tétrade, tandis que dans le SDDF tous les nombres décimaux sont exprimés leurs équivalents binaires entiers.
Ainsi, tout nombre réel décimal peut être représenté en SDDF avec un code binaire jusqu'à N chiffres décimaux significatifs.
Toutes les opérations arithmétiques sur les CTD décimaux dans SDDF sont effectuées selon les règles de l'arithmétique ordinaire, où tous les arguments sont des entiers.
Avant chaque opération arithmétique, le nombre décimal est représenté au format SDDF: [S, M, z, e]. Où est le code S du signe du nombre (0 ou 1). M est l'équivalent entier binaire de la mantisse d'un nombre avec le nombre de chiffres décimaux N. Où N est la précision des calculs. z est le signe de l'exposant, e est la valeur de l'exposant. Une telle représentation est une représentation décimale normalisée.
Par exemple, pour des calculs précis à N = 7 chiffres significatifs, le nombre 123,456 doit être représenté par 1234560 * 10 ^ -4.
La mantisse décimale minimale pour N = 7 sera M = 1 000 000.
La mantisse décimale maximale pour N = 7 sera M = 9999999.
L'équivalent binaire du nombre maximal de 7 bits 9999999 sera 100 110 001 001 011 001 111 111. Il contient 24 chiffres binaires. Par conséquent, un registre binaire de 24 bits est requis pour représenter les mantisses décimales dans la plage de 1 000 000 à 9999999.
Si dans un mot machine binaire 32 bits, dans lequel 24 chiffres sont affectés à la mantisse, un chiffre est affecté au signe du nombre S, un chiffre au signe de l'exposant z et 6 chiffres à l'exposant, alors les nombres réels décimaux peuvent être représentés dans un tel SDF précis à N = 7 nombres décimaux significatifs. Les valeurs absolues de ces nombres varient de 1 000 000 * 10 ^ -64 à 9999999 * 10 ^ 64.
Après chaque opération arithmétique, la mantisse décimale du nombre doit être normalisée et arrondie à l'entier le plus proche. Pour ce faire, l'équivalent binaire résultant de la mantisse du nombre, si nécessaire, doit être multiplié ou divisé par l'équivalent binaire de 10 à un point tel que le nombre de chiffres de l'équivalent décimal de la mantisse devient égal à N. Le nombre résultant doit être arrondi à l'entier le plus proche.
Un exemple.Trouvez, jusqu'à N = 7, le résultat de l'expression (9675,423 * 10 ^ 2-9,675421 * 10 ^ 5) * 10 ^ 6 - 199992
Calculée manuellement ou sur une calculatrice Windows, cette expression sera égale au nombre 8,000000
Nous écrivons les opérandes sous forme normalisée:
A=9,675423*10^5= 9675423*10^-1
B= 9675,421*10^2 = 9675421*10^-1
C=1000000 = 1000000*10^0
D = 1999920*10^-1Dans SDDF, ces opérandes seront représentés comme:
A=[0, 9675423,1, 1]
B=[0,9675421,1, 1]
C=[0, 1000000,0, 0]
D=[0, 1999920,1, 1]Trouvez la différence S = AB. Puisque les exposants des opérandes A et B sont les mêmes, on retrouve la mantisse de leur différence:
9675423-9675421=2Pour normaliser la mantisse S, nous devons la multiplier par 10 ^ 6, tandis que l'exposant doit être réduit de 6. Alors S = 2 * 1,000,000 = 2,000,000 * 10 ^ -7
Nous calculons le produit P = D * C. Pour ce faire, multipliez la mantisse des facteurs et ajoutez les exponentielles:
M = 2 000 000 * 10 ^ -7 * 1 000 000 * 10 * 0 = 2 000 000 000 000 * 10 ^ -7
Après normalisation de la mantisse, nous obtenons P = 2 000 000 * 10 ^ -1.
Le résultat du calcul R sera égal à:
R = PD = 2 000 000 * 10 ^ -1-1999920 * 10 ^ -1 = 80 * 10 ^ -1
Après normalisation, nous obtenons R = 8000000 * 10 ^ -6.
A titre de comparaison, le calcul de cette expression dans Excel donne le résultat R = 8,0000698E + 00.
L'auteur a développé un algorithme de calcul dans le SDDF qui effectue l'addition, la soustraction, la multiplication et la division des nombres décimaux jusqu'à 18 chiffres significatifs. Pour confirmer l'exactitude de l'algorithme, un programme C ++ a été écrit. Étant donné que l'auteur n'est pas un programmeur professionnel, le programme développé est destiné uniquement à l'étude de l'algorithme de calcul.
Ci-dessous, pour un exemple, une capture d'écran illustrant le calcul de l'expression suivante:
1,23456789098765432*10^8 * 9,87654321234567891*10^(-9) - 1,2193263123914037*10^0≈ 3.0*10^(-17)
Pour tester les performances, l'opération de multiplication de deux nombres de 18 bits a été lancée dans un cycle. Le programme s'exécutait sur un ordinateur Intel® Core (TM) i3-4330 CPU@3.50GHz 3,50 GHz. RAM 8,0 Go. Type de système: 64 bits La vitesse était égale à multipl 2,4 * 10 ^ 6 multiplications par seconde.
Je ne peux pas comparer avec la vitesse des calculatrices Windows et Excel jusqu'à présent, il n'y a pas assez d'éducation :(. Quant à la précision des calculs, c'est la même chose que si les calculs étaient faits manuellement.
Références:
- Vue latérale: norme IEEE754
- La normalisation du flotteur est-elle nécessaire?
- Erreurs arithmétiques binaires fatales lors de l'utilisation de nombres à virgule flottante
- Encore une fois sur les nombres à virgule flottante
- Systèmes de numérotation
- Règles de base pour les calculs approximatifs