Comparer deux nombres sans les convertir

/ Christian Nguembou Tagne

Rangez par ordre alphabétique des fichiers nommés photo1, photo2, et ainsi de suite jusqu’à photo10. Un tri naïf place photo10 entre photo1 et photo2 : il compare les caractères un à un, de gauche à droite, comme un dictionnaire, et le caractère « 1 » vient avant le caractère « 2 ». L’ordre du dictionnaire n’est pas l’ordre des nombres. Un élève de sixième compare pourtant quatre-vingt-dix-neuf et cent sans hésiter : le nombre qui a le plus de chiffres est le plus grand, et à longueur égale on compare de gauche à droite. Cette règle de deux lignes est un théorème. Elle vaut dans toute base, et elle repose sur une seule inégalité.

Cet article est le troisième de la série Écrire un nombre, tirée de Mathématiques en terminales scientifiques (Tome 2). Il emploie l’inégalité centrale du premier article, « Dix doigts, et un théorème », paru le 8 octobre, et les écritures en base deux construites dans le deuxième, « Du décimal au binaire, et pourquoi l’algorithme s’arrête », paru le 10 octobre.

1. L’énoncé

Proposition. Soit a\geq 2 un entier, et soient x=\overline{x_{m}\cdots x_{1}x_{0}}^{\,a} et y=\overline{y_{n}\cdots y_{1}y_{0}}^{\,a} deux entiers naturels distincts, écrits en base a.

(1) Si m<n, alors x<y.

(2) Si m=n, soit p le plus grand indice tel que x_{p}\neq y_{p}. Alors x<y si, et seulement si, x_{p}<y_{p}.

Les indices comptent à partir de la droite : x_{0} est le chiffre des unités. Le « plus grand indice où les chiffres diffèrent » est donc le premier chiffre qui diffère quand on lit de gauche à droite. Cet indice existe, puisque deux écritures de même longueur dont tous les chiffres coïncident désignent le même nombre.

2. Le nombre de chiffres d’abord

Le premier article a établi qu’un entier dont l’écriture en base a compte m+1 chiffres vérifie a^{m}\leq x<a^{m+1}. Si m<n, alors m+1\leq n et

\displaystyle x<a^{m+1}\leq a^{n}\leq y.

C’est tout. Le point (1) n’est qu’une réécriture de l’encadrement par deux puissances consécutives de la base. En base dix, il dit que tout nombre à deux chiffres est inférieur à 100, et que tout nombre à trois chiffres lui est supérieur ou égal.

3. Puis le premier chiffre qui diffère

Supposons m=n, et soit p le plus grand indice tel que x_{p}\neq y_{p}. Au-dessus de p, les chiffres coïncident ; notons S la valeur commune de \sum_{i>p}x_{i}a^{i} et de \sum_{i>p}y_{i}a^{i}, nulle si p=n. Supposons x_{p}<y_{p}, c’est-à-dire x_{p}+1\leq y_{p}. Le lemme du premier article majore la partie basse de x par a^{p}-1, et il vient

\displaystyle \sum_{i\leq p}x_{i}a^{i}\leq x_{p}a^{p}+a^{p}-1<(x_{p}+1)a^{p}\leq y_{p}a^{p}\leq\sum_{i\leq p}y_{i}a^{i}.

En ajoutant S aux deux membres, on obtient x<y. Réciproquement, si x_{p}>y_{p}, le même calcul, les rôles échangés, donne x>y ; et l’égalité x_{p}=y_{p} est exclue par le choix de p. Ainsi x<y équivaut à x_{p}<y_{p}. \quad\Box

L’argument dit pourquoi les chiffres qui suivent ne comptent plus : tout ce qu’ils peuvent apporter est strictement inférieur à une unité du rang p. Un exemple en base sept montre que la marge peut être aussi mince que possible. Les nombres \overline{3666}^{\,7} et \overline{4000}^{\,7} diffèrent dès le premier chiffre, et le second est donc le plus grand ; or ils valent 1371 et 1372. Les trois chiffres maximaux du premier le rapprochent à une unité du second, sans jamais le rattraper.

4. Le zéro de tête, et le tri des fichiers

Le point (1) utilise une hypothèse cachée dans le mot « écriture » : le premier chiffre n’est pas nul. Sans elle, il est faux. La chaîne 0099 compte quatre caractères, la chaîne 100 en compte trois, et pourtant 99<100. La démonstration du point (2), en revanche, ne s’est jamais servie de cette hypothèse : elle reste valable pour deux chaînes de même longueur, zéros de tête compris.

Ce qui suit ne figure pas dans le Tome 2. C’est exactement ce qu’exploitent les informaticiens quand ils nomment leurs fichiers photo001, photo002, …, photo010. En complétant tous les numéros par des zéros à gauche jusqu’à une longueur commune, ils se ramènent au seul point (2), et le tri du dictionnaire, qui compare de gauche à droite sans regarder la longueur, coïncide alors avec l’ordre des nombres. Les deux règles de l’élève de sixième n’en font qu’une, à condition de mettre d’abord les deux nombres à la même longueur.

5. Après la virgule, l’autre règle

Une erreur fréquente au collège consiste à affirmer que 0{,}25 est plus grand que 0{,}3, « parce que 25 est plus grand que 3 ». L’élève applique à la partie décimale la règle des entiers, celle du nombre de chiffres. Or après la virgule, la longueur ne dit rien : 0{,}3 et 0{,}30 sont le même nombre, comme 99 et 0099.

La section précédente donne le remède. On complète par des zéros, à droite cette fois, jusqu’à la même longueur : 0{,}25 contre 0{,}30. Puis on compare de gauche à droite, et le premier chiffre qui diffère, 2 contre 3, tranche. La justification est celle du point (2), avec des puissances négatives de dix : tout ce que les chiffres suivants peuvent ajouter reste strictement inférieur à une unité du rang où l’on a tranché.

« Strictement » n’est vrai que pour un nombre fini de chiffres. La fin du premier article l’a montré : une suite infinie de neuf rattrape l’unité supérieure. Les écritures 0{,}2999\ldots et 0{,}3 diffèrent dès le premier chiffre et désignent pourtant le même nombre. La règle de comparaison vaut pour les écritures décimales finies, et plus généralement pour celles qui ne se terminent pas par une suite infinie de neuf.

6. D’une base à l’autre ?

La proposition suppose les deux nombres écrits dans la même base, et l’hypothèse n’est pas décorative. Le nombre \overline{100000}^{\,2} a six chiffres et vaut 32 ; le nombre \overline{100}^{\,7} en a trois et vaut 49. Le plus long est le plus petit.

Entre deux bases, la longueur ne fournit qu’un encadrement : une écriture à k chiffres en base a désigne un nombre compris entre a^{k-1} et a^{k}-1. Ici, cela place le premier nombre entre 32 et 63, le second entre 49 et 342. Les deux intervalles se chevauchent, et l’encadrement ne tranche pas. Le titre promettait de comparer sans convertir. C’est vrai dans une même base, et seulement là.

Le prochain article de la série, qui paraît le 14 octobre, est un exercice : des nombres dont l’écriture change de forme selon la base, et que l’on peut manipuler sans jamais revenir à la base dix.

La proposition et sa démonstration sont celles de la section Systèmes de numération du chapitre 1 de Mathématiques en terminales scientifiques (Tome 2), qui en tire une méthode de comparaison. Le rôle du zéro de tête, le tri des fichiers, le cas des écritures décimales et la comparaison entre deux bases n’y figurent pas et sont ajoutés ici.

Votre commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.