Booth's multiplication algorithm
बूथ का गुणन एल्गोरिथ्म एक गुणन एल्गोरिथ्म है जो दो हस्ताक्षरित द्विआधारी संख्याओं को दो के पूरक संकेतन में गुणा करता है। एल्गोरिथम का आविष्कार 1950 में एंड्रयू डोनाल्ड बूथ ने लंदन के ब्लूम्सबरी में बर्कबेक कॉलेज में क्रिस्टलोग्राफी पर शोध करते हुए किया था। बूथ का एल्गोरिदम कंप्यूटर वास्तुकला के अध्ययन में रुचि रखता है। एल्गोरिथ्म बूथ का एल्गोरिथ्म हस्ताक्षरित दो के पूरक प्रतिनिधित्व में 'एन'-बिट गुणक वाई के बिट्स के आसन्न जोड़े की जांच करता है, जिसमें कम से कम महत्वपूर्ण बिट, y−1 = 0 से नीचे एक अंतर्निहित बिट शामिल है। प्रत्येक बिट yi के लिए, 0 से N−1 तक चलने वाले i के लिए, बिट्स yi और yi−1 पर विचार किया जाता है। जहाँ ये दो बिट्स बराबर हैं, उत्पाद संचायक पी को अपरिवर्तित छोड़ दिया जाता है। जहाँ yi = 0 और yi-1 = 1 है, वहाँ P में गुणक गुना 2i जोड़ा जाता है; और जहाँ yi = 1 और yi-1 = 0 है, वहाँ गुणक गुना 2i को P से घटाया जाता है। गुणक और उत्पाद के प्रतिनिधित्व निर्दिष्ट नहीं हैं; आम तौर पर, ये दोनों दो के पूरक प्रतिनिधित्व में भी होते हैं, जैसे गुणक, लेकिन कोई भी संख्या प्रणाली जो जोड़ और घटाव का समर्थन करती है, वह भी काम करेगी। जैसा कि यहाँ बताया गया है, चरणों का क्रम निर्धारित नहीं किया गया है। आम तौर पर, यह एलएसबी से एमएसबी तक आगे बढ़ता है, जो आई = 0 से शुरू होता है; 2आई द्वारा गुणन को आम तौर पर पी संचायक को चरणों के बीच दाईं ओर वृद्धिशील स्थानांतरण द्वारा प्रतिस्थापित किया जाता है; कम बिट्स को बाहर स्थानांतरित किया जा सकता है, और बाद के परिवर्धन और घटाव को पी के उच्चतम एन बिट्स पर किया जा सकता है। इन विवरणों पर कई भिन्नताएं और अनुकूलन हैं। एल्गोरिथ्म को अक्सर गुणक में 1s के स्ट्रिंग को उच्च-क्रम + 1 और स्ट्रिंग के अंत में निम्न-क्रम-1 में परिवर्तित करने के रूप में वर्णित किया जाता है। जब एक स्ट्रिंग एमएसबी के माध्यम से चलती है, तो कोई उच्च-क्रम + 1 नहीं होता है, और शुद्ध प्रभाव उचित मूल्य के नकारात्मक के रूप में व्याख्या है। एक विशिष्ट कार्यान्वयन बूथ के एल्गोरिथ्म को एक उत्पाद पी में दो पूर्व निर्धारित मानों ए और एस में से एक को बार-बार जोड़कर (साधारण अहस्ताक्षरित द्विआधारी जोड़ के साथ) लागू किया जा सकता है, फिर पी पर दाईं ओर अंकगणितीय बदलाव किया जा सकता है। मान लीजिए कि एम और आर क्रमशः गुणक और गुणक हैं; और मान लीजिए कि एक्स और वाई एम और आर में बिट्स की संख्या का प्रतिनिधित्व करते हैं। ए और एस के मान और पी का प्रारंभिक मान निर्धारित करें। इन सभी संख्याओं की लंबाई (x + y + 1) के बराबर होनी चाहिए। उत्तरः सबसे महत्वपूर्ण (सबसे बाएँ) बिट्स को m के मान से भरें। शेष (y + 1) बिट्स को शून्य से भरें। एसः सबसे महत्वपूर्ण बिट्स को दो के पूरक संकेतन में (-m) के मान से भरें। शेष (y + 1) बिट्स को शून्य से भरें। पीः सबसे महत्वपूर्ण एक्स बिट्स को शून्य से भरें। इसके दाईं ओर, आर का मान जोड़ें। शून्य के साथ सबसे कम महत्वपूर्ण (सबसे दाएं) बिट भरें। पी के दो सबसे कम महत्वपूर्ण (सबसे दाएं) बिट्स का निर्धारण करें। यदि वे 1 हैं, तो पी + ए का मान ज्ञात करें। किसी भी अतिप्रवाह को नजरअंदाज करें। यदि वे 10 हैं, तो पी + एस का मान ज्ञात करें। किसी भी अतिप्रवाह को नजरअंदाज करें। यदि वे 00 हैं, तो कुछ न करें। अगले चरण में सीधे पी का उपयोग करें। अगर वे 11 साल के हैं, तो कुछ न करें। अगले चरण में सीधे पी का उपयोग करें। अंकगणितीय रूप से दूसरे चरण में प्राप्त मान को एक ही स्थान से दाईं ओर स्थानांतरित करें। मान लीजिए कि P अब इस नए मान के बराबर है। 2 और 3 चरणों को तब तक दोहराएं जब तक कि वे y बार नहीं हो जाते। पी से सबसे कम महत्वपूर्ण (सबसे दाएं) बिट निकालें। यह एम और आर का गुणनफल है। उदाहरण 3 × (-4), जिसमें एम = 3 और आर =-4, और एक्स = 4 और वाई = 4: एम = 0011,-एम = 1101, आर = 1100 ए = 0011 0000 0 एस = 1101 0000 0 पी = 0000 1100 0 लूप को चार बार निष्पादित करेंः पी = 0000 1100 0। अंतिम दो बिट 00 हैं। पी = 0000 0110 0। अंकगणितीय सही बदलाव। पी = 0000 0110 0। अंतिम दो बिट 00 हैं। पी = 0000 0011 0। अंकगणितीय सही बदलाव। पी = 0000 0011 0। अंतिम दो बिट 10 हैं। पी = 1101 0011 0। पी = पी + एस. पी. = 1110 1001 1। अंकगणितीय सही बदलाव। पी = 1110 1001 1। अंतिम दो बिट 11 हैं। पी = 1111 0100 1। अंकगणितीय सही बदलाव। उत्पाद 11110100 है, जो-12 है। उपर्युक्त तकनीक तब अपर्याप्त होती है जब गुणक सबसे अधिक ऋणात्मक संख्या होती है जिसे दर्शाया जा सकता है (जैसे। यदि गुणक में 4 बिट हैं तो यह मान-8 है)। ऐसा इसलिए है क्योंकि तब-m की गणना करते समय एक अतिप्रवाह होता है, जो गुणक का निषेध है, जिसकी आवश्यकता S को निर्धारित करने के लिए होती है। इस समस्या का एक संभावित सुधार ए, एस और पी को एक-एक बिट से बढ़ाना है, जबकि वे अभी भी एक ही संख्या का प्रतिनिधित्व करते हैं। यानी, जबकि-8 को पहले 1000 से चार बिट्स में दर्शाया जाता था, अब इसे 1000 से 5 बिट्स में दर्शाया जाता है। यह फिर ऊपर वर्णित कार्यान्वयन का अनुसरण करता है, ए और एस के बिट्स को निर्धारित करने में संशोधन के साथ; उदाहरण के लिए, एम का मान, जो मूल रूप से ए के पहले एक्स बिट्स को सौंपा गया था, अब एक्स + 1 बिट्स तक बढ़ाया जाएगा और ए के पहले एक्स + 1 बिट्स को सौंपा जाएगा। नीचे, गुणक और गुणक के लिए 4 बिट्स का उपयोग करके −8 को 2 से गुणा करके बेहतर तकनीक का प्रदर्शन किया गया हैः A = 1 1000 0000 0 S = 0 1000 0000 0 P = 0 0000 0010 0 लूप को चार बार निष्पादित करेंः P = 0 0000 0010 0। अंतिम दो बिट 00 हैं। पी = 0 0000 0001 0। राइट शिफ्ट। पी = 0 0000 0001 0। अंतिम दो बिट 10 हैं। पी = 0 1000 0001 0। पी = पी + एस. पी. = 0 0 100 0000 1. राइट शिफ्ट। पी = 0 0100 0000 1। अंतिम दो बिट्स 1 हैं। पी = 1 1100 0000 1। पी = पी + ए. पी = 1 1110 0000 0। राइट शिफ्ट। पी = 1 1110 0000 0। अंतिम दो बिट 00 हैं। पी = 1111 0000 0। राइट शिफ्ट। उत्पाद 11110000 (पहले और अंतिम बिट को छोड़ने के बाद) है जो-16 है। यह कैसे काम करता है एक सकारात्मक गुणक पर विचार करें जिसमें 0s से घिरे 1s का एक ब्लॉक होता है। उदाहरण के लिए, 00111110। उत्पाद इस प्रकार दिया जाता हैः जहाँ M गुणक है। वास्तव में, यह दिखाया जा सकता है कि द्विआधारी संख्या में 1s के किसी भी अनुक्रम को दो द्विआधारी संख्याओं के अंतर में विभाजित किया जा सकता हैः इसलिए, गुणन को वास्तव में मूल संख्या में एक की स्ट्रिंग द्वारा सरल संचालन द्वारा प्रतिस्थापित किया जा सकता है, गुणक को जोड़ना, इस प्रकार उपयुक्त स्थानों द्वारा बनाए गए आंशिक उत्पाद को स्थानांतरित करना, और फिर अंत में गुणक को घटाना। यह इस तथ्य का उपयोग कर रहा है कि द्विआधारी गुणक में 0s के साथ व्यवहार करते समय शिफ्ट के अलावा कुछ भी करना आवश्यक नहीं है, और 99 से गुणा करते समय 99 = 100−1 गणितीय गुण का उपयोग करने के समान है। इस योजना को एक गुणक में 1s के किसी भी संख्या के ब्लॉक तक बढ़ाया जा सकता है (एक ब्लॉक में एकल 1 के मामले सहित)। इस प्रकार, बूथ का एल्गोरिथ्म इस पुरानी योजना का अनुसरण करता है जब यह एक के ब्लॉक (0 1) के पहले अंक का सामना करता है और जब यह ब्लॉक के अंत (0) का सामना करता है तो घटाव करता है। यह एक नकारात्मक गुणक के लिए भी काम करता है। जब एक गुणक में वाले को लंबे ब्लॉकों में समूहीकृत किया जाता है, तो बूथ का एल्गोरिथ्म सामान्य गुणन एल्गोरिथ्म की तुलना में कम परिवर्धन और घटाव करता है। इसे भी देखें द्विआधारी गुणक गैर-आसन्न रूप रेडंडेंट द्विआधारी प्रतिनिधित्व वालेस ट्री डैडी गुणक संदर्भ आगे पढ़ने के लिए बाहरी लिंक रेडिक्स-4 बूथ एन्कोडिंग रेडिक्स-8 बूथ एन्कोडिंग इन ए फॉर्मल थ्योरी ऑफ आरटीएल और कंप्यूटर अर्थमेटिक बूथ के एल्गोरिदम जावास्क्रिप्ट सिम्युलेटर इम्प्लीमेंटेशन इन पायथन 1950 इंट्रोडक्शन 1950 इन लंदन 1950 इन साइंस बाइनरी अर्थमेटिक कंप्यूटर अर्थमेटिक एल्गोरिदम गुणन बर्कबेक, लंदन विश्वविद्यालय