करत्सुबा एल्गोरिथम

az+b और cz+d (बॉक्सिंग) का करत्सुबा गुणन, और 1234 और 567। मैजेंटा तीर गुणन को दर्शाता है, एम्बर जोड़ को दर्शाता है, चांदी घटाव को दर्शाता है और हल्का सियान बाएं शिफ्ट को दर्शाता है। (ए), (बी) और (सी) मध्यवर्ती मान प्राप्त करने के लिए प्रयुक्त रिकर्सन दिखाते हैं।

करात्सुबा एल्गोरिथ्म तेज़ गुणन एल्गोरिथ्म है। यह 1960 में अनातोली करत्सुबा द्वारा खोजा गया था और 1962 में प्रकाशित हुआ था। यह फूट डालो और जीतो एल्गोरिथ्म है जो दो n-अंकीय संख्याओं के गुणन को n/2-अंकीय संख्याओं के तीन गुणा तक कम कर देता है और, इस कमी को दोहराकर, अधिकतम करने के लिए $n^{\log _{2}3}\approx n^{1.58}$ एकल अंकों का गुणन। इसलिए यह लंबे गुणन एल्गोरिथ्म की तुलना में स्पर्शोन्मुख जटिलता है, जो प्रदर्शन करता है $n^{2}$ एकल अंक वाले उत्पाद। उदाहरण के लिए, दो 1024-अंकीय संख्याओं को गुणा करने के लिए (n = 1024 = 2¹⁰), पारंपरिक एल्गोरिथम की आवश्यकता है (2¹⁰)² = 1,048,576 एक-अंकीय गुणन, जबकि करात्सुबा एल्गोरिदम के लिए 3 की आवश्यकता होती है¹⁰ = 59,049 इस प्रकार ~17.758 गुना तेज है।

करात्सुबा एल्गोरिथम द्विघात ग्रेड स्कूल एल्गोरिथम की तुलना में एसिम्प्टोटिक रूप से तेज़ पहला गुणन एल्गोरिथम था। टूम-कुक गुणन | टूम-कुक एल्गोरिथम (1963) करात्सुबा की विधि का तेज़ सामान्यीकरण है, और शॉनहेज-स्ट्रैसन एल्गोरिथम (1971) पर्याप्त रूप से बड़े n के लिए और भी तेज़ है।

इतिहास

दो एन-अंकीय संख्याओं के गुणा के लिए मानक प्रक्रिया के लिए कई प्राथमिक संक्रियाओं की आवश्यकता होती है $n^{2}\,\!$, या $O(n^{2})\,\!$ बिग-ओ नोटेशन में। एंड्री कोलमोगोरोव ने अनुमान लगाया कि पारंपरिक एल्गोरिदम असीमित रूप से इष्टतम था, जिसका अर्थ है कि उस कार्य के लिए किसी भी एल्गोरिदम की आवश्यकता होगी $\Omega (n^{2})\,\!$ प्राथमिक संचालन।

1960 में, कोलमोगोरोव ने मॉस्को स्टेट यूनिवर्सिटी में साइबरनेटिक्स में गणितीय समस्याओं पर संगोष्ठी का आयोजन किया, जहाँ उन्होंने कहा कि $\Omega (n^{2})\,\!$ कम्प्यूटेशनल जटिलता सिद्धांत में अनुमान और अन्य समस्याएं। सप्ताह के भीतर, 23 वर्षीय छात्र करत्सुबा ने एल्गोरिदम पाया जो दो एन-अंकीय संख्याओं को गुणा करता है $O(n^{\log _{2}3})$ प्रारंभिक चरण, इस प्रकार अनुमान को अस्वीकार करते हैं। कोलमोगोरोव इस खोज को लेकर बहुत उत्साहित थे; उन्होंने संगोष्ठी की अगली बैठक में इसकी सूचना दी, जिसे तब समाप्त कर दिया गया था। कोलमोगोरोव ने दुनिया भर के सम्मेलनों में करात्सुबा परिणाम पर कुछ व्याख्यान दिए (उदाहरण के लिए देखें, गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस की कार्यवाही 1962, पीपी। 351-356, और स्टॉकहोम में गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस में दिए गए 6 व्याख्यान, 1962 ) और यूएसएसआर एकेडमी ऑफ साइंसेज की कार्यवाही में 1962 में विधि प्रकाशित की। लेख कोल्मोगोरोव द्वारा लिखा गया था और इसमें गुणन पर दो परिणाम शामिल थे, करात्सुबा के एल्गोरिथ्म और यूरी पेट्रोविच ऑफमैन द्वारा अलग परिणाम; इसमें ए. करत्सुबा और यू. लेखक के रूप में ऑफमैन। करत्सुबा को केवल कागज के बारे में पता चला जब उन्हें प्रकाशक से पुनर्मुद्रण प्राप्त हुआ।

एल्गोरिथम

बुनियादी कदम

करात्सुबा के एल्गोरिथ्म का मूल सिद्धांत विभाजित और जीत एल्गोरिथ्म है | फूट डालो और जीतो, सूत्र का उपयोग करके जो दो बड़ी संख्याओं के उत्पाद की गणना करने की अनुमति देता है $x$ और $y$ छोटी संख्याओं के तीन गुणन का उपयोग करते हुए, प्रत्येक में लगभग आधे अंक होते हैं $x$ या $y$, साथ ही कुछ जोड़ और अंक बदलाव। यह बुनियादी कदम, वास्तव में, गुणा एल्गोरिथम#जटिल संख्या गुणन का सामान्यीकरण है, जहां काल्पनिक इकाई i मूलांक की शक्ति द्वारा प्रतिस्थापित किया जाता है।

होने देना $x$ और $y$ के रूप में प्रतिनिधित्व किया जाए $n$-डिजिट तार कुछ आधार में $B$. किसी भी सकारात्मक पूर्णांक के लिए $m$ से कम $n$, दी गई दो संख्याओं को इस प्रकार लिख सकते हैं

$x=x_{1}B^{m}+x_{0},$

$y=y_{1}B^{m}+y_{0},$

कहाँ $x_{0}$ और $y_{0}$ से कम हैं $B^{m}$. उत्पाद तो है

${\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}$ कहाँ

$z_{2}=x_{1}y_{1},$

$z_{1}=x_{1}y_{0}+x_{0}y_{1},$

$z_{0}=x_{0}y_{0}.$

इन सूत्रों के लिए चार गुणन की आवश्यकता होती है और वे चार्ल्स बैबेज के लिए जाने जाते थे। करत्सुबा ने देखा $xy$ कुछ अतिरिक्त परिवर्धन की कीमत पर, केवल तीन गुणा में गणना की जा सकती है। साथ $z_{0}$ और $z_{2}$ जैसा कि पहले कोई देख सकता है

${\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}+x_{0}y_{0}-x_{0}y_{0}\\&=x_{1}y_{0}+x_{0}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})y_{0}+(x_{0}+x_{1})y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.\\\end{aligned}}$

उदाहरण

12345 और 6789 के उत्पाद की गणना करने के लिए, जहां बी = 10, एम = 3 चुनें। हम परिणामी आधार (बी) का उपयोग करके इनपुट ऑपरेंड को विघटित करने के लिए एम राइट शिफ्ट का उपयोग करते हैं^m = 1000), जैसा:

12345 = '12' · 1000 + '345'

6789 = '6' · 1000 + '789'

केवल तीन गुणन, जो छोटे पूर्णांकों पर संचालित होता है, का उपयोग तीन आंशिक परिणामों की गणना करने के लिए किया जाता है:

जेड₂ = 12 × 6 = 72

साथ₀ = 345 × 789 = 272205

साथ₁ = (12 + 345) × (6 + 789) - जेड₂ - जेड₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

हम केवल इन तीन आंशिक परिणामों को जोड़कर परिणाम प्राप्त करते हैं, तदनुसार स्थानांतरित कर दिया जाता है (और फिर इनपुट ऑपरेंड के लिए इन तीन इनपुटों को आधार 1000 में विघटित करके ध्यान में रखा जाता है):

परिणाम = जेड₂ · (बी^मी)² + के साथ₁ · (बी^मी)¹ + के साथ₀ · (बी^मी)⁰, यानी

परिणाम = 72 · 1000² + 11538 · 1000 + 272205 = '83810205'।

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

पुनरावर्ती अनुप्रयोग

यदि n चार या अधिक है, तो करात्सुबा के मूल चरण में तीन गुणन में n अंकों से कम वाले ऑपरेंड शामिल हैं। इसलिए, उन उत्पादों की गणना करत्सुबा एल्गोरिथम की पुनरावर्ती कॉल द्वारा की जा सकती है। पुनरावर्तन तब तक लागू किया जा सकता है जब तक कि संख्याएं इतनी छोटी न हों कि उन्हें सीधे (या आवश्यक) गणना की जा सके।

पूर्ण 32-बिट गुणा 32-बिट बाइनरी गुणक वाले कंप्यूटर में, उदाहरण के लिए, कोई B = 2 चुन सकता है³¹ और प्रत्येक अंक को अलग 32-बिट बाइनरी शब्द के रूप में संग्रहीत करें। फिर योग x₁ + एक्स₀ और वाई₁ + और₀ कैरी-ओवर डिजिट (कैरी-सेव योजक के रूप में) को स्टोर करने के लिए अतिरिक्त बाइनरी शब्द की आवश्यकता नहीं होगी, और करत्सुबा रिकर्सन को तब तक लागू किया जा सकता है जब तक कि संख्याओं को गुणा करने के लिए केवल अंक लंबा न हो।

समय जटिलता विश्लेषण

करात्सुबा का मूल चरण किसी भी आधार बी और किसी भी एम के लिए काम करता है, लेकिन पुनरावर्ती एल्गोरिथ्म सबसे अधिक कुशल होता है जब एम एन / 2 के बराबर होता है, गोल होता है। विशेष रूप से, यदि n 2 है^k , कुछ पूर्णांक k के लिए, और पुनरावर्तन केवल तभी रुकता है जब n 1 हो, तो एकल-अंक गुणन की संख्या 3 है^k, जो कि n है^c जहाँ c = लॉग₂3.

चूंकि कोई भी इनपुट शून्य अंकों के साथ बढ़ा सकता है जब तक कि उनकी लंबाई दो की शक्ति न हो, यह निम्नानुसार है कि किसी भी एन के लिए प्राथमिक गुणन की संख्या अधिकतम है $3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!$.

चूंकि करात्सुबा के बुनियादी कदम में जोड़, घटाव और अंकों की शिफ्ट (बी की शक्तियों से गुणा) n के अनुपात में समय लेती है, इसलिए n बढ़ने पर उनकी लागत नगण्य हो जाती है। अधिक सटीक रूप से, यदि टी (एन) प्राथमिक संचालन की कुल संख्या को दर्शाता है जो एल्गोरिदम दो एन-अंकीय संख्याओं को गुणा करते समय करता है, तो

$T(n)=3T(\lceil n/2\rceil )+cn+d$

कुछ स्थिरांक c और d के लिए। इस पुनरावर्तन संबंध के लिए, मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) | डिवाइड-एंड-कॉनकर पुनरावृत्ति संबंध लिए मास्टर प्रमेय बिग ओ नोटेशन बाउंड देता है $T(n)=\Theta (n^{\log _{2}3})\,\!$.

यह इस प्रकार है कि, पर्याप्त रूप से बड़े n के लिए, करत्सुबा का एल्गोरिथ्म लांगहैंड गुणन की तुलना में कम बदलाव और एकल-अंक जोड़ देगा, भले ही इसका मूल चरण सीधे सूत्र की तुलना में अधिक जोड़ और बदलाव का उपयोग करता है। एन के छोटे मूल्यों के लिए, हालांकि, अतिरिक्त शिफ्ट और ऐड ऑपरेशंस इसे लांगहैंड विधि से धीमा कर सकते हैं। सकारात्मक रिटर्न का बिंदु कंप्यूटर मंच और संदर्भ पर निर्भर करता है। अंगूठे के नियम के रूप में, करात्सुबा की विधि आमतौर पर तेज़ होती है जब गुणक 320-640 बिट्स से अधिक होते हैं।

कार्यान्वयन

यहाँ इस एल्गोरिथम के लिए स्यूडोकोड है, आधार दस में प्रदर्शित संख्याओं का उपयोग करते हुए। पूर्णांकों के द्विआधारी प्रतिनिधित्व के लिए, यह हर जगह 10 को 2 से बदलने के लिए पर्याप्त है। split_at फ़ंक्शन का दूसरा तर्क दाईं ओर से निकाले जाने वाले अंकों की संख्या निर्दिष्ट करता है: उदाहरण के लिए, split_at( 12345 , 3) ​​3 अंतिम अंक निकालेगा, जो देगा: high= 12 , low= 345 ।

<वाक्यविन्यास प्रकाश लैंग = सी> समारोह करात्सुबा (संख्या 1, संख्या 2)

   अगर (संख्या 1 <10 या संख्या 2 <10)
       वापसी num1 × num2 /* पारंपरिक गुणन पर वापस जाएँ */
   
   / * संख्याओं के आकार की गणना करता है। */
   एम = अधिकतम (आकार_बेस 10 (संख्या 1), आकार_बेस 10 (संख्या 2))
   एम 2 = मंजिल (एम / 2)
   /* एम2 = छत (एम/2) भी काम करेगा */
   
   /* अंकों के क्रम को बीच में विभाजित करें। */
   हाई1, लो1 = स्प्लिट_एट (संख्या1, एम2)
   हाई2, लो2 = स्प्लिट_एट (संख्या2, एम2)
   
   /* 3 पुनरावर्ती कॉल लगभग आधे आकार के नंबरों पर किए गए। */
   z0 = करात्सुबा (low1, low2)
   z1 = करात्सुबा (low1 + high1, low2 + high2)
   z2 = करात्सुबा (हाई1, हाई2)
   
   वापसी (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

</वाक्यविन्यास हाइलाइट>

समस्या जो तब होती है जब कार्यान्वयन यह है कि उपरोक्त गणना $(x_{1}+x_{0})$ और $(y_{1}+y_{0})$ के लिए $z_{1}$ परिणाम अतिप्रवाह हो सकता है (परिणाम श्रेणी में उत्पन्न करेगा $B^{m}\leq {\text{result}}<2B^{m}$), जिसके लिए अतिरिक्त बिट वाले गुणक की आवश्यकता होती है। इसका ध्यान रखकर इससे बचा जा सकता है

$z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.$

यह गणना $(x_{0}-x_{1})$ और $(y_{1}-y_{0})$ की सीमा में परिणाम देगा $-B^{m}<{\text{result}}<B^{m}$. यह विधि ऋणात्मक संख्याओं का उत्पादन कर सकती है, जिसके लिए अतिरिक्त बिट की आवश्यकता होती है, और फिर भी गुणक के लिए अतिरिक्त बिट की आवश्यकता होगी। हालाँकि, इससे बचने का तरीका यह है कि चिन्ह को रिकॉर्ड किया जाए और फिर के निरपेक्ष मान का उपयोग किया जाए $(x_{0}-x_{1})$ और $(y_{1}-y_{0})$ अहस्ताक्षरित गुणन करने के लिए, जिसके बाद दोनों संकेतों के मूल रूप से भिन्न होने पर परिणाम को नकारा जा सकता है। और फायदा यह है कि भले ही $(x_{0}-x_{1})(y_{1}-y_{0})$ नकारात्मक हो सकता है, की अंतिम गणना $z_{1}$ केवल जोड़ शामिल है।

बाहरी संबंध

• Karatsuba's Algorithm for Polynomial Multiplication
• Weisstein, Eric W. "Karatsuba Multiplication". MathWorld.
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.