दोनचे पूरक आणि समूह सिद्धांत || गणित ∩ प्रोग्रामिंग

मी गणित शोधण्याआधी, मी इलेक्ट्रिकल इंजिनिअरिंग 101 घेणारा प्रथम वर्षाचा अंडरग्रेड कॉम्प्युटर सायन्सचा विद्यार्थी होतो. बिट्स आणि बुलियन गेट्स म्हणजे काय हे मी शिकलेला पहिला विषय होता आणि दुसरा म्हणजे नकारात्मक n-बिट पूर्णांकाचे दोन पूरक प्रतिनिधित्व.

त्या वेळी दोघांची पूरकता मला संगणक प्रोग्रामिंगच्या विचित्र चकचकीत वाटली, ज्यात तुम्हाला फक्त लक्षात ठेवायचे होते. जर अग्रगण्य बिट 1 असेल, तर ते ऋण आहे आणि अन्यथा ते सकारात्मक आहे. संख्या नाकारण्यासाठी, बिट्स फ्लिप करा आणि एक जोडा. अर्थात संख्या वगळता 1000 0000जे 8-बिट दोनचे पूरक आहे -128, कारण या ऑपरेशननुसार त्याचे “ऋण” देखील आहे 1000 0000 = -128.

विचित्र नकार ऑपरेशन सहसा प्राथमिक शाळेतील वजाबाकीमधून “कर्ज घेण्याच्या” ऑपरेशनला आवाहन करून स्पष्ट केले जाते. किंवा सामायिक असहायतेच्या भावनेला आवाहन. अशाच गोष्टी दोघांच्या पूरक आहेत. परंतु स्वाक्षरी नसलेल्या आणि दोनच्या पूरक स्वाक्षरी केलेल्या पूर्णांकांची बेरीज आणि गुणाकार मोजण्यासाठी एकच बुलियन सर्किट का वापरता येईल याचे स्पष्टीकरण नाही.

गणित विचित्रपणासाठी वेगळे, स्पष्ट स्पष्टीकरण देऊ शकते. हे अनियंत्रित नाही, परंतु सक्तीचे आहे. स्पष्टीकरण गट सिद्धांत वापरते, जे मी खूप पूर्वी लिहिले होते. येथे वापरल्या गेलेल्या समूह सिद्धांतातील मुख्य कल्पना म्हणजे चक्रीय गट, भागफल गट, समूह समरूपता आणि समूह क्रिया.

प्रथम अंतर्दृष्टी अशी आहे की अंकगणितासाठी निवडलेल्या भिन्न समतुल्य वर्ग प्रतिनिधीसह, स्वाक्षरी केलेले पूर्णांक भागांक गट म्हणून सही न केलेल्या पूर्णांकांसारखेच असतात.

$n$-bit अस्वाक्षरित पूर्णांकांचा संच $\mathbb{Z}/2^n\mathbb{Z} = \{ 0, 1, \dots, 2^n-1 \}$ $2^n$ अतिरिक्त मोड्यूलो अंतर्गत एक गट तयार करतो. $n$-bit स्वाक्षरी केलेल्या पूर्णांकांचा संच $\{ -2^{n-1}, \dots, -1, 0, 1, \dots, 2^{n-1} – 1 \}$ देखील एक गट बनवतो, परंतु का ते पाहणे कठीण आहे. ऑपरेशन अजूनही “ॲडिशन मॉड्युलो $2^n$” आहे, परंतु का ते पाहण्यासाठी तुम्हाला भागफल गटाची व्याख्या आठवावी लागेल.

भागफल गटाचे घटक $\mathbb{Z}/2^n \mathbb{Z}$ पूर्णांक नाहीत, उलट समतुल्यता वर्ग पूर्णांकांची. आम्ही $(x) \in \mathbb{Z}/2^n \mathbb{Z}$ हे $x \in \mathbb{Z}$ चा समतुल्य वर्ग म्हणून दर्शवतो. उदाहरणार्थ, “घटक” $1$ हा समतुल्य वर्ग आहे $(1) = \{ \dots, -2^n+1, 1, 2^n + 1, 2\cdot 2^n + 1, \dots \}$. आणि समतुल्य वर्ग परिभाषित करण्याचा संपूर्ण मुद्दा असा आहे की तुम्ही समतुल्य वर्गातून कोणताही प्रतिनिधी घटक निवडू शकता, त्या घटकाचा वापर करून अंकगणित करू शकता आणि तुम्ही “नेहमीचे” प्रतिनिधी वापरल्यास तुम्हाला समान (समतुल्य वर्ग) आउटपुट मिळेल. दुसऱ्या शब्दांत, याची हमी आहे की $(x+y) = (x) + (y) = (x’) + (y’) = (x’ + y’)$, जोपर्यंत $(x) = (x’)$ आणि $(y) = (y’)$.

स्वाक्षरी केलेले पूर्णांक नेमके हे आहेत: काही समतुल्य वर्गांसाठी भिन्न प्रतिनिधी निवडणे. घटक $(2^{n-1}) = \{ \dots, -2\cdot 2^{n-1}, -2^{n-1}, 2^{n-1}, 2\cdot 2^{n-1}, \dots \}$ $-2^{n-1}$ द्वारे दर्शविले जाते, घटक $-(2} $ 1 द्वारे दर्शविले जाते) $-2^{n-1} + 1$, $2^n पर्यंत – 1$ $-1$ द्वारे प्रस्तुत केले जात आहे. दोनची पूरकता म्हणजे स्वाक्षरी न केलेल्या पूर्णांकाच्या बिट्सचे “पुनर्व्याख्या” असे म्हणण्याचा हा औपचारिक मार्ग आहे. हे एक अनियंत्रित पुनर्व्याख्या नाही, परंतु स्वाक्षरी न केलेल्या व्याख्येप्रमाणेच अंकगणितीय रचना पूर्ण करते.

त्यामुळे बेरीज ऑपरेशनचे कोणतेही सर्किट प्रतिनिधित्व जे अस्वाक्षरित पूर्णांकांसाठी कार्य करते ते जोडण्यासाठी देखील वापरले जाऊ शकते सर्व समतुल्य वर्ग प्रतिनिधींच्या संभाव्य पर्यायी निवडी. याची नोंद घ्या काहीही नाही ज्या पद्धतीने या संख्यांना बिट्स म्हणून दर्शविले जाते. हे मॉड्यूलर अंकगणिताच्या अंतर्निहित गणिताची हमी आहे. जर संख्या टर्नरी किंवा बेस 10 मध्ये दर्शवली गेली असेल तर ते कार्य करेल (काही अतिरिक्त इनपुट आणि आउटपुट सेटमध्ये नसतील हे तथ्य वगळता). हे देखील लक्षात घ्या की ते गुणाकाराला तितकेच चांगले लागू होते, कारण येथे सांगितलेली प्रत्येक गोष्ट भागाला तितकीच चांगली लागू होते अंगठी पूर्णांक मोड्युलो $2^n$.

हे हे देखील स्पष्ट करते की सर्वात लहान ऋण संख्या म्हणून $-2^{n-1}$ ची निवड अनियंत्रित आहे, आणि $2^n-1$ ही सर्वात लहान ऋण म्हणून सोडून $2^n-1$ ही सर्वात मोठी धन म्हणून समाविष्ट करू शकते. मला वाटते की सध्याची मानक निवड ($-2^{n-1}$ ही सर्वात लहान ऋण संख्या म्हणून) या पर्यायापेक्षा वस्तुनिष्ठपणे चांगली आहे, कारण ती नकारात्मकता/ओव्हरफ्लो/अंडरफ्लो डिटेक्टर म्हणून अग्रगण्य चिन्ह बिट वापरण्याची परवानगी देते.

आता आपण या गटातील निगेशन ऑपरेशनचा अभ्यास करू शकतो. सुरुवातीच्यासाठी, $-2^{n-1}$ वगळता प्रत्येक घटक $x$ साठी, $-x$ ही संख्या आधीपासूनच $n$-bit पूर्णांक आहे. त्यामुळे नकार म्हणजे फक्त नकार (आम्ही एका सेकंदात बिट म्हणून याचा अर्थ कसा लावला जातो ते पाहू). आणि जर आपण $-2^{n-1}$ चा समतुल्य वर्ग म्हणून विचार केला, तर तो $2^{n-1}$ सारखाच आहे, जो स्वाक्षरी न केलेला पूर्णांक म्हणून स्वतःचा व्यस्त आहे. ते स्वतःमध्ये जोडा आणि तुम्हाला $2^n \equiv 0 \mod 2^n$ मिळेल. समतुल्य वर्ग प्रतिनिधी काहीही असले तरीही समान रीतीने वागतात, $-2^{n-1}$ हे त्याचे स्वतःचे व्यस्त असणे आवश्यक आहे आणि म्हणून $-(-2^{n-1}) = -2^{n-1}$ स्वाक्षरी पूर्णांक म्हणून.

त्याचा बिट्स म्हणून अर्थ लावण्यासाठी, पुन्हा स्वाक्षरी न केलेल्या पूर्णांकांकडे परत उचला आणि लक्षात घ्या की स्वाक्षरी न केलेल्या पूर्णांकासाठी “नकार” $x$—म्हणजे $y$ असे मूल्य शोधणे की $x+y \equiv 0 \mod 2^n$—$-(x) = (2^n – x)$ द्वारे मोजले जाते जरी ते e’valence वर्गात वापरले जात असले तरीही $-(x)$ परिभाषित करण्यासाठी, कारण समतुल्य वर्गामध्ये अंकगणित हे पूर्णांकांवर फक्त अंकगणित असते). परंतु $2^n$ ठोस $n$-बिट संख्यांमध्ये दर्शविण्यायोग्य नसल्यामुळे (ते फक्त शून्य आहे), त्याची संपूर्णपणे $n$-बिट पूर्णांकांमध्ये गणना करण्यासाठी, आम्हाला अंकगणित आणखी खाली मोडणे आवश्यक आहे:

$$ (2^n – x ) = ( 2^n – 1 – x + 1 ) = ( 2^n – 1 – x ) + ( 1 ) $$

$2^n-1$ ही सर्व 1ची स्ट्रिंग आहे, म्हणून $2^n – 1 – x$ हे $x$ च्या बिट्स फ्लिप करण्यासारखे आहे आणि 1 जोडल्याने गणना पूर्ण होते.

शेवटी, हा $-2^{n-1}$-स्वतःचा-विलोम व्यवसाय आहे. जर तुम्ही स्वाक्षरी न केलेल्या पूर्णांकांचा समूह वर्तुळ म्हणून पाहत असाल-एक नैसर्गिक निवड कारण घड्याळाच्या गणिताप्रमाणे जोडणी “रॅप्सभोवती” असते—नकार ऑपरेशन $0$ आणि वर्तुळाच्या केंद्रातून जाणाऱ्या रेषेवरचे प्रतिबिंब म्हणून पाहिले जाऊ शकते. साहजिकच हे $0$ चे नकार $0$ च्या बरोबरीचे बनवते. सममितीची रेषा ज्यातून जाते तो दुसरा बिंदू म्हणजे $(2^{n-1}) = (-2^{n-1})$, आणि म्हणून ते $-2^{n-1}$ देखील निश्चित केले पाहिजे.

हे पुरेसे स्पष्टीकरण आहे, परंतु त्रासदायक प्रश्न हा आहे की ते सक्तीचे आहे का. हे वर्तन घडत नाही अशा दोघांच्या पूरकतेपेक्षा आणखी काही चांगले प्रतिनिधित्व आहे का? जोपर्यंत आपल्या संख्या प्रणालीचा आकार सम आहे आणि ० स्वतःचा व्यस्त आहे, तोपर्यंत साधी मोजणी अशक्य असल्याचे दर्शवते. आमच्याकडे शून्य घटकांची विषम संख्या $2^n – 1$ असेल, आणि व्यस्त ऑपरेशन त्यांना जोड्यांमध्ये जुळवेल, जोपर्यंत “जोड्या” पैकी एक सिंगलटन नसेल तोपर्यंत सम एकूण उत्पन्न होईल.

बाजूला: या विषयावरील विकिपीडिया लेखात समूह क्रिया (खरोखर, बर्नसाइडचा लेमा) वापरून काहीसे तिरकस स्पष्टीकरण दिले होते, जे बरोबर असले तरी, मिलेनियम फाल्कनचा वापर चिमणीला गोळ्या घालण्यासारखे आहे. मी वरील मोजणी युक्तिवादासाठी ते सोपे केले आहे.

---

---