गणितज्ञों ने संख्याओं को गुणा करने का सही तरीका खोजा है

बड़ी संख्या को छोटी संख्या में तोड़कर, शोधकर्ताओं ने मौलिक गणितीय गति सीमा को पार कर लिया

चार हजार साल पहले, बेबीलोनिया के निवासियों ने गुणा का आविष्कार किया। और इस वर्ष के मार्च में, गणितज्ञों ने इसमें सुधार किया।

18 मार्च 2019 को, दो शोधकर्ताओं ने दो बहुत बड़ी संख्याओं को गुणा करने का सबसे तेज़ ज्ञात तरीका बताया । यह कार्य गणित के बुनियादी कार्यों में से एक के लिए सबसे कुशल प्रक्रिया के लिए लंबे समय से चली आ रही खोज की परिणति का प्रतीक है।

फ्रेंच नेशनल सेंटर फॉर साइंटिफिक रिसर्च के गणितज्ञ जोरिस वान डर होवेन कहते हैं, "हर कोई सोचता है कि स्कूल में उन्हें कई बार पढ़ाया जाने वाला तरीका सबसे अच्छा है, लेकिन इस क्षेत्र में सक्रिय शोध चल रहा है।"

कई कम्प्यूटेशनल समस्याओं की जटिलता, संख्या के नए अंकों की गिनती से of बड़े अपराधों को खोजने के लिए, गुणा की दर को कम करती है। Van der Hoeven कई अन्य समस्याओं को हल करने के लिए एक प्रकार की गणितीय गति सीमा के असाइनमेंट के रूप में उनके परिणाम का वर्णन करता है।

"भौतिकी में, प्रकाश की गति जैसे महत्वपूर्ण स्थिरांक हैं जो आपको सभी प्रकार की घटनाओं का वर्णन करने की अनुमति देते हैं," वैन डेर बोवेन ने कहा। "यदि आप जानना चाहते हैं कि कंप्यूटर कुछ गणितीय समस्याओं को कितनी जल्दी हल कर सकते हैं, तो पूर्णांक का गुणन कुछ बुनियादी बिल्डिंग ब्लॉक के रूप में उत्पन्न होता है, जिसके संबंध में आप इस तरह की गति व्यक्त कर सकते हैं।"

लगभग हर कोई उसी तरह संख्याओं को गुणा करना सीखता है। हम एक कॉलम में संख्या लिखते हैं, नीचे के प्रत्येक अंक (अंकों को ध्यान में रखते हुए) द्वारा शीर्ष संख्या को गुणा करते हैं और परिणाम जोड़ते हैं। जब आप दो दो अंकों की संख्या को गुणा करते हैं, तो आपको अंतिम परिणाम प्राप्त करने के लिए चार छोटे गुणा करना पड़ता है।

" ट्रांसफर " की स्कूल पद्धति के लिए n ² चरणों की आवश्यकता होती है, जहां n प्रत्येक गुणा संख्याओं में अंकों की संख्या होती है। तीन-अंकीय संख्याओं वाली गणनाओं में नौ गुणा और एक-अंकीय संख्याओं के साथ 10,000 की आवश्यकता होती है।

स्थानांतरण विधि कई अंकों से मिलकर संख्याओं के साथ ठीक काम करती है, हालांकि, लाखों या अरबों अंकों से गुणा करने वाली संख्याओं को गुणा करना शुरू कर देती है (जो कि कंप्यूटर जब सटीक गणना π या जब दुनिया भर में बड़ी प्राइम संख्याओं की खोज करते हैं )। एक अरब अंकों के साथ दो संख्याओं को गुणा करने के लिए, आपको एक अरब वर्ग, या 10 ¹⁸ , गुणा करने की आवश्यकता होगी - यह एक आधुनिक कंप्यूटर के लिए लगभग 30 साल लगेंगे।

कई सदियों के लिए, यह माना जाता था कि संख्याओं को तेजी से गुणा नहीं किया जा सकता है। फिर 1960 में, 23 वर्षीय सोवियत और रूसी गणितज्ञ अनातोली अलेक्सेविच कारत्सुबा , आंद्रेई निकोलेयेविच कोलमोगोरोव , एक सोवियत गणितज्ञ, 20 वीं शताब्दी के महानतम गणितज्ञों में से एक सेमिनार में भाग लिया। कोलमोगोरोव ने कहा कि एन ² संचालन से कम के गुणन की कोई सामान्य विधि नहीं है। करतसुबा ने फैसला किया कि इस तरह की एक विधि थी - और एक सप्ताह की खोज के बाद उन्होंने इसकी खोज की।


अनातोली अलेक्सेविच कारत्सुबा

करतसुबा के गुणन में संख्या के अंकों को तोड़ने और उनके संयोजन को एक नए तरीके से दोहराते हैं, जो बड़ी संख्या में गुणा के बजाय कम परिवर्धन और घटाव को पूरा करने की अनुमति देता है। विधि समय की बचत करती है, क्योंकि जोड़ n ^{2 के} बजाय केवल 2n चरण लेता है।


पारंपरिक 25x63 गुणन विधि में चार एकल-अंक गुणा और कई परिवर्धन की आवश्यकता होती है


करतसुबा 25x63 के गुणन में एक ही संख्या में तीन गुणा और कई जोड़ और घटाव की आवश्यकता होती है।
a) संख्याओं को तोड़ो
b) दसियों गुणा करें
ग) इकाइयों को गुणा करें
d) संख्याएँ जोड़ें
e) इन राशियों को गुणा करें
च) ई - बी - सी पर विचार करें
छ) बी, सी और एफ के कुल इकट्ठा

जैसे-जैसे संख्याओं की संख्या बढ़ती जाती है, करतसुबा पद्धति का पुनरावर्ती उपयोग किया जा सकता है।


2531x1467 को गुणा करने की पारंपरिक विधि को एक अंक से 16 गुणा की आवश्यकता होती है।


करतसुबा 2531x1467 के गुणन में 9 गुणा की आवश्यकता होती है।

पेंसिल्वेनिया स्टेट यूनिवर्सिटी के गणितज्ञ मार्टिन फहरर ने कहा, "स्कूल में एडिशन एक साल पहले होता है, क्योंकि यह बहुत सरल होता है, यह रैखिक समय में चलता है, बाएं से दाएं पढ़ने की संख्या में तेजी से।"

बड़ी संख्या के साथ काम करते समय, करतसुबा के गुणन को पुनरावृत्ति से दोहराया जा सकता है, मूल संख्याओं को लगभग उतने हिस्सों में तोड़ दिया जाता है जैसे कि उनमें संकेत हैं। और प्रत्येक विभाजन के साथ, आप गुणन को बदलते हैं, जिसके लिए कई चरणों की आवश्यकता होती है, इसके अलावा और घटाव, जिसके लिए बहुत कम चरणों की आवश्यकता होती है।

न्यू साउथ वेल्स विश्वविद्यालय के गणितज्ञ और नए कार्य के सह-लेखक डेविड हार्वे ने कहा, "कई गुणाओं को परिवर्धन में बदल दिया जा सकता है, जो कि कंप्यूटर तेजी से कर सकेंगे।"

करतसुबा पद्धति ने केवल एक अंक द्वारा केवल n ^1.58 गुणा का उपयोग करके संख्याओं को गुणा करना संभव बनाया। फिर, 1971 में, अर्नोल्ड श्नहगे और वोल्कर स्ट्रैसेन ने बड़ी संख्या में n × log n × log (log n) छोटे गुणा से गुणा करने के लिए एक विधि प्रकाशित की। एक अरब वर्णों से दो संख्याओं को गुणा करने के लिए, प्रत्येक करत्सुबा पद्धति को 165 ट्रिलियन चरणों की आवश्यकता होगी।


जोरिस वैन डेर होवेन, फ्रेंच नेशनल सेंटर फॉर साइंटिफिक रिसर्च में गणितज्ञ

Schönhage-Strassen विधि का उपयोग कंप्यूटरों द्वारा बड़ी संख्या में गुणा करने के लिए किया जाता है, और इसके दो अन्य महत्वपूर्ण परिणाम सामने आए हैं। सबसे पहले, उन्होंने फास्ट फूरियर ट्रांसफॉर्म नामक सिग्नल प्रोसेसिंग के क्षेत्र से एक तकनीक शुरू की। तब से, यह तकनीक सभी तेज गुणा एल्गोरिदम का आधार रही है।

दूसरे, एक ही काम में, शॉनहेज और स्ट्रैसेन ने एक और भी तेज एल्गोरिथ्म की संभावना का सुझाव दिया - एक संकेत द्वारा केवल n × लॉग एन गुणन की आवश्यकता वाली विधि - और इस तरह के एक एल्गोरिथ्म सबसे तेज संभव होगा। यह धारणा इस भावना पर आधारित थी कि इस तरह के एक मौलिक संचालन के लिए गुणन के रूप में, संचालन के प्रतिबंध को किसी भी तरह से n × लॉग एन × लॉग (लॉग एन) की तुलना में अधिक सुरुचिपूर्ण ढंग से लिखा जाना चाहिए।

"आम तौर पर सहमत हुए कि गुणा एक महत्वपूर्ण बुनियादी ऑपरेशन है, जो विशुद्ध रूप से सौंदर्य की दृष्टि से, इसे जटिलता में एक सुंदर प्रतिबंध की आवश्यकता है," फ्यूहरर ने कहा। "अनुभव से, हम जानते हैं कि बुनियादी चीजों का गणित हमेशा सुरुचिपूर्ण होता है।"

स्कोन्हागे और स्ट्रैसेन का अजीब प्रतिबंध, एन × लॉग एन × लॉग (लॉग एन), पिछले 36 वर्षों से। 2007 में, फ्यूहरर ने इस रिकॉर्ड को तोड़ दिया , और यह सब हुआ। पिछले एक दशक में, गणितज्ञों ने कभी-कभी तेज गुणा एल्गोरिदम पाया है, जिनमें से प्रत्येक धीरे-धीरे एन × लॉग एन मार्क तक क्रॉल किया गया है, जो काफी हद तक नहीं पहुंच रहा है। फिर इस साल मार्च में, हार्वे और वैन डेर होवेन इसके पास पहुंचे।

उनकी विधि उनके सामने किए गए महान कार्यों में सुधार है। वह संख्याओं को संकेतों में तोड़ता है, तेजी से फूरियर रूपांतरण के बेहतर संस्करण का उपयोग करता है, और पिछले 40 वर्षों में किए गए अन्य सफलताओं का लाभ उठाता है। "हम तेजी से फूरियर का उपयोग अधिक मोटे तौर पर रूपांतरित करते हैं, इसे कई बार इस्तेमाल करते हैं, केवल एक ही नहीं, और जोड़ और घटाव के साथ और भी अधिक गुणा करते हैं," वैन डेर होवेन ने कहा।

हार्वे और वैन डेर हूवन के एल्गोरिथ्म से साबित होता है कि गुणा को × × एन एन चरणों में किया जा सकता है। हालांकि, वह एक तेज़ विधि की अनुपस्थिति साबित नहीं करता है। यह स्थापित करना अधिक कठिन होगा कि उनका दृष्टिकोण जितना संभव हो उतना तेज़ हो। फरवरी के अंत में, आरहस विश्वविद्यालय के कंप्यूटर वैज्ञानिकों की एक टीम ने एक पत्र प्रकाशित किया जिसमें दावा किया गया था कि यदि कोई अप्रमाणिक सिद्धांत सही निकला, तो यह विधि वास्तव में गुणा करने का सबसे तेज़ तरीका होगा।

और यद्यपि सिद्धांत रूप में यह नया एल्गोरिथ्म बहुत महत्वपूर्ण है, व्यवहार में यह बहुत अधिक नहीं बदलेगा, क्योंकि यह केवल पहले से उपयोग किए गए एल्गोरिदम को थोड़ा हरा देता है। "हम सभी के लिए उम्मीद कर सकते हैं तीन गुना त्वरण है," वैन डेर होवेन ने कहा। "इससे ज्यादा कुछ नहीं।"

इसके अलावा, कंप्यूटर उपकरण सर्किट बदल गए हैं। बीस साल पहले, कंप्यूटर ने गुणा की तुलना में बहुत तेजी से प्रदर्शन किया। गुणा और जोड़ की दरों में अंतर तब से गंभीर रूप से कम हो गया है, जिसके परिणामस्वरूप, कुछ चिप्स पर, गुणा भी आगे निकल सकता है। कुछ प्रकार के उपकरणों का उपयोग करते हुए, "आप कंप्यूटर को संख्याओं को गुणा करने के लिए मजबूर करके इसके अलावा गति बढ़ा सकते हैं, और यह कुछ प्रकार का पागलपन है," हार्वे ने कहा।

समय के साथ उपकरण बदलता है, लेकिन अपनी कक्षा का सबसे अच्छा एल्गोरिदम हमेशा के लिए रहता है। कोई फर्क नहीं पड़ता कि भविष्य में कंप्यूटर कैसे दिखते हैं, हार्वे और वैन डेर हूवन एल्गोरिदम अभी भी संख्याओं को गुणा करने का सबसे कुशल तरीका होगा।