Phép trừ IEEE-754 là hoàn thiện hàm

 (orlp.net)
3 điểm bởi GN⁺ 2023-10-09 | 2 bình luận | Chia sẻ qua WhatsApp
  • Phép trừ số dấu phẩy động IEEE-754 có thể dùng để tạo ra mạch nhị phân tùy ý nhờ số 0 có dấu và quy tắc dấu của kết quả
  • Nếu xem -0 là false và +0 là true, thì x - y trong chế độ làm tròn mặc định sẽ hoạt động như A ∨ ¬B, tức cổng IMPLY với đối số bị đảo
  • Với hằng false, cổng này có thể tạo ra NOT, và tổ hợp NOT + IMPLY trở thành một tập cổng logic hoàn thiện hàm
  • Ví dụ Python phân biệt trực tiếp dấu của -0.0 và 0.0 để triển khai f_not, f_or, f_and, f_xor đều dựa trên phép trừ
  • Ví dụ Rust biểu diễn số nguyên 8 bit bằng mảng f32, tính 23 + 19 = 42, và cần khoảng 120 lệnh dấu phẩy động cho phép cộng hai số nguyên 8 bit

Điểm khởi đầu do quy tắc dấu IEEE-754 tạo ra

  • Phép trừ số dấu phẩy động IEEE-754 có tính hoàn thiện hàm
  • Hoàn thiện hàm nghĩa là chỉ với phép toán đó cũng có thể xây dựng mạch nhị phân tùy ý
  • Điểm cốt lõi nằm ở quy tắc bit dấu trong mục 6.3 của chuẩn IEEE 754-2019
    • Phép trừ x - y được xem là tổng x + (-y)
    • Số 0 có thể mang dấu, nên -0 và +0 được xem là hai giá trị khác nhau
    • Tuy vậy, trong so sánh IEEE-754 thì -0 == +0 là đúng
    • Khi đầu vào và kết quả không phải NaN, dấu của tổng hoặc hiệu tuân theo quy tắc dấu của các toán hạng
    • Nếu hiệu của hai giá trị cùng dấu chính xác bằng 0, thì trong các chế độ làm tròn ngoại trừ roundTowardNegative, kết quả sẽ là +0
  • Phần xây dựng phía sau giả định chế độ làm tròn mặc định là roundTiesToEven
    • Với roundTowardNegative cũng hoạt động theo cách tương tự

Bảng chân trị khi trừ các số 0

  • Nếu chỉ lấy -0 và +0 để làm phép trừ thì thu được kết quả sau
    • -0 - -0 = +0
    • -0 - +0 = -0
    • +0 - -0 = +0
    • +0 - +0 = +0
  • Nếu đặt -0 là false và +0 là true, thì bảng chân trị đầu ra sẽ như sau
    • 0 0 -> 1
    • 0 1 -> 0
    • 1 0 -> 1
    • 1 1 -> 1
  • Bảng chân trị này tương đương A ∨ ¬B, cũng chính là cổng IMPLY dạng B → A
    • So với cổng IMPLY thông thường, đây là dạng có đối số bị đảo

Có hằng false thì trở thành hoàn thiện hàm

  • Bảng chân trị này sẽ hoàn thiện hàm nếu có thể truy cập hằng false
  • Khi có hằng false, ta có thể tạo cổng NOT
  • NOT + IMPLY là một tập hoàn thiện hàm
  • NAND và NOR thì bản thân đã hoàn thiện hàm mà không cần hằng cụ thể nào
    • Khi chế tạo vi mạch, điều này có lợi thế là chỉ cần sản xuất một loại linh kiện duy nhất
    • Không cần định tuyến tín hiệu low cố định để tạo cổng NOT

Mạch logic bằng phép trừ viết bằng Python

  • Ví dụ Python định nghĩa -0.0 là false và 0.0 là true
    • Trong IEEE-754, +0 và -0 bằng nhau khi so sánh, nên dùng math.copysign để trích xuất dấu và phân biệt chúng
  • Cổng NOT dùng tính chất -0 - x làm đảo dấu của số 0
    • f_not = lambda x: f_false - x
    • f_not(-0.0) sẽ là true
    • f_not(+0.0) sẽ là false
  • Cổng OR được tạo bằng cách đảo dấu đối số thứ hai rồi thực hiện phép trừ
    • f_or = lambda a, b: a - f_not(b)
    • Chỉ khi cả hai đối số đều là -0 thì kết quả mới là false, còn lại đều là true
  • AND và XOR cũng có thể được tạo bằng cách kết hợp OR và 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)))

Số nguyên phần mềm viết bằng Rust

  • Ví dụ Rust đặt Bit = f32, và dùng ZERO = -0.0, ONE = 0.0 để biểu diễn bit
  • not, or, and, xor đều được triển khai dựa trên phép trừ dấu phẩy động, rồi dùng chúng để tạo bộ cộng đầy đủ adder
  • SoftU8 = [Bit; 8] được dùng để biểu diễn số nguyên 8 bit
    • to_softu8 chuyển từng bit của u8 thành ONE hoặc ZERO
    • from_softu8 kiểm tra dấu của từng phần tử để chuyển ngược lại thành u8
  • Chương trình ví dụ chuyển 23 và 19 thành SoftU8, cộng chúng rồi in ra 42
  • Cần khoảng 120 lệnh dấu phẩy động để cộng hai số nguyên 8 bit
  • Trên x86-64 không có lệnh đảo dấu dấu phẩy động thực sự, nên trình biên dịch dùng mặt nạ và XOR để đảo bit dấu, tức bit cao nhất của số dấu phẩy động IEEE-754

Bài viết liên quan

2 bình luận

 
GN⁺ 2023-10-09
Ý kiến trên Hacker News

  • Có thể tưởng tượng kiểu lạm dụng kỳ quặc các lệnh dấu phẩy động như thế này là thứ một DRM nào đó sẽ dùng làm phương tiện làm rối máy ảo
    Bước tiếp theo có lẽ là tạo một trình biên dịch tận dụng tính chất này để chạy mã nguồn thông thường dưới dạng số nguyên dấu phẩy động, rồi gắn thêm thứ gì đó kiểu FFI để gọi các API OS thông thường

    • Một số tài liệu có thể đáng quan tâm: http://tom7.org/grad/ dùng sai số dấu phẩy động IEEE làm hàm truyền trong machine learning, và http://tom7.org/nand/ tạo cổng logic và cả một CPU chỉ bằng IEEE NaN và vô cực
    • Biến thể này từng được hiện thực bằng xử lý ngoại lệ của Intel MMU: https://github.com/jbangert/trapcc
      Đây là một chứng minh mang tính xây dựng rằng cơ chế xử lý ngoại lệ của Intel MMU là Turing-complete
      Họ đã tạo một assembler chuyển các lệnh Move, Branch if Zero, Decrement thành mã nguồn C thiết lập nhiều bảng điều khiển bộ xử lý, và sau khi mã đó chạy, CPU tính toán bằng cách cố gây ngoại lệ mà không thực thi dù chỉ một lệnh nào
      Tùy chọn, assembler cũng có thể sinh các lệnh X86 hiển thị biến lên VGA framebuffer và chuyển quyền điều khiển qua lại giữa lệnh hiển thị native và lệnh trap của weird machine
    • Có cảm giác giống https://github.com/xoreaxeaxeax/movfuscator

  • Nhớ tới video tuyệt vời này về việc tạo phép tính chỉ bằng NaN và vô cực của IEEE-754: https://www.youtube.com/watch?v=5TFDG-y-EHs

    • Cả kênh đó, suckerpinch / Tom 7, thật sự xuất sắc
      Nội dung cực kỳ nerd, sâu sắc và hài hước, cách truyền tải cũng rất hay
      Đặc biệt khuyến nghị mạnh cho độc giả HN

  • Trong truyện ngắn Coding Machines, việc lạm dụng bit dấu theo cách tương tự là manh mối lớn cho thấy một AI thật sự đã được thả ra ngoài thế giới
    https://www.teamten.com/lawrence/writings/coding-machines/

  • Tài liệu liên quan: https://dougallj.wordpress.com/2020/05/10/bitwise-conversion...
    Đây là một hiện thực chuyển một IEEE-754 double thành một cặp gồm hai double chứa giá trị số nguyên của 32 bit thấp và 32 bit cao trong biểu diễn bit của đối số, chỉ dùng cộng/trừ/nhân double

  • Nhìn vào bảng chân trị thì phép trừ rõ ràng là bảo toàn giá trị đúng, nên thực tế có vẻ không thể functionally complete
    Mình đang bỏ sót điều gì?

    • Nói nghiêm ngặt thì nó functionally complete khi có thể truy cập hằng false, tức -0.0
      Không có hằng này thì nó không functionally complete, và khác với NAND vốn có thể tạo false từ bất kỳ giá trị nào
      Ý của bài viết là cho thấy chỉ với số 0 có dấu và phép trừ dấu phẩy động ta có thể mô phỏng mạch tùy ý; tôi nghĩ “functional completeness” là thuật ngữ ngắn gọn nhất để diễn đạt điều đó, nhưng nếu nhìn thật chặt vào bảng chân trị thì đúng là đã hơi bẻ quy tắc, nên tôi sẽ làm rõ trong bài
    • Ở đây tôi không chắc “bảo toàn giá trị đúng” chính xác nghĩa là gì, nhưng gợi ý là không phải chỉ phép trừ functionally complete, mà là phép trừ cùng với ký hiệu hằng 0
      Với phép trừ và 0, ta tạo được false dưới dạng -0.0, và thu được tập functionally complete {->, _|_} như trên Wikipedia [1]
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Phép trừ bảo toàn giá trị đúng đối với bit dấu, nhưng không bảo toàn giá trị đúng đối với các bit của phép trừ thực sự
      Tôi không đồng ý với tuyên bố rằng chỉ riêng các bit của phép trừ là functionally complete
      Nhận định rằng vì nó bảo toàn giá trị đúng nên không functionally complete có vẻ đúng
    • Ở dưới bảng chân trị của phép kéo theo, với thứ tự đối số bị đảo, có nói “bảng chân trị này functionally complete [1]”, nhưng Wikipedia được liên kết viết rõ rằng chỉ riêng IMPLY thì không functionally complete
      Nội dung là “mọi tập liên kết hai phần tử gồm NOT và một trong {AND, OR, IMPLY} là một tập con functionally complete tối thiểu của {NOT, AND, OR, IMPLY, IFF}”
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Tôi không hiểu vì sao tính bảo toàn giá trị đúng lại ngăn functional completeness
      Trước hết, làm sao biết được bảng chân trị có bảo toàn giá trị đúng hay không? Bảng chân trị đâu phải là một lập luận logic

  • Nếu tính đầy đủ về mặt hàm có nghĩa là có thể tạo ra bất kỳ mạch logic nào, thì có phải phép trừ số dấu phẩy động IEEE-754 về thực chất là Turing-complete không? Hay không phải?

    • Không
      Tính đầy đủ về mặt hàm thiếu chức năng lặp cần có để trở thành Turing-complete
      Turing-completeness thường bị dùng sai khi người ta muốn nói đến tính đầy đủ về mặt hàm; cũng có trường hợp nhầm lẫn hai khái niệm, hoặc dùng như vậy vì nghe có vẻ hợp hơn cho bài blog/tiêu đề bài viết
      mov thực ra không Turing-complete, mà cần lệnh jmp: https://harrisonwl.github.io/assets/courses/malware/spring20...
      Các hệ thống mã hóa đồng cấu có tính đầy đủ về mặt hàm nhưng không Turing-complete. Vì việc lặp sẽ làm lộ số phép toán đã được thực hiện, phá vỡ mã hóa
    • Mượn cách nói tôi thấy trên Reddit: cứ thay cổng NAND bằng phép trừ mà đọc là được
      Có thể tạo ra một cỗ máy Turing-complete bằng các cổng NAND, nhưng nói bản thân cổng NAND là Turing-complete thì giống như nói bạn có thể sống bên trong một viên gạch
      Bạn không thể sống bên trong một viên gạch, nhưng có thể xây nhà bằng gạch rồi sống trong đó
    • Gần đúng
      “Trừ và rẽ nhánh nếu nhỏ hơn hoặc bằng 0” là Turing-complete chỉ với một lệnh
      https://en.wikipedia.org/wiki/One-instruction_set_computer

  • Trước đây tôi đã đăng lên một thread ở /r/programming, giờ đăng ở đây nữa
    Có thể triển khai bộ cộng chỉ bằng “vỏn vẹn” 11 phép trừ
    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)
    }

  • Nếu là “số nguyên được triển khai bằng phần mềm chỉ dùng các phép toán dấu phẩy động”, thì về cơ bản giống như mọi nỗ lực dùng number của JavaScript như int

  • Câu “Nếu dấu của hai significand giống nhau thì đầu ra cũng phải có dấu đó. Nhưng trong x−y, nếu dấu của x và y khác nhau thì đầu ra phải có dấu của x” hoặc sai một cách nhỏ nhặt, hoặc đang trộn lẫn từ dấu theo hai nghĩa khác nhau
    Nếu cả hai đều có dấu dương như x=5, y=10, thì x-y thành -5, có dấu âm
    Ngay cả khi giả định dấu của biến y thực sự bị đảo, chọn -3 và -6 thì số sau bị đảo thành 6, kết quả là +3 nên có dấu khác x

    • Nếu x và y đều có dấu dương thì không thỏa điều kiện “trong x−y, nếu dấu của x và y khác nhau”
      -3 và -6 cũng vậy: x và y có cùng dấu, nên không thỏa điều kiện về phép trừ
    • Có vẻ bạn đã bỏ sót từ “khác nhau”
      Ví dụ là về cùng dấu
 
asd142513 2023-10-11

Tiêu đề có lỗi rồi. Ý ở đây không phải là phép trừ đã hoàn thiện, mà là phép trừ được diễn đạt là hoàn chỉnh về mặt chức năng theo nghĩa có thể biểu diễn mọi chức năng bằng phép trừ.