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

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-अंकीय संख्याओं के गुणा के लिए मानक प्रक्रिया के लिए बिग-ओ नोटेशन में $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 के उत्पाद की गणना करने के लिए, जहां b = 10, M = 3 चुनें। हम परिणामी आधार (b) का उपयोग करके इनपुट ऑपरेंड को विघटित करने के लिए M^m = 1000) राइट शिफ्ट का उपयोग करते हैं, जैसा:

12345 = '12' · 1000 + '345'

6789 = '6' · 1000 + '789'

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

Z₂ = 12 × 6 = 72

Z₀ = 345 × 789 = 272205

Z₁ = (12 + 345) × (6 + 789) - Z₂ - Z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

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

परिणाम = Z₂ · (B^m)² + के Z₁ · (B^m)¹ + के Z₀ · (B^m)⁰, अर्थात्

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

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

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

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

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

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

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

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

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

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

कुछ स्थिरांक c और d के लिए। इस पुनरावर्तन संबंध के लिए, मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) पुनरावृत्ति संबंध लिए मास्टर प्रमेय बिग ओ नोटेशन सीमा देता है

$T(n)=\Theta (n^{\log _{2}3})\,\!$.

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

कार्यान्वयन

यहाँ इस एल्गोरिथम के लिए स्यूडोकोड है, आधार दस में प्रदर्शित संख्याओं का उपयोग करते हुए। पूर्णांकों के द्विआधारी प्रतिनिधित्व के लिए, यह हर जगह 10 को 2 से बदलने के लिए पर्याप्त है।

विभाजन_पर फलन का दूसरा तर्क दाईं ओर से निकाले जाने वाले अंकों की संख्या निर्दिष्ट करता है: उदाहरण के लिए, विभाजन_पर( 12345 , 3) ​​3 अंतिम अंक निकालेगा, जो देगा: उच्च= 12 , निम्न= 345 ।

function karatsuba(num1, num2)
    if (num1 < 10 or num2 < 10)
        return num1 × num2 /* fall back to traditional multiplication */
    
    /* Calculates the size of the numbers. */
    m = max(size_base10(num1), size_base10(num2))
    m2 = floor(m / 2) 
    /* m2 = ceil (m / 2) will also work */
    
    /* Split the digit sequences in the middle. */
    high1, low1 = split_at(num1, m2)
    high2, low2 = split_at(num2, m2)
    
    /* 3 recursive calls made to numbers approximately half the size. */
    z0 = karatsuba(low1, low2)
    z1 = karatsuba(low1 + high1, low2 + high2)
    z2 = karatsuba(high1, high2)
    
    return (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.