Arithmétique des ordinateurs

Un additionneur binaire effectue la même petite opération à chaque position de bit. Il combine les deux bits des opérandes avec une retenue provenant de la position située à droite. La signification de la configuration de bits obtenue vient ensuite.

Suivre la retenue

Un demi-additionneur possède deux entrées : sa somme est leur OU exclusif et sa retenue est leur ET. Un additionneur complet accepte aussi une retenue entrante :

Ici, la multiplication signifie ET et l’addition signifie OU. La somme vaut 1 pour un nombre impair d’entrées à 1 ; la retenue vaut 1 lorsqu’au moins deux entrées sont à l’état haut. Enchaîner des additionneurs complets forme un additionneur à propagation de retenue. Seul le bit 0 reçoit la retenue initiale ; chaque bit suivant reçoit la retenue produite par son voisin.

Pour 23 + 45, écris 0001 0111 + 0010 1101. Au bit 0, 1 + 1 produit une somme de 0 et une retenue de 1. Au bit 1, 1 + 0 + 1 produit à nouveau 0 et une retenue de 1. Au bit 2, trois entrées à 1 produisent une somme de 1 et une retenue de 1. En continuant vers la gauche, on obtient 0100 0100, soit 68, sans retenue finale.

Un résultat de n bits ne conserve que les n bits de poids faible : le circuit calcule donc la somme modulo $2^n$. Sur 8 bits, 1111 1100 + 0000 0101 produit 0000 0001 et une retenue sortante de 1. En signé, cela donne −4 + 5 = 1. En non signé, cela donne 252 + 5 = 257, dont les huit bits de poids faible représentent 1. Le circuit n’a pas changé ; c’est la plage autorisée qui a changé.

Transformer la soustraction en addition

Le complément à deux donne l’identité

Une ligne de commande de soustraction combine par OU exclusif chaque bit du second opérande avec 1, ce qui l’inverse, et fixe la retenue entrante initiale à 1. Pour l’addition, cette ligne vaut 0 : le second opérande passe donc sans changement et la retenue initiale vaut 0.

Pour calculer 23 − 45, inverse 0010 1101 pour obtenir 1101 0010. Additionne 0001 0111 + 1101 0010 + 1 pour obtenir 1110 1010, avec une retenue sortante de 0. Sa valeur signée est −22. Laisser la retenue initiale à 0 donnerait −23 : l’inversion seule fournit une valeur inférieure de un à la valeur négative recherchée.

Pour une soustraction non signée, une retenue sortante de 1 signifie aucun emprunt ; une retenue sortante de 0 signifie qu’un emprunt a été nécessaire. Ainsi, la retenue sortante de 0 dans 23 − 45 indique un résultat non signé inférieur à zéro. Arm enregistre cette retenue qui indique l’absence d’emprunt ; x86 enregistre son inverse comme indicateur d’emprunt.

Adapter les largeurs avant l’opération

En RISC-V, lb étend le signe d’un octet, lbu l’étend par des zéros et addi étend le signe de sa valeur immédiate de 12 bits. Choisis l’extension selon la signification de l’opérande avant d’envoyer les bits à l’additionneur.

La plus petite valeur signée négative n’a pas de valeur positive correspondante sur la même largeur. Calculer l’opposé de 1000 0000 sur 8 bits consiste à l’inverser en 0111 1111 puis à ajouter 1, ce qui redonne 1000 0000. La valeur souhaitée +128 nécessite un format signé plus large.

Un dépassement de capacité signifie que le résultat exact se trouve hors de la plage du format de destination. Les valeurs non signées de n bits vont de 0 à $2^n-1$ ; les valeurs signées en complément à deux vont de $-2^{n-1}$ à $2^{n-1}-1$. Huit bits représentent les valeurs de 0 à 255 en non signé, ou de −128 à 127 en signé. Un même résultat stocké peut être valide dans une interprétation et correspondre à un dépassement dans l’autre.

Tester le bon signal

Pour une addition ou une soustraction signée, le circuit peut utiliser

les deux retenues entrant dans la position du signe et en sortant. La retenue sortante seule répond à la question pour les valeurs non signées.

Additionne 107 et 54 sur 8 bits : 0110 1011 + 0011 0110 donne 1010 0001. Une retenue entre dans le bit 7 mais aucune n’en sort, donc le dépassement vaut 1. La valeur non signée 161 est représentable ; la valeur signée −95 n’est pas égale à la somme exacte 161. Inversement, −4 + 5 donne une retenue de 1 mais un dépassement signé de 0. L’addition de 1000 0000 à lui-même donne une retenue de 1 et un dépassement de 1 : les deux interprétations échouent donc.

L’addition de nombres de signes opposés ne peut pas produire de dépassement : la somme exacte se trouve entre les opérandes. La soustraction nécessite sa propre règle de signe, car soustraire un nombre négatif augmente le premier opérande. Par exemple, 100 − (−40) est trop grand pour un entier signé sur 8 bits, même si les deux valeurs d’entrée sont représentables.

Comprendre l’effet de l’instruction

Sur x86, add définit les indicateurs de retenue et de dépassement. Sur Arm, les opérations qui définissent les indicateurs, comme ADDS, les modifient ; un ADD ordinaire conserve les indicateurs existants. Sur MIPS, add et addi déclenchent une trappe en cas de dépassement signé, contrairement à addu et addiu. L’addition entière RISC-V écrit les bits de poids faible et ne possède ni indicateur de dépassement ni trappe de dépassement arithmétique.

Après add t0, t1, t2, une vérification RISC-V non signée est :

bltu t0, t1, overflow

Une somme non signée ayant subi un retour circulaire est inférieure à un opérande d’origine. Les valeurs signées nécessitent une autre vérification :

slti t3, t2, 0
slt  t4, t0, t1
bne  t3, t4, overflow

La première instruction indique si le second opérande est négatif. La deuxième indique si le résultat est inférieur au premier opérande. Sans dépassement, ces tests concordent : ajouter un nombre négatif diminue la valeur, tandis qu’ajouter une valeur positive ou nulle ne peut pas la diminuer. Une différence détecte un dépassement. Pour une valeur immédiate connue comme positive, un branchement signé vérifiant si la somme a diminué suffit.

Distinguer les règles du matériel et celles du langage

En C et C++, l’arithmétique non signée revient dans la plage modulo $2^n$ ; un dépassement signé est un comportement indéfini. En Java, int et long reviennent dans la plage, tandis que Math.addExact signale un dépassement par une exception. Les entiers Python grandissent selon les besoins. Un retour circulaire du matériel ne détermine donc pas ce qu’un programme C est autorisé à faire.

Les additions et soustractions avec retour circulaire conservent un résultat final représentable : en arithmétique modulaire sur 8 bits, (100 + 50) − 60 devient d’abord −106, puis 90 par retour circulaire. Ce raisonnement s’applique à l’arithmétique avec retour circulaire, pas aux expressions signées en C qui produisent un dépassement.

La saturation est une autre politique. En non signé sur 8 bits, 200 + 100 est saturé à 255 au lieu de revenir à 44. Cela sert pour les intensités de pixels et d’autres signaux bornés, pour lesquels le retour circulaire d’un grand résultat positif vers une petite valeur serait trompeur.

Une unité arithmétique et logique reçoit des opérandes et des entrées de commande et produit un résultat ainsi que des sorties d’état. Elle est combinatoire : ses sorties dépendent des entrées présentes. Les registres conservent les opérandes et recueillent les résultats ; l’unité elle-même ne stocke rien.

Construire un bit, puis le répéter

Une tranche de 1 bit calcule en parallèle les opérations ET et OU et la somme d’un additionneur complet. Un multiplexeur sélectionne le résultat qui atteint le bit de sortie. Dans une unité arithmétique et logique de n bits, toutes les tranches partagent les commandes d’opération, tandis que la retenue sortante de chaque additionneur alimente la retenue entrante de la tranche suivante. Les opérations logiques fonctionnent indépendamment à chaque position ; l’addition dépend de la chaîne de retenue.

Une commande Bnegate inverse le second opérande et fixe aussi la retenue entrante du bit 0. La sélection de l’additionneur calcule alors une soustraction. Les tranches de poids plus fort reçoivent leur retenue de la tranche précédente, et non directement de Bnegate. Mettre toutes les entrées de retenue à l’état haut insérerait des uns supplémentaires dans le calcul.

Une commande Ainvert peut aussi inverser le premier opérande. Sélectionner ET avec les deux opérandes inversés produit NON-OU, d’après la loi de De Morgan :

Sélectionner OU avec les deux opérandes inversés produit NON-ET. Dans ces équations logiques, le signe plus désigne OU.

Lire un mot de commande

Une unité arithmétique et logique classique présentée dans les manuels utilise les champs Ainvert, Bnegate et un sélecteur Operation de deux bits :

Ce sont les codages propres à cette conception. Il s’agit de commandes internes, et non de codages d’instructions RISC-V.

Pour les entrées 0101 et 0011, la commande 0110 inverse la seconde entrée en 1100 et fournit une retenue initiale de 1. L’additionneur produit 0010, avec une retenue sortante de 1 : 5 − 3 = 2, sans emprunt en non signé. Sélectionner ET pour les entrées d’origine produirait au contraire 0001. Les valeurs d’entrée peuvent rester fixes tandis qu’un changement de commande sélectionne un autre chemin de résultat.

La tranche de poids fort fournit aussi des informations de dépassement et de comparaison. Une réduction de tous les bits du résultat fournit la sortie zéro. Ces sorties d’état permettent à l’unité de commande du processeur de tester le résultat arithmétique sans stocker un second résultat de pleine largeur.

Ajouter le décalage à côté de l’additionneur

Une unité arithmétique et logique complète pour les instructions entières de base RISC-V nécessite aussi le OU exclusif, la comparaison non signée et les décalages. Un décaleur à barillet utilise une suite de niveaux de multiplexeurs. Chaque niveau laisse passer son entrée ou la décale d’une puissance de deux. Un décaleur de 32 bits possède des niveaux pour 1, 2, 4, 8 et 16 positions ; il réalise donc tout décalage de 0 à 31 en cinq niveaux.

Pour décaler de 13 positions, sélectionne les niveaux de 8, 4 et 1. Les décalages sélectionnés se combinent en un seul résultat. Un décalage logique à droite insère des zéros. Un décalage arithmétique à droite recopie le bit de signe, ce qui préserve le signe d’une valeur négative. Ainsi, 1111 0000 décalé de deux positions à droite donne 0011 1100 avec un décalage logique et 1111 1100 avec un décalage arithmétique.

Les comparaisons réutilisent souvent la soustraction. Pour l’égalité, on vérifie si la différence est nulle. Pour l’ordre, on vérifie si la différence mathématique est négative, ce qui demande une attention particulière lorsqu’une soustraction de largeur fixe produit un dépassement de capacité.

Détecter l’égalité sur tous les bits

La sortie zéro est le NON-OU de tous les bits du résultat :

Un seul bit de résultat non nul met la sortie zéro à faux. La soustraction de deux configurations de bits égales produit zéro ; deux configurations distinctes de n bits ne peuvent pas différer d’un multiple non nul de $2^n$, donc une soustraction avec retour circulaire ne crée pas de fausse égalité. Un autre circuit d’égalité combine par OU exclusif les bits correspondants des opérandes et vérifie si tous les résultats valent zéro.

Corriger le signe pour la comparaison signée inférieur à

En RISC-V, slt écrit l’entier 1 sur toute la largeur si le premier opérande signé est plus petit, ou 0 sinon. Dans une unité arithmétique et logique à tranches, la tranche de poids fort calcule un signal Set et le renvoie à l’entrée Less du bit 0. Tous les bits de poids plus fort du résultat sont forcés à zéro.

Le signal Set correct est

En l’absence de dépassement, le signe de la différence convient directement. En cas de dépassement, ce signe est inversé par rapport à celui de la différence exacte : un OU exclusif avec 1 le corrige donc.

Compare 7 à −8 sur quatre bits. La soustraction 0111 + 0111 + 1 donne 1111. Son signe suggère une différence négative, mais la différence exacte est 15, hors de la plage de −8 à 7. Le dépassement vaut 1, donc le signal Less corrigé vaut 1 OU exclusif 1 = 0. Le résultat de slt est 0000, ce qui indique correctement que 7 n’est pas inférieur à −8.

Utiliser l’emprunt pour la comparaison non signée inférieur à

La comparaison non signée utilise un autre signal :

pour une soustraction effectuée avec la seconde entrée inversée et une retenue initiale de 1. Une retenue sortante de 0 signifie qu’un emprunt a été nécessaire : le premier opérande non signé est donc plus petit.

Cette distinction apparaît entre slt et sltu, ainsi qu’entre les branchements blt et bltu et entre bge et bgeu. Ni le signe du résultat seul ni un « indicateur négatif » générique ne répond aux deux questions.

Appliquer la comparaison dans un programme

Une vérification des bornes non signée peut rejeter les indices négatifs ainsi que les indices supérieurs ou égaux à la longueur du tableau :

bgeu x10, x11, IndexOutOfBounds

Ici, x10 contient l’indice signé et x11 contient une longueur positive ou nulle représentable dans la plage signée. Un indice négatif, réinterprété comme non signé, vaut au moins $2^{n-1}$ et dépasse donc toute longueur de ce type. La condition sur la longueur compte : elle permet à une seule comparaison non signée de suffire.

Les conversions du langage peuvent aussi changer le sens d’une comparaison. Avec un unsigned int C de 32 bits, -1 < 0u est faux car −1 est converti en 4 294 967 295 avant la comparaison. Suis la conversion avant de raisonner à partir du signe moins écrit.

Dans un additionneur à propagation, la retenue doit traverser chaque bit successivement. L’anticipation de retenue remplace cette attente séquentielle par un circuit logique qui prévoit les retenues à partir des bits des opérandes et de la retenue initiale.

Décrire le comportement de chaque bit vis-à-vis de la retenue

Définissons les signaux de génération et de propagation par

Ce sont des expressions booléennes : la multiplication représente ET et l’addition représente OU. Le signal de génération vaut 1 lorsque le bit crée une retenue indépendamment de la retenue entrante. Le signal de propagation vaut 1 lorsqu’une retenue entrante peut passer. La relation de récurrence est

Un bit dont les deux entrées valent 1 génère une retenue ; un bit dont une entrée vaut 1 transmet une retenue ; un bit dont les deux entrées valent 0 l’arrête. Avec cette définition par OU, un bit qui génère une retenue a aussi un signal de propagation égal à 1, ce qui ne change pas la formule de la retenue.

Développer la dépendance

Remplace chaque retenue précédente par son expression :

Chaque expression dépend désormais de signaux issus des opérandes et de la retenue initiale, et non d’une chaîne séquentielle de retenues sortantes intermédiaires. Une fois les retenues disponibles, chaque bit de somme reste le OU exclusif de ses deux entrées et de sa retenue entrante.

Pour 1011 + 0110 avec une retenue initiale de 0, les signaux de génération à partir du bit 0 sont 0, 1, 0, 0 et les signaux de propagation sont 1, 1, 1, 1. Les retenues entrant dans les bits 1 à 4 sont donc 0, 1, 1, 1. Les quatre bits du résultat sont 0001 avec une retenue sortante de 1, ce qui représente 11 + 6 = 17.

Construire des groupes plutôt que des portes géantes

Un bloc de quatre bits possède les signaux de groupe

Sa retenue sortante est $G+P{c}_0$. Un second niveau d’anticipation combine ces signaux de bloc selon la même règle. Quatre blocs de quatre bits et une unité d’anticipation de groupe forment un additionneur de 16 bits. Des regroupements supplémentaires permettent de construire des circuits plus larges ; les additionneurs à préfixe parallèle comme Kogge–Stone organisent ces relations en un réseau rapide.

Dans un modèle simple de délai de porte, la propagation de retenue coûte environ deux délais de porte par bit, soit 32 pour 16 bits. Une conception à anticipation sur deux niveaux peut fournir la dernière retenue en environ cinq délais : un pour les signaux de bit, deux pour les signaux de groupe et deux pour la retenue de groupe. Cette estimation compte les niveaux logiques et suppose que les portes nécessaires sont disponibles ; le délai réel dépend aussi de la taille des portes et du câblage. Le regroupement utilise davantage de matériel pour obtenir un chemin de retenue dont le délai croît approximativement de façon logarithmique avec la largeur.

Un additionneur à sélection de retenue utilise la surface autrement : il calcule deux fois un bloc de poids fort, une fois pour une retenue entrante de 0 et une fois pour une retenue entrante de 1. Un multiplexeur sélectionne le bon résultat lorsque la retenue du bloc de poids faible arrive.

Certains additionneurs définissent la propagation avec un OU exclusif au lieu d’un OU. Cela donne aussi des retenues correctes et permet d’écrire la somme $s_i=p_i\oplus c_i$. Garde la même définition lorsque tu déduis le circuit logique des groupes.

Chaque bit du multiplicateur binaire sélectionne une copie décalée du multiplicande ou zéro. L’addition de ces produits partiels donne le résultat. Un opérande de n bits multiplié par un opérande de m bits peut nécessiter n + m bits : deux opérandes de 32 bits nécessitent donc un produit complet de 64 bits.

Suivre les décalages et additions

Pour des opérandes non signés de n bits, initialise à zéro un produit de 2n bits. Répète n fois : teste le bit de poids faible du multiplicateur, ajoute le multiplicande courant si ce bit vaut 1, décale le multiplicande à gauche et décale le multiplicateur à droite. Le registre du multiplicande doit être assez large pour conserver ses copies décalées.

Pour 6 × 5 sur quatre bits, le multiplicateur est 0101 :

Le produit final est 30. Le bit testé et la direction du décalage vont ensemble : tester le bit de poids fort tout en décalant le multiplicateur à droite associerait les bits aux mauvais poids. Cette conception séquentielle prend n étapes, y compris celles dont le bit du multiplicateur vaut zéro.

Partager l’espace des registres

La première conception utilise un registre de multiplicande et un additionneur de 2n bits. Une conception améliorée garde le multiplicande fixe sur n bits, place le multiplicateur dans la moitié de poids faible d’un registre de produit de 2n bits et initialise la moitié de poids fort à zéro.

Lorsque le bit de poids faible vaut 1, ajoute le multiplicande à la moitié de poids fort. Conserve la retenue sortante de l’additionneur dans un bit supplémentaire, puis décale cette retenue et les deux moitiés du produit ensemble à droite. Les bits du multiplicateur sortent par la droite à mesure que les bits du produit occupent l’espace libéré. Supprimer la retenue fausse les grands produits : avec des opérandes de quatre bits, 15 × 15 deviendrait à tort 1 au lieu de 225. À raison d’une étape par cycle d’horloge, l’implémentation simple sur 32 bits prend environ 32 cycles.

Tenir compte de la largeur du produit

Un produit non signé est représentable sur n bits si et seulement si les n bits de poids fort de son produit complet sont nuls. Pour 6 × 5, le résultat complet est 0001 1110 ; stocker uniquement 1110 donne 14. La multiplication était correcte, mais le format de destination trop étroit en a éliminé une partie.

Un décalage de k positions à gauche multiplie par $2^k$ lorsque le résultat est représentable. La multiplication par 8 devient un décalage de trois positions ; la multiplication par 10 peut utiliser deux copies décalées :

(x << 3) + (x << 1)

Le calcul est $8x+2x=10x$. Les règles de largeur et du langage de programmation s’appliquent toujours aux décalages et à l’addition ; cette réécriture ne crée pas de bits de résultat supplémentaires.

Lire les moitiés du résultat RISC-V

mul renvoie les XLEN bits de poids faible, où XLEN est la largeur des registres entiers. mulhu renvoie la moitié de poids fort pour des opérandes non signés. Les instructions de moitié de poids fort avec opérandes signés sont mulh pour deux opérandes signés et mulhsu pour un premier opérande signé et un second non signé.

Un programme qui demande le produit complet peut émettre l’instruction appropriée pour la moitié de poids fort, suivie de mul avec les mêmes opérandes. Une implémentation peut fusionner ces deux instructions. Le résultat de poids faible seul ne permet pas d’établir si un produit non signé est représentable ; la moitié de poids fort fournit cette information.

La multiplication signée doit traiter les signes des opérandes sans perdre la plus petite valeur négative. Des circuits plus rapides doivent aussi réduire de nombreux produits partiels sans attendre à chaque fois une addition complète avec propagation de retenue.

Multiplier les valeurs absolues sans erreur

Une approche consiste à mémoriser les signes, à former des valeurs absolues non signées de n bits, à les multiplier pour obtenir un résultat de 2n bits, puis à prendre l’opposé du produit complet si un seul opérande était négatif. Pour −8 sur quatre bits, les bits de valeur absolue 1000 représentent 8 en non signé. Ils ne peuvent pas être interprétés comme une valeur signée positive sur quatre bits.

Les n bits de poids faible du produit sont identiques dans les interprétations signée et non signée. 1111 × 0010 donne 30 en non signé (0001 1110) ou −2 en signé (1111 1110). Les deux moitiés de poids faible sont 1110 ; seules les moitiés de poids fort diffèrent. C’est pourquoi une seule instruction mul convient aux deux interprétations.

Suivre les décisions de Booth

L’algorithme de Booth opère directement en complément à deux. Donne n + 1 bits à l’accumulateur et étends le signe du multiplicande à cette largeur, afin que le multiplicande et son opposé soient tous deux représentables. Initialise l’accumulateur à zéro, place le multiplicateur dans son registre de n bits et ajoute un bit supplémentaire initialisé à zéro.

Examine ensemble le bit de poids faible du multiplicateur et le bit ajouté :

Après chaque décision, décale arithmétiquement à droite l’ensemble formé par l’accumulateur, le multiplicateur et le bit supplémentaire. Répète n fois ; élimine le bit ajouté et le bit de signe redondant de poids fort de l’accumulateur pour obtenir le produit de 2n bits.

Pour 2 × (−3), utilise le multiplicande 00010, le multiplicateur 1101 et l’accumulateur 00000. Les paires sont 10, 01, 10, 11. Après les opérations et décalages respectifs, l’accumulateur et le multiplicateur valent 11111 0110, 00000 1011, 11111 0101 et 11111 1010. Les huit bits de poids faible du produit 1111 1010 représentent −6.

Un décalage logique insérerait zéro en position de poids fort et fausserait les résultats partiels négatifs. Le bit supplémentaire de l’accumulateur compte aussi : soustraire le plus petit multiplicande négatif de n bits nécessite une valeur positive indisponible sur n bits signés.

Réduire le travail et les chemins de retenue

Le recodage de Booth remplace une suite de 1 par une soustraction à son extrémité de poids faible et une addition au-dessus de son extrémité de poids fort. Par exemple, 126 vaut 128 − 2. Des bits alternés peuvent ne procurer aucune économie. Le recodage de Booth en base 4 examine deux bits du multiplicateur par étape et utilise des chiffres de −2 à +2, ce qui réduit le nombre de produits partiels.

Un multiplicateur rapide forme les produits partiels en parallèle. Un additionneur à sauvegarde de retenue comprime trois mots en deux sans propager les retenues à travers le mot. Les arbres de Wallace ou de Dadda répètent cette réduction, puis utilisent un dernier additionneur à propagation de retenue. Réduire 32 rangées à deux prend huit niveaux de sauvegarde de retenue. L’exécution en pipeline permet de traiter plusieurs produits simultanément ; accepter un nouveau produit à chaque cycle ne signifie pas que chacun se termine en un cycle.

Pour un résultat signé réduit à n bits, chaque bit de la moitié de poids fort doit être égal au bit de signe de la moitié de poids faible. Sur quatre bits, −8 × −1 donne le produit complet 0000 1000. La moitié de poids fort est nulle mais le bit de signe conservé vaut 1 : +8 n’est donc pas représentable dans le format signé de destination.

La division produit un quotient et un reste liés par

Pour un diviseur non signé non nul, le reste est positif ou nul et inférieur au diviseur. Un dividende et un diviseur de n bits nécessitent un quotient et un reste de n bits.

Produire le quotient un bit à la fois

Lis les bits du dividende en commençant par le poids fort. Double le reste partiel, fais entrer le bit suivant et vérifie si le diviseur peut être soustrait. Si oui, soustrais-le et écris 1 comme bit du quotient ; sinon, conserve le reste partiel et écris 0.

Pour 0111 divisé par 0010, les restes partiels après abaissement du bit suivant sont 0, 1, 3 et 3. Les deux premiers sont inférieurs à 2, donc leurs bits de quotient valent 0. Chaque 3 permet une soustraction, laissant un reste de 1 et un bit de quotient de 1. Le quotient est 0011 et le reste 0001 : 3 × 2 + 1 = 7.

La division avec restauration essaie d’abord une soustraction. Si le résultat de l’essai est négatif, ajoute à nouveau le diviseur et écris 0 ; sinon, conserve le résultat et écris 1. Détecte l’échec à l’aide d’un emprunt ou d’une différence signée sur n + 1 bits. Un test du signe sur n bits n’est pas fiable : sur quatre bits, 0 − 9 donne 0111 par retour circulaire, dont le bit de poids fort vaut 0 malgré l’emprunt.

Un circuit compact place le dividende dans la moitié de poids faible d’un registre de 2n bits et le reste partiel dans la moitié de poids fort. Il décale le registre à gauche à chaque étape et insère les bits du quotient à droite. À la fin, la moitié de poids fort contient le reste et la moitié de poids faible le quotient.

La division sans restauration conserve un résultat d’essai négatif pour l’étape suivante et ajoute alors le diviseur au lieu de restaurer immédiatement le reste. Un reste partiel final négatif nécessite une dernière addition du diviseur. La division SRT sélectionne plusieurs bits du quotient par étape à l’aide des bits de poids fort du diviseur et du reste ; des entrées manquantes dans une telle table de sélection ont causé le bogue FDIV du Pentium en 1994. La division reste dépendante de chaque reste partiel précédent.

Appliquer la division signée avec troncature

Divise les valeurs absolues, prends l’opposé du quotient si les signes diffèrent et donne à un reste non nul le signe du dividende.

Ces résultats tronquent le quotient vers zéro et conservent l’identité de la division. RISC-V, Java et C depuis C99 utilisent cette règle. L’opérateur Python // arrondit au contraire à l’entier inférieur : -7 // 2 vaut −4 et -7 % 2 vaut 1.

Traiter les entrées exceptionnelles

La division par zéro en RISC-V renvoie un quotient dont tous les bits valent un et le dividende d’origine comme reste. Le cas de dépassement signé, la plus petite valeur négative divisée par −1, renvoie cette même valeur comme quotient et zéro comme reste. Aucun des deux cas ne déclenche de trappe. x86 déclenche une exception de division dans les deux cas. Un programme qui doit signaler les erreurs vérifie d’abord si le diviseur vaut zéro et vérifie aussi la paire qui produit le dépassement signé.

Un décalage logique à droite divise les valeurs non signées par des puissances de deux en arrondissant à l’entier inférieur. Un décalage arithmétique arrondit aussi les valeurs négatives à l’entier inférieur : −5 décalé d’une position à droite devient −3, tandis que la division par 2 avec troncature donne −2. Pour obtenir une troncature avec un décalage, ajoute $2^k-1$ à une entrée négative avant de la décaler de k positions à droite. Pour −5 et k = 1, décale −4 pour obtenir −2.

Une valeur binaire normale à virgule flottante a la forme

Le significande est la valeur complète 1,f ; la fraction stockée ne contient que f. La normalisation garantit le 1 de tête : omettre ce bit implicite fait donc gagner un bit de précision.

Lire les trois champs

IEEE 754-2019 définit ces formats. Les termes simple et double précision désignent généralement binary32 et binary64. L’ordre de stockage est signe, exposant, fraction. Pour une valeur normale, soustrais le biais du champ d’exposant non signé :

Fraction désigne la fraction binaire après la virgule, et non ses bits interprétés comme un entier. En binary32, les champs d’exposant de 1 à 254 codent les exposants de −126 à 127. Les champs 0 et 255 ont des significations spéciales.

Avec un biais, les exposants plus grands ont des champs non signés plus grands. Pour les nombres finis positifs, l’ordre non signé des configurations complètes suit l’ordre numérique. Les valeurs négatives et les NaN nécessitent un traitement supplémentaire.

Coder et décoder

Pour coder −0,75, écris sa valeur absolue sous la forme ${\mathrm{0,11}}_2={\mathrm{1,1}}_2\times 2^{-1}$. Le signe vaut 1 et le champ d’exposant vaut −1 + 127 = 126, soit 01111110. Supprime le 1 de tête implicite et complète la fraction avec des zéros. Les champs sont 1 01111110 10000000000000000000000, ce qui donne 0xBF400000. En binary64, la même valeur est 0xBFE8000000000000.

Pour décoder 0x41460000, décompose-le en 0 10000010 10001100000000000000000. Le champ d’exposant vaut 130, donc l’exposant réel est 3. Le significande est

La multiplication par 8 donne 12,375. Écrire le 1 implicite dans la fraction stockée changerait la valeur ; stocker directement −1 dans le champ d’exposant ferait perdre la règle du biais.

Distinguer plage de valeurs et précision

binary32 atteint environ $\mathrm{3,40}\times {10}^{38}$, avec une plus petite valeur normale positive de $2^{-126}$ et environ sept chiffres décimaux significatifs. binary64 atteint environ $\mathrm{1,80}\times {10}^{308}$, avec une plus petite valeur normale positive de $2^{-1022}$ et environ 15 à 16 chiffres significatifs. binary16 a un maximum de 65 504, une plus petite valeur normale positive de $2^{-14}$, une plus petite valeur sous-normale positive de $2^{-24}$ et environ 3,3 chiffres décimaux significatifs.

La précision compte les chiffres significatifs, et non les chiffres après la virgule. Par exemple, binary32 stocke 1 234 567,89 sous la forme 1 234 567,875.

Dans l’intervalle binary32 de $2^e$ à $2^{e+1}$ exclu, les valeurs normales voisines sont espacées de $2^{e-23}$. Cet espacement est une ulp, une unité au dernier rang. Juste au-dessus de 1, il vaut $2^{-23}$, souvent appelé epsilon machine. À $2^{24}$, l’espacement devient 2 : 16 777 217 manque donc, même si des nombres bien plus grands sont représentables. Davantage de bits d’exposant élargissent la plage d’échelle ; davantage de bits de fraction rapprochent les valeurs représentables à une échelle donnée.

Les configurations d’exposant réservées permettent à IEEE 754 de représenter d’autres valeurs que les nombres normalisés ordinaires. Identifie toujours les champs avant d’appliquer une formule de valeur.

Reconnaître les configurations réservées

binary32 possède +0 à 0x00000000 et −0 à 0x80000000. Ils sont égaux à la comparaison, mais une division peut révéler leur signe : 1 divisé par +0 donne +∞, tandis que 1 divisé par −0 donne −∞. Un petit résultat négatif qui s’arrondit à zéro devient −0.

L’infini positif est 0x7F800000 ; la plus grande valeur positive finie est 0x7F7FFFFF. Avec l’arrondi au plus proche, un dépassement arithmétique renvoie un infini signé. Diviser une valeur finie non nulle par zéro renvoie aussi un infini signé, avec un indicateur d’exception différent. Les opérations suivantes traitent l’infini de manière cohérente : ajouter 1 à +∞ laisse +∞, le multiplier par −2 donne −∞ et son inverse est +0.

Distinguer NaN de l’infini

Des opérations comme zéro divisé par zéro, l’infini moins lui-même, zéro multiplié par l’infini et la racine carrée réelle de −1 n’ont pas de résultat numérique qui ait un sens. Elles produisent NaN, une valeur qui n’est pas un nombre, et signalent une opération invalide.

NaN est non ordonné : les tests d’égalité et les comparaisons inférieur à ou supérieur à qui le font intervenir sont faux, tandis que le test de différence est vrai. En particulier, x == NaN ne peut pas détecter NaN. Utilise isnan(x). Les NaN silencieux se propagent normalement dans les opérations arithmétiques ; les NaN signalants déclenchent l’exception d’opération invalide lorsqu’ils sont utilisés. Dans ces formats binaires, le bit de poids fort de la fraction distingue un NaN silencieux. Le NaN silencieux canonique binary32 de RISC-V est 0x7FC00000.

Approcher zéro progressivement

Un nombre sous-normal n’a pas de 1 implicite. Son exposant est fixé au plus petit exposant normal :

En binary32, 0x00000001 vaut $2^{-149}$ et 0x00400000 vaut $2^{-127}$. En binary64, la plus petite valeur positive est $2^{-1074}$. Utiliser le champ d’exposant nul moins le biais produirait une erreur d’un facteur deux, même avant l’ajout erroné d’un 1 implicite.

Les nombres sous-normaux assurent le sous-dépassement graduel : la précision diminue lorsque les valeurs se rapprochent de zéro, avec un espacement absolu fixe près de zéro. Des valeurs finies distinctes d’un même format ont toujours une différence non nulle représentable. Les modes qui ramènent ces valeurs à zéro suppriment cette protection et peuvent accélérer leur traitement sur certains processeurs.

Lire les indicateurs d’exception

IEEE 754 définit les exceptions d’opération invalide, de division par zéro, de dépassement de capacité, de sous-dépassement et de résultat inexact. Le traitement par défaut renvoie un résultat et enregistre l’état ; il n’arrête pas nécessairement l’exécution. Un résultat inexact signifie que le résultat arrondi diffère du résultat exact.

Avec le traitement par défaut, le sous-dépassement exige à la fois une très petite valeur et un résultat inexact. En binary32, $2^{-126}\mathrm{/}2=2^{-127}$ est un résultat sous-normal exact qui ne déclenche pas de sous-dépassement. RISC-V enregistre NV, DZ, OF, UF et NX dans fflags au sein de fcsr, et les exceptions à virgule flottante ne déclenchent pas de trappes arithmétiques. Un infini renvoyé ne suffit pas à déterminer si un dépassement ou une division par zéro s’est produit ; examine l’indicateur.

L’arithmétique à virgule flottante traite séparément les significandes et les exposants. Le résultat final doit être le résultat exact de l’opération arrondi dans le format de destination : les déplacements intermédiaires de bits doivent donc conserver assez d’informations pour cette dernière décision.

Additionner avec un exposant commun

L’addition suit quatre étapes : aligner, effectuer l’opération, normaliser, arrondir. Compare les exposants et décale à droite le significande de l’opérande le plus petit du nombre de positions correspondant à leur différence. Additionne les valeurs absolues si les signes sont identiques ; soustrais-les s’ils sont opposés. Décale le résultat sous forme normalisée et ajuste son exposant. Arrondis ensuite, puis normalise à nouveau si l’arrondi crée une retenue.

Utilise des significandes de quatre bits pour étudier 0,5 + (−0,4375) :

1. Écris les opérandes sous les formes ${\mathrm{1,000}}_2\times 2^{-1}$ et $-{\mathrm{1,110}}_2\times 2^{-2}$.
2. Aligne le second pour obtenir $-{\mathrm{0,111}}_2\times 2^{-1}$.
3. Soustrais les valeurs absolues : ${\mathrm{1,000}}_2-{\mathrm{0,111}}_2={\mathrm{0,001}}_2$.
4. Normalise pour obtenir ${\mathrm{1,000}}_2\times 2^{-4}$, soit 0,0625. Aucun bit non nul n’a été perdu, donc l’arrondi ne modifie pas le résultat.

L’annulation peut nécessiter un grand décalage de normalisation à gauche. Le circuit utilise un soustracteur d’exposants, un décaleur d’alignement, un additionneur de significandes, un compteur de zéros de tête et des circuits de normalisation et d’arrondi. Les additionneurs à virgule flottante sont couramment organisés en pipeline sur plusieurs cycles.

Un modèle décimal montre pourquoi les chiffres supplémentaires comptent : avec quatre chiffres significatifs, 99,99 + 0,161 s’aligne sous la forme $\mathrm{9,999}+\mathrm{0,01610}$ à l’échelle ${10}^1$. Le résultat intermédiaire exact est 10,01510 à cette échelle. Normalise pour obtenir $\mathrm{1,00151}\times {10}^2$ et arrondis à $\mathrm{1,002}\times {10}^2$. Tronquer trop tôt le terme aligné ferait perdre les informations nécessaires pour choisir 100,2.

Multiplier les échelles et les significandes

Multiplie les significandes, additionne les exposants réels et combine les signes par OU exclusif. Avec des champs biaisés, soustrais une fois le biais :

avant les ajustements de normalisation. Deux significandes normaux donnent un produit compris entre 1 inclus et 4 exclu : leur produit nécessite donc au plus un décalage de normalisation à droite. L’arrondi peut nécessiter un ajustement supplémentaire ; il faut aussi vérifier les bornes de l’exposant.

Pour 0,5 × (−0,4375), les champs d’exposant binary32 donnent 126 + 125 − 127 = 124, soit un exposant réel de −3. Le produit des significandes est ${\mathrm{1,000}}_2\times {\mathrm{1,110}}_2={\mathrm{1,110}}_2$. Le OU exclusif des signes vaut 1, ce qui donne $-{\mathrm{1,110}}_2\times 2^{-3}=-\mathrm{0,21875}$.

Arrondir une fois avec la multiplication-addition fusionnée

La FMA calcule a × b + c avec un seul arrondi après l’expression complète. Une multiplication et une addition séparées arrondissent deux fois. En binary32, prends $a=1+2^{-23}$, $b=1-2^{-23}$ et c = −1. Leur produit exact est $1-2^{-46}$. Une multiplication séparée l’arrondit à 1, donc l’addition renvoie zéro. La FMA conserve la petite différence du produit et renvoie $-2^{-46}$.

RISC-V F fournit 32 registres à virgule flottante, de f0 à f31 ; D élargit le même banc pour la double précision. flw/fsw et fld/fsd transfèrent les valeurs. Les opérations arithmétiques comprennent fadd.s, fmul.s, fdiv.s et fsqrt.s, avec des formes .d pour la double précision. fmadd.s calcule une multiplication-addition fusionnée. Des comparaisons comme flt.s écrivent 0 ou 1 dans un registre entier, et fcvt convertit des formats ou des valeurs entières.

Un format fini ne peut pas stocker tous les résultats exacts. Un arrondi correct consiste à choisir le résultat représentable imposé par la direction d’arrondi, comme si l’opération avait d’abord été calculée exactement. Les opérations arithmétiques de base, la racine carrée et la FMA respectent cette règle. Les bits de charge utile et de signe d’un NaN ne sont pas nécessairement identiques d’un processeur à l’autre.

Choisir une direction d’arrondi

Les quatre premières sont obligatoires pour les implémentations binaires ; le départage au pair est le mode par défaut. Le départage à l’opposé de zéro est obligatoire pour les formats décimaux, et RISC-V le fournit aussi pour les opérations binaires. Leurs noms sont RNE, RUP, RDN, RTZ et RMM ; une instruction peut sélectionner directement un mode ou utiliser le mode dynamique de fcsr.

Avec le départage au pair à l’entier, 2,5 devient 2 et 3,5 devient 4. En binaire avec des significandes de quatre bits, ${\mathrm{1,0011}}_2$ s’arrondit à ${\mathrm{1,010}}_2$ et ${\mathrm{1,0101}}_2$ s’arrondit aussi à ${\mathrm{1,010}}_2$. Le bit pair appartient au significande conservé, et non à l’exposant ou à un chiffre décimal affiché.

Conserver les informations de garde, d’arrondi et collantes

Après normalisation, conserve deux bits supplémentaires après le significande de destination : le bit de garde et le bit d’arrondi. Le bit collant est le OU de tous les bits éliminés ensuite. Il indique si toute cette partie est nulle.

Pour l’arrondi au plus proche, un bit de garde à 0 indique une valeur inférieure à la moitié. Un bit de garde à 1 avec un bit d’arrondi ou collant à 1 indique une valeur supérieure à la moitié. Un bit de garde à 1 avec les deux indicateurs suivants à 0 indique une valeur exactement à mi-chemin. Dans ce cas, incrémente le significande conservé uniquement si son bit de poids faible actuel vaut 1.

Pour la somme 8 + 0,5625 avec un significande de quatre bits, l’alignement donne

Conserve 1.000 ; le bit de garde vaut 1, le bit d’arrondi vaut 0 et le bit collant vaut 1 car la partie restante contient un 1. La valeur est supérieure à la moitié, donc incrémente pour obtenir ${\mathrm{1,001}}_2\times 2^3=9$. Supprimer le bit collant ferait croire à tort que la valeur est à mi-chemin et conduirait à choisir 8.

Un bit collant renseigne sur tous les bits perdus, et non simplement sur le troisième bit après la partie conservée. Pendant le décalage, dès qu’un bit perdu vaut 1, l’état collant reste à 1 pour cette partie accumulée.

Interpréter l’erreur et le dépassement de capacité

Pour les résultats finis dans la plage, l’arrondi au plus proche a une erreur absolue d’au plus une demi-ulp ; l’arrondi dirigé a une erreur inférieure à une ulp. Pour les résultats normaux binary32, la borne relative habituelle de l’arrondi au plus proche est $2^{-24}$ ; pour binary64, elle est $2^{-53}$. Les résultats sous-normaux nécessitent un raisonnement en erreur absolue, car leur précision relative diminue.

La direction d’arrondi détermine aussi les résultats d’un dépassement de capacité. Un dépassement positif donne +∞ avec l’arrondi au plus proche ou vers le positif, mais la plus grande valeur positive finie avec l’arrondi vers zéro ou vers le négatif. Un dépassement négatif se comporte de façon symétrique.

Les conversions en entiers ont leurs propres règles. En C, les conversions de valeurs représentables comme (int)2.7 et (int)-2.7 tronquent à 2 et −2, indépendamment de la direction d’arrondi à virgule flottante courante. Vérifie la plage du type de destination ainsi que la partie fractionnaire éliminée.

Les erreurs en virgule flottante découlent souvent directement de l’espacement fini des valeurs. Distingue l’erreur déjà présente dans les opérandes stockés de l’arrondi effectué par une opération et des informations perdues lors d’une conversion.

Repérer l’erreur de représentation

Une fraction irréductible a une écriture binaire finie si et seulement si son dénominateur est une puissance de deux. Des valeurs comme 0,5, 0,25 et 0,375 sont exactes. L’écriture de 0,1 est périodique, donc binary32 stocke 0x3DCCCCCD, soit environ 0,10000000149011612. binary64 stocke aussi une approximation.

Par conséquent, 0.1 + 0.2 en binary64 produit 0,30000000000000004, différent de la valeur stockée la plus proche de 0,3. Un résultat affiché court comme 0.1 peut être le plus court nombre décimal qui se reconvertit dans les mêmes bits stockés ; il ne prouve pas l’exactitude.

Pour des résultats finis approchés, utilise une tolérance choisie pour le problème, par exemple

La tolérance absolue traite les valeurs proches de zéro ; la tolérance relative s’adapte à l’ordre de grandeur. Les tolérances doivent refléter le calcul et l’erreur acceptable, pas simplement le nombre de chiffres affichés.

Observer la perte d’un petit terme lors d’une addition

L’absorption se produit avec l’arrondi au plus proche lorsqu’un petit terme ne peut pas faire passer un grand opérande à la valeur représentable voisine. En binary32, 16 777 216 + 1 s’arrondit à 16 777 216 : les valeurs voisines sont espacées de deux et ce cas à mi-chemin sélectionne le significande pair. Un compteur float qui ajoute 1 peut donc cesser d’avancer.

Changer l’ordre des additions peut changer la réponse. En binary32, avec x = −1,5 × 10³⁸, y = 1,5 × 10³⁸ et z = 1, (x + y) + z donne 1. Mais y + z s’arrondit à y, donc x + (y + z) donne zéro. L’addition n’est pas associative. Les réductions parallèles peuvent changer leur regroupement lorsque le nombre de threads change, ce qui affecte les derniers bits.

Les arrondis répétés s’accumulent aussi : ajouter dix millions de fois 0,1 en binary32 à un total binary32 donne 1 087 937 au lieu de 1 000 000. Un accumulateur plus large réduit la perte due aux arrondis. Additionner d’abord les valeurs de plus petite valeur absolue peut aussi préserver des contributions qu’un total courant élevé absorberait.

Distinguer l’annulation d’une soustraction inexacte

L’annulation supprime les chiffres de tête communs à des opérandes presque égaux. La soustraction elle-même peut être exacte alors que les erreurs antérieures des opérandes deviennent grandes par rapport à la petite différence obtenue. En binary32, 1,0000001 est stocké sous la forme $1+2^{-23}$. Soustraire 1 donne environ $\mathrm{1,1920929}\times {10}^{-7}$ au lieu de $\mathrm{1,0}\times {10}^{-7}$, soit environ 19 % d’erreur relative.

Vérifier les conversions et les choix de format

binary64 représente exactement tous les entiers de 32 bits. binary32 ne le fait pas : 16 777 217 s’arrondit à 16 777 216 avec le départage au pair. Au-dessus de $2^{53}$, binary64 ne représente pas non plus tous les entiers. La conversion d’une valeur à virgule flottante dans un type entier plus petit peut dépasser entièrement sa plage.

Lors du premier vol d’Ariane 5 en 1996, une conversion hors plage d’une valeur à virgule flottante de 64 bits en entier signé de 16 bits a arrêté les systèmes de référence inertielle et contribué à la perte de la fusée. Lors de l’échec du Patriot à Dhahran en 1991, une approximation tronquée de 0,1 en virgule fixe a accumulé environ 0,34 s d’erreur de temps après environ 100 heures, décalant la fenêtre de suivi d’environ 687 m. Il s’agissait d’une erreur de représentation en virgule fixe, et non d’une opération IEEE à virgule flottante.

Choisis binary64 pour une précision plus large dans les calculs courants, binary32 lorsque sa plus faible utilisation de mémoire convient au travail, et binary16 ou bfloat16 pour les calculs adaptés à une faible précision. bfloat16 possède huit bits d’exposant et sept bits de fraction. Les montants monétaires exacts doivent être représentés par des entiers comptant les plus petites unités monétaires ou par un type décimal.