Représentation des entiers naturels

Rappel d'ouverture (5 minutes, cours fermé)

Une case du LMC contient trois chiffres. Quel est le plus grand nombre qu'on peut y ranger, et que se passe-t-il si l'on veut y mettre 1500 ?
Pourquoi un processeur ne dispose-t-il que de deux symboles pour écrire ses nombres ?
Le nombre 306 désignait l'instruction « ranger l'accumulateur en case 06 ». Ce choix aurait-il pu être différent ?

Corrigé

999. Au-delà, la valeur ne rentre plus : il faudrait davantage de chiffres, ou bien la case déborde.
Parce que ses circuits ne savent distinguer que deux états, par exemple le passage ou non du courant. Toute l'écriture des nombres doit tenir avec deux symboles.
Oui, entièrement. C'est une convention décidée par les concepteurs de la machine : elle n'est ni vraie ni fausse, elle est seulement partagée. C'est le codage. Cette page traite d'autre chose : comment écrire les nombres eux-mêmes.

Préambule

Quel est le premier chiffre?
Quel est le dernier chiffre?
Combien y-a-t-il de chiffres?
Donnez les valeurs de $10^k$ pour $k$ allant de 0 à 5
Plus grand nombre:
- Quel est le plus grand nombre représentable sur:
  - 1 chiffres?
  - 4 chiffres?
  - 9 chiffres?
- Pour chaque résultat précédent, Ajoutez-y 1. D'après ce que vous obtenez, exprimez les solutions en vous aidant de puissances.
- Quel calcul faut-il faire pour obtenir le plus grand nombre sur 5678 chiffres?
- Donnez une formule permettant de connaître le plus grand nombre représentable sur $n>0$ chiffres.

Un peu de philosophie: Le signifiant et le signifié

Sur terre, il existe des centaines de manière de signifier qu'on parle d'un poisson.

On peut écrire et dire "poisson" en français.

On peut écrire et dire "fish" en anglais.

On peut écrire 魚, ou さかな et dire "sakana" en japonais.

alt text

Ce qu'on dit ou écrit (le signifiant) peut varier d'une personne à l'autre sur terre. L'idée qu'on désigne (le signifié), par contre, reste inchangé.

Ce qui réveille l'idée d'un poisson est différent, mais l'idée d'un poisson est globalement la même pour tous.

La relation entre le signifiant et le signifié est arbitraire. Il n'y a aucune raison qu'on choisisse un signifiant particulier pour décrire un signifié. Autrement dit, les deux n'ont pas de relation logique et doivent être apprises. Il s'agit d'une convention humaine.

Les chiffres et les nombres

Dans la vie courante, on pense d'abord aux nombres pour signifier une quantité ou un ordre.

Il y a 53 pommes dans le panier $\rarr$ cardinal
Je suis arrivé en 3ème position $\rarr$ ordinal

Pour l'instant vous n'avez été habitués qu'à dire, lire et écrire les nombres sur base de cet ensemble de dessins $<0, 1, 2, 3, 4, 5, 6, 7, 8, 9>$. On appelle chacun de ces dessins un chiffre (indo-arabe).

Au japon, leur équivalent est <零, 一, 二, 三, 四, 五, 六, 七, 八, 九> mais les nombres ne sont pas construits de la même façon que chez nous. Le Japon a totalement adopté le système de numération occidental au cours du XXème siècle. (vous remarquerez au passage qu'en France, nous utilisons toujours les chiffres romains pour écrire les siècles)

Une lettre est un dessin. Nous disposons de 26 lettres dans l'alphabet. Avec ces lettres, nous composons des mots auxquels nous attribuons un sens.

Un chiffre est un dessin. Nous disposons de dix chiffres. Avec ces chiffres, nous composons des nombres auxquels nous attribuons un sens, celui d'une quantité ou d'un ordre.

alt text

Contrairement à l'exemple du poisson, pratiquement tout le monde sur terre s'accorde maintenant sur les symboles, mais pas sur leur prononciation.

Presque tous les adultes alphabétisés sur terre comprennent le dessin $88$ de la même façon, mais peu comprennent le dessin $quatre\text{-}vingt\text{-}huit$

Il existe un nombre incroyable de signifiants pour un signifié. En voici un exemple pour le nombre 42:

Langue :

Pour aller plus loin : la notion d'alphabet

Notre liste de chiffres $<0, 1, ..., 9>$ et notre liste de lettres $<a, b, ..., z>$ ne sont que deux exemples de ce que l'informatique appelle un alphabet : un ensemble fini de symboles.

À partir d'un alphabet, en mettant les symboles bout à bout, on forme des mots (on dit aussi des chaînes). Un ensemble de mots est un langage.

Avec l'alphabet $<0, 1>$, on forme les mots du binaire.
Avec l'alphabet latin, on forme les mots du français.
Avec l'alphabet des symboles de Python, on forme les mots-clés de Python pour écrire des programmes.

C'est le point de départ de la théorie des langages formels (mots, langages, automates, expressions régulières), une branche centrale de l'informatique : c'est elle qui permet, par exemple, à Python de décider si votre code est bien écrit. Rien de tout cela n'est à connaître cette année, mais sachez que « chiffres » et « lettres » sont deux instances d'une même idée plus générale.

Les chiffres et les codes

Signifier une quantité ou un ordre n'est pas le seul usage. Une suite de chiffres peut aussi servir de code : une étiquette qui désigne autre chose, et dont la valeur ne représente ni une quantité ni un rang.

Mon numéro de téléphone est le 06... $\rarr$ code (l'additionner à un autre n'aurait aucun sens)
La lettre 'A' est codée par le nombre 65 $\rarr$ code (norme ASCII)

En réalité, ce rôle de code est le plus général, et les deux premiers n'en sont qu'un cas particulier. Représenter, c'est toujours la même opération : choisir un signifiant pour un signifié, par une convention arbitraire, comme on l'a vu plus haut.

Quand le signifié est une quantité ou un rang, on le représente avec des chiffres : c'est le cas cardinal et ordinal, et c'est précisément l'objet de ce chapitre.
Quand le signifié est une lettre, une couleur ou un son, on lui associe un nombre, qui sera lui-même écrit avec des chiffres.

Autrement dit, « signifier une quantité avec des chiffres » n'est qu'une façon de coder parmi d'autres. C'est l'idée centrale de tout ce qui suit : la machine ne sait manipuler que des nombres, et au fond uniquement des 0 et des 1. Pour qu'un ordinateur traite un texte, une image ou un son, il faut donc d'abord coder cette information sous forme de nombres. Nous le retrouverons très concrètement en codant les caractères.

La roue des chiffres

Vocabulaire

Incrémenter est l'action d'ajouter un
Décrémenter est l'action de retirer un

La petite application ci-dessous permet d'incrémenter ou décrémenter un compteur constitué de roues de chiffres.

La colonne (ou roue) 0 est celle de droite. La colonne 1 est celle juste à sa gauche, et ainsi de suite.

Combien de fois faut-il incrémenter le compteur pour faire bouger :
- la roue 0 d'un seul cran ?
- la roue 1 ?
- la roue 2 ?
- la roue 3 ?
Exprimez chacune de ces réponses à l'aide d'une puissance de 10. Que remarquez-vous ?
Que doit faire la roue 2 pour que la roue 3 bouge ?

Le poids d'une roue

Le nombre d'incréments nécessaires pour faire bouger la roue $k$ d'un seul cran vaut $10^k$ : $1$ pour la roue 0, $10$ pour la roue 1, $100$ pour la roue 2, $1000$ pour la roue 3... On appelle ce nombre le poids de la roue (ou de la colonne).

Changer de base

Jusqu'ici, nos roues disposent de 10 chiffres : c'est la base 10. Que se passe-t-il avec moins (ou plus) de chiffres ? Choisissez une base ci-dessous, recopiez l'alphabet proposé dans le compteur, puis répondez aux questions. Vous remarquerez que l'énoncé ne change jamais : seul le nombre en bleu change.

Choisissez votre base :

Alphabet à recopier dans le compteur ci-dessus :

Vous travaillez maintenant en base . Répondez aux questions suivantes (cherchez d'abord, puis dépliez la réponse pour vérifier) :

En partant de 0, incrémentez le compteur douze fois. Vous obtenez toujours la même quantité ; comment s'écrit-elle en base ?
Réponse
On a compté douze fois : la quantité obtenue est toujours douze, quelle que soit la base. Seule son écriture change. En base , douze s'écrit .
Combien de fois faut-il incrémenter le compteur pour faire bouger :
- la roue 0 d'un seul cran ?
- la roue 1 ?
- la roue 2 ?
- la roue 3 ?
Réponse
Roue 0 : 1. Roue 1 : . Roue 2 : . Roue 3 : .
Exprimez ces réponses à l'aide de puissances de . Quel est le poids de la roue numéro k ?
Réponse
. Le poids de la roue k est ^k.
Que doit faire la roue 2 pour que la roue 3 bouge ?
Réponse
Elle doit faire un tour complet : parcourir ses chiffres et revenir à 0.
Écrivez le plus grand nombre possible sur 4 chiffres en base . Écrivez ensuite la représentation en base 10 de ce nombre.
Réponse
C'est en base , soit en base 10 (c'est-à-dire ⁴ - 1).

Réglez maintenant le compteur en base 2 (alphabet 01, 4 roues) pour les questions 6 et 7 : c'est la seule base où l'on atteint les situations intéressantes en quelques clics. La question 8, elle, vous fera changer d'alphabet.

Repartez de 0000 et cliquez 7 fois : le compteur affiche 0111. Sans cliquer, prédisez ce qu'il affichera au clic suivant. Écrivez votre réponse, puis vérifiez.
Réponse
0111 devient 1000. Les trois roues pleines repassent à 0 d'un coup et chacune fait avancer sa voisine de gauche : c'est une cascade. Un seul clic, quatre roues qui bougent. C'est le moment vraiment difficile de la numération, et c'est précisément celui qu'on ne voit pas quand on se contente de regarder défiler le compteur. En base 2, il revient sans arrêt ; en base 10, une fois sur dix seulement, ce qui explique qu'on puisse traverser toute sa scolarité sans jamais l'avoir compris.
Continuez jusqu'à 1111 (15 clics depuis zéro). Que se passe-t-il au clic suivant ? Prédisez, puis essayez.
Réponse
Le compteur repasse à 0000, sans le moindre avertissement. Avec 4 roues en base 2, on ne compte que de 0 à 15 : au-delà, la valeur ne « rentre » plus et le compteur recommence à zéro. C'est un débordement. Une machine fait exactement la même chose, et c'est pour cela qu'on doit toujours savoir combien de roues (de bits) on s'est donné avant d'écrire un nombre.
Dans le champ « Alphabet de chiffres », remplacez 0123456789 par trois symboles de votre choix, par exemple @#$ (le premier jouera le rôle du zéro). Comptez. Le système fonctionne-t-il encore ? Pourquoi ?
Réponse
Oui, il fonctionne exactement pareil : c'est une base 3, avec d'autres dessins. Le choix des symboles est une pure convention, une correspondance arbitraire, comme le mot « poisson » pour l'animal. En revanche, la règle de position (une roue pleine fait avancer sa voisine, dont le poids vaut 3 fois plus) n'a, elle, rien d'arbitraire : c'est elle qui fabrique les quantités. Ne confondez jamais les deux, c'est le cœur de tout ce chapitre.

Comment travailler

Commencez par la base 3 avec votre professeur. Refaites ensuite seul(e) tout le travail en base 2. Pour aller plus loin, essayez aussi les bases 4, 8 et 16 : vous constaterez que la méthode est toujours la même.

Le binaire

Le binaire, c'est tout simplement la base 2.

Le mot "binaire" vient du latin binarius, qui signifie "composé de deux".

En base 2, chaque chiffre (appelé bit, contraction de binary digit) ne peut valoir que :

0 : "éteint", "faux", "non", etc.
1 : "allumé", "vrai", "oui", etc.

L'hexadécimal

L'hexadécimal, c'est la base 16

On ne dispose que de 10 chiffres, pas de 16, il nous en manque donc 6. On n'a pas voulu recréer de nouveaux symboles pour ces chiffres, alors on utilise les lettres de l'alphabet. Les chiffres de l'hexadécimal sont donc

\[<0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F>\]

l'hexadécimal revient souvent en informatique:

Utilisé pour les couleurs en HTML/CSS (ex : #FF0000 pour rouge)
1 chiffre hexadécimal représente 4 bits → lecture plus simple du binaire
Plus lisible que le binaire ou le décimal pour les données machines
Utilisé pour représenter les adresses mémoire en informatique bas niveau
Indispensable pour déboguer ou lire les fichiers binaires
Utile en systèmes, électronique, assembleur, sécurité informatique

Combien de bits pour un entier ?

On range le compteur

À partir d'ici, le compteur ne sert plus. Il vous a servi à comprendre ce que fait une position ; il ne sait pas répondre aux questions qui suivent, et de toute façon vous serez évalué sans lui. Tout le reste du chapitre se fait avec l'écriture seule, papier et crayon. Si un raisonnement vous échappe, revenez y jeter un coup d'œil, puis refermez-le.

Sur $k$ bits, on écrit les entiers de $0$ à $2^k - 1$ (c'est le cas particulier en base 2 de la formule $n^k - 1$). C'est exactement le débordement que vous avez provoqué à la question 7 : avec 4 roues, on s'arrête à 15.

Inversement, pour savoir combien de bits sont nécessaires pour écrire un entier donné, on cherche la plus petite puissance de 2 qui le dépasse. Par exemple, $13 = 1101_2$ tient sur 4 bits, car $2^3 <= 13 < 2^4$.

Quand on calcule, le résultat peut demander plus de bits que les nombres de départ :

Somme : additionner deux nombres de $k$ bits peut créer une retenue finale, donc un résultat sur $k+1$ bits au plus. Exemple : $1111_2 + 1111_2 = 11110_2$ (4 bits + 4 bits donne 5 bits).
Produit : multiplier un nombre de $k$ bits par un nombre de $m$ bits donne un résultat sur $k+m$ bits au plus.

Les tailles que les machines utilisent vraiment

Une machine ne choisit pas le nombre de bits au cas par cas : elle travaille sur des tailles fixes, presque toujours 8, 16, 32 ou 64 bits. Cela borne, une fois pour toutes, ce qu'un entier peut valoir :

Taille	Nombre d'entiers naturels représentables	Plus grand
8 bits (un octet)	$2^8 = 256$	$255$
16 bits	$2^{16} = 65\,536$	$65\,535$
32 bits	$2^{32}$, soit environ 4,3 milliards	$4\,294\,967\,295$
64 bits	$2^{64}$, soit environ $1,8 \times 10^{19}$	$2^{64}-1$

Choisir une taille, c'est donc accepter un débordement au-delà. C'est un vrai problème d'ingénierie, pas une curiosité : un compteur de 32 bits qui déborde, et un logiciel se met à compter à l'envers.

Pour aller plus loin : et Python, alors ?

Vous n'avez jamais vu un entier déborder en Python, et pour cause : Python n'impose aucune taille fixe à ses entiers. Il en agrandit la représentation autant que nécessaire, tant qu'il reste de la mémoire. Écrivez 2 ** 1000 dans une console, vous obtiendrez les 302 chiffres du résultat.

C'est confortable, et ce n'est pas gratuit : ces entiers coûtent plus de mémoire et de temps de calcul que les entiers de taille fixe d'un processeur. La plupart des langages (C, Java, Rust) font le choix inverse. Retenez surtout que le débordement existe partout ailleurs, et que ne l'avoir jamais rencontré est une particularité de votre langage, pas une loi de l'informatique.

Systèmes alternatifs

En réalité vous utilisez sans le savoir d'autres modes.

Vous comptez par exemple les minutes et les secondes dans le système sexagésimal hérité des babyloniens (-3000).

Vous dites quatre-vingt quinze (4 × 20 + 15) en héritage des celtes qui comptaient sur une base de 20 chiffres (ils comptaient aussi sur les doigts de pied). Tout comme les mayas

Taille	Nombre d'entiers naturels représentables	Plus grand
8 bits (un octet)	\(2^8 = 256\)	\(255\)
16 bits	\(2^{16} = 65\,536\)	\(65\,535\)
32 bits	\(2^{32}\), soit environ 4,3 milliards	\(4\,294\,967\,295\)
64 bits	\(2^{64}\), soit environ \(1,8 \times 10^{19}\)	\(2^{64}-1\)