Représentation des nombres en machine

3.1 Introduction et Motivation

Dans ce chapitre, nous allons nous intéresser à la façon dont un nombre (qu'il soit entier ou réel) est représenté en mémoire à l'intérieur d'un ordinateur. La mémoire des ordinateurs est découpée en blocs élémentaires de 8 bits (un octet) et les processeurs modernes de 64 bits travaillent généralement avec des registres de 8 octets (soit 64 bits).

Disposant d'un nombre fini de bits pour représenter un ensemble infini de nombres mathématiques, il est indispensable de comprendre comment les nombres sont codés en base 2 pour anticiper les limites physiques du matériel (dépassements de capacité) et les erreurs d'arrondis qui peuvent fausser des simulations numériques sensibles.

3.2 Représentation dans une Base

Nous utilisons naturellement l'écriture décimale (base 10) depuis l'enfance. Plus généralement, pour tout entier base $b\ge 2$, on peut définir la représentation d'un entier en convenant que l'écriture positionnelle $(a_p{a}_{p-1}\dots a_0{)}_b$ représente le nombre :

$$x=a_p{b}^p+a_{p-1}{b}^{p-1}+\cdots +a_1{b}^1+a_0{b}^0=\sum _{k=0}^p{a}_k{b}^k$$

Pour assurer l'unicité de l'écriture, on impose pour chaque chiffre $a_k$ la contrainte $a_k\in \{0,1,\dots ,b-1\}$ et $a_p\ne 0$.

3.2.1 Écriture en Base 2

En base 2 (système binaire), seuls les chiffres 0 et 1 sont autorisés. Les opérations arithmétiques élémentaires s'y effectuent de façon similaire à la base 10 :

3.2.2 Algorithmes de Changement de Base

Pour convertir une chaîne représentant un nombre écrit en base $b$ vers son équivalent entier en base 10, nous pouvons implémenter la formule directe ou appliquer de manière plus efficace le schéma de Horner :

# Algorithme direct avec calculs de puissances
def base10_direct(x, b=2):
    s = 0
    k = len(x) - 1
    for a in x:
        s += int(a) * (b ** k)
        k -= 1
    return s

# Algorithme de Horner (sans puissance, O(n) multiplications)
def base10_horner(x, b=2):
    u = 0
    for a in x:
        u = b * u + int(a)
    return u

Pour l'opération inverse (conversion d'un entier décimal vers sa représentation en base $b$), on effectue des divisions euclidiennes successives par la base $b$ :

def baseb(x, b=2):
    s = ''
    y = x
    while y > 0:
        s = str(y % b) + s
        y //= b
    return s if s != '' else '0'

3.2.3 Cas Particuliers : Base 2 et Base 16

En Python, il est possible de saisir directement des littéraux dans d'autres bases :

• Binaire (base 2) : préfixe 0b (ex. 0b1011011 vaut 91).
• Hexadécimal (base 16) : préfixe 0x. Les chiffres de 10 à 15 sont représentés par les lettres de a à f (ex. 0xa27c vaut $10\times 16^3+2\times 16^2+7\times 16+12=41596$).

Comme $16=2^4$, un chiffre hexadécimal correspond exactement à un groupe de 4 bits. Les fonctions intégrées bin(x) et hex(x) réalisent ces conversions vers des chaînes de caractères formatées.

3.3 Codification des Nombres Entiers

Les ordinateurs manipulent des types d'entiers à taille fixe au niveau du processeur.

3.3.1 Les Entiers Naturels

Sur $n$ bits, on peut coder les entiers de l'intervalle $[0,2^n-1]$. Pour $n=64$ bits, cela permet d'adresser des cellules mémoire allant de $0$ à $2^{64}-1\approx 1.84\times 10^{19}$.

3.3.2 Les Entiers Relatifs et le Complément à Deux

Pour coder les entiers relatifs, on doit pouvoir représenter le signe. La solution standard est le codage en complément à deux.

Le premier bit (le bit de poids fort) sert naturellement de bit de signe (0 pour positif, 1 pour négatif). Pour obtenir l'opposé $-x$ d'un nombre $x$ sous cette codification, il existe un algorithme matériel très simple :

• Inverser tous les bits de la représentation de $x$ (opération logique NON).
• Ajouter 1 au résultat.

3.3.3 Dépassement de Capacité et Cyclicité

L'addition binaire en complément à deux présente l'immense avantage que l'unité arithmétique et logique (ALU) traite les nombres signés exactement comme des nombres non signés, en tronquant simplement le résultat aux $n$ bits de poids faible.

Toutefois, si le résultat d'une opération sort de l'intervalle $[-2^{n-1},2^{n-1}-1]$, un dépassement de capacité (overflow) survient : la structure est cyclique. Le successeur du plus grand entier positif $2^{n-1}-1$ est le plus petit entier négatif $-2^{n-1}$.

3.4 Codification des Nombres Réels (Flottants)

Un nombre possédant une écriture décimale finie est un nombre décimal (de la forme $x\cdot 10^{-n}$). De même, un nombre représentable par une écriture binaire finie est un nombre dyadique.

3.4.1 Le problème de la conversion binaire

La plupart des nombres décimaux (tels que $0.1$ ou $0.2$) ne sont pas des nombres dyadiques. Leur développement en base 2 est infini et périodique :

$$0.1=(0.00011001100110011\dots {)}_2$$

Par conséquent, lorsqu'on saisit 0.1 dans un programme, l'ordinateur le tronque pour le stocker, introduisant une erreur d'arrondi dès le départ.

>>> 0.1 + 0.2
0.30000000000000004

Pour tester l'égalité de nombres réels en programmation scientifique, on doit toujours utiliser une tolérance (ou seuil de précision $\epsilon$) :

# Utilisation d'une marge absolue
if abs((0.1 + 0.2) - 0.3) <= 1e-10:
    print("Égalité approchée")

3.4.2 La Norme IEEE-754 (Double Précision 64 bits)

Les nombres à virgule flottante sont codés en standard IEEE-754 double précision sur 64 bits selon la répartition suivante :

• 1 bit de signe ($s$) : 0 pour positif, 1 pour négatif.
• 11 bits d'exposant ($e^{\prime }$) : stocke l'exposant décalé par un biais de $1023$, soit $e^{\prime }=e+1023$.
• 52 bits de mantisse ($m$) : stocke la partie fractionnaire de la forme normalisée $1.b_1{b}_2\dots b_{52}$.

Le nombre réel représenté sous forme normalisée est :

$$x=(-1{)}^s\times (1+m)\times 2^e$$

avec $e=e^{\prime }-1023$.

Les exposants extrêmes ont des significations particulières :

• $e^{\prime }=0$ : représente les nombres dénormalisés (au voisinage de $0$, de la forme $\pm 0.m\times 2^{-1022}$). Si $m=0$, le nombre vaut $\pm 0.0$.
• $e^{\prime }=2^{11}-1=2047$ : représente l'infini (inf si $m=0$) ou les calculs impossibles (nan - Not a Number, si $m\ne 0$, comme 0/0 ou inf - inf).

3.5 Calculs Flottants et Phénomènes Numériques

L'arithmétique flottante induit des comportements non intuitifs qui exigent une vigilance particulière.

3.5.1 L'Absorption Numérique

L'addition de deux nombres flottants d'ordres de grandeur très différents provoque la perte des chiffres significatifs du plus petit nombre. C'est l'absorption. En précision double, la mantisse ne codant que 52 bits (soit environ 15 à 17 chiffres décimaux significatifs), l'opération suivante :

>>> (1.0 + 2.0**53) - 2.0**53
0.0

renvoie 0.0 car la valeur 1.0 est totalement absorbée lors de l'addition. Pour corriger cela, il faut réorganiser les calculs :

>>> 1.0 + (2.0**53 - 2.0**53)
1.0

3.5.2 La Cancellation (Perte de Précision par Soustraction)

Lorsqu'on soustrait deux nombres très proches, les chiffres significatifs communs s'annulent, et le résultat est dominé par des erreurs d'arrondis initiales. C'est la cancellation.

3.5.3 Étude de Cas : La Catastrophe du Missile Patriot (1991)

Le 25 février 1991, une batterie de missiles Patriot américaine a manqué l'interception d'un missile Scud irakien à Dharan, causant la mort de 28 soldats. La commission d'enquête a identifié une simple erreur d'arrondi dans le logiciel de calcul de temps :