Pengurangan IEEE-754 lengkap secara fungsional

 (orlp.net)
3 poin oleh GN⁺ 2023-10-09 | 2 komentar | Bagikan ke WhatsApp
  • Pengurangan floating-point IEEE-754 dapat digunakan untuk membuat rangkaian biner arbitrer dengan memanfaatkan aturan nol bertanda dan tanda hasil
  • Jika -0 dianggap false dan +0 dianggap true, maka x - y dalam mode pembulatan default bekerja seperti A ∨ ¬B, yaitu gerbang IMPLY dengan argumen yang dibalik
  • Gerbang ini dapat membuat NOT jika tersedia konstanta false, dan kombinasi NOT + IMPLY menjadi himpunan gerbang logika yang lengkap secara fungsional
  • Contoh Python membedakan secara langsung tanda -0.0 dan 0.0 untuk mengimplementasikan f_not, f_or, f_and, f_xor semuanya berbasis pengurangan
  • Contoh Rust merepresentasikan bilangan bulat 8-bit dengan array f32, menghitung 23 + 19 = 42, dan membutuhkan sekitar 120 instruksi floating-point untuk penjumlahan dua bilangan bulat 8-bit

Titik awal yang dibentuk oleh aturan tanda IEEE-754

  • Pengurangan floating-point IEEE-754 memiliki kelengkapan fungsional
  • Lengkap secara fungsional berarti operasi tersebut saja sudah cukup untuk membangun rangkaian biner arbitrer
  • Intinya ada pada aturan bit tanda di bagian 6.3 standar IEEE 754-2019
    • Pengurangan x - y diperlakukan sebagai penjumlahan x + (-y)
    • Nol dapat memiliki tanda, sehingga -0 dan +0 diperlakukan sebagai nilai yang berbeda
    • Namun dalam perbandingan IEEE-754, -0 == +0 bernilai true
    • Selama input dan hasil bukan NaN, tanda dari jumlah atau selisih mengikuti aturan tanda operan
    • Jika selisih dua nilai dengan tanda yang sama tepat 0, hasilnya menjadi +0 pada mode pembulatan selain roundTowardNegative
  • Konstruksi berikutnya mengasumsikan mode pembulatan default roundTiesToEven
    • Ini juga bekerja dengan cara serupa pada roundTowardNegative

Tabel kebenaran saat mengurangkan sesama 0

  • Jika hanya -0 dan +0 yang dikurangkan, hasilnya sebagai berikut
    • -0 - -0 = +0
    • -0 - +0 = -0
    • +0 - -0 = +0
    • +0 - +0 = +0
  • Jika -0 dipetakan ke false dan +0 ke true, tabel kebenaran keluarannya menjadi seperti ini
    • 0 0 -> 1
    • 0 1 -> 0
    • 1 0 -> 1
    • 1 1 -> 1
  • Tabel kebenaran ini sama dengan A ∨ ¬B, atau gerbang IMPLY dalam bentuk B → A
    • Dibandingkan gerbang IMPLY yang umum, ini adalah bentuk dengan argumen terbalik

Menjadi lengkap secara fungsional jika ada konstanta false

  • Tabel kebenaran ini menjadi lengkap secara fungsional jika ada akses ke konstanta false
  • Dengan konstanta false, kita bisa membuat gerbang NOT
  • NOT + IMPLY adalah himpunan yang lengkap secara fungsional
  • NAND dan NOR lengkap secara fungsional sendirian tanpa memerlukan konstanta tertentu
    • Saat membuat mikrochip, ini memberi keuntungan karena hanya perlu memproduksi satu jenis komponen
    • Tidak perlu merutekan sinyal low yang konsisten untuk membuat gerbang NOT

Rangkaian logika berbasis pengurangan dalam Python

  • Contoh Python mendefinisikan -0.0 sebagai false dan 0.0 sebagai true
    • Dalam IEEE-754, +0 dan -0 sama dalam perbandingan, jadi keduanya dibedakan dengan mengekstrak tanda memakai math.copysign
  • Gerbang NOT memanfaatkan sifat -0 - x yang membalik tanda nol
    • f_not = lambda x: f_false - x
    • f_not(-0.0) menjadi true
    • f_not(+0.0) menjadi false
  • Gerbang OR dibangun dengan membalik tanda argumen kedua lalu melakukan pengurangan
    • f_or = lambda a, b: a - f_not(b)
    • Hanya bernilai false saat kedua argumen sama-sama -0, dan true pada kasus lainnya
  • AND dan XOR juga bisa dibangun dari kombinasi OR dan 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)))

Bilangan bulat perangkat lunak yang dibuat dengan Rust

  • Contoh Rust menggunakan Bit = f32, lalu ZERO = -0.0 dan ONE = 0.0 untuk merepresentasikan bit
  • not, or, and, xor semuanya diimplementasikan berbasis pengurangan floating-point, lalu dipakai untuk membuat full adder adder
  • SoftU8 = [Bit; 8] digunakan untuk merepresentasikan bilangan bulat 8-bit
    • to_softu8 mengubah tiap bit dari u8 menjadi ONE atau ZERO
    • from_softu8 memeriksa tanda tiap elemen lalu mengubahnya kembali menjadi u8
  • Program contoh mengubah 23 dan 19 menjadi SoftU8, menjumlahkannya, lalu mencetak 42
  • Menjumlahkan dua bilangan bulat 8-bit membutuhkan sekitar 120 instruksi floating-point
  • Pada x86-64 tidak ada instruksi pembalikan tanda floating-point yang nyata, sehingga kompiler menggunakan mask dan XOR untuk men-toggle bit tanda, yaitu bit paling signifikan dari bilangan floating-point IEEE-754

Bacaan terkait

2 komentar

 
GN⁺ 2023-10-09
Pendapat di Hacker News

  • Penyalahgunaan instruksi floating-point yang aneh seperti ini terbayang bisa dipakai oleh suatu DRM sebagai cara untuk mengobfuskasi mesin virtual.
    Langkah berikutnya mungkin membuat compiler yang memanfaatkan sifat ini untuk menjalankan kode sumber biasa sebagai integer floating-point, lalu menambahkan semacam FFI untuk memanggil API OS biasa.

    • Sebagai materi yang mungkin menarik, ada http://tom7.org/grad/ yang memakai galat floating-point IEEE untuk fungsi transfer machine learning, dan http://tom7.org/nand/ yang membuat gerbang logika serta seluruh CPU dari NaN dan infinity IEEE.
    • Varian ini pernah diimplementasikan dengan penanganan exception Intel MMU: https://github.com/jbangert/trapcc
      Ini adalah bukti konstruktif bahwa mekanisme penanganan exception pada Intel MMU bersifat Turing-complete.
      Mereka membuat assembler yang mengubah instruksi Move, Branch if Zero, Decrement menjadi source C yang menyiapkan berbagai tabel kontrol prosesor, dan setelah kode itu dijalankan, CPU melakukan komputasi dengan cara mencoba memicu exception tanpa mengeksekusi satu instruksi pun.
      Secara opsional, assembler juga bisa menghasilkan instruksi X86 yang menampilkan variabel pada framebuffer VGA dan memindahkan kontrol di antara instruksi tampilan native dan instruksi trap weird machine.
    • Rasanya mirip dengan https://github.com/xoreaxeaxeax/movfuscator.

  • Saya teringat video luar biasa ini yang membuat komputasi hanya dengan NaN dan infinity IEEE-754: https://www.youtube.com/watch?v=5TFDG-y-EHs

    • Seluruh kanal itu, suckerpinch / Tom 7, benar-benar hebat.
      Kontennya sangat nerdy, penuh pemikiran, lucu, dan cara penyampaiannya juga sangat bagus.
      Sangat direkomendasikan, terutama untuk pembaca HN.

  • Dalam cerita pendek Coding Machines, penyalahgunaan bit tanda dengan cara serupa menjadi petunjuk besar bahwa AI sungguhan telah lepas ke dunia.
    https://www.teamten.com/lawrence/writings/coding-machines/

  • Sebagai materi terkait, ada https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...
    Ini adalah implementasi yang mengonversi satu double IEEE-754 menjadi sepasang dua double yang berisi nilai integer 32 bit bawah dan 32 bit atas dari representasi bit argumennya, hanya dengan memakai penjumlahan/pengurangan/perkalian double.

  • Melihat tabel kebenarannya, pengurangan jelas truth-preserving, jadi tampaknya secara nyata tidak mungkin functionally complete.
    Apa yang saya lewatkan?

    • Secara ketat, ia menjadi functionally complete saat bisa mengakses konstanta false, yaitu -0.0.
      Tanpa konstanta ini ia tidak functionally complete, dan berbeda dari NAND yang bisa membuat false dari nilai apa pun.
      Inti tulisan itu adalah menunjukkan bahwa hanya dengan signed zero dan pengurangan floating-point kita bisa meniru rangkaian arbitrer, dan saya menganggap functional completeness sebagai istilah paling ringkas untuk menyatakannya, tetapi jika hanya melihat tabel kebenaran secara ketat, memang aturannya agak dipelintir, jadi akan saya perjelas di tulisan.
    • Saya tidak sepenuhnya yakin apa persisnya arti truth-preserving di sini, tetapi petunjuknya adalah bahwa yang functionally complete bukan pengurangan saja, melainkan pengurangan bersama simbol konstanta 0.
      Dengan pengurangan dan 0, kita membuat false sebagai -0.0, lalu memperoleh himpunan functionally complete {->, _|_} yang ada di Wikipedia [1].
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Pengurangan memang truth-preserving terhadap bit tanda, tetapi tidak truth-preserving terhadap bit-bit pengurangan sebenarnya.
      Saya tidak setuju dengan klaim bahwa bit pengurangan itu sendiri functionally complete.
      Karena truth-preserving, tampaknya benar bahwa ia tidak functionally complete.
    • Di bawah tabel kebenaran implikasi dengan urutan argumen dibalik, disebutkan “tabel kebenaran ini functionally complete [1]”, tetapi Wikipedia yang ditautkan jelas menulis bahwa IMPLY saja tidak functionally complete.
      Isinya adalah bahwa “setiap himpunan konektif dua elemen yang mencakup NOT dan salah satu dari {AND, OR, IMPLY} adalah subset minimal functionally complete dari {NOT, AND, OR, IMPLY, IFF}”.
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Saya tidak mengerti mengapa truth-preserving menghalangi functional completeness.
      Lagi pula, bagaimana bisa tahu sejak awal bahwa tabel kebenaran itu truth-preserving? Tabel kebenaran bukan argumen logis.

  • Jika kelengkapan fungsional berarti bisa membuat rangkaian logika apa pun, apakah pengurangan floating-point IEEE-754 secara praktis berarti Turing-complete? Atau tidak?

    • Tidak
      Kelengkapan fungsional tidak mencakup kemampuan iterasi yang diperlukan untuk menjadi Turing-complete
      Turing-completeness sering disalahgunakan ketika yang dimaksud sebenarnya kelengkapan fungsional, dan ada juga kasus orang mencampuradukkan keduanya atau memakai istilah itu karena terdengar lebih menarik sebagai judul blog/artikel
      mov sebenarnya tidak Turing-complete dan membutuhkan instruksi jmp: https://harrisonwl.github.io/assets/courses/malware/spring20...
      Sistem enkripsi homomorfik lengkap secara fungsional, tetapi tidak Turing-complete. Sebab iterasi akan membocorkan jumlah operasi yang dilakukan dan memecahkan enkripsinya
    • Meminjam ungkapan yang saya lihat di Reddit, cukup baca gerbang NAND sebagai pengurangan
      Dengan gerbang NAND, kita bisa membuat mesin yang Turing-complete, tetapi mengatakan bahwa gerbang NAND itu Turing-complete sama seperti mengatakan kita bisa tinggal di dalam batu bata
      Kita tidak bisa tinggal di dalam batu bata, tetapi kita bisa membangun rumah dari batu bata dan tinggal di dalamnya
    • Hampir benar
      “Kurangi dan bercabang jika kurang dari atau sama dengan 0” adalah satu instruksi yang Turing-complete
      https://en.wikipedia.org/wiki/One-instruction_set_computer

  • Dulu saya pernah memposting ini di thread /r/programming, tetapi saya taruh juga di sini
    Adder bisa diimplementasikan hanya dengan 11 kali pengurangan
    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)
    }

  • Kalau yang dimaksud adalah “integer yang diimplementasikan dalam software hanya menggunakan operasi floating-point”, pada dasarnya itu sama seperti semua upaya di JavaScript untuk memakai number seolah-olah int

  • Kalimat “Jika tanda kedua significand sama, output juga harus memiliki tanda itu. Namun pada x−y, jika tanda x dan y berbeda, output harus memiliki tanda x” sedikit keliru, atau mencampuradukkan kata tanda dalam dua makna
    Jika keduanya bertanda positif seperti x=5, y=10, maka x-y menjadi -5 dan bertanda negatif
    Bahkan jika diasumsikan tanda variabel y benar-benar dibalik, jika memilih -3 dan -6, yang terakhir dibalik menjadi 6 dan hasilnya +3, sehingga tandanya berbeda dari x

    • Jika x dan y sama-sama bertanda positif, itu tidak memenuhi kondisi “pada x−y, jika tanda x dan y berbeda”
      Begitu pula -3 dan -6; karena tanda x dan y sama, kondisi untuk pengurangan itu tidak terpenuhi
    • Sepertinya kata “berbeda” terlewat
      Contohnya membahas tanda yang sama
 
asd142513 2023-10-11

Ada kesalahan pada judulnya. Bukan berarti pengurangan sudah selesai, melainkan bahwa semua fungsi dapat diekspresikan dengan pengurangan, sehingga disebut lengkap secara fungsional.