IEEE-754 घटाव कार्यात्मक रूप से पूर्ण है

(orlp.net)

3 पॉइंट द्वारा GN⁺ 2023-10-09 | 2 टिप्पणियां | WhatsApp पर शेयर करें

IEEE-754 floating-point subtraction signed zero और result sign rules का उपयोग करके कोई भी binary circuit बना सकता है
अगर -0 को false और +0 को true माना जाए, तो default rounding mode में x - y, A ∨ ¬B, यानी arguments उलटे हुए IMPLY gate की तरह काम करता है
यह gate constant false होने पर NOT बना सकता है, और NOT + IMPLY का संयोजन functionally complete logic gate set बन जाता है
Python उदाहरण -0.0 और 0.0 के sign को सीधे अलग करके f_not, f_or, f_and, f_xor सभी को subtraction-आधारित तरीके से implement करता है
Rust उदाहरण f32 array से 8-bit integer को represent करता है और 23 + 19 = 42 की गणना करता है, जबकि दो 8-bit integers के addition के लिए लगभग 120 floating-point instructions चाहिए

IEEE-754 sign rules से बनने वाला शुरुआती आधार

IEEE-754 floating-point subtraction में functional completeness होती है
Functionally complete होने का मतलब है कि सिर्फ उसी operation से कोई भी binary circuit बनाया जा सकता है
इसका मुख्य बिंदु IEEE 754-2019 standard के section 6.3 के sign bit rules हैं
- subtraction x - y को sum x + (-y) के रूप में माना जाता है
- 0 का sign हो सकता है, इसलिए -0 और +0 को अलग-अलग values की तरह संभाला जाता है
- लेकिन IEEE-754 comparison में -0 == +0 true होता है
- जब input और result NaN न हों, तो sum या difference का sign operands के sign rules का पालन करता है
- अगर same sign वाले दो values का difference ठीक 0 हो, तो roundTowardNegative को छोड़कर बाकी rounding modes में result +0 होता है
आगे की रचना default rounding mode roundTiesToEven मानकर की जाती है
- roundTowardNegative में भी यह लगभग इसी तरह काम करता है

0 के बीच subtraction से निकलने वाली truth table

सिर्फ -0 और +0 का subtraction करने पर ये results मिलते हैं
- -0 - -0 = +0
- -0 - +0 = -0
- +0 - -0 = +0
- +0 - +0 = +0
अगर -0 को false और +0 को true माना जाए, तो output truth table यह बनती है
- 0 0 -> 1
- 0 1 -> 0
- 1 0 -> 1
- 1 1 -> 1
यह truth table A ∨ ¬B के बराबर है, और B → A रूप वाले IMPLY gate के समान है
- सामान्य IMPLY gate की तुलना में इसमें arguments उलटे हुए हैं

Constant false होने पर यह functionally complete बन जाता है

यह truth table तब functionally complete हो जाती है जब constant false तक पहुंच हो
Constant false होने पर NOT gate बनाया जा सकता है
NOT + IMPLY एक functionally complete set है
NAND और NOR बिना किसी खास constant value के भी अकेले functionally complete होते हैं
- Microchip बनाते समय इसका फायदा यह है कि सिर्फ एक ही तरह का component बनाना पड़ता है
- NOT gate बनाने के लिए consistent low signal को route करने की जरूरत नहीं पड़ती

Python से बना subtraction logic circuit

Python उदाहरण -0.0 को false और 0.0 को true के रूप में define करता है
- IEEE-754 में +0 और -0 comparison में बराबर होते हैं, इसलिए math.copysign से sign निकाला जाता है और उन्हें अलग किया जाता है
NOT gate -0 - x की उस property का उपयोग करता है जो 0 के sign को flip कर देती है
- f_not = lambda x: f_false - x
- f_not(-0.0) true बन जाता है
- f_not(+0.0) false बन जाता है
OR gate दूसरे argument का sign flip करने के बाद subtraction करके बनाया जाता है
- f_or = lambda a, b: a - f_not(b)
- सिर्फ तब false मिलता है जब दोनों arguments -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 से बने software integers

Rust उदाहरण Bit = f32 रखता है और ZERO = -0.0, ONE = 0.0 के जरिए bits को represent करता है
not, or, and, xor सभी को floating-point subtraction के आधार पर implement करता है, और इन्हीं से full adder adder बनाता है
SoftU8 = [Bit; 8] से 8-bit integer को represent किया जाता है
- to_softu8 u8 के हर bit को ONE या ZERO में बदलता है
- from_softu8 हर element का sign देखकर उसे फिर u8 में वापस बदलता है
Example program 23 और 19 को SoftU8 में बदलकर जोड़ता है और 42 print करता है
दो 8-bit integers को जोड़ने के लिए लगभग 120 floating-point instructions चाहिए
x86-64 में floating-point sign inversion के लिए कोई वास्तविक instruction नहीं है, इसलिए compiler IEEE-754 floating-point number के सबसे ऊपरी bit यानी sign bit को toggle करने वाले mask और XOR का उपयोग करता है

2 टिप्पणियां

GN⁺ 2023-10-09

Hacker News राय

इस तरह के floating-point निर्देशों का अजीब दुरुपयोग कुछ ऐसा लगता है जिसे कोई DRM virtual machine को obfuscate करने के तरीके के रूप में इस्तेमाल कर सकता है।
अगला कदम शायद ऐसा compiler बनाना होगा जो इस गुण का इस्तेमाल करके सामान्य source code को floating-point integers के रूप में चलाए, और सामान्य OS API कॉल करने के लिए FFI जैसा कुछ जोड़ दे।
- रुचि हो तो, IEEE floating-point errors को machine learning transfer functions में इस्तेमाल करने वाला http://tom7.org/grad/ और IEEE NaN व infinities से logic gates और पूरा CPU बनाने वाला http://tom7.org/nand/ भी है।
- यह variant Intel MMU exception handling के साथ पहले ही implement किया जा चुका है: https://github.com/jbangert/trapcc
  यह इस बात का constructive proof है कि Intel MMU का exception handling mechanism Turing complete है।
  इसमें एक assembler बनाया गया जो Move, Branch if Zero, Decrement निर्देशों को कई processor control tables सेट करने वाले C source में बदलता था, और उस code के चलने के बाद CPU एक भी instruction execute किए बिना exception trigger करने की कोशिश करके computation करता है।
  वैकल्पिक रूप से assembler ऐसे X86 निर्देश भी generate कर सकता है जो VGA frame buffer में variables दिखाते हैं और native display instructions तथा weird machine trap instructions के बीच control पास करते हैं।
- https://github.com/xoreaxeaxeax/movfuscator जैसा अहसास है।
IEEE-754 NaN और infinity भर से computation बनाने वाला यह शानदार video याद आता है: https://www.youtube.com/watch?v=5TFDG-y-EHs
- वह पूरा channel, suckerpinch / Tom 7, वाकई कमाल है।
  बेहद nerdy, सोच-समझकर बनाया गया और मजेदार content है, और presentation भी बहुत अच्छा है।
  खासकर HN readership के लिए जोरदार recommendation।
छोटी कहानी Coding Machines में, इसी तरह sign bit का दुरुपयोग इस बात का बड़ा clue था कि असली AI दुनिया में छूट गया है।
https://www.teamten.com/lawrence/writings/coding-machines/
- कहानी शानदार है, लेकिन concept साफ तौर पर Ken Thompson की classic On Trusting Trust से काफी उधार लिया हुआ लगता है: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_Ref...
संबंधित resource के तौर पर https://dougallj.wordpress.com/2020/05/10/bitwise-conversion... है।
यह एक implementation है जो एक IEEE-754 double को argument के bit representation से lower 32-bit और upper 32-bit integer values रखने वाले दो doubles की जोड़ी में बदलता है, और सिर्फ double addition/subtraction/multiplication का इस्तेमाल करता है।
truth table देखें तो subtraction साफ तौर पर truth-preserving है, इसलिए असल में functionally complete नहीं हो सकता लगता है।
मैं क्या miss कर रहा हूं?
- सख्ती से कहें तो constant false, यानी -0.0, तक access होने पर यह composition के जरिए functionally complete है।
  इस constant के बिना यह functionally complete नहीं है, और NAND से अलग है, जो किसी भी value से false बना सकता है।
  लेख का मकसद यह दिखाना था कि signed zero और floating-point subtraction भर से किसी भी circuit की नकल की जा सकती है, और इसे व्यक्त करने के लिए functional completeness सबसे concise term लगा, लेकिन सिर्फ truth table को strict तौर पर देखें तो यह नियमों को थोड़ा मोड़ना है, इसलिए लेख में इसे स्पष्ट करूंगा।
- यहां truth-preserving से ठीक क्या मतलब है, यह मुझे पक्का नहीं, लेकिन hint यह है कि सिर्फ subtraction functionally complete नहीं है; subtraction और constant symbol 0 साथ में हैं।
  subtraction और 0 से false को -0.0 के रूप में बनाते हैं, और Wikipedia [1] में दिया functionally complete set {->, _|_} मिलता है।
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- subtraction sign bit के लिहाज से truth-preserving है, लेकिन वास्तविक subtraction bits के लिहाज से truth-preserving नहीं है।
  मैं इस दावे से सहमत नहीं कि सिर्फ subtraction bit अपने-आप में functionally complete है।
  truth-preserving होने के कारण यह functionally complete नहीं है—यह आकलन सही लगता है।
- implication की truth table, arguments का order उलटने वाली table के नीचे, कहा गया है “यह truth table functionally complete है [1]”, लेकिन linked Wikipedia साफ लिखता है कि केवल IMPLY functionally complete नहीं है।
  उसमें कहा गया है कि “NOT और {AND, OR, IMPLY} में से किसी एक को शामिल करने वाला हर two-element connective set {NOT, AND, OR, IMPLY, IFF} का minimal functionally complete subset है।”
  [1] https://en.wikipedia.org/wiki/Functional_completeness
- समझ नहीं आता कि truth-preserving होना functional completeness को क्यों रोकता है।
  और पहले तो यह कैसे पता चले कि truth table truth-preserving है? truth table कोई logical argument नहीं है।
अगर functional completeness का मतलब है कि उससे कोई भी logical circuit बनाया जा सकता है, तो क्या इसका मतलब है कि IEEE-754 floating-point subtraction असल में Turing complete है? या नहीं?
- नहीं
  Functional completeness में वह repetition क्षमता नहीं होती जो Turing completeness के लिए चाहिए
  Turing completeness का इस्तेमाल अक्सर functional completeness कहना चाहने पर गलत तरह से किया जाता है, और कभी-कभी लोग दोनों को मिला देते हैं या blog post/article title में यह ज़्यादा प्रभावशाली लगता है इसलिए ऐसा लिखते हैं
  mov असल में Turing complete नहीं है, jmp instruction की ज़रूरत होती है: https://harrisonwl.github.io/assets/courses/malware/spring20...
  Homomorphic encryption systems functionally complete होते हैं, लेकिन Turing complete नहीं। क्योंकि repetition किए गए operations की संख्या leak कर देता है और encryption तोड़ देता है
- Reddit पर देखी गई बात उधार लें तो, NAND gate को subtraction से बदलकर पढ़ लें
  NAND gates से Turing complete machine बनाई जा सकती है, लेकिन NAND gate को Turing complete कहना ऐसा है जैसे कहना कि आप ईंट के अंदर रह सकते हैं
  ईंट के अंदर नहीं रहा जा सकता, लेकिन ईंटों से घर बनाकर उसके अंदर रहा जा सकता है
- लगभग सही
  “0 या उससे कम हो तो subtract करके branch करो” single-instruction Turing complete है
  https://en.wikipedia.org/wiki/One-instruction_set_computer
पहले /r/programming thread में भी डाला था, यहाँ भी डाल रहा हूँ
adder को “सिर्फ” 11 subtractions से implement किया जा सकता है
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)
}
अगर यह “सिर्फ floating-point operations का उपयोग करके software में implement किया गया integer” है, तो मूल रूप से यह JavaScript के number को int की तरह इस्तेमाल करने की हर कोशिश जैसा है
“अगर दो significands के signs समान हैं, तो output में भी वही sign होना चाहिए। लेकिन x−y में अगर x और y के signs अलग हैं, तो output में x का sign होना चाहिए” वाला वाक्य या तो मामूली तौर पर गलत है, या sign शब्द को दो अलग अर्थों में मिला रहा है
अगर x=5, y=10 की तरह दोनों positive sign वाले हैं, तो x-y = -5 होगा और negative sign बनेगा
भले ही मान लें कि y variable का sign वास्तव में invert होता है, -3 और -6 चुनने पर दूसरा 6 में invert होगा और result +3 होगा, यानी x से अलग sign
- अगर x और y दोनों positive sign वाले हैं, तो “x−y में x और y के signs अलग हैं” वाली condition पूरी नहीं होती
  -3 और -6 भी इसी तरह x और y के समान sign वाले हैं, इसलिए subtraction वाली condition पूरी नहीं करते
- लगता है “अलग” शब्द छूट गया है
  उदाहरण समान sign के बारे में है

asd142513 2023-10-11

शीर्षक में गलती है। इसका मतलब यह नहीं कि subtraction पूरा हो गया है, बल्कि यह है कि subtraction के जरिए सभी functions को व्यक्त किया जा सकता है, इसलिए इसे functionally complete कहा गया है।