La resta IEEE-754 es funcionalmente completa

(orlp.net)

3 puntos por GN⁺ 2023-10-09 | 2 comentarios | Compartir por WhatsApp

La resta de punto flotante IEEE-754 puede usarse para construir cualquier circuito binario aprovechando el cero con signo y las reglas de signo del resultado
Si -0 se considera false y +0 true, entonces x - y en el modo de redondeo predeterminado se comporta como A ∨ ¬B, es decir, como una compuerta IMPLY con los argumentos invertidos
Esta compuerta puede producir NOT si existe una constante false, y la combinación de NOT + IMPLY forma un conjunto de compuertas lógicas funcionalmente completo
El ejemplo en Python distingue directamente el signo de -0.0 y 0.0 para implementar f_not, f_or, f_and y f_xor basándose solo en resta
El ejemplo en Rust representa enteros de 8 bits con arreglos de f32 y calcula 23 + 19 = 42, requiriendo alrededor de 120 instrucciones de punto flotante para sumar dos enteros de 8 bits

El punto de partida creado por las reglas de signo de IEEE-754

La resta de punto flotante IEEE-754 tiene completitud funcional
Ser funcionalmente completa significa que con esa sola operación se puede construir cualquier circuito binario
La clave está en las reglas del bit de signo de la sección 6.3 del estándar IEEE 754-2019
- La resta x - y se trata como la suma x + (-y)
- El cero puede tener signo, así que -0 y +0 se consideran valores distintos
- Aun así, en las comparaciones IEEE-754 se cumple que -0 == +0
- Cuando ni las entradas ni el resultado son NaN, el signo de una suma o resta sigue las reglas de signo de los operandos
- Si la diferencia de dos valores con el mismo signo es exactamente 0, el resultado será +0 en los modos de redondeo distintos de roundTowardNegative
La construcción posterior asume el modo de redondeo predeterminado, roundTiesToEven
- También funciona de forma similar con roundTowardNegative

La tabla de verdad que aparece al restar ceros

Si solo se restan -0 y +0, se obtienen estos resultados
- -0 - -0 = +0
- -0 - +0 = -0
- +0 - -0 = +0
- +0 - +0 = +0
Si -0 se toma como false y +0 como true, la tabla de verdad de salida queda así
- 0 0 -> 1
- 0 1 -> 0
- 1 0 -> 1
- 1 1 -> 1
Esta tabla de verdad equivale a A ∨ ¬B y corresponde a una compuerta IMPLY con la forma B → A
- Comparada con una compuerta IMPLY convencional, los argumentos están invertidos

Con una constante false se vuelve funcionalmente completa

Esta tabla de verdad es funcionalmente completa cuando se tiene acceso a una constante false
Con una constante false se puede construir una compuerta NOT
NOT + IMPLY es un conjunto funcionalmente completo
NAND y NOR son funcionalmente completas por sí solas, incluso sin un valor constante específico
- Al fabricar microchips, eso tiene la ventaja de que solo hace falta producir un único tipo de componente
- No hace falta enrutar una señal low constante para construir una compuerta NOT

Circuito lógico por resta hecho en Python

El ejemplo en Python define -0.0 como false y 0.0 como true
- Como en IEEE-754 +0 y -0 son iguales al compararse, se distinguen extrayendo el signo con math.copysign
La compuerta NOT usa la propiedad de que -0 - x invierte el signo del cero
- f_not = lambda x: f_false - x
- f_not(-0.0) produce true
- f_not(+0.0) produce false
La compuerta OR se construye invirtiendo primero el signo del segundo argumento y luego restando
- f_or = lambda a, b: a - f_not(b)
- Solo devuelve false cuando ambos argumentos son -0; en los demás casos devuelve true
AND y XOR también pueden construirse combinando OR y 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)))

Enteros por software hechos en Rust

El ejemplo en Rust define Bit = f32 y representa los bits con ZERO = -0.0 y ONE = 0.0
not, or, and y xor se implementan todos a partir de resta de punto flotante, y con ellos se construye un sumador completo adder
SoftU8 = [Bit; 8] representa un entero de 8 bits
- to_softu8 convierte cada bit de un u8 en ONE o ZERO
- from_softu8 revisa el signo de cada elemento para convertirlo de vuelta a u8
El programa de ejemplo convierte 23 y 19 a SoftU8, los suma y luego imprime 42
Para sumar dos enteros de 8 bits se requieren alrededor de 120 instrucciones de punto flotante
En x86-64 no existe una instrucción real para invertir el signo en punto flotante, así que el compilador usa una máscara y XOR para alternar el bit de signo, que es el bit más alto de un número de punto flotante IEEE-754

2 comentarios

GN⁺ 2023-10-09

Opiniones en Hacker News

Me imagino que este tipo de uso perverso y extraño de instrucciones de punto flotante es algo que algún DRM podría usar como forma de ofuscar una máquina virtual.
El siguiente paso probablemente sería crear un compilador que use esta propiedad para ejecutar código fuente normal como enteros de punto flotante, y agregarle algo tipo FFI para llamar APIs normales del SO.
- Como material que puede resultar interesante, están http://tom7.org/grad/, que usa errores de punto flotante IEEE en funciones de transferencia de machine learning, y http://tom7.org/nand/, que construye compuertas lógicas y una CPU completa con NaN e infinitos de IEEE.
- Esta variante ya fue implementada con manejo de excepciones de la MMU de Intel: https://github.com/jbangert/trapcc
  Es una prueba constructiva de que el mecanismo de manejo de excepciones de la MMU de Intel es Turing completo.
  Crearon un ensamblador que convierte instrucciones Move, Branch if Zero, Decrement en código fuente C que configura varias tablas de control del procesador, y después de ejecutar ese código, la CPU calcula intentando provocar excepciones sin ejecutar ni una sola instrucción.
  Opcionalmente, el ensamblador también puede generar instrucciones X86 que muestran variables en el framebuffer VGA y transfieren el control entre instrucciones nativas de visualización e instrucciones trampa de una weird machine.
- Tiene una onda parecida a https://github.com/xoreaxeaxeax/movfuscator.
Me hizo acordar a este excelente video que construye cómputo solo con NaN e infinitos de IEEE-754: https://www.youtube.com/watch?v=5TFDG-y-EHs
- Todo ese canal, suckerpinch / Tom 7, es realmente impresionante.
  Es contenido extremadamente nerd, reflexivo y gracioso, y además está muy bien presentado.
  Lo recomiendo muchísimo, en especial para el público de HN.
En el cuento Coding Machines, un abuso similar del bit de signo era una gran pista de que una IA real había sido liberada al mundo.
https://www.teamten.com/lawrence/writings/coding-machines/
- Es una gran historia, pero el concepto claramente parece tomar bastante prestado del clásico On Trusting Trust de Ken Thompson: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
Como material relacionado está https://dougallj.wordpress.com/2020/05/10/bitwise-conversion....
Es una implementación que convierte un double IEEE-754 en un par de dos doubles que contienen los valores enteros de los 32 bits bajos y los 32 bits altos de la representación de bits del argumento, usando solo suma/resta/multiplicación de doubles.
Viendo la tabla de verdad, la resta claramente preserva la verdad, así que en realidad no parece que pueda ser funcionalmente completa.
¿Qué me estoy perdiendo?
- Estrictamente hablando, es funcionalmente completa por composición cuando se tiene acceso a la constante false, es decir, -0.0.
  Sin esa constante no es funcionalmente completa, y no es como NAND, que puede producir false a partir de cualquier valor.
  La idea del artículo era mostrar que solo con cero con signo y resta de punto flotante se puede simular cualquier circuito, y me pareció que completitud funcional era el término más conciso para expresarlo, pero si uno mira estrictamente solo la tabla de verdad, es cierto que se están doblando un poco las reglas; lo aclararé en el texto.
- No estoy muy seguro de qué significa exactamente “preservar la verdad” aquí, pero la pista es que no es solo la resta la que es funcionalmente completa, sino la resta junto con el símbolo constante 0.
  Con la resta y 0 se construye false como -0.0, y se obtiene el conjunto funcionalmente completo {->, _|_} que aparece en Wikipedia [1].
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- La resta preserva la verdad respecto del bit de signo, pero no respecto de los bits reales de la resta.
  No estoy de acuerdo con la afirmación de que los bits de la resta por sí solos sean funcionalmente completos.
  Como preserva la verdad, parece correcto concluir que no es funcionalmente completa.
- Debajo de la tabla de verdad de la implicación, con el orden de los argumentos invertido, se dice que “esta tabla de verdad es funcionalmente completa [1]”, pero la Wikipedia enlazada escribe claramente que IMPLY por sí sola no es funcionalmente completa.
  Dice que “todos los conjuntos de conectivos de dos elementos que contienen NOT y uno de {AND, OR, IMPLY} son subconjuntos mínimamente funcionalmente completos de {NOT, AND, OR, IMPLY, IFF}”.
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- No entiendo por qué preservar la verdad impediría la completitud funcional.
  Para empezar, ¿cómo se sabe que la tabla de verdad preserva la verdad? Una tabla de verdad no es un argumento lógico.
Si completitud funcional significa que se puede construir cualquier circuito lógico, ¿eso implica que la resta de punto flotante IEEE-754 es, en la práctica, Turing completa? ¿O no?
- No
  A la completitud funcional le falta la capacidad de iteración necesaria para ser Turing completa
  La completitud de Turing suele usarse mal cuando se quiere hablar de completitud funcional, y a veces se confunden ambas, o se usa así porque suena mejor como título de una entrada de blog/artículo
  mov en realidad no es Turing completo; necesita la instrucción jmp: https://harrisonwl.github.io/assets/courses/malware/spring20...
  Los sistemas de cifrado homomórfico son funcionalmente completos, pero no Turing completos. Esto se debe a que la iteración filtraría la cantidad de operaciones realizadas y rompería el cifrado
- Tomando prestada una frase que vi en Reddit, basta con leerlo cambiando la puerta NAND por la resta
  Se puede construir una máquina Turing completa con puertas NAND, pero decir que una puerta NAND es Turing completa es como decir que se puede vivir dentro de un ladrillo
  No se puede vivir dentro de un ladrillo, pero sí se puede construir una casa con ladrillos y vivir dentro de ella
- Casi correcto
  “restar y bifurcar si es menor o igual que 0” es Turing completo con una sola instrucción
  https://en.wikipedia.org/wiki/One-instruction_set_computer
Ya lo había publicado antes en un hilo de /r/programming, pero también lo dejo aquí
Se puede implementar un sumador con “solo” 11 restas
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 hablamos de “enteros implementados en software usando solo operaciones de punto flotante”, básicamente es lo mismo que todo intento de usar el number de JavaScript como si fuera un int
La frase “si los signos de las dos mantisas son iguales, la salida también debe tener ese signo. Pero en x−y, si los signos de x e y son diferentes, la salida debe tener el signo de x” es ligeramente incorrecta, o mezcla la palabra signo en dos sentidos distintos
Si ambos tienen signo positivo, como x=5, y=10, entonces x-y es -5 y queda con signo negativo
Incluso suponiendo que el signo de la variable y realmente se invierte, si tomamos -3 y -6, esta última se invierte a 6 y el resultado es +3, con un signo distinto al de x
- Si x e y tienen ambos signo positivo, no se cumple la condición “si los signos de x e y son diferentes” en x−y
  Con -3 y -6 pasa lo mismo: como x e y tienen el mismo signo, no se cumple la condición para la resta
- Parece que se te pasó la palabra “diferentes”
  Los ejemplos son sobre signos iguales

asd142513 2023-10-11

Hay un error en el título. No quiere decir que la resta esté completa, sino que se la describe como funcionalmente completa en el sentido de que todas las funciones pueden expresarse mediante la resta.