Subtração IEEE-754 é funcionalmente completa

(orlp.net)

3 pontos por GN⁺ 2023-10-09 | 2 comentários | Compartilhar no WhatsApp

A subtração de ponto flutuante IEEE-754 consegue criar circuitos binários arbitrários usando zeros com sinal e as regras de sinal do resultado
Se tratarmos -0 como false e +0 como true, no modo de arredondamento padrão x - y se comporta como A ∨ ¬B, ou seja, como uma porta IMPLY com os argumentos invertidos
Essa porta consegue criar NOT quando há uma constante false e, com a combinação NOT + IMPLY, torna-se um conjunto de portas lógicas funcionalmente completo
O exemplo em Python distingue diretamente os sinais de -0.0 e 0.0 e implementa f_not, f_or, f_and e f_xor todos com base em subtração
O exemplo em Rust representa inteiros de 8 bits com arrays de f32 e calcula 23 + 19 = 42; somar dois inteiros de 8 bits exige cerca de 120 instruções de ponto flutuante

O ponto de partida criado pelas regras de sinal do IEEE-754

A subtração de ponto flutuante IEEE-754 tem completude funcional
Ser funcionalmente completa significa que é possível construir qualquer circuito binário usando apenas essa operação
O ponto central é a regra do bit de sinal na seção 6.3 do padrão IEEE 754-2019
- A subtração x - y é tratada como a soma x + (-y)
- Zero pode ter sinal, portanto -0 e +0 são tratados como valores diferentes
- No entanto, em comparações IEEE-754, -0 == +0 é verdadeiro
- Quando entradas e resultado não são NaN, o sinal de uma soma ou diferença segue as regras de sinal dos operandos
- Se a diferença entre dois valores de mesmo sinal for exatamente 0, o resultado será +0 nos modos de arredondamento, exceto roundTowardNegative
A construção a seguir assume o modo de arredondamento padrão, roundTiesToEven
- Ela também funciona de forma semelhante em roundTowardNegative

A tabela-verdade ao subtrair zeros

Ao subtrair apenas -0 e +0, obtemos os seguintes resultados
- -0 - -0 = +0
- -0 - +0 = -0
- +0 - -0 = +0
- +0 - +0 = +0
Se definirmos -0 como false e +0 como true, a tabela-verdade de saída fica assim
- 0 0 -> 1
- 0 1 -> 0
- 1 0 -> 1
- 1 1 -> 1
Essa tabela-verdade é igual a A ∨ ¬B e equivale a uma porta IMPLY na forma B → A
- Em comparação com uma porta IMPLY comum, é uma forma com os argumentos invertidos

Com uma constante false, torna-se funcionalmente completa

Essa tabela-verdade é funcionalmente completa quando há acesso a uma constante false
Com uma constante false, é possível criar uma porta NOT
NOT + IMPLY é um conjunto funcionalmente completo
NAND e NOR são funcionalmente completas sozinhas, sem nenhum valor constante específico
- Isso tem a vantagem de exigir apenas um único tipo de componente ao fabricar microchips
- Não é necessário rotear um sinal low consistente para criar uma porta NOT

Circuito lógico de subtração feito em Python

O exemplo em Python define -0.0 como false e 0.0 como true
- Como +0 e -0 são iguais em comparações no IEEE-754, ele usa math.copysign para extrair o sinal e distingui-los
A porta NOT usa a propriedade de -0 - x inverter o sinal do zero
- f_not = lambda x: f_false - x
- f_not(-0.0) vira true
- f_not(+0.0) vira false
A porta OR é construída invertendo o sinal do segundo argumento e depois fazendo a subtração
- f_or = lambda a, b: a - f_not(b)
- Ela só vira false quando os dois argumentos são -0; nos demais casos vira true
AND e XOR também podem ser criadas combinando OR e 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)))

Inteiros de software feitos em Rust

O exemplo em Rust define Bit = f32 e representa bits com ZERO = -0.0 e ONE = 0.0
not, or, and e xor são todos implementados com base em subtração de ponto flutuante, e são usados para criar um somador completo adder
SoftU8 = [Bit; 8] representa um inteiro de 8 bits
- to_softu8 converte cada bit de um u8 em ONE ou ZERO
- from_softu8 verifica o sinal de cada elemento e converte de volta para u8
O programa de exemplo converte 23 e 19 para SoftU8, soma os dois e imprime 42
Somar dois inteiros de 8 bits exige cerca de 120 instruções de ponto flutuante
No x86-64 não há uma instrução real para inverter o sinal de ponto flutuante, então o compilador usa uma máscara e XOR para alternar o bit de sinal, que é o bit mais significativo de um número de ponto flutuante IEEE-754

2 comentários

GN⁺ 2023-10-09

Opiniões no Hacker News

Dá para imaginar esse tipo de uso bizarro e abusivo de instruções de ponto flutuante sendo usado por algum DRM como meio de ofuscar uma máquina virtual
O próximo passo provavelmente seria criar um compilador que use essas propriedades para executar código-fonte comum como inteiros de ponto flutuante, e acoplar algo como uma FFI para chamar APIs normais do sistema operacional
- Como material que pode ser interessante, há http://tom7.org/grad/, que usa erros de ponto flutuante IEEE em funções de transferência de machine learning, e http://tom7.org/nand/, que cria portas lógicas e uma CPU inteira com NaN e infinitos IEEE
- Essa variante já foi implementada antes com tratamento de exceções da MMU da Intel: https://github.com/jbangert/trapcc
  É uma prova construtiva de que o mecanismo de tratamento de exceções da MMU da Intel é Turing-completo
  Foi criado um assembler que transforma a instrução Move, Branch if Zero, Decrement em código-fonte C que configura várias tabelas de controle do processador; depois que esse código é executado, a computação acontece quando a CPU tenta gerar exceções sem executar uma única instrução sequer
  Opcionalmente, o assembler também pode gerar instruções x86 que exibem variáveis no framebuffer VGA e passam o controle entre instruções nativas de exibição e instruções de trap de weird machine
- Tem uma vibe parecida com https://github.com/xoreaxeaxeax/movfuscator
Lembrei deste excelente vídeo que constrói computação usando apenas NaN e infinitos do IEEE-754: https://www.youtube.com/watch?v=5TFDG-y-EHs
- O canal inteiro dele, suckerpinch / Tom 7, é realmente incrível
  Conteúdo extremamente nerd, cuidadoso e engraçado, e a apresentação também é muito boa
  Recomendo fortemente, especialmente para o público do HN
No conto Coding Machines, uma exploração parecida do bit de sinal era a grande pista de que uma IA de verdade havia sido solta no mundo
https://www.teamten.com/lawrence/writings/coding-machines/
- É uma ótima história, mas o conceito claramente parece ter tomado bastante emprestado do clássico On Trusting Trust, de Ken Thompson: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
Como material relacionado, há https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...
É uma implementação que converte um double IEEE-754 em um par de dois doubles contendo, a partir da representação em bits do argumento, os valores inteiros dos 32 bits inferiores e dos 32 bits superiores, usando apenas adição/subtração/multiplicação de doubles
Olhando a tabela-verdade, a subtração é claramente preservadora de verdadeiro, então na prática parece que não pode ser funcionalmente completa
O que estou deixando passar?
- Estritamente falando, ela é funcionalmente completa em combinação quando se tem acesso à constante false, ou seja, -0.0
  Sem essa constante, não é funcionalmente completa, e é diferente de NAND, que consegue produzir false a partir de qualquer valor
  A ideia do texto era mostrar que, apenas com zero sinalizado e subtração de ponto flutuante, é possível simular circuitos arbitrários; achei que completude funcional era o termo mais conciso para expressar isso, mas, olhando rigorosamente apenas a tabela-verdade, é mesmo uma pequena torção das regras, então vou deixar isso mais claro no texto
- Não sei exatamente o que “preservadora de verdadeiro” quer dizer aqui, mas a dica é que não é só a subtração que é funcionalmente completa, e sim a subtração junto com o símbolo constante 0
  Com subtração e 0, construímos false como -0.0 e obtemos o conjunto funcionalmente completo {->, _|_} que aparece na Wikipedia [1]
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- A subtração é preservadora de verdadeiro em relação ao bit de sinal, mas não é preservadora de verdadeiro em relação aos bits reais da subtração
  Não concordo com a afirmação de que os bits da subtração por si só sejam funcionalmente completos
  A conclusão de que, por ser preservadora de verdadeiro, não é funcionalmente completa parece correta
- Sob a tabela-verdade da implicação, com a ordem dos argumentos invertida, o texto diz “esta tabela-verdade é funcionalmente completa [1]”, mas a Wikipedia vinculada afirma claramente que IMPLY sozinho não é funcionalmente completo
  O que ela diz é que “todo conjunto de conectivos binários contendo NOT e um de {AND, OR, IMPLY} é um subconjunto funcionalmente completo mínimo de {NOT, AND, OR, IMPLY, IFF}”
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- Não entendo por que a preservação de verdadeiro impediria a completude funcional
  Para começo de conversa, como dá para saber que a tabela-verdade é preservadora de verdadeiro? Uma tabela-verdade não é um argumento lógico
Se completude funcional significa que é possível construir qualquer circuito lógico, então a subtração de ponto flutuante IEEE-754 é, na prática, Turing-completa? Ou não?
- Não
  A completude funcional não inclui a capacidade de repetição necessária para ser Turing-completa
  Turing-completude é muitas vezes usada incorretamente quando se quer falar de completude funcional; às vezes as pessoas confundem as duas coisas ou usam assim porque soa mais convincente em um post de blog/título de artigo
  mov na verdade não é Turing-completo; é preciso a instrução jmp: https://harrisonwl.github.io/assets/courses/malware/spring20...
  Sistemas de criptografia homomórfica são funcionalmente completos, mas não Turing-completos. Isso porque laços vazariam o número de operações executadas, quebrando a criptografia
- Pegando emprestada uma frase que vi no Reddit, basta ler trocando porta NAND por subtração
  É possível construir uma máquina Turing-completa com portas NAND, mas dizer que uma porta NAND é Turing-completa é como dizer que dá para morar dentro de um tijolo
  Você não consegue morar dentro de um tijolo, mas pode construir uma casa com tijolos e morar nela
- Quase isso
  “subtraia e desvie se for menor ou igual a 0” é Turing-completa como uma única instrução
  https://en.wikipedia.org/wiki/One-instruction_set_computer
Já tinha postado isto antes em uma thread do /r/programming, mas vou deixar aqui também
Dá para implementar um somador com “apenas” 11 subtrações
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)
}
Se forem “inteiros implementados em software usando apenas operações de ponto flutuante”, é basicamente o mesmo que toda tentativa de usar o number do JavaScript como int
A frase “se os sinais dos dois significandos forem iguais, a saída também deve ter esse sinal. Mas em x−y, se os sinais de x e y forem diferentes, a saída deve ter o sinal de x” está ligeiramente errada, ou mistura a palavra sinal em dois sentidos
Se x=5 e y=10, ambos têm sinal positivo, mas x-y é -5, portanto tem sinal negativo
Mesmo supondo que o sinal da variável y seja de fato invertido, se escolhermos -3 e -6, o segundo vira 6 e o resultado é +3, com sinal diferente de x
- Se x e y têm ambos sinal positivo, a condição “se os sinais de x e y forem diferentes em x−y” não é satisfeita
  O mesmo vale para -3 e -6: como x e y têm o mesmo sinal, não satisfazem a condição sobre a subtração
- Parece que você deixou passar a palavra “diferentes”
  Os exemplos são sobre sinais iguais

asd142513 2023-10-11

Há um erro no título. Não quer dizer que a subtração foi concluída, mas sim que todas as funcionalidades podem ser expressas por meio da subtração, por isso foi dito que ela é funcionalmente completa.