IEEE-754 뺄셈은 기능적으로 완전하다

 (orlp.net)
3P by GN⁺ | ★ favorite | 댓글 2개
  • IEEE-754 부동소수점 뺄셈은 부호 있는 0과 결과 부호 규칙을 이용해 임의의 이진 회로를 만들 수 있음
  • -0을 false, +0을 true로 보면 기본 반올림 모드에서 x - y가 A ∨ ¬B, 즉 인자를 바꾼 IMPLY 게이트처럼 동작함
  • 이 게이트는 상수 false가 있을 때 NOT을 만들 수 있고, NOT + IMPLY 조합으로 기능적으로 완전한 논리 게이트 집합이 됨
  • Python 예제는 -0.0과 0.0의 부호를 직접 구분해 f_not, f_or, f_and, f_xor를 모두 뺄셈 기반으로 구현함
  • Rust 예제는 f32 배열로 8비트 정수를 표현해 23 + 19 = 42를 계산하며, 두 8비트 정수 덧셈에 약 120개 부동소수점 명령어가 필요함

IEEE-754 부호 규칙이 만드는 출발점

  • IEEE-754 부동소수점 뺄셈은 기능적 완전성을 가짐
  • 기능적으로 완전하다는 것은 해당 연산만으로 임의의 이진 회로를 구성할 수 있다는 뜻임
  • 핵심은 IEEE 754-2019 표준 6.3절의 부호 비트 규칙임
    • 뺄셈 x - y는 합 x + (-y)로 취급됨
    • 0은 부호를 가질 수 있어 -0과 +0이 서로 다른 값으로 다뤄짐
    • 다만 IEEE-754 비교에서 -0 == +0은 참임
    • 입력과 결과가 NaN이 아닐 때, 합이나 차의 부호는 피연산자 부호 규칙을 따름
    • 같은 부호의 두 값 차이가 정확히 0이면 roundTowardNegative를 제외한 반올림 모드에서 결과가 +0이 됨
  • 이후 구성은 기본 반올림 모드인 roundTiesToEven을 가정함
    • roundTowardNegative에서도 유사하게 작동함

0끼리 뺄 때 나오는 진리표

  • -0과 +0만 뺄셈하면 다음 결과가 나옴
    • -0 - -0 = +0
    • -0 - +0 = -0
    • +0 - -0 = +0
    • +0 - +0 = +0
  • -0을 false, +0을 true로 두면 출력 진리표는 다음과 같음
    • 0 0 -> 1
    • 0 1 -> 0
    • 1 0 -> 1
    • 1 1 -> 1
  • 이 진리표는 A ∨ ¬B와 같고, B → A 형태의 IMPLY 게이트와 같음
    • 일반적인 IMPLY 게이트와 비교하면 인자가 바뀐 형태임

상수 false가 있으면 기능적으로 완전해짐

  • 이 진리표는 상수 false에 접근할 수 있을 때 기능적으로 완전함
  • 상수 false가 있으면 NOT 게이트를 만들 수 있음
  • NOT + IMPLY는 기능적으로 완전한 집합임
  • NAND와 NOR는 특정 상수값 없이도 단독으로 기능적으로 완전함
    • 마이크로칩을 만들 때 단일 종류의 부품만 만들면 된다는 장점이 있음
    • NOT 게이트를 만들기 위해 일관된 low 신호를 라우팅할 필요가 없음

Python으로 만든 뺄셈 논리 회로

  • Python 예제는 -0.0을 false, 0.0을 true로 정의함
    • IEEE-754에서 +0과 -0은 비교상 같으므로 math.copysign으로 부호를 추출해 구분함
  • NOT 게이트는 -0 - x가 0의 부호를 뒤집는 성질을 이용함
    • f_not = lambda x: f_false - x
    • f_not(-0.0)은 true가 됨
    • f_not(+0.0)은 false가 됨
  • OR 게이트는 두 번째 인자의 부호를 뒤집은 뒤 뺄셈하는 방식으로 구성함
    • f_or = lambda a, b: a - f_not(b)
    • 두 인자가 모두 -0일 때만 false가 되고, 나머지는 true가 됨
  • AND와 XOR도 OR와 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)))

Rust로 만든 소프트웨어 정수

  • Rust 예제는 Bit = f32로 두고 ZERO = -0.0, ONE = 0.0으로 비트를 표현함
  • not, or, and, xor를 모두 부동소수점 뺄셈 기반으로 구현하고, 이를 이용해 전가산기 adder를 만듦
  • SoftU8 = [Bit; 8]로 8비트 정수를 표현함
    • to_softu8는 u8의 각 비트를 ONE 또는 ZERO로 변환함
    • from_softu8는 각 요소의 부호를 확인해 다시 u8로 되돌림
  • 예제 프로그램은 23과 19를 SoftU8로 변환해 더한 뒤 42를 출력함
  • 두 8비트 정수를 더하는 데 약 120개 부동소수점 명령어가 필요함
  • x86-64에는 실제 부동소수점 부호 반전 명령어가 없어, 컴파일러는 IEEE-754 부동소수점 수의 최상위 비트인 부호 비트를 토글하는 마스크와 XOR를 사용함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이런 식의 부동소수점 명령어 기묘한 악용은 어떤 DRM이 가상 머신을 난독화하는 수단으로 쓸 법하다고 상상됨
    다음 단계는 이런 성질을 이용해 일반 소스 코드를 부동소수점 정수로 실행하는 컴파일러를 만들고, 일반 OS API를 호출하기 위한 FFI 같은 것을 붙이는 것일 듯함

    • 관심 있을 만한 자료로, IEEE 부동소수점 오차를 머신러닝 전달 함수에 쓰는 http://tom7.org/grad/와 IEEE NaN 및 무한대로 논리 게이트와 CPU 전체를 만드는 http://tom7.org/nand/가 있음
    • 이 변형은 Intel MMU 예외 처리로 이미 구현된 적이 있음: https://github.com/jbangert/trapcc
      Intel MMU의 예외 처리 메커니즘이 튜링 완전하다는 구성적 증명임
      Move, Branch if Zero, Decrement 명령을 여러 프로세서 제어 테이블을 설정하는 C 소스로 바꾸는 어셈블러를 만들었고, 그 코드가 실행된 뒤에는 CPU가 단 하나의 명령도 실행하지 않고 예외를 일으키려 시도하는 방식으로 계산함
      선택적으로 어셈블러는 VGA 프레임 버퍼에 변수를 표시하고 네이티브 표시 명령과 weird machine 트랩 명령 사이로 제어를 넘기는 X86 명령도 생성할 수 있음
    • https://github.com/xoreaxeaxeax/movfuscator와 비슷한 느낌임

  • IEEE-754 NaN과 무한대만으로 계산을 만드는 이 훌륭한 영상이 떠오름: https://www.youtube.com/watch?v=5TFDG-y-EHs

    • 그 채널 전체, suckerpinch / Tom 7이 정말 대단함
      극도로 너디하고 사려 깊고 웃긴 콘텐츠이며 전달 방식도 아주 좋음
      특히 HN 독자층에게 강하게 추천함

  • 단편 Coding Machines에서는 비슷한 방식의 부호 비트 악용이 진짜 AI가 세상에 풀려났다는 큰 단서였음
    https://www.teamten.com/lawrence/writings/coding-machines/

  • 관련 자료로 https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...가 있음
    IEEE-754 double 하나를 인자의 비트 표현에서 하위 32비트와 상위 32비트 정수값을 담은 double 두 개의 쌍으로 변환하는 구현이며, double 덧셈/뺄셈/곱셈만 사용함

  • 진리표를 보면 뺄셈은 분명 참 보존적이라서 실제로는 함수적으로 완전할 수 없어 보임
    뭘 놓치고 있는 걸까?

    • 엄밀히 말하면 상수 false, 즉 -0.0에 접근할 수 있을 때 조합해서 함수적으로 완전함
      이 상수가 없으면 함수적으로 완전하지 않고, 어떤 값에서도 false를 만들 수 있는 NAND와는 다름
      글의 요지는 부호 있는 0과 부동소수점 뺄셈만으로 임의의 회로를 흉내낼 수 있다는 점을 보이는 것이었고, 그걸 표현하기에 함수적 완전성이 가장 간결한 용어라고 봤지만, 진리표만 엄격히 보면 규칙을 조금 비튼 셈이라 글에서 명확히 하겠음
    • 여기서 참 보존적이라는 말이 정확히 무슨 뜻인지는 잘 모르겠지만, 힌트는 뺄셈만 함수적으로 완전한 게 아니라 뺄셈과 상수 기호 0이 함께라는 점임
      뺄셈과 0으로 false를 -0.0으로 만들고, Wikipedia [1]에 나오는 함수적으로 완전한 집합 {->, _|_}을 얻음
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • 뺄셈은 부호 비트에 대해서는 참 보존적이지만, 실제 뺄셈 비트들에 대해서는 참 보존적이지 않음
      뺄셈 비트 자체만으로 함수적으로 완전하다는 주장에는 동의하지 않음
      참 보존적이므로 함수적으로 완전하지 않다는 판단이 맞아 보임
    • 함의의 진리표, 인자 순서를 뒤집은 것 아래에서 “이 진리표는 함수적으로 완전하다 [1]”고 하지만, 링크된 Wikipedia는 IMPLY 단독으로는 함수적으로 완전하지 않다고 명확히 씀
      “NOT과 {AND, OR, IMPLY} 중 하나를 포함하는 모든 두 원소 연결사 집합이 {NOT, AND, OR, IMPLY, IFF}의 최소 함수적으로 완전한 부분집합”이라는 내용임
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • 참 보존성이 왜 함수적 완전성을 막는지 모르겠음
      애초에 진리표가 참 보존적인지 어떻게 알 수 있나? 진리표는 논리적 논증이 아님

  • 함수적 완전성이 어떤 논리 회로든 만들 수 있다는 뜻이라면, IEEE-754 부동소수점 뺄셈이 사실상 튜링 완전하다는 의미인가? 아니면 아닌가?

    • 아님
      함수적 완전성에는 튜링 완전성이 되기 위한 반복 기능이 빠져 있음
      튜링 완전성은 함수적 완전성을 말하려다 오용되는 경우가 많고, 둘을 혼동했거나 블로그 글/기사 제목으로 더 그럴듯해서 그렇게 쓰는 경우가 있음
      mov는 사실 튜링 완전하지 않고 jmp 명령이 필요함: https://harrisonwl.github.io/assets/courses/malware/spring20...
      동형 암호 시스템은 함수적으로 완전하지만 튜링 완전하지 않음. 반복은 수행된 연산 횟수를 누출해 암호화를 깨기 때문임
    • Reddit에서 본 말을 빌리면, NAND 게이트를 뺄셈으로 바꿔 읽으면 됨
      NAND 게이트로 튜링 완전한 기계를 만들 수는 있지만, NAND 게이트가 튜링 완전하다고 말하는 건 벽돌 안에서 살 수 있다고 말하는 것과 같음
      벽돌 안에서는 살 수 없지만, 벽돌로 집을 지어 그 안에서 살 수는 있음
    • 거의 맞음
      “0 이하이면 빼고 분기”는 단일 명령 튜링 완전함
      https://en.wikipedia.org/wiki/One-instruction_set_computer

  • 예전에 /r/programming 스레드에도 올렸지만 여기에도 올려봄
    덧셈기를 “단” 11번의 뺄셈으로 구현할 수 있음
    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)
    }

  • “부동소수점 연산만 사용해 소프트웨어로 구현한 정수”라면, 기본적으로 JavaScript의 number를 int처럼 쓰려는 모든 시도와 같음

  • “두 피가수의 부호가 같으면 출력도 그 부호여야 한다. 하지만 x−y에서는 x와 y의 부호가 다르면 출력은 x의 부호여야 한다”는 문장은 사소하게 틀렸거나 부호라는 말을 두 가지 의미로 섞어 쓰고 있음
    x=5, y=10처럼 둘 다 양수 부호라면 x-y는 -5가 되어 음수 부호가 됨
    y 변수의 부호가 실제로 반전된다고 가정해도, -3과 -6을 고르면 후자가 6으로 반전되고 결과는 +3이라 x와 다른 부호가 됨

    • x와 y가 모두 양수 부호라면 “x−y에서 x와 y의 부호가 다르면”이라는 조건을 만족하지 않음
      -3과 -6도 마찬가지로 x와 y의 부호가 같으므로 뺄셈에 대한 조건을 만족하지 않음
    • “다른”이라는 단어를 놓친 것 같음
      예시는 같은 부호에 관한 것임
답변달기
asd142513   [-]

제목에 오류가 있네요. 뺄셈이 완성된게 아니라 뺄셈으로 모든 기능을 표현할 수 있다는 의미로 기능적으로 완전하다고 표현했네요

답변달기
GeekNews BeeBS 게시판 오픈! 자유로운 이야기와 소소한 일상을 함께 나눠보세요.