La soustraction IEEE-754 est fonctionnellement complète

• La soustraction en virgule flottante IEEE-754 permet de construire n’importe quel circuit binaire grâce au zéro signé et aux règles de signe du résultat
• Si l’on considère -0 comme false et +0 comme true, alors en mode d’arrondi par défaut, x - y se comporte comme A ∨ ¬B, c’est-à-dire comme une porte IMPLY avec les arguments inversés
• Avec une constante false, cette porte permet de construire un NOT, et la combinaison NOT + IMPLY forme alors un ensemble de portes logiques fonctionnellement complet
• L’exemple Python distingue directement le signe de -0.0 et 0.0 pour implémenter f_not, f_or, f_and, f_xor uniquement à partir de soustractions
• L’exemple Rust représente des entiers 8 bits avec des tableaux de f32, calcule 23 + 19 = 42, et nécessite environ 120 instructions en virgule flottante pour additionner deux entiers 8 bits

---

Le point de départ créé par les règles de signe IEEE-754

• La soustraction en virgule flottante IEEE-754 possède la complétude fonctionnelle
• Être fonctionnellement complet signifie qu’avec cette seule opération, on peut construire n’importe quel circuit binaire
• Le point clé réside dans les règles sur le bit de signe de la section 6.3 de la norme IEEE 754-2019
  • La soustraction x - y est traitée comme la somme x + (-y)
  • Le zéro peut porter un signe, donc -0 et +0 sont traités comme deux valeurs distinctes
  • En revanche, dans les comparaisons IEEE-754, -0 == +0 est vrai
  • Tant que les entrées et le résultat ne sont pas NaN, le signe d’une somme ou d’une différence suit les règles de signe des opérandes
  • Si la différence de deux valeurs de même signe vaut exactement 0, le résultat est +0 dans tous les modes d’arrondi sauf roundTowardNegative
• La construction qui suit suppose le mode d’arrondi par défaut, roundTiesToEven
  • Elle fonctionne de façon similaire avec roundTowardNegative

La table de vérité obtenue en soustrayant des zéros

• Si l’on ne soustrait que -0 et +0, on obtient les résultats suivants
  • -0 - -0 = +0
  • -0 - +0 = -0
  • +0 - -0 = +0
  • +0 - +0 = +0
• Si l’on prend -0 pour false et +0 pour true, la table de vérité de sortie devient
  • 0 0 -> 1
  • 0 1 -> 0
  • 1 0 -> 1
  • 1 1 -> 1
• Cette table de vérité est équivalente à A ∨ ¬B, soit une porte IMPLY de forme B → A
  • Par rapport à une porte IMPLY classique, les arguments sont inversés

Avec une constante false, on obtient la complétude fonctionnelle

• Cette table de vérité devient fonctionnellement complète dès lors qu’on a accès à une constante false
• Avec une constante false, on peut construire une porte NOT
• NOT + IMPLY forme un ensemble fonctionnellement complet
• Les portes NAND et NOR sont fonctionnellement complètes à elles seules, sans constante particulière
  • Lors de la fabrication de micropuces, cela présente l’avantage de ne produire qu’un seul type de composant
  • Il n’est pas nécessaire de router un signal low constant pour construire une porte NOT

Un circuit logique par soustraction en Python

• L’exemple Python définit -0.0 comme false et 0.0 comme true
  • En IEEE-754, +0 et -0 sont égaux à la comparaison ; on les distingue donc en extrayant le signe avec math.copysign
• La porte NOT exploite le fait que -0 - x inverse le signe du zéro
  • f_not = lambda x: f_false - x
  • f_not(-0.0) devient true
  • f_not(+0.0) devient false
• La porte OR est construite en inversant le signe du deuxième argument avant la soustraction
  • f_or = lambda a, b: a - f_not(b)
  • Elle ne vaut false que lorsque les deux arguments valent -0, et true dans tous les autres cas
• AND et XOR peuvent eux aussi être construits par composition de OR et NOT
  • f_and = lambda a, b: f_not(f_or(f_not(a), f_not(b)))
  • f_xor = lambda a, b: f_or(f_and(f_not(a), b), f_and(a, f_not(b)))

Des entiers logiciels construits en Rust

• L’exemple Rust pose Bit = f32, et représente les bits avec ZERO = -0.0 et ONE = 0.0
• not, or, and et xor sont tous implémentés à partir de soustractions en virgule flottante, puis utilisés pour créer un additionneur complet adder
• SoftU8 = [Bit; 8] sert à représenter un entier 8 bits
  • to_softu8 convertit chaque bit d’un u8 en ONE ou ZERO
  • from_softu8 vérifie le signe de chaque élément pour reconstruire un u8
• Le programme d’exemple convertit 23 et 19 en SoftU8, les additionne, puis affiche 42
• L’addition de deux entiers 8 bits nécessite environ 120 instructions en virgule flottante
• Sur x86-64, il n’existe pas d’instruction réelle d’inversion de signe en virgule flottante ; le compilateur utilise donc un masque et un XOR pour basculer le bit de signe, c’est-à-dire le bit de poids fort d’un nombre IEEE-754

[GN⁺]

Avis de Hacker News

• On peut imaginer que ce genre de détournement bizarre d’instructions en virgule flottante soit le genre de chose qu’un DRM pourrait utiliser pour obscurcir une machine virtuelle.
  L’étape suivante serait sans doute de créer un compilateur qui exploite cette propriété pour exécuter du code source ordinaire sous forme d’entiers en virgule flottante, puis d’y ajouter quelque chose comme une FFI pour appeler les API d’un OS classique.

  • Parmi les ressources susceptibles de vous intéresser, il y a http://tom7.org/grad/, qui utilise les erreurs IEEE en virgule flottante comme fonctions de transfert pour le machine learning, et http://tom7.org/nand/, qui construit des portes logiques et un CPU entier à partir de NaN et d’infinis IEEE.
  • Cette variante a déjà été implémentée avec la gestion des exceptions de la MMU Intel : https://github.com/jbangert/trapcc
    C’est une preuve constructive que le mécanisme de gestion des exceptions de la MMU Intel est Turing-complet.
    Un assembleur a été écrit pour transformer les instructions Move, Branch if Zero, Decrement en source C configurant plusieurs tables de contrôle du processeur ; une fois ce code exécuté, le CPU effectue le calcul en essayant de déclencher des exceptions, sans exécuter une seule instruction.
    En option, l’assembleur peut aussi générer des instructions x86 qui affichent des variables dans le framebuffer VGA et passent le contrôle entre les instructions d’affichage natives et les instructions de trap de la weird machine.
  • Ça rappelle https://github.com/xoreaxeaxeax/movfuscator.

• Ça me fait penser à cette excellente vidéo qui construit un calcul uniquement avec des NaN et des infinis IEEE-754 : https://www.youtube.com/watch?v=5TFDG-y-EHs

  • Toute cette chaîne, suckerpinch / Tom 7, est vraiment formidable.
    Du contenu extrêmement nerd, réfléchi et drôle, avec une très bonne présentation.
    Je la recommande vivement, en particulier au public de HN.

• Dans la nouvelle Coding Machines, une exploitation similaire du bit de signe était le grand indice qu’une véritable IA avait été lâchée dans le monde.
  https://www.teamten.com/lawrence/writings/coding-machines/

  • C’est une excellente histoire, mais le concept semble clairement beaucoup emprunter au classique de Ken Thompson, On Trusting Trust : https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...

• Voir aussi https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...
  C’est une implémentation qui convertit un double IEEE-754 en une paire de doubles contenant les valeurs entières des 32 bits de poids faible et des 32 bits de poids fort de la représentation binaire de l’argument, en n’utilisant que l’addition, la soustraction et la multiplication de doubles.

• En regardant la table de vérité, la soustraction est clairement préservante du vrai, donc elle ne semble pas pouvoir être réellement fonctionnellement complète.
  Qu’est-ce que je rate ?

  • À strictement parler, elle est fonctionnellement complète en combinaison avec l’accès à la constante false, c’est-à-dire -0.0.
    Sans cette constante, elle ne l’est pas, contrairement à NAND qui peut produire false à partir de n’importe quelle valeur.
    Le but de l’article était de montrer qu’avec seulement le zéro signé et la soustraction en virgule flottante, on peut simuler n’importe quel circuit ; j’ai trouvé que la complétude fonctionnelle était le terme le plus concis pour l’exprimer, mais si l’on s’en tient strictement à la table de vérité, c’est un léger détournement des règles, et je le préciserai dans l’article.
  • Je ne suis pas sûr de ce que « préservante du vrai » signifie exactement ici, mais l’indice est que ce n’est pas la soustraction seule qui est fonctionnellement complète, mais la soustraction avec le symbole constant 0.
    Avec la soustraction et 0, on construit false sous la forme -0.0, et on obtient l’ensemble fonctionnellement complet {->, _|_} mentionné sur Wikipédia [1].
    [1] https://en.wikipedia.org/wiki/Functional_completeness
  • La soustraction est préservante du vrai pour le bit de signe, mais pas pour les bits de la soustraction elle-même.
    Je ne suis pas d’accord avec l’idée que les bits de soustraction seuls soient fonctionnellement complets.
    Le raisonnement selon lequel, puisqu’ils préservent le vrai, ils ne sont pas fonctionnellement complets me semble correct.
  • Sous la table de vérité de l’implication, avec l’ordre des arguments inversé, il est écrit « cette table de vérité est fonctionnellement complète [1] », mais la page Wikipédia liée dit clairement que IMPLY seul n’est pas fonctionnellement complet.
    Elle dit que « tout ensemble de connecteurs binaires contenant NOT et l’un de {AND, OR, IMPLY} est un sous-ensemble minimal fonctionnellement complet de {NOT, AND, OR, IMPLY, IFF} ».
    [1] https://en.wikipedia.org/wiki/Functional_completeness
  • Je ne vois pas pourquoi la préservation du vrai empêcherait la complétude fonctionnelle.
    D’abord, comment savoir que la table de vérité est préservante du vrai ? Une table de vérité n’est pas un argument logique.

• Si la complétude fonctionnelle signifie que l’on peut construire n’importe quel circuit logique, est-ce que cela veut dire que la soustraction en virgule flottante IEEE-754 est, en pratique, Turing-complète ? Ou non ?

  • Non
    La complétude fonctionnelle n’inclut pas la capacité d’itération nécessaire à la complétude de Turing
    La complétude de Turing est souvent employée à tort quand on veut parler de complétude fonctionnelle ; les deux sont parfois confondues, ou bien le terme est utilisé parce qu’il sonne mieux dans le titre d’un billet de blog ou d’un article
    mov n’est en fait pas Turing-complet ; il faut une instruction jmp : https://harrisonwl.github.io/assets/courses/malware/spring20...
    Les systèmes de chiffrement homomorphe sont fonctionnellement complets, mais pas Turing-complets. L’itération révélerait le nombre d’opérations effectuées, ce qui casserait le chiffrement
  • Pour reprendre une formule vue sur Reddit, il suffit de remplacer « porte NAND » par « soustraction » en lisant
    On peut construire une machine Turing-complète avec des portes NAND, mais dire qu’une porte NAND est Turing-complète, c’est comme dire qu’on peut vivre à l’intérieur d’une brique
    On ne peut pas vivre dans une brique, mais on peut construire une maison avec des briques et y vivre
  • Presque
    « soustraire et brancher si inférieur ou égal à 0 » est une instruction unique Turing-complète
    https://en.wikipedia.org/wiki/One-instruction_set_computer

• Je l’avais déjà posté autrefois dans un fil /r/programming, mais je le remets ici
  On peut implémenter un additionneur avec « seulement » 11 soustractions
  fn adder(a: Bit, b: Bit, c: Bit) -> (Bit, Bit) {
let r0 = c - b;
let r1 = c - r0;
let r2 = ZERO - r0;
let r3 = b - r1;
let r4 = r2 - r3;
let r5 = a - r4;
let r6 = r4 - a;
let r7 = ZERO - r5;
let r8 = r7 - r1;
let r9 = r7 - r6;
let r10 = ZERO - r8;
(r9, r10)
}

• Si l’on parle d’« entiers implémentés en logiciel uniquement avec des opérations en virgule flottante », c’est en gros comme toutes les tentatives d’utiliser le type number de JavaScript comme un int

• La phrase « si les deux significandes ont le même signe, la sortie doit aussi avoir ce signe. Mais dans x−y, si x et y ont des signes différents, la sortie doit avoir le signe de x » est soit légèrement erronée, soit elle mélange deux sens du mot signe
  Si x=5 et y=10, donc tous deux positifs, x-y vaut -5 et a donc un signe négatif
  Même si l’on suppose que le signe de la variable y est effectivement inversé, en prenant -3 et -6, le second devient 6 et le résultat est +3, donc d’un signe différent de x

  • Si x et y sont tous deux positifs, la condition « dans x−y, si x et y ont des signes différents » n’est pas satisfaite
    Il en va de même pour -3 et -6 : x et y ont le même signe, donc la condition concernant la soustraction n’est pas satisfaite
  • Il semble que le mot « différents » ait été manqué
    Les exemples portent sur des signes identiques

[asd142513]

Il y a une erreur dans le titre. Cela ne veut pas dire que la soustraction est achevée, mais qu’elle est dite fonctionnellement complète au sens où toutes les fonctions peuvent être exprimées à l’aide de la soustraction.