Unum
Les « nombres universels » (universal numbers), dits unum, sont une famille de quantifications de la droite projective proposées depuis 2015 par John L. Gustafson. Elles sont conçues comme une alternative au standard IEEE 754, relatif aux nombres flottants.
Gustafson a révisé plusieurs fois son modèle, de telle sorte qu'il existe plusieurs versions : l'unum de type I, l'unum de type II et l'unum de type III, dit posit. Le nom posit provient du verbe anglais to posit qui lorsque utilisé comme un nom peut signifier « assertion » ou bien « conjecture ». Gustafson définit aussi deux formats dits valid et quire qui complémentent le posit en apportant respectivement des fonctionnalités différentes et une aide pour les calculs intermédiaires.
Toutes ces variantes ont en commun les propriétés suivantes :
- le codage en binaire est à longueur fixe, typiquement choisie comme un nombre entier d'octets.
- il existe deux valeurs dites exceptionnelles: 0 et infini (). Elles sont encodées différemment des autres valeurs.
- le décodage est injectif : deux éléments distincts de l'ensemble discret correspondent toujours à deux points distincts de la droite projective.
Depuis 2017, les efforts de standardisation du système des nombres universels portent essentiellement sur le posit. Cet effort a abouti en 2022 à la publication d'un document normatif[1].
Unum
[modifier | modifier le code]Type I
[modifier | modifier le code]L'unum de type I est assez proche de la norme IEEE 754. La principale différence consiste dans l'utilisation du bit de poids faible pour implémenter une arithmétique d'intervalles.
Type II
[modifier | modifier le code]L'unum de type II est radicalement différent de la norme IEEE 754. En plus du bit de signe et du bit d'intervalle mentionné précédemment, l'unum de type II utilise un bit pour signifier l'inversion. La donnée de ces trois opérations permet, à partir d'un ensemble fini de points entre l'unité et l'infini, de quantifier toute la droite projective hormis quatre points : les deux exceptions 0 et , puis 1 et -1. Cet ensemble de points est choisi arbitrairement et les calculs arithmétiques les concernant sont effectués non pas de façon logique, mais en faisant appel à une table de correspondance. La taille d'une telle table devient rédhibitoire pour un format d'encodage de plusieurs octets. Cette difficulté a rendu nécessaire le développement de l'unum de type III, dit posit, discuté ci-après.
Posit
[modifier | modifier le code]Le posit est plus proche de IEEE 754 que ne l'est l'unum de type II. En substance, la principale différence avec IEEE 754 est que l'exposant est encodé en taille variable. Il en résulte que la précision est plus élevée auprès de l'unité qu'elle ne l'est auprès de zéro ou de l'infini.
Le posit n'implémente pas d'arithmétique d'intervalles. Gustafson a cependant conçu un format companion, le valid, qui lui permet ce genre de calculs. Gustafson semble considérer posit et valid comme deux modes de fonctionnement du format unum.
Principe général
[modifier | modifier le code]Le format posit de précision est un format d'encodage de fractions dyadiques sur bits. Toute fraction dyadique qui peut être encodée de façon exacte sous un tel format sera ici dite représentable. Le format nécessite un processus d'arrondissage pour encoder les réels qui ne sont pas des fractions dyadiques, ou les fractions dyadiques qui ne sont pas représentables.
Fractions dyadiques représentables
[modifier | modifier le code]Soit une fraction dyadique représentable que Gustafson écrit sous la forme :
où et sont deux entiers relatifs qu'il faut encoder ensemble dans bits, la précision du format. On se réduit ici au cas et donc . L'encodage des nombres négatifs est discuté plus loin.
Comme mentionné plus haut, doit être encodé en longueur variable : les bits restants, s'il y en a, doivent être utilisés pour encoder . Comme est nécessairement non nul puisque zéro est un point exceptionnel, son bit de poids fort est nécessairement 1 et on peut le considérer implicite. Considérons donc tel que K s'écrit sur bits. peut alors s'écrire , où . On doit donc encoder non pas mais . contrairement à , peut être nul. doit coïncider avec le nombre de bits restant après l'encodage de . C'est aussi le nombre de bits nécessaires pour encoder .
On a:
Notons et . On a alors: et, par construction :
Il suit:
Et donc, par définition de la partie entière:
Il suffit alors d'encoder . Le nombre de bits restants est , ce qui nous donne , et donc .
Arrondissage des nombres réels et des fractions dyadiques non-représentables
[modifier | modifier le code]Codage de l'exposant
[modifier | modifier le code]L'exposant N est encodé avec un codage de Rice adapté pour encoder des entiers relatifs. Le paramètre utilisé est . Il peut être nul et est typiquement choisi petit (inférieur à trois). Si les versions initiales du format posit faisaient de un paramètre au même titre que , le standard de 2022 semble avoir finalisé la valeur 2.
Le signe du quotient est encodé en faisant usage des deux conventions possibles pour un codage unaire, selon que le bit répété est 0 ou 1. Plus précisément, est encodé avec une séquence commençant par un bit égal à 0 si est strictement négatif, et 1 sinon :
Ce bit est répété fois[note 1], avec :
La séquence de bits encodant le quotient q peut alors s'écrire:
Le reste de la division euclidienne est quant à lui encodé comme dans le codage Rice proprement dit.
Seuls les bits sont nécessaires. Le codage de Rice est tronqué lorsque . Les bits absents sont alors implicitement égaux à zéro.
Exceptions
[modifier | modifier le code]Zéro est codé par un champ de bits tous égaux à 0. Il s'agit d'une exception car s'il devait être décodé par l'algorithme décrit plus haut, un tel champ de bits correspondrait à la valeur [à vérifier].
L'infini est codé par un champ de bits dont le premier est 1 et tous les autres sont 0. S'il devait être décodé par l'algorithme décrit plus haut, un tel champ de bits correspondrait à la valeur [à vérifier].
Complément à deux
[modifier | modifier le code]Afin d'assurer un décodage injectif, les valeurs négatives (marquées comme telles par le bit de signe) doivent être complémentée à deux en première étape de décodage et en dernière étape de codage.
Notes et références
[modifier | modifier le code]Notes
[modifier | modifier le code]- Il ne faut pas ici confondre avec celui de la section précédente.
Références
[modifier | modifier le code]- (en) Posit Standard Document.