IEEE-754-Subtraktion ist funktional vollständig

 (orlp.net)
3 Punkte von GN⁺ 2023-10-09 | 2 Kommentare | Auf WhatsApp teilen
  • IEEE-754-Gleitkomma-Subtraktion kann mithilfe von vorzeichenbehaftetem Nullwert und Regeln für das Ergebnisvorzeichen beliebige binäre Schaltungen bilden
  • Wenn man -0 als false und +0 als true betrachtet, verhält sich x - y im Standard-Rundungsmodus wie A ∨ ¬B, also wie ein IMPLY-Gatter mit vertauschten Argumenten
  • Mit einer Konstante false lässt sich aus diesem Gatter ein NOT bilden; die Kombination aus NOT + IMPLY ergibt damit eine funktional vollständige Menge logischer Gatter
  • Das Python-Beispiel unterscheidet das Vorzeichen von -0.0 und 0.0 direkt und implementiert f_not, f_or, f_and, f_xor vollständig subtraktionsbasiert
  • Das Rust-Beispiel stellt 8-Bit-Ganzzahlen als f32-Arrays dar, berechnet 23 + 19 = 42 und benötigt für die Addition zweier 8-Bit-Ganzzahlen etwa 120 Gleitkomma-Instruktionen

Der Ausgangspunkt: Vorzeichenregeln in IEEE-754

  • Die IEEE-754-Gleitkomma-Subtraktion ist funktional vollständig
  • Funktional vollständig bedeutet, dass sich allein mit dieser Operation beliebige binäre Schaltungen konstruieren lassen
  • Der Kern liegt in den Regeln für das Vorzeichenbit in Abschnitt 6.3 des Standards IEEE 754-2019
    • Die Subtraktion x - y wird als Summe x + (-y) behandelt
    • Null kann ein Vorzeichen tragen, daher werden -0 und +0 als unterschiedliche Werte behandelt
    • In IEEE-754-Vergleichen gilt allerdings -0 == +0 als wahr
    • Wenn Eingaben und Ergebnis kein NaN sind, folgt das Vorzeichen von Summe oder Differenz den Vorzeichenregeln der Operanden
    • Wenn die Differenz zweier Werte mit gleichem Vorzeichen exakt 0 ist, wird das Ergebnis in Rundungsmodi außer roundTowardNegative zu +0
  • Die weitere Konstruktion nimmt den Standard-Rundungsmodus roundTiesToEven an
    • Unter roundTowardNegative funktioniert es ähnlich

Wahrheitstabelle für die Subtraktion von Nullen

  • Wenn man nur -0 und +0 subtrahiert, ergeben sich folgende Resultate
    • -0 - -0 = +0
    • -0 - +0 = -0
    • +0 - -0 = +0
    • +0 - +0 = +0
  • Setzt man -0 als false und +0 als true, ergibt sich folgende Wahrheitstabelle
    • 0 0 -> 1
    • 0 1 -> 0
    • 1 0 -> 1
    • 1 1 -> 1
  • Diese Wahrheitstabelle entspricht A ∨ ¬B und damit dem IMPLY-Gatter in der Form B → A
    • Verglichen mit dem üblichen IMPLY-Gatter sind die Argumente vertauscht

Mit einer Konstante false wird es funktional vollständig

  • Diese Wahrheitstabelle ist funktional vollständig, wenn Zugriff auf eine Konstante false besteht
  • Mit einer Konstante false lässt sich ein NOT-Gatter konstruieren
  • NOT + IMPLY ist eine funktional vollständige Menge
  • NAND und NOR sind auch ohne bestimmte Konstantenwerte jeweils für sich funktional vollständig
    • Beim Entwurf von Mikrochips hat das den Vorteil, dass nur ein einziger Bauteiltyp hergestellt werden muss
    • Für ein NOT-Gatter muss kein konstanter Low-Pegel geroutet werden

Mit Python gebaute Subtraktions-Logikschaltung

  • Das Python-Beispiel definiert -0.0 als false und 0.0 als true
    • Da +0 und -0 in IEEE-754 bei Vergleichen gleich sind, werden sie mit math.copysign über das Vorzeichen unterschieden
  • Das NOT-Gatter nutzt die Eigenschaft, dass -0 - x das Vorzeichen von 0 umkehrt
    • f_not = lambda x: f_false - x
    • f_not(-0.0) wird zu true
    • f_not(+0.0) wird zu false
  • Das OR-Gatter wird konstruiert, indem zunächst das Vorzeichen des zweiten Arguments invertiert und dann subtrahiert wird
    • f_or = lambda a, b: a - f_not(b)
    • Nur wenn beide Argumente -0 sind, ist das Ergebnis false, sonst true
  • Auch AND und XOR lassen sich durch die Kombination von OR und NOT bilden
    • 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)))

Software-Ganzzahlen in Rust

  • Das Rust-Beispiel verwendet Bit = f32 und stellt Bits mit ZERO = -0.0 und ONE = 0.0 dar
  • not, or, and, xor werden alle auf Basis von Gleitkomma-Subtraktion implementiert; darauf aufbauend entsteht ein Volladdierer adder
  • SoftU8 = [Bit; 8] repräsentiert eine 8-Bit-Ganzzahl
    • to_softu8 wandelt jedes Bit eines u8 in ONE oder ZERO um
    • from_softu8 prüft das Vorzeichen jedes Elements und wandelt es zurück in u8
  • Das Beispielprogramm wandelt 23 und 19 in SoftU8 um, addiert sie und gibt 42 aus
  • Für die Addition zweier 8-Bit-Ganzzahlen werden etwa 120 Gleitkomma-Instruktionen benötigt
  • Da es auf x86-64 keine echte Instruktion zum Invertieren des Gleitkomma-Vorzeichens gibt, verwendet der Compiler eine Maske und XOR, um das Vorzeichenbit als höchstwertiges Bit einer IEEE-754-Gleitkommazahl umzuschalten

Verwandte Beiträge

2 Kommentare

 
GN⁺ 2023-10-09
Hacker-News-Kommentare

  • Eine solche kuriose Zweckentfremdung von Floating-Point-Instruktionen kann ich mir gut als Mittel vorstellen, mit dem irgendein DRM eine virtuelle Maschine obfuskiert.
    Der nächste Schritt wäre wohl, mit dieser Eigenschaft einen Compiler zu bauen, der normalen Quellcode als Floating-Point-Integer ausführt, und so etwas wie ein FFI anzuhängen, um normale OS-APIs aufzurufen.

    • Als möglicherweise interessante Materialien gibt es http://tom7.org/grad/, wo IEEE-Floating-Point-Fehler für Machine-Learning-Transferfunktionen genutzt werden, sowie http://tom7.org/nand/, wo aus IEEE-NaNs und Unendlichkeiten Logikgatter und eine ganze CPU gebaut werden.
    • Diese Variante wurde bereits mit Intel-MMU-Exception-Handling umgesetzt: https://github.com/jbangert/trapcc
      Das ist ein konstruktiver Beweis, dass der Exception-Handling-Mechanismus der Intel-MMU Turing-vollständig ist.
      Es wurde ein Assembler gebaut, der Move, Branch if Zero, Decrement-Anweisungen in C-Quellcode übersetzt, der mehrere Prozessor-Kontrolltabellen einrichtet; nachdem dieser Code ausgeführt wurde, rechnet die CPU, indem sie versucht, Exceptions auszulösen, ohne eine einzige Instruktion auszuführen.
      Optional kann der Assembler auch X86-Instruktionen erzeugen, die Variablen im VGA-Framebuffer anzeigen und die Kontrolle zwischen nativen Anzeige-Instruktionen und weird machine-Trap-Instruktionen übergeben.
    • Fühlt sich ähnlich an wie https://github.com/xoreaxeaxeax/movfuscator.

  • Mir fällt dieses hervorragende Video ein, in dem Berechnungen nur mit IEEE-754-NaN und Unendlichkeit gebaut werden: https://www.youtube.com/watch?v=5TFDG-y-EHs

    • Der ganze Kanal, suckerpinch / Tom 7, ist wirklich großartig.
      Extrem nerdiger, durchdachter und lustiger Content, und die Präsentation ist ebenfalls sehr gut.
      Besonders für die HN-Leserschaft sehr zu empfehlen.

  • In der Kurzgeschichte Coding Machines war ein ähnlicher Missbrauch des Vorzeichenbits der große Hinweis darauf, dass eine echte KI auf die Welt losgelassen worden war.
    https://www.teamten.com/lawrence/writings/coding-machines/

  • Als verwandtes Material gibt es https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...
    Das ist eine Implementierung, die ein IEEE-754-Double in ein Paar aus zwei Doubles umwandelt, die den unteren 32-Bit- und den oberen 32-Bit-Integerwert der Bitdarstellung des Arguments enthalten, und dabei nur Double-Addition/-Subtraktion/-Multiplikation verwendet.

  • Wenn man sich die Wahrheitstabelle ansieht, ist Subtraktion eindeutig wahrheitserhaltend, sodass sie in Wirklichkeit nicht funktional vollständig sein kann.
    Was übersehe ich?

    • Streng genommen ist sie in Kombination funktional vollständig, wenn man Zugriff auf die Konstante false, also -0.0, hat.
      Ohne diese Konstante ist sie nicht funktional vollständig, anders als NAND, das aus jedem Wert false erzeugen kann.
      Der Punkt des Artikels war zu zeigen, dass man mit vorzeichenbehafteter Null und Floating-Point-Subtraktion beliebige Schaltungen nachbilden kann; funktionale Vollständigkeit schien mir der knappste Begriff dafür zu sein, aber wenn man nur streng auf die Wahrheitstabelle schaut, ist das eine leichte Verbiegung der Regeln. Ich werde das im Artikel klarstellen.
    • Ich bin mir nicht ganz sicher, was „wahrheitserhaltend“ hier genau bedeuten soll, aber der Hinweis ist, dass nicht Subtraktion allein funktional vollständig ist, sondern Subtraktion zusammen mit dem Konstantensymbol 0.
      Mit Subtraktion und 0 erzeugt man false als -0.0 und erhält die auf Wikipedia [1] genannte funktional vollständige Menge {->, _|_}.
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Subtraktion ist in Bezug auf das Vorzeichenbit wahrheitserhaltend, aber nicht in Bezug auf die eigentlichen Subtraktionsbits.
      Ich stimme der Behauptung nicht zu, dass die Subtraktionsbits allein funktional vollständig sind.
      Die Einschätzung, dass sie wegen Wahrheitserhaltung nicht funktional vollständig sind, scheint richtig zu sein.
    • Unter der Wahrheitstabelle der Implikation mit vertauschter Argumentreihenfolge heißt es: „Diese Wahrheitstabelle ist funktional vollständig [1]“, aber der verlinkte Wikipedia-Artikel schreibt klar, dass IMPLY allein nicht funktional vollständig ist.
      Dort steht, dass jede zweielementige Menge von Junktoren, die NOT und eines aus {AND, OR, IMPLY} enthält, eine minimale funktional vollständige Teilmenge von {NOT, AND, OR, IMPLY, IFF} ist.
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Ich verstehe nicht, warum Wahrheitserhaltung funktionale Vollständigkeit verhindern sollte.
      Wie kann man überhaupt wissen, ob eine Wahrheitstabelle wahrheitserhaltend ist? Eine Wahrheitstabelle ist kein logisches Argument.

  • Wenn funktionale Vollständigkeit bedeutet, dass man jede beliebige logische Schaltung bauen kann: Heißt das dann, dass IEEE-754-Gleitkomma-Subtraktion praktisch Turing-vollständig ist? Oder nicht?

    • Nein
      Bei funktionaler Vollständigkeit fehlt die Fähigkeit zur Wiederholung, die für Turing-Vollständigkeit nötig ist
      Turing-Vollständigkeit wird oft fälschlich verwendet, wenn eigentlich funktionale Vollständigkeit gemeint ist; manchmal werden beide verwechselt oder es klingt als Blogpost-/Artikelüberschrift einfach plausibler
      mov ist tatsächlich nicht Turing-vollständig, man braucht den jmp-Befehl: https://harrisonwl.github.io/assets/courses/malware/spring20...
      Homomorphe Verschlüsselungssysteme sind funktional vollständig, aber nicht Turing-vollständig. Wiederholung würde die Anzahl der ausgeführten Operationen verraten und damit die Verschlüsselung brechen
    • Um einen Satz zu übernehmen, den ich auf Reddit gesehen habe: Man kann NAND-Gatter gedanklich durch Subtraktion ersetzen
      Man kann mit NAND-Gattern eine Turing-vollständige Maschine bauen, aber zu sagen, ein NAND-Gatter sei Turing-vollständig, ist so, als würde man sagen, man könne in einem Ziegelstein wohnen
      In einem Ziegelstein kann man nicht wohnen, aber man kann aus Ziegelsteinen ein Haus bauen und darin wohnen
    • Fast richtig
      „Subtrahiere und verzweige, wenn ≤ 0“ ist als einzelne Instruktion Turing-vollständig
      https://en.wikipedia.org/wiki/One-instruction_set_computer

  • Ich hatte das früher schon in einem /r/programming-Thread gepostet, stelle es aber auch hier ein
    Einen Addierer kann man mit „nur“ 11 Subtraktionen implementieren
    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)
    }

  • Wenn es um „Integer, die in Software nur mit Gleitkomma-Operationen implementiert sind“ geht, ist das im Grunde wie jeder Versuch in JavaScript, number wie int zu verwenden

  • Der Satz „Wenn die Vorzeichen der beiden Signifikanden gleich sind, muss die Ausgabe ebenfalls dieses Vorzeichen haben. Bei x−y muss die Ausgabe aber das Vorzeichen von x haben, wenn x und y unterschiedliche Vorzeichen haben“ ist in einer Kleinigkeit falsch oder vermischt das Wort Vorzeichen in zwei Bedeutungen
    Wenn x=5 und y=10 sind, also beide ein positives Vorzeichen haben, ergibt x-y den Wert -5 und damit ein negatives Vorzeichen
    Selbst wenn man annimmt, dass das Vorzeichen der Variablen y tatsächlich invertiert wird: Wählt man -3 und -6, wird Letzteres zu 6 invertiert und das Ergebnis ist +3, also ein anderes Vorzeichen als x

    • Wenn x und y beide ein positives Vorzeichen haben, erfüllt das nicht die Bedingung „wenn x und y bei x−y unterschiedliche Vorzeichen haben“
      Dasselbe gilt für -3 und -6: Auch dort haben x und y dasselbe Vorzeichen, also erfüllen sie die Bedingung für die Subtraktion nicht
    • Du scheinst das Wort „unterschiedliche“ übersehen zu haben
      Die Beispiele handeln von gleichen Vorzeichen
 
asd142513 2023-10-11

Im Titel ist ein Fehler. Es heißt nicht, dass die Subtraktion fertiggestellt wurde, sondern dass sich mit der Subtraktion alle Funktionen ausdrücken lassen und sie in diesem Sinn als funktional vollständig bezeichnet wird.