11. Arithmétique de l'ordinateur

11.1 Types entiers

Ces types correspondent généralement aux entiers de l'ordinateur utilisé. Les notices du constructeur et de l'auteur du compilateur donneront des informations sur leurs caractéristiques physiques (nombre de chiffres binaires, notamment, dont se déduit la valeur absolue maximum). Une machine à mots de 32 bits autorisera des entiers compris entre -2 147 483 648 et 2 147 483 647.

11.1.1 Principe de représentation

La représentation des nombres est en général caractéristique de l'architecture d'un ordinateur donné, et non pas du langage de programmation utilisé. Les lignes qui suivent décrivent la représentation des nombres entiers en « virgule fixe » et valent pour la plupart des ordinateurs contemporains et la plupart des langages de programmation.

Si la représentation des entiers positifs se fait selon la notation de position usuelle et n'appelle pas de remarques particulières, celle des nombres négatifs se fait par la méthode du « complément à 2 », qui appelle une description. Cette méthode, plus complexe au premier abord, simplifie la conception des algorithmes de calcul comme nous allons le voir.

Soit un ordinateur dont l'architecture matérielle met à notre diposition, pour représenter les entiers, des emplacements de n positions en base B. Nous pouvons représenter Bⁿ nombres différents : nous prenons ceux compris entre -Bⁿ/2 et (Bⁿ/2)-1. La représentation se fera comme suit :

les nombres compris entre 0 et (Bⁿ/2)-1, soit Bⁿ/2 nombres, seront représentés selon la notation usuelle de position ; remarquons que le chiffre de poids fort (rang n) est toujours 0 pour ces nombres ;
pour représenter au moyen des combinaisons restantes les Bⁿ/2 nombres compris entre -1 et -Bⁿ/2 nous leur ferons correspondre, dans cet ordre, les nombres à n chiffres binaires compris entre Bⁿ/2 et Bⁿ-1. Cela revient à dire que le chiffre de poids fort (rang n) est toujours égal à 1 et qu'un nombre négatif p sera représenté par le nombre obtenu en remplaçant chacun des chiffres de -p par son complément à 2 et en additionnant 1 au résultat.

Prenons un exemple avec B=2 et n=4. Les entiers représentés seront tels que décrits dans la table ci-dessous :

Représentation physique	Nombre représenté
(chaîne de chiffres binaires)
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7
1000	-8
1001	-7
1010	-6
1011	-5
1100	-4
1101	-3
1110	-2
1111	-1

L'intérêt de cette notation réside dans le fait que l'addition peut se faire selon le même algorithme, quel que soit le signe des opérandes, il suffira « d'oublier » la retenue éventuelle qui donnerait un n+1ème chiffre. Évidemment, si le calcul excède la capacité physique de la représentation il y aura une erreur.

11.2 Types fractionnaires

11.2.1 Les « réels »

Ces types usurpent volontiers le qualificatif « réel », et correspondent aux nombres en virgule flottante de l'ordinateur utilisé, dont la notice du constructeur et celle de l'auteur du compilateur comportent une description. Ils servent à représenter les nombres « avec des chiffres après la virgule ».

La norme IEEE 754 définit deux formats de nombres fractionnaires que l'on retrouve sur la plupart des ordinateurs. Elle est le plus généralement implantée physiquement sur l'ordinateur, c'est à dire que les lignes qui suivent ne s'appliquent pas à un langage particulier, mais à l'utilisation de la plupart des ordinateurs et de la plupart des langages de programmation.

Un type fractionnaire est défini sur un sous-ensemble borné, incomplet et fini des rationnels. En effet, le « nombre de chiffres après la virgule » est limité par la taille physique d'une représentation concrète. Un tel type peut être utilisé pour représenter approximativement les nombres réels.

11.2.2 Principe de représentation

Les nombres fractionnaires sont représentés dans les registres des ordinateurs selon le principe de la virgule flottante. Ce principe est inspiré de la notation familière aux scientifiques, qui préfèrent écrire 197.10⁶ plutôt que 197 000 000.

Soit un système de numération de base B (entier positif), un nombre x pourra être représenté par le doublet :

$\begin{displaymath}[m,p]\mbox{ tel que : }x = m . B^p \end{displaymath}$

m, la mantisse du nombre x, est un nombre positif compris entre :

$\begin{displaymath}1\mbox{ (compris) et }B\mbox{ (exclus),} \end{displaymath}$

ou nul si x=0. Ceci correspondrait, en notation décimale usuelle, à des nombres tels que :

$\begin{displaymath}1,000000000\mbox{ à }1,9999999999 \end{displaymath}$

Cette mantisse m sera représentée par un nombre fixe de S chiffres binaires : elle pourra donc prendre 2^S valeurs différentes.

L'exposant p sera un entier compris entre deux valeurs MIN et MAX.

Les quatre entiers B (la base), N (le nombre de chiffres significatifs de la mantisse), MIN et MAX (les bornes de l'exposant) suffisent à définir un système de virgule flottante. Tout nombre réel de l'intervalle :

]-BMAX, +BMAX[

sera approché par un nombre représentable exactement, c'est à dire de la forme :

x = m .B^p

La norme IEEE 754 définit deux types de nombres en virgule flottante, en simple ou double précision. On donne aussi les caractéristiques de la double précision sur Cray YMP, qui ne respecte pas la norme :

	Simple précision	Double précision	Cray (double)
B	2	2	2
MIN	-126	-1022	-16382
MAX	127	1023	16383
S	24	53	48

plus petite
valeur absolue	1,1754944.10^-38	2,225073858507201.10^-308

plus grande
valeur absolue	3,4028235.10⁺³⁸	1,797693134862317.10⁺³⁰⁸

On remarquera qu'avec des emplacements de même taille physique pour placer les nombres, Cray privilégie la largeur de l'intervalle utilisable (ce que l'on appelle la « dynamique » de la représentation) aux dépens de la précision. D'autre part la représentation IEEE est dite « normalisée », c'est à dire que le premier chiffre de la mantisse (devant la virgule) est toujours égal à 1 et que l'on peut donc se dispenser de le stocker, ce qui assure 53 chiffres significatifs sur 52 bits. La virgule flottante Cray n'est pas normalisée, ce qui accroît encore la dynamique et diminue la précision.

Voici à titre d'illustration le format physique d'un nombre à la norme IEEE simple précision :

**Figure 11.1:** Format d'un nombre en virgule flottante
$\includegraphics{../Images/Arithmetique/nb-flottant.epsi}$ 59

S	le bit de signe, 0 pour un nombre
	positif, 1 pour un nombre négatif ;

Exposant	exposant binaire « biaisé », c'est à dire
	que s'il est représenté sur E chiffres
	binaires (E=8 ici), on ajoute à sa valeur
	effective 2^E-1, afin de n'avoir à
	représenter que des valeurs positives ;

Mantisse	une valeur fractionnaire. Un bit à 1 implicite
	figure « à gauche » du bit 22. La virgule est à
	droite du bit implicite.

En fait, la norme IEE754 est plus complexe que le résumé que nous en donnons, et elle admet des variantes. Les valeurs conventionnelles suivantes sont définies, ici en simple précision (les valeurs des mantisses et des exposants sont les configurations binaires physiques) :

Nom	Valeur	Signe	Exposant	Mantisse
zéro positif	+0	0	0	0
zéro négatif	-0	1	0	0
infini positif	$+\infty$	0	255	0
infini négatif	$-\infty$	1	255	0
NaN (not a number)	aucune	1 ou 0	255	différente de 0

11.2.3 Exemple

Un exemple simple illustrera quelques aspects intéressants de ce type de représentation. Soit un système où B=2, N=3, MIN=-1 et MAX=2, les nombres susceptibles d'être représentés exactement sont les suivants :

	p = - 1	p = 0	p = + 1	p = + 2
m = (1,00)₂ = 1	1/2	1	2	4
m = (1,01)₂ = 5/4	5/8	5/4	5/2	5
m = (1,10)₂ = 3/2	3/4	3/2	3	6
m = (1,11)₂ = 7/4	7/8	7/4	7/2	7

**Figure:** Axe des nombres représentés
$\includegraphics[scale=0.7]{../Images/Arithmetique/axe-nb.epsi}$ 67

Seules les valeurs positives ont été représentées dans le tableau et sur le graphique, les valeurs négatives s'en déduiraient par symétrie. On remarquera que la « densité » des nombres représentés exactement (ou la précision absolue de la représentation) est variable. Le lecteur pourra se convaincre facilement de ce qui suit :

si l'on représente les nombres réels par un tel ensemble de nombres, l'opérateur d'égalité n'est pas utilisable (non plus que l'inégalité d'ailleurs), il faut se contenter de vérifier que la différence entre deux nombres est inférieure à un seuil que l'on se donne ;
la soustraction risque de provoquer une grande perte de précision dans les calculs (cas de deux nombres « grands » mais peu différents) ;
il est dangereux d'additionner ou de soustraire des nombres d'ordres de grandeur différents, parce qu'une « mise au même exposant » sera nécessaire, au prix de la précision ;
des changements de variable judicieux peuvent augmenter la qualité des résultats ;
le premier chiffre de la mantisse vaut toujours 1 (on dit que la virgule flottante est normalisée), il sera donc sous-entendu dans le matériel.

Pour donner un tour plus concret à cet exposé, nous empruntons au Numerical Computations Guide de Sun Microsystems la table suivante, qui donne pour la représentation IEEE 754 simple précision la taille des intervalles entre deux nombres représentés exactement consécutifs, et ce pour différents ordres de grandeur :

x	nextafter	Gap
0.0	1.1754944e-38	1.1754945e-38
1.0000000e+00	1.0000001	1.1920929e-07
2.0000000e+00	2.0000002e.00	2.3841858e-07
1.6000000e+01	1.6000002e+01	1.9073486e-06
1.2800000e+02	1.2800002e+02	1.5258789e-05
1.0000000e+20	1.0000001e+20	8.7960930e+12
9.9999997e+37	1.0000001e+38	1.0141205e+31