Utilisateur:Padex/Complément à b-1

Intro

En informatique, on représente souvent les entiers sur un nombre fixe de bits.

A priori, si on utilise $n$ bits, on peut écrire $2^{n}$ nombres différents.

Si on ne s'intéresse qu'aux entiers positifs, la notation binaire nous permet d'écrire tous les entiers de $0$ à $2^{n}-1$.

Si maintenant on veut également écrire des entiers négatifs, plusieurs solutions s'offrent à nous. La première, la plus simple, est de s'inspirer de notre notation quotidienne, et de réserver un bit pour indiquer le signe du nombre. Ainsi, pour $n=4$ :

$0110$ représente $6$

$1110$ représente $-6$

Cette notation possède cependant deux inconvénients : la première est que le $0$ possède deux notations ($0000$ et $1000$ pour $n=4$), donc on ne peut plus écrire que $2^{n}-2$ nombres ; la seconde est que l'arithmétique n'y est plus triviale ($0001+1001\neq 0$).

Dans les faits, cette notation n'est donc jamais utilisée.

Une autre approche est de considérer un décalage constant de $2^{n-1}-1$, utilisée notamment par la notation normalisée des nombres à virgule flottante IEEE 754. Cependant là aussi, l'addition n'est pas simple, et passe d'une opération linéaire à une opération affine.

La dernière approche que j'exposerai est celle de l'arithmétique modulaire. Elle est plus connue sous le nom de complément à deux, car c'est ainsi qu'on passe facilement de l'écriture d'un nombre à celle de son opposé ; mais au fond, ce qui légitime toutes les opérations, c'est de raisonner modulo $2^{n}$.

Avant le complément à deux, celui à un

Lorsqu'on veut introduire le complément à deux, il est courant d'introduire au préalable le complément à un.

L'idée est simple : pour obtenir le complément à un d'une chaîne de bits, vous modifiez chaque bit de cette dernière. Ainsi, $0000$ devient $1111$, $0101$ devient $1010$, $0010$ devient $1101$, etc.

Ce que l'on constate ensuite trivialement, c'est que pour toute chaîne de bits $s$, on a $s+{\text{Complément à un}}(s)=1\dots 1$ (i.e. $n$ 1 d'affilée).

Or $1\dots 1+1=0\dots 0=0$ (ou bien en considérant que la dernière retenue « se perd » du fait du nombre limité de bits pour écrire le nombre, ou bien en raisonnant de façon modulaire).

Donc on observe que pour toute chaîne de bits $s$, on a $s+({\text{Complément à un}}(s)+1)=0$.

Par définition, ${\text{Complément à un}}(s)+1$ est donc l'écriture légitime de $-s$. On nomme alors ${\text{Complément à deux}}(\cdot )={\text{Complément à un}}(\cdot )+1$.

Du vrai complément à un

Et si maintenant on voulait écrire des réels avec la même approche ?

Essayons pour voir. Mais cette fois-ci, on va faire du vrai complément à un, c'est-à-dire un complément à un (doublement) infini.

Prenons $1,1$ par exemple. Au fond, $1,1$ est une écriture extrêmement réduite d'un nombre dont l'écriture complète serait :

$\dots 0\dots 01,10\dots 0\dots$.

Si on applique le complément à un sur cette écriture complète, que se passe-t-il ? On obtient :

$\dots 1\dots 10,01\dots 1\dots$.

On reconnaît deux choses.

D'une part, à droite de la virgule, on reconnaît une écriture impropre, et donc on peut d'ores et déjà simplifier :

$\dots 1\dots 10,01\dots 1\dots =\dots 1\dots 10,1$.

D'autre part, à gauche de la virgule, on lit le nombre $\sum _{k\in \mathbb {N} }2^{k}-1$. Ceux familiers avec les nombres $2$-adiques ne seront pas surpris si j'identifie ce nombre à $-2$. Pour les autres, je vous propose ce petit jeu d'écriture (parfaitement informel sur les réels) :

$2\cdot {\big (}\sum _{k\in \mathbb {N} }2^{k}{\big )}=\sum _{k\in \mathbb {N} }2^{k+1}=\sum _{k'\neq 0\in \mathbb {N} }2^{k'}=\sum _{k'\in \mathbb {N} }2^{k'}-1$

Donc

$\sum _{k\in \mathbb {N} }2^{k}=-1$

Pour en revenir à notre exemple, on trouve que ${\text{Vrai complément à un}}(1,1)=-10+0,1=-1,1$. Pas mal, non ?

Si on en revient à nos entiers, on s'aperçoit que le complément à deux n'est en fait qu'un vrai complément à un, tronqué à gauche. En effet, le développement complet de notre entier après la virgule donne $\cdot ,0\dots 0\dots$ donc son vrai complément à un donne $\cdot ,1\dots 1\dots =1$.

Une notation pas inintéressante

Écrire une infinité de chiffres à gauche, c'est long, surtout au début.

Heureusement pour nous, on peut constater que si un nombre est positif, alors de façon classique son développement complet à gauche sera, à partir d'un certain rang, uniquement constitué de $0$. Et s'il est négatif, alors son développement complet à gauche sera, à partir d'un certain rang, uniquement constitué de $1$. C'est d'ailleurs là que l'analogie avec les nombres 2-adiques s'arrête : il est hors de question d'avoir des développements à gauche non-stationnaires.

On peut alors vouloir écrire les réels positifs comme en notation binaire classique, à ceci près qu'on laisse au moins un 0 à gauche pour indiquer que le développement est stationnaire au-delà. Ainsi, pour les entiers, cela donne : 0, 01, 010, 011, 0100, etc.

De même, pour écrire les négatifs, on considère le vrai complément à un de leur opposé, puis on tronque à gauche en veillant à laisser un 1 pour indiquer que le développement est stationnaire au-delà. Ainsi, pour les entiers strictement négatifs, cela donne : 1, 10, 101, 100, 1011, 1010, 1001, 1000, etc.

Comparaison avec la notation binaire classique

On constate alors deux points. Le premier est que le $0$ ne fait plus figure d'exception. En effet, en notation classique, $0$ possède deux écritures : $+0$ et $-0$, qui ont toutes les deux un développement après la virgule fini (pour ne pas dire nul). Alors que tous les autres entiers possèdent deux écritures : $1$ par exemple peut s'écrire $+1$ ou $+0,1\dots 1\dots$, la seconde étant jugée impropre. En vrai complément à un, $0$ peut s'écrire $0$ (propre) ou $1,1\dots 1\dots$ (impropre).

Le second point est que l'ordre des nombres devient beaucoup plus logique. Ainsi, en notation décimale classique, $8<8,5$ mais $-8>-8,5$. Cela parce que $-8,5=-8-0,5$. Cela n'a l'air de rien, mais combien ont commis des erreurs en manipulant les parties entières de négatifs ? En vrai complément à un, $01000<01000,1$ et $10111,1<1000=11000$. La partie entière de $10111,1$ est bien ce qui précède la virgule, à savoir $10111$.

De même, on n'est plus obligés de faire des tours de passe-passe pour additionner deux nombres. Ainsi, en notation décimale classique, pour additionner -7 et -9, on va avoir tendance à effectuer -(7+9), c'est-à-dire qu'on prend l'opposé de chacun des termes, qu'on les additionne, puis qu'on reprend l'opposé du résultat ! Pire, s'il s'agit d'effectuer -7 + 9, on va considérer qu'on soustrait 7 à 9.

En vrai complément à un, si je veux additionner $1001$ et $10111$, j'additionne, tout simplement. Pour éviter les erreurs, on pourra s'autoriser à écrire le premier terme $11001$ (qui est une écriture correcte bien que non minimale de $1001$, tout comme 042 est une écriture correcte de 42 en notation décimale classique), et j'obtiens bien $10000$, en me souvenant que $1+1+01=1$ et que les $1$ à gauche sont négatifs ($1$), là où la retenue est positive ($01$).

Et si je veux additionner $1001$ et $01001$, là encore il me suffit d'additionner directement pour obtenir $00010$, qu'on simplifiera en $010$.

Lacunes mineures

Il ne s'agit pas d'une notation bijective, tout comme notre notation habituelle.

Dans sa représentation compacte, tout nombre positif commence par 01, sauf le 0 ; de même, tout nombre négatif commence par 10, sauf -1. À cause de 0 et de -1, on ne peut pas optimiser la représentation en faisant sauter le premier bit, bien qu'il soit tout le reste du temps redondant avec le deuxième bit.

En base b

On peut généraliser le jeu d'écriture précédent et obtenir :

$\sum _{n\in \mathbb {N} }(b-1)*b^{n}=-1$

D'où le titre : complément à b-1.

Base hexadécimale

Idem que pour passer de la représentation binaire classique à la représentation hexadécimale classique : on regroupe les bits de la notation en (vrai) complément à un par quatre, jusqu'à atteindre au moins un bit, tel que le développement à gauche est stationnaire au-delà de ce bit. Puis on convertit.

Pour les entiers positifs, cela donne : 0, …, 7, 08, …, 0F, 10, …, 7F, 080, …, 0FF, etc.

Pour les entiers strictement négatifs, cela donne : F, E, …, 8, F7, …, F0, EF, EE, …, 80, F7F, etc.

Base décimale

On peut s'inspirer du cas précédent et profiter de la parité de 10 pour décider que :

$0=\dots 0\dots \ 0$

$1=\dots 0\dots 01$

$\dots$

$4=\dots 0\dots 04$

$5=\dots 9\dots 95$

$\dots$

$8=\dots 9\dots 98$

$9=\dots 9\dots \ 9$

Pour les entiers positifs, cela donne : 0, …, 4, 05, …, 09, 10, …, 49, 050, …, 099, 100, etc.

Pour les entiers strictement négatifs, on obtient : 9, …, 5, 94, …, 50, 949, …, 500, etc.

Base ternaire

On s'inspire des autres bases mais cette fois-ci on ne bénéficie plus d'une parité, donc les nombres positifs commencent par 01 ou 02 et les nombres négatifs commencent par 20 ou 21 (aucun ne peut commencer par 1).

HH:MM:SS en notation décimale

En supposant qu'on veuille noter des heures négatives, et qu'a priori on ne soit plus bornés entre 0 et 23.

Les minutes et les secondes s'écrivent comme on en a l'habitude : de 00 à 59. (on oubliera les secondes intercalaires !)

Les heures peuvent s'écrire en complément à 9 en base décimale, par exemple 9:59:59 précédant 0:00:00.

Formalisation

Manifestement, ce système de notation semble fonctionnel, et présente même quelques avantages pratiques sur notre système classique.

Cependant, pour l'introduire j'ai été contraint de poser :

$\sum _{n\in \mathbb {N} }2^{n}=-1$

Or cette égalité pose deux problèmes.

Le premier est qu'elle n'est pas rigoureuse (la série ne converge clairement pas dans $\mathbb {R}$).

Le second est qu'elle est contraire à toute intuition, notamment parce qu'il paraît absurde qu'une somme de termes strictement positifs puisse être égale à un terme strictement négatif.

Pour rendre cela rigoureux, en sachant que je souhaite conserver la métrique euclidienne sur $\mathbb {R}$ (je ne manipule pas des nombres 2-adiques), j'ai la conviction profonde que la justification de tout ceci est identique à celle du complément à deux : on raisonne en arithmétique modulaire. Tout se passerait donc comme si nous raisonnions « modulo l'infini ». Ou plutôt, modulo un infini.

J'ai cherché du côté de l'arithmétique des ordinaux, cela ne m'a pas inspiré ; je me suis tourné vers les nombres surréels, cela n'a rien donné non plus. Je suis tombé sur un article de Terence Tao pour formaliser d'autres bizarreries similaires, mais c'était assez bourrin et je ne me sens pas le niveau pour explorer cette voie. De plus, elle ne correspond pas à mon intuition.

Récemment je suis tombé sur les nombres hyperréels, une piste qui me semble cette fois la bonne, notamment grâce au principe de transfert. Je pense qu'avec cette notation, je suis en train de quotienter $^{*}\mathbb {R}$ par le groupe engendré par la suite $(b^{0},b^{1},b^{2},\dots ,b^{n},\dots )$.

Si j'écris $\omega$ comme étant l'hyperréel classe d'équivalence de la suite $(u_{n})_{n\in \mathbb {N} }$ avec $u_{n}=n$, nous avons : $(b^{0},\dots ,b^{n},\dots )=b^{\omega }$.

Finalement, je pense que la structure $^{*}\mathbb {R} /b^{\omega }{^{*}\mathbb {Z} }$ correspond exactement à ce que je recherche. Je vous invite à lire la version anglaise de cette sous-page (qui n'est en rien sa traduction) pour plus de détails.

Si vous avez des idées ou des connaissances, n'hésitez pas à les partager ! :)

Notation Q

Pour des raisons de commodités et de compatibilité avec notre système décimal actuel, on peut choisir d'utiliser un « onzième chiffre » pour remplacer la notation $\dots 9$.

J'ai choisi d'utiliser une lettre, comme on le fait en base hexadécimale. J'en ai pris une dont certaines graphies comme « q » rappellent le nombre 9 ; je n'ai pas choisi la lettre G pour qu'on ne s'imagine pas qu'il s'agit de F+1 = 16.

De plus, comme nous le rappelle Murakami, les japonais ne seront pas choqués par ce choix.

Une version simplifiée est de considérer que Q = -1, mais qu'on ne peut et doit utiliser ce chiffre que pour les réels négatifs, qui est le chiffre le plus à gauche (donc nécessairement avant la virgule).

Ainsi :

-0,07 = Q,93

-0,7 = Q,3

-1 = Q

-1,4 = Q8,6

-2 = Q8

…

-10 = Q0

-11 = Q89 etc.

Avec cette notation, tous les réels positifs s'écrivent de la façon usuelle. Comme on peut le voir ci-dessus, la notation Q n'est pas plus longue que l'usuelle pour les réels négatifs ; elle est au plus aussi longue, parfois même plus courte.