การลบแบบ IEEE-754 มีความสมบูรณ์เชิงฟังก์ชัน

• การลบเลขทศนิยมลอยตัวแบบ IEEE-754 สามารถใช้สร้างวงจรไบนารีใด ๆ ก็ได้ โดยอาศัย signed zero และกฎเครื่องหมายของผลลัพธ์
• หากมอง -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 มี ความสมบูรณ์เชิงฟังก์ชัน
• ความสมบูรณ์เชิงฟังก์ชันหมายความว่า เราสามารถประกอบ วงจรไบนารี ใด ๆ ก็ได้โดยใช้งานปฏิบัติการนี้เพียงอย่างเดียว
• แก่นสำคัญอยู่ที่กฎบิตเครื่องหมายในมาตรา 6.3 ของมาตรฐาน IEEE 754-2019
  • การลบ x - y ถูกพิจารณาเป็นผลบวก x + (-y)
  • ศูนย์สามารถมีเครื่องหมายได้ ดังนั้น -0 และ +0 จึงถูกปฏิบัติเป็นค่าที่ต่างกัน
  • อย่างไรก็ตาม ในการเปรียบเทียบแบบ IEEE-754 นั้น -0 == +0 เป็นจริง
  • เมื่ออินพุตและผลลัพธ์ไม่ใช่ NaN เครื่องหมายของผลบวกหรือผลต่างจะเป็นไปตามกฎเครื่องหมายของโอเปอแรนด์
  • หากผลต่างของค่าสองค่าที่มีเครื่องหมายเดียวกันออกมาเป็น 0 พอดี ผลลัพธ์จะเป็น +0 ในโหมดปัดเศษทุกแบบยกเว้น roundTowardNegative
• การประกอบต่อจากนี้สมมติให้ใช้ roundTiesToEven ซึ่งเป็นโหมดปัดเศษปริยาย
  • ใน roundTowardNegative ก็ทำงานได้ในลักษณะคล้ายกัน

ตารางค่าความจริงเมื่อเอาศูนย์มาลบกัน

• หากนำแค่ -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 และตรงกับเกต IMPLY ในรูป B → A
  • เมื่อเทียบกับเกต IMPLY ทั่วไป นี่คือ รูปแบบที่สลับอาร์กิวเมนต์

เมื่อมีค่าคงที่ false ก็จะสมบูรณ์เชิงฟังก์ชัน

• ตารางค่าความจริงนี้มีความสมบูรณ์เชิงฟังก์ชันเมื่อสามารถเข้าถึง ค่าคงที่ false ได้
• เมื่อมีค่าคงที่ false ก็สามารถสร้างเกต NOT ได้
• NOT + IMPLY เป็นชุดที่มีความสมบูรณ์เชิงฟังก์ชัน
• ส่วน NAND และ NOR นั้นมีความสมบูรณ์เชิงฟังก์ชันได้ด้วยตัวเองโดยไม่ต้องมีค่าคงที่เฉพาะ
  • สำหรับการสร้างไมโครชิป ข้อดีคือผลิตชิ้นส่วนเพียงชนิดเดียวก็พอ
  • และไม่จำเป็นต้องเดินสัญญาณ low แบบคงที่เพื่อสร้างเกต NOT

วงจรตรรกะจากการลบที่สร้างด้วย Python

• ตัวอย่างใน Python กำหนด -0.0 เป็น false และ 0.0 เป็น true
  • เนื่องจากใน IEEE-754 นั้น +0 และ -0 เปรียบเทียบแล้วเท่ากัน จึงใช้ math.copysign เพื่อ ดึงเครื่องหมาย ออกมาแยกความต่าง
• เกต NOT อาศัยคุณสมบัติที่ -0 - x สามารถกลับเครื่องหมายของศูนย์ได้
  • 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)
  • จะได้ false เฉพาะเมื่ออินพุตทั้งสองเป็น -0 เท่านั้น นอกนั้นเป็น 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 ไม่มีคำสั่งกลับเครื่องหมายเลขทศนิยมลอยตัวโดยตรงจริง ๆ ดังนั้นคอมไพเลอร์จึงใช้มาสก์และ XOR เพื่อสลับ บิตเครื่องหมาย ซึ่งเป็นบิตบนสุดของเลขทศนิยมลอยตัวแบบ IEEE-754

[GN⁺]

ความคิดเห็นจาก Hacker News

• การ นำไปใช้ในทางแปลกประหลาด ของคำสั่ง floating-point แบบนี้ นึกภาพได้เลยว่า DRM บางตัวน่าจะใช้เป็นวิธีทำให้ virtual machine อ่านยาก/สับสน
  ขั้นต่อไปน่าจะเป็นการสร้างคอมไพเลอร์ที่ใช้คุณสมบัตินี้เพื่อรันซอร์สโค้ดทั่วไปในฐานะ จำนวนเต็มแบบ floating-point แล้วต่ออะไรทำนอง FFI เพื่อเรียก OS API ทั่วไป

  • แหล่งข้อมูลที่น่าจะน่าสนใจมี http://tom7.org/grad/ ซึ่งใช้ความคลาดเคลื่อนของ IEEE floating-point เป็นฟังก์ชันส่งผ่านของ machine learning และ http://tom7.org/nand/ ซึ่งสร้างลอจิกเกตและ CPU ทั้งตัวด้วย IEEE NaN และอนันต์
  • รูปแบบดัดแปลงนี้เคยถูกนำไปใช้ด้วย การจัดการ exception ของ Intel MMU แล้ว: https://github.com/jbangert/trapcc
    เป็นการพิสูจน์เชิงสร้างสรรค์ว่ากลไกการจัดการ exception ของ Intel MMU มีความสมบูรณ์แบบทัวริง
    มีการสร้าง assembler ที่แปลงคำสั่ง Move, Branch if Zero, Decrement ให้เป็นซอร์ส C ที่ตั้งค่าตารางควบคุมโปรเซสเซอร์หลายชุด และหลังจากโค้ดนั้นรันแล้ว CPU จะคำนวณด้วยการพยายามก่อให้เกิด exception โดยไม่รันคำสั่งแม้แต่คำสั่งเดียว
    เลือกได้ด้วยว่า assembler จะสร้างคำสั่ง X86 ที่แสดงตัวแปรบน VGA frame buffer และส่งต่อการควบคุมไปมาระหว่างคำสั่งแสดงผลแบบ native กับคำสั่ง trap ของ weird machine ได้
  • ให้ความรู้สึกคล้าย 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...
  เป็น implementation ที่แปลง IEEE-754 double หนึ่งตัวให้เป็นคู่ของ double สองตัวที่เก็บค่าจำนวนเต็มของ 32 บิตล่างและ 32 บิตบนจากการแทนค่าระดับบิตของอาร์กิวเมนต์ โดยใช้เพียงการบวก/ลบ/คูณ double

• ดูจากตารางค่าความจริงแล้ว การลบดูเป็นแบบ true-preserving ชัด ๆ ดังนั้นในความเป็นจริงไม่น่าจะ functionally complete ได้
  ผมพลาดอะไรไปหรือเปล่า?

  • พูดให้เคร่งครัดคือ เมื่อเข้าถึงค่าคงที่ false หรือก็คือ -0.0 ได้ ก็สามารถประกอบกันจน functionally complete ได้
    ถ้าไม่มีค่าคงที่นี้ก็ไม่ functionally complete และต่างจาก NAND ที่สามารถสร้าง false ได้จากค่าใด ๆ
    ใจความของบทความคือการแสดงว่าสามารถเลียนแบบวงจรใด ๆ ได้ด้วย 0 ที่มีเครื่องหมายกับการลบ floating-point เท่านั้น และผมมองว่า functional completeness เป็นคำที่กระชับที่สุดในการสื่อเรื่องนั้น แต่ถ้าดูแค่ตารางค่าความจริงอย่างเคร่งครัด ก็ถือว่าบิดกฎไปเล็กน้อย ดังนั้นจะทำให้ชัดเจนในบทความ
  • ผมไม่แน่ใจนักว่า true-preserving ในที่นี้หมายถึงอะไรกันแน่ แต่คำใบ้คือไม่ใช่ การลบเพียงอย่างเดียว ที่ functionally complete หากเป็นการลบร่วมกับสัญลักษณ์ค่าคงที่ 0
    ด้วยการลบและ 0 เราสร้าง false เป็น -0.0 ได้ และได้เซตที่ functionally complete {->, _|_} ตาม Wikipedia [1]
    [1] https://en.wikipedia.org/wiki/Functional_completeness
  • การลบเป็น true-preserving สำหรับ บิตเครื่องหมาย แต่ไม่ใช่ true-preserving สำหรับบิตของการลบจริง ๆ
    ผมไม่เห็นด้วยกับข้ออ้างว่าบิตของการลบเพียงอย่างเดียว functionally complete
    การตัดสินว่าไม่ functionally complete เพราะเป็น true-preserving นั้นดูถูกต้องแล้ว
  • ใต้ตารางค่าความจริงของ implication ที่สลับลำดับอาร์กิวเมนต์ เขียนว่า “ตารางค่าความจริงนี้ functionally complete [1]” แต่ Wikipedia ที่ลิงก์ไปเขียนชัดเจนว่า IMPLY เพียงอย่างเดียว ไม่ functionally complete
    เนื้อหาคือ “เซตตัวเชื่อมสองสมาชิกทุกเซตที่มี NOT และมีหนึ่งใน {AND, OR, IMPLY} เป็นสับเซตขั้นต่ำที่ functionally complete ของ {NOT, AND, OR, IMPLY, IFF}”
    [1] https://en.wikipedia.org/wiki/Functional_completeness
  • ผมไม่เข้าใจว่าทำไม true-preserving ถึงขัดขวาง functional completeness
    ก่อนอื่นเลย เราจะรู้ได้อย่างไรว่าตารางค่าความจริงเป็น true-preserving? ตารางค่าความจริงไม่ใช่การให้เหตุผลเชิงตรรกะ

• ถ้าความสมบูรณ์เชิงฟังก์ชันหมายถึงสามารถสร้างวงจรตรรกะใด ๆ ก็ได้ แบบนี้การ ลบเลขทศนิยมลอยตัว ของ IEEE-754 ก็เท่ากับว่าเป็น Turing complete โดยพฤตินัยหรือเปล่า? หรือไม่ใช่?

  • ไม่ใช่
    ความสมบูรณ์เชิงฟังก์ชัน ขาดความสามารถในการทำซ้ำที่จำเป็นต่อการเป็น Turing complete
    Turing completeness มักถูกใช้ผิดเวลาที่จริง ๆ ต้องการพูดถึง functional completeness และบางครั้งก็เป็นเพราะสับสนสองอย่างนี้ หรือเพราะใช้เป็นชื่อบทความ/พาดหัวบล็อกแล้วดูน่าเชื่อกว่า
    mov จริง ๆ แล้วไม่ใช่ Turing complete ต้องมีคำสั่ง jmp: https://harrisonwl.github.io/assets/courses/malware/spring20...
    ระบบเข้ารหัสแบบโฮโมมอร์ฟิกมีความสมบูรณ์เชิงฟังก์ชัน แต่ไม่ใช่ Turing complete เพราะการวนซ้ำจะรั่วจำนวนครั้งของการดำเนินการที่ทำไป และทำให้การเข้ารหัสถูกทำลาย
  • ยืมคำพูดที่เห็นใน Reddit มา ถ้าอ่านโดยเปลี่ยนเกต NAND เป็นการลบก็ได้
    เราสามารถสร้างเครื่องที่เป็น Turing complete ด้วยเกต NAND ได้ แต่การบอกว่าเกต NAND เป็น Turing complete ก็เหมือนบอกว่าสามารถอาศัยอยู่ในก้อนอิฐได้
    คุณอาศัยอยู่ในก้อนอิฐไม่ได้ แต่เอาอิฐไปสร้างบ้านแล้วอาศัยอยู่ในนั้นได้
  • เกือบถูก
    “ลบแล้วกระโดดถ้าน้อยกว่าหรือเท่ากับ 0” เป็นคำสั่งเดียวที่ Turing complete
    https://en.wikipedia.org/wiki/One-instruction_set_computer

• เคยโพสต์ไว้ในเธรด /r/programming มาก่อน แต่ขอเอามาโพสต์ที่นี่ด้วย
  สามารถทำ adder ได้ด้วยการลบ “เพียง” 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)
}

• ถ้าเป็น “จำนวนเต็มที่ implement ในซอฟต์แวร์โดยใช้เฉพาะการคำนวณแบบทศนิยมลอยตัว” โดยพื้นฐานแล้วก็เหมือนกับ ความพยายามทั้งหมดที่จะใช้ number ของ JavaScript เหมือน int

• ประโยคที่ว่า “ถ้าเครื่องหมายของ significand ทั้งสองเหมือนกัน ผลลัพธ์ก็ต้องมีเครื่องหมายนั้นด้วย แต่ใน 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]

ชื่อเรื่องมีข้อผิดพลาดนะครับ ไม่ใช่ว่าการลบถูกทำให้สมบูรณ์แล้ว แต่หมายความว่าสามารถแสดงฟังก์ชันทั้งหมดได้ด้วยการลบ จึงใช้คำว่า functionally complete