De la construction des réels à la norme IEEE 754

11 avril 2020 — Introduction, Python

Fractions et nombres rationnels

Nous avons vu ce que sont les entiers naturels $\N$, qui nous permettent de compter des quantités « avec les doigts ». Si maintenant, nous souhaitons compter des quantités non-entières, comme des parts de gâteaux, et pouvoir les comparer, il faut introduire des fractions.

On définit ainsi pour deux entiers $m \isin \Z$ et $n \isin \N, n \neq 0$ le nombre $m \over n$ correspondant à $m$ parts de gâteaux coupés en $n$ parts égales.

Si l’on prend un gâteau coupé en parts deux fois plus petites, il faut en servir deux fois plus pour arriver à la même quantité, et le même raisonnement en remplaçant $2$ par $k \isin \N, k \neq 0$ justifie que : $\frac{m}{n} = \frac{k \times m}{k \times n}$.

Pour cette raison, on peut donc toujours réduire une fraction en éliminant les diviseurs communs et supposer que $\gcd(m,n) = 1$ ($m$ et $n$ sont dits premiers entre eux).

Les nombres que l’on peut ainsi écrire sous forme de fraction s’appellent les nombres rationnels et forment un ensemble noté $\Bbb{Q}$.

Notion de corps

L’ensemble $\Bbb{Q}$ partage certaines propriétés avec $\Z$ :

• il est muni d’une addition : ${\cfrac{a}{b} + \cfrac{c}{d} = \cfrac{a \times d + c \times b}{b \times d}}$
• chaque nombre $x$ dans $\Bbb{Q}$ a un opposé, noté $-x$
• il est muni d’une multiplication : ${\cfrac{a}{b} \times \cfrac{c}{d} = \cfrac{a \times c}{b \times d}}$

Chaque nombre non nul dans $\Bbb{Q}$ (notons le $a \over b$, avec $a \neq 0$) a un inverse pour la multiplication : $(\cfrac{a}{b})^{-1} = \cfrac{b}{a}$ (propriété qui n’est pas vraie dans $\Z$).

Ces propriétés sont caractéristiques d’une catégorie d’ensembles que les mathématiciens appellent les corps.

💡 La notion de corps est au coeur des mathématiques et de ses applications. Les corps finis sont notamment utilisés en cryptographie et le corps des nombres complexes que nous verrons plus tard est au coeur de la physique.

Dans la suite, nous allons construire le corps des nombres réels $\R$, qui est celui des nombres que nous manipulons habituellement.

💻 Les rationnels en Python

Nous allons utiliser le module fractions, qui fait partie de la bibliothèque standard de Python. Son usage reste assez limité dans la pratique, mais il est intéressant d’un point de vue didactique.

Ce module définit notamment un type Fraction qui permet d’effectuer des calculs sur les nombres rationnels (comme nous le verrons, les nombres flottants ne permettent que du calcul approximatif, certaines fractions se retrouvant automatiquement tronquées).

from fractions import Fraction
>>> Fraction(19, 23) + Fraction(13, 42)
Fraction(1097, 966)

Développements en base décimale, binaire, …

Les nombres décimaux sont les fractions qui peuvent s’écrire avec un dénominateur qui est une puissance de 10, c’est-à-dire sous la forme $x = \cfrac{m}{10^d}$ où $m \isin \Z$ et $d \isin \N$.

Si $m$ n’est pas divisible par $10$, le nombre $d$ correspond au nombre de chiffres après la virgule dans l’écriture décimale de $x$.

Par exemple : $\cfrac{389532}{10^3} = 389.532$

Un nombre rationnel peut toujours s’approximer par un nombre décimal avec $d$ chiffres après la virgule, l’erreur d’approximation étant alors inférieure à $10^{-d}$.

L’algorithme suivant permet d’obtenir ce développement, sous la forme de la partie entière puis des premiers chiffres décimaux :

def decimals_dev(x: Fraction, digits=10):
    for _ in range(digits + 1):
        q, r = x.numerator // x.denominator, x.numerator % x.denominator
        yield q
        if r == 0:
            break
        x = Fraction(10 * r, x.denominator)

On a :

>>> list(decimals_dev(Fraction(987654321, 16)))
[61728395, 0, 6, 2, 5]
>>> list(decimals_dev(Fraction(1, 3), digits = 20))
[0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

De la même façon, on peut écrire le développement d’un nombre rationnel en base $n > 0$. Par exemple, si $n = 2$ il s’agit du développement binaire.

💻 Modifier le code précédent pour obtenir la fonction binary_dev qui donne le développement binaire d’un nombre.

On observe :

>>> list(binary_dev(Fraction(1, 2)))
['0', '1']
>>> list(binary_dev(Fraction(343, 16)))
['10101', '0', '1', '1', '1']
>>> list(binary_dev(Fraction(1, 10)))
['0', '0', '0', '0', '1', '1', '0', '0', '1', '1', '0']

💡 On notera en particulier que tous ces développements présentent une périodicité : on peut montrer que les développpements des nombres rationnels sont toujours constitués de séquences qui se répètent, quelle que soit la base utilisée.

Questions :

• À quelle condition sur le dénominateur d’un nombre rationnel, son développement binaire est-il fini (nombre de chiffres fini) ?
• Montrer qu’un nombre rationnel dont le développement binaire est fini admet un développement décimal fini, mais que la réciproque n’est pas vraie.
• Dans quelle base le développement de $1 \over 3$ sera-t-il fini ?

Une séquence mystérieuse

Considérons la suite de nombre rationnels $(x_n)_{n \geq 0}$, définie par la formule récurrente suivante :

$x_0 = 1$ et $x_{n+1} = \frac{1}{2} (x_n + \cfrac{2}{x_n})$

Le programme Python suivant va nous aider à calculer les premières valeurs de cette suite :

def magic_sequence(n, x_0=Fraction(1)):
    x = x_0
    for i in range(n):
        x = (x + 2 / x) / 2
        yield x

>>> for x in magic_sequence(5):
...     print(x)
... 
3/2
17/12
577/408
665857/470832
886731088897/627013566048

On constate que cette suite prend pour valeurs des fractions avec un dénominateur toujours plus grand — c’est-à-dire avec une précision toujours plus grande, par exemple :

À quoi peuvent bien ressembler les développements décimaux de ces nombres ? Nous savons le déterminer simplement :

>>> for x in magic_sequence(5):
...     print(list(decimals_dev(x, digits=20)))
... 
[1, 5]
[1, 4, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
[1, 4, 1, 4, 2, 1, 5, 6, 8, 6, 2, 7, 4, 5, 0, 9, 8, 0, 3, 9, 2]
[1, 4, 1, 4, 2, 1, 3, 5, 6, 2, 3, 7, 4, 6, 8, 9, 9, 1, 0, 6, 2]
[1, 4, 1, 4, 2, 1, 3, 5, 6, 2, 3, 7, 3, 0, 9, 5, 0, 4, 8, 8, 0]

Quel est donc ce nombre mystérieux dont on obtient le développement décimal ?

Les observateurs avisés auront reconnu une approximation de $\sqrt{2}$, soit par exemple en calculant $x_7$ avec $50$ décimales :

Mais ce nombre en est-il vraiment un ? Et si oui, en quel sens ?

La suite précédente nous montre que si on veut s’approcher d’un nombre dont le carré est $2$ avec des rationnels, il faut considérer des fractions toujours plus précises (c’est-à-dire, avec un dénominateur toujours plus grand).

En fait, c’est la conséquence d’un résultat fondamental : $\sqrt{2}$ n’existe pas sous forme de fraction, mais on peut trouver une suite de fractions qui converge vers ce nombre.

💡 La suite utilisée précédemment pour approximer $\sqrt{2}$ par des rationnels correspond à une idée très ancienne. C’est la méthode de Héron.

Pas de $\sqrt{2}$ dans $\Bbb{Q}$

Il n’existe pas de nombres entiers $m$ et $n \neq 0$ tels que ${(\frac{m}{n})^2 = 2}$, autrement dit ${\sqrt{2} \notin \Bbb{Q}}$.

Ce résultat très classique peut se prouver en utlisant la décomposition unique d’un entier en facteurs premiers, vue à l’article précédent.

On écrit $m$ et $n$ comme produits de nombres premiers, en isolant le facteur correspondant à $2$ et les autres facteurs, dont on note les produits $a$ et $b$ :

${m = 2^i \times a}$ et ${n = 2^j \times b}$

On a alors : ${2 = (\frac{m}{n})^2 = \cfrac{2^{2i} \times a^2}{2^{2j} \times b^2}}$

Soit encore : ${2^{2j + 1} \times b^2 = 2^{2i} \times a^2}$

Cette dernière égalité est impossible car par unicité de la décomposition en facteurs premiers on aurait alors ${2j + 1 = 2i}$ (égalité entre un nombre impair et un nombre pair).

💡 Le résultat et sa preuve restent valables en remplaçant $2$ par n’importe quel autre nombre premier.

Les nombres réels $\R$

Définition par développements décimaux infinis

Une intuition classique pour définir les nombres réels, est de considérer qu’ils sont définis comme limite d’une suite infinie de nombres décimaux.

Dans notre suite étudiée précédemment, on a ainsi obtenu pour $\sqrt{2}$ :

Ci-dessus, on observé que la partie en gras du développement décimal reste figée (c’est-à-dire, elle est la même dans les itérations suivantes).

On peut alors définir $\sqrt{2}$ comme la suite des développements décimaux obtenus: $1$, $1.4$, $1.414$, etc.

Cette première approche est correcte mathématiquement, tout nombre réel pouvant être approché par des développements décimaux infinis.

Choix de base arbitraire

Cette définition donne cependant un rôle particulier à la base $10$, alors qu’un nombre réel représente une quantité qui n’est intrinsèquement liée à aucune base.

Par exemple, on peut aussi définir un nombre réel comme une limite de développements binaires. Par exemple pour $\sqrt{2}$ :

>>> for x in magic_sequence(5):
...     print(list(binary_dev(x, digits=20)))
... 
[1, 1]
[1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0]
[1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0]

D’où le développement approché en binaire :

$\sqrt{2} \approx 1.01101010000010011110_2$

Définition par les suites de Cauchy

Une définition équivalente des nombres réels $\R$, plus générique, utilse des suites avec une propriété particulière, qu’on appelle des suites de Cauchy.

Intuitivement, une suite de Cauchy dans $\Bbb{Q}$ est une suite dont les valeurs se rapprochent de plus en plus, comme pour une suite convergente — mais dont on ne peut pas toujours exprimer de limite dans $\Bbb{Q}$.

En quel sens les valeurs se rapprochent-elles ?

Si l’on considère une distance $\epsilon \isin \Bbb{Q}$, aussi petite soit-elle, à partir d’un certain indice $N$ les éléments de la suite seront tous à une distance inférieure à $\epsilon$ les uns des autres. En voici la traduction mathématique :

${\forall \epsilon > 0, \exists N \isin \N, \forall m, n \gt N, |x_m - x_n| < \epsilon}$

Si l’on fixe une base numérique, les suites de Cauchy de $\Bbb{Q}$ sont caractérisées par la propriété suivante : leurs premiers chiffres (digits) finissent toujours par se figer quand on itère.

Par exemple, en base $10$, si l’on considère $\epsilon = 0.001$, la définition nous garantit que la suite finira par prendre des valeurs dont tous les chiffres jusqu’à la deuxième décimale coincident.

Ainsi, toutes les suites que l’on a étudiées précédemment sont de Cauchy :

• Notre suite convergeant vers $\sqrt{2}$ car on a vu que ses décimales se figent progressivement
• Toute suite des développements décimaux d’un nombre quelconque (par construction, les premières décimales sont figées)
• Toute suite des développements binaires d’un nombre quelconque (même argument)

On peut définir $\R$ comme l’ensemble des suites de Cauchy de nombres rationnels, regroupées par suites « équivalentes » :

si la différence entre deux suites converge vers $0$, alors elles sont dites équivalentes et définissent un seul et même nombre réel (par ex. $1.000... = 0.999...$).

Le nombre $\sqrt{2}$ peut ainsi être défini par n’importe laquelle de ces suites (de Cauchy) :

• la suite de ses développements décimaux
• celle de ses développements binaires
• la suite définie par notre magic_sequence étudiée au départ
• par cette même suite, mais pour laquelle on change la valeur de $x_0$ ($1$ dans notre exemple, mais on aurait pu prendre $2$ ou $100$, ce qui aurait simplement affecté la vitesse de convergence)

Dans tous les cas, les suites obtenues sont équivalentes et définissent le même nombre de $\R$.

Petit résumé

Avant d’étudier les problématiques liées aux nombres en informatique, résumons ce que l’on a vu:

• On part des nombres entiers naturels $\N$, qui servent à « compter avec les doigts ».
• On construit les entiers relatifs $\Z$, qui expriment des différences entre deux nombres, positives ou négatives.
• Pour pouvoir compter des « parts de gâteaux », non entières, on construire le corps des fractions $\Bbb{Q}$.
• On constate que certains nombres, par exemple $\sqrt{2}$, n’existent pas comme fractions mais qu’on peut constuire des suites de fractions qui les approximent de façon toujours plus précise.
• On introduit la notion de suite de Cauchy, ces suites dont les termes se rapprochent toujours plus.
• $\R$ est l’ensemble des suites de Cauchy à valeurs dans $\Bbb{Q}$.
  Celles qui sont équivalentes (leur différence tend vers $0$) définissent le même nombre.
• $\R$ peut aussi être vu comme l’ensemble des développements décimaux infinis, mais la définition précédente évite la référence à une base particulière.

💻 Et en informatique ?

Le cadre mathématique définit, avec les nombres réels $\R$, les nombres que l’on s’attend à pouvoir manipuler.

On s’attend ainsi à pouvoir manipuler informatiquement des nombres comme $23$, $1 \over 3$, $\pi$, $\sqrt{2}$, etc.

Dans la pratique, ces nombres sont d’ailleurs généralement accessibles via la bibliothèque standard des langages, par ex.:

>>> import math
>>> math.pi
3.141592653589793
>>> math.sqrt(2)
1.4142135623730951
>>> 1/3
0.3333333333333333

L’utilisation de ces nombres présente cependant des limites, conséquences de deux contraintes fondamentales du monde de l’informatique :

• Les données sont stockées et circulent sous forme binaire (en RAM, sur disque, dans les câbles, etc.)
• La mémoire est finie. En particulier, le nombre de bits alloués par défaut pour un nombre est généralement limité.

Ceci peut avoir des conséquences inattendues.

Représentation des entiers

Il y aurait beaucoup à dire sur le cas des entiers, qui sont représentés en mémoire à l’aide d’un nombre fixe de chiffres binaires (8, 16, 32, 64, …), et prennent donc leurs valeurs dans une plage limitée. Ces limites dépendent également de si ces entiers sont signés (représentent des nombres de $\Z$) ou non (représentent des nombres de $\N$).

Ces représentations de taille fixée induisent des limites qu’il faut connaître, en particulier lorsque l’on utilise un langage bas niveau comme le C.

Les entiers en Python 3

Python implémente les entiers par des objets de taille variable, la mémoire étant allouée en fonction du nombre de chiffre nécessaires pour permettre une précision arbitraire (la seule limite étant alors la mémoire disponible à l’allocation).

Contrairement au C, il n’existe donc pas de limite du type INT_MAX en Python.

Pour en savoir plus sur les subtilités de l’implémentation des entiers en Python, je vous renvoie à cet article.

Représentation des flottants

Contrairement aux entiers, les nombres réels ne sont représentés en Python que de façon approximative. Il serait de toute façon illusoire d’espérer pouvoir stocker en mémoire toutes les décimales de $1 \over 3$, $\pi$ ou $\sqrt{2}$, puisqu’il y en a une infinité.

La fonction suivante, qui utilise le module struct de Python, permet d’obtenir la représentation binaire d’un nombre flottant :

import struct
from math import pi, sqrt
def show_binary_rep(num):
    print('{:064b}'.format(*struct.unpack(">Q", struct.pack(">d", num))))
>>> show_binary_rep(42)
0100000001000101000000000000000000000000000000000000000000000000
>>> show_binary_rep(pi)
0100000000001001001000011111101101010100010001000010110100011000
>>> show_binary_rep(sqrt(2))
0011111111110110101000001001111001100110011111110011101111001101
>>> show_binary_rep(1/10)
0011111110111001100110011001100110011001100110011001100110011010

On observe en particulier que ces nombres sont représentés sur 64 bits. Concrètement, Python comme beaucoup de langages utilise la norme IEEE 754 et la précision double pour la représentation des nombres réels. Ce n’est qu’une représentation approximative.

Cette représentation binaire se compose en fait de 3 parties : 1 bit de signe, 11 bits d’exposant et 52 bits pour la mantisse (chiffres significatifs).

Elle correspond à l’écriture d’un nombre sous la forme ${x = \pm 1 \times 2^{exposant} \times mantisse}$.

La table suivante donne cette décomposition pour les exemples précédents :

Quelques remarques :

• L’exposant est signé (voir la règle du complément à deux)
• Le premier chiffre significatif de la mantisse est toujours omis (il est implicite).
  Ainsi $42 = 00101010 = 2^2 \times 1.0101000$ mais le premier $1$ n’apparait pas.
• Les développements de $\pi$ et $\sqrt{2}$ sont tronqués, donc approximatifs (ce sont des nombres irrationnels, donc ils ne peuvent certainement pas s’écrire avec un nombre de chiffres finis, quelle que soit la base).

Le cas de $0.1 = {1 \over 10}$ est plus subtil.

Ce nombre s’écrit en base décimale de façon exacte avec un chiffre significatif. Son développement binaire est en revanche $0.000110011001100...$ avec une séquence qui se répète à l’infini. Sa représentation tronquée est donc forcément approximative.

En fait, le nombre stocké en mémoire lorsque l’on saisit $0.1$ dans son terminal est le suivant : $0.1000000000000000055511151231257827021181583404541015625$

Très proche, mais pas identique.

Quelles conséquences pratiques ?

Cette approximation a des conséquences qu’il est important d’avoir en tête lorsque l’on manipule des nombres, en particulier pour des quantités que l’on voudrait exacte (montant de transaction, etc.).

Par exemple en Python (je vous laisse vérifier ce résultat, dans la plupart des langages classiques, utilisant la même norme) :

>>> 0.1 + 0.2
0.30000000000000004

😯

Que s’est-il passé ?

Ce résultat surprenant est simplement la conséquence de la valeur approximative des deux termes sommés.

Il est plus grand que $3$ car les représentations binaires sont arrondies vers le haut, lorsqu’elles sont tronquées.

De façon pratique, lorsque l’on souhaite manipuler des montants décimaux en Python (valeurs monétaires, etc.), on privilégiera l’utilisation de types dédiés comme Decimal (voir aussi la doc. Python à ce sujet).

from decimal import Decimal
>>> Decimal('0.1') + Decimal('0.2')
Decimal('0.3')

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• ← Arithmétique des entiers, base64 et algorithme d'Euclide
• Arithmétique modulaire, RSA et clefs privées →