IEEE-754の減算は機能的に完全である

(orlp.net)

3 ポイント投稿者 GN⁺ 2023-10-09 | 2件のコメント | WhatsAppで共有

IEEE-754浮動小数点減算は、符号付きゼロと結果の符号規則を利用して任意の二値回路を作れる
-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を計算し、2つの8ビット整数の加算に約120個の浮動小数点命令が必要になる

IEEE-754の符号規則が作る出発点

IEEE-754浮動小数点減算は機能的完全性を持つ
機能的に完全であるとは、その演算だけで任意の二値回路を構成できるという意味
核心はIEEE 754-2019標準6.3節の符号ビット規則にある
- 減算x - yは和x + (-y)として扱われる
- 0は符号を持つことができ、-0と+0は異なる値として扱われる
- ただしIEEE-754の比較では-0 == +0は真である
- 入力と結果がNaNでない場合、和または差の符号はオペランドの符号規則に従う
- 同じ符号の2つの値の差が正確に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ゲートは、2番目の引数の符号を反転してから減算する方式で構成する
- f_or = lambda a, b: a - f_not(b)
- 2つの引数がどちらも-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を出力する
2つの8ビット整数を加算するには約120個の浮動小数点命令が必要になる
x86-64には実際の浮動小数点符号反転命令がないため、コンパイラはIEEE-754浮動小数点数の最上位ビットである符号ビットをトグルするマスクとXORを使用する

2件のコメント

GN⁺ 2023-10-09

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/
- 素晴らしい物語だが、コンセプトは Ken Thompson の古典 On Trusting Trust からかなり多く借りているのは明らかに見える: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
関連資料として https://dougallj.wordpress.com/2020/05/10/bitwise-conversion... がある
IEEE-754 double 1 個を、引数のビット表現における下位 32 ビットと上位 32 ビットの整数値を格納した 2 個の 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} のうち 1 つを含むすべての 2 要素の結合子集合が、{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のように使おうとするあらゆる試みと同じ
「2つの仮数の符号が同じなら、出力もその符号でなければならない。しかし x−y では x と y の符号が異なる場合、出力は x の符号でなければならない」という文は、些細に間違っているか、符号という言葉を2つの意味で混ぜて使っている
x=5, y=10 のようにどちらも正の符号なら、x-y は -5 になって負の符号になる
y 変数の符号が実際に反転すると仮定しても、-3 と -6 を選ぶと後者は 6 に反転され、結果は +3 なので x とは異なる符号になる
- x と y がどちらも正の符号なら、「x−y で x と y の符号が異なる場合」という条件を満たさない
  -3 と -6 も同様に、x と y の符号が同じなので減算に関する条件を満たさない
- 「異なる」という単語を見落としたようだ
  例は同じ符号についてのもの

asd142513 2023-10-11

タイトルに誤りがありますね。減算が完成したということではなく、減算によってすべての機能を表現できるという意味で、機能的に完全だと表現しているようです

IEEE-754の減算は機能的に完全である

IEEE-754の符号規則が作る出発点

0同士を減算したときに出る真理値表

定数falseがあれば機能的に完全になる

Pythonで作る減算論理回路

Rustで作るソフトウェア整数

関連記事

2件のコメント

Hacker News のコメント