करत्सुबा एल्गोरिथम: Difference between revisions

Latest revision as of 13:04, 13 September 2023

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

करात्सुबा कलनविधि तेज़ गुणन कलनविधि है। इसकी खोज 1960 में अनातोली करत्सुबा द्वारा की गई थी और 1962 में प्रकाशित हुई थी।^[1]^[2]^[3] यह विभाजन और जीत कलनविधि है जो दो 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 में विधि प्रकाशित किया था। लेख कोल्मोगोरोव द्वारा लिखा गया था और इसमें गुणन पर दो परिणाम, करात्सुबा के कलनविधि और यूरी पेट्रोविच ऑफमैन द्वारा अलग परिणाम; इसमें ए. करत्सुबा और यू. लेखक के रूप में ऑफमैन सम्मिलित थे। करत्सुबा को केवल कागज के बारे में पता चला जब उन्हें प्रकाशक से पुनर्मुद्रण प्राप्त हुआ है।^[2]

एल्गोरिथम

मूलभूत चरण

करात्सुबा के कलनविधि का मूल सिद्धांत एक सूत्र का उपयोग करके विभाजित और जीतना है, जो किसी को दो बड़ी संख्याओं $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}.

इन सूत्रों के लिए चार गुणन की आवश्यकता होती है और वे चार्ल्स बैबेज के लिए जाने जाते थे।^[4] करत्सुबा ने देखा $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 बिट्स से अधिक होते हैं।^[5]

कार्यान्वयन

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

विभाजन पर फलन का दूसरा तर्क दाईं ओर से निकाले जाने वाले अंकों की संख्या निर्दिष्ट करता है: उदाहरण के लिए, विभाजन_पर( 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}$ केवल जोड़ शामिल है।

संदर्भ

↑ A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596{{cite journal}}: CS1 maint: postscript (link)
↑ ^2.0 ^2.1 A. A. Karatsuba (1995). "The Complexity of Computations" (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183. Translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995){{cite journal}}: CS1 maint: postscript (link)
↑ Knuth D.E. (1969) The Art of Computer Programming. v.2. Addison-Wesley Publ.Co., 724 pp.
↑ Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, Passages from the Life of a Philosopher, Longman Green, London, 1864; page 125.
↑ "Karatsuba multiplication". www.cburch.com.
↑ Weiss, Mark A. (2005). Data Structures and Algorithm Analysis in C++. Addison-Wesley. p. 480. ISBN 0321375319.

बाहरी संबंध

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.

[kara1962-1] A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596{{cite journal}}: CS1 maint: postscript (link)

[kara1995-2] 2.0 ^2.1 A. A. Karatsuba (1995). "The Complexity of Computations" (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183. Translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995){{cite journal}}: CS1 maint: postscript (link)

[knuthV2-3] Knuth D.E. (1969) The Art of Computer Programming. v.2. Addison-Wesley Publ.Co., 724 pp.

[4] Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, Passages from the Life of a Philosopher, Longman Green, London, 1864; page 125.

[5] "Karatsuba multiplication". www.cburch.com.

[6] Weiss, Mark A. (2005). Data Structures and Algorithm Analysis in C++. Addison-Wesley. p. 480. ISBN 0321375319.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
 {{short description|Algorithm for integer multiplication}}
-[[File:Karatsuba_multiplication.svg|thumb|300px|az+b और cz+d (बॉक्सिंग) का करत्सुबा गुणन, और 1234 और 567। मैजेंटा तीर गुणन को दर्शाता है, एम्बर जोड़ को दर्शाता है, चांदी घटाव को दर्शाता है और हल्का सियान बाएं शिफ्ट को दर्शाता है। (ए), (बी) और (सी) मध्यवर्ती मान प्राप्त करने के लिए प्रयुक्त रिकर्सन दिखाते हैं।]]करात्सुबा एल्गोरिथ्म तेज़ [[गुणन एल्गोरिथ्म]] है। इसकी खोज 1960 में [[अनातोली करत्सुबा]] द्वारा की गई थी और 1962 में प्रकाशित हुई थी।<ref name="kara1962">
+[[File:Karatsuba_multiplication.svg|thumb|300px|az+b और cz+d (बॉक्सिंग) का करत्सुबा गुणन, और 1234 और 567। मैजेंटा तीर गुणन को दर्शाता है, एम्बर जोड़ को दर्शाता है, चांदी घटाव को दर्शाता है और हल्का सियान बाएं शिफ्ट को दर्शाता है। (ए), (बी) और (सी) मध्यवर्ती मान प्राप्त करने के लिए प्रयुक्त रिकर्सन दिखाते हैं।]]'''करात्सुबा कलनविधि''' तेज़ गुणन कलनविधि है। इसकी खोज 1960 में अनातोली करत्सुबा द्वारा की गई थी और 1962 में प्रकाशित हुई थी।<ref name="kara1962">
    {{cite journal
    | author = A. Karatsuba and Yu. Ofman
@@ Line 22: / Line 22: @@
 </ref><ref name="knuthV2">
    Knuth D.E. (1969) ''[[The Art of Computer Programming]]. v.2.'' Addison-Wesley Publ.Co., 724 pp.
-</ref> यह [[फूट डालो और जीतो एल्गोरिथ्म]] है जो दो n-अंकीय संख्याओं के गुणन को घटाकर n/2-अंकीय संख्याओं के तीन गुणा तक कम कर देता है और, इस कमी को, अधिकतम <math> n^{\log_23}\approx n^{1.58}</math> एकल अंकों का गुणन में दोहराता है। इसलिए यह लंबे गुणन एल्गोरिथ्म की तुलना में [[स्पर्शोन्मुख जटिलता]] है, जो प्रदर्शन करता है <math>n^2</math> एकल अंक वाले उत्पाद। उदाहरण के लिए, दो 1024-अंकीय संख्याओं (n = 1024 = 2<sup>10</sup>) को गुणा करने के लिए, पारंपरिक एल्गोरिथम को (2<sup>10</sup>)<sup>2</sup> = 1,048,576 एकल-अंकीय गुणन की आवश्यकता है, जबकि करात्सुबा एल्गोरिदम के लिए 3<sup>10</sup> = 59,049 की आवश्यकता होती है, इस प्रकार ~17.758 गुना तेज है।
+</ref> यह विभाजन और जीत कलनविधि है जो दो n-अंकीय संख्याओं के गुणन को घटाकर n/2-अंकीय संख्याओं के तीन गुणा तक कम कर देता है और, इस कमी को, अधिकतम <math> n^{\log_23}\approx n^{1.58}</math> एकल अंकों का गुणन में दोहराता है। इसलिए यह लंबे गुणन कलनविधि की तुलना में [[स्पर्शोन्मुख जटिलता|स्पर्शोन्मुख सम्मिश्र]] है, जो प्रदर्शन  <math>n^2</math> एकल अंक वाले उत्पाद करता है। उदाहरण के लिए, दो 1024-अंकीय संख्याओं (n = 1024 = 2<sup>10</sup>) को गुणा करने के लिए, पारंपरिक एल्गोरिथम को (2<sup>10</sup>)<sup>2</sup> = 1,048,576 एकल-अंकीय गुणन की आवश्यकता है, चूंकि करात्सुबा एल्गोरिदम के लिए 3<sup>10</sup> = 59,049 की आवश्यकता होती है, इस प्रकार ~17.758 गुना तेज है।
 करात्सुबा एल्गोरिथम द्विघात ग्रेड स्कूल एल्गोरिथम की तुलना में एसिम्प्टोटिक रूप से तेज़ पहला गुणन एल्गोरिथम था।
@@ Line 29: / Line 29: @@
 == इतिहास ==
-दो एन-अंकीय संख्याओं के गुणा के लिए मानक प्रक्रिया के लिए कई प्राथमिक संक्रियाओं की आवश्यकता होती है <math>n^2\,\!</math>, या <math>O(n^2)\,\!</math> [[बिग-ओ नोटेशन]] में। [[एंड्री कोलमोगोरोव]] ने अनुमान लगाया कि पारंपरिक एल्गोरिदम असीमित रूप से इष्टतम था, जिसका अर्थ है कि उस कार्य के लिए किसी भी एल्गोरिदम की आवश्यकता होगी <math>\Omega(n^2)\,\!</math> प्राथमिक संचालन।
+दो n-अंकीय संख्याओं के गुणा के लिए मानक प्रक्रिया के लिए [[बिग-ओ नोटेशन]] में <math>n^2\,\!</math>, या <math>O(n^2)\,\!</math> के समानुपातिक कई प्राथमिक संक्रियाओं की आवश्यकता होती है। [[एंड्री कोलमोगोरोव]] ने अनुमान लगाया कि पारंपरिक एल्गोरिदम असीमित रूप से इष्टतम था, जिसका अर्थ है कि उस कार्य के लिए किसी भी एल्गोरिदम <math>\Omega(n^2)\,\!</math> प्राथमिक संचालन की आवश्यकता होगी।
-में, कोलमोगोरोव ने [[मॉस्को स्टेट यूनिवर्सिटी]] में [[साइबरनेटिक्स]] में गणितीय समस्याओं पर संगोष्ठी का आयोजन किया, जहाँ उन्होंने कहा कि <math>\Omega(n^2)\,\!</math> [[कम्प्यूटेशनल जटिलता सिद्धांत]] में अनुमान और अन्य समस्याएं। सप्ताह के भीतर, 23 वर्षीय छात्र करत्सुबा ने एल्गोरिदम पाया जो दो एन-अंकीय संख्याओं को गुणा करता है <math>O(n^{\log_2 3})</math> प्रारंभिक चरण, इस प्रकार अनुमान को अस्वीकार करते हैं। कोलमोगोरोव इस खोज को लेकर बहुत उत्साहित थे; उन्होंने संगोष्ठी की अगली बैठक में इसकी सूचना दी, जिसे तब समाप्त कर दिया गया था। कोलमोगोरोव ने दुनिया भर के सम्मेलनों में करात्सुबा परिणाम पर कुछ व्याख्यान दिए (उदाहरण के लिए देखें, गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस की कार्यवाही 1962, पीपी। 351-356, और स्टॉकहोम में गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस में दिए गए 6 व्याख्यान, 1962 ) और [[यूएसएसआर एकेडमी ऑफ साइंसेज की कार्यवाही]] में 1962 में विधि प्रकाशित की। लेख कोल्मोगोरोव द्वारा लिखा गया था और इसमें गुणन पर दो परिणाम शामिल थे, करात्सुबा के एल्गोरिथ्म और [[यूरी पेट्रोविच ऑफमैन]] द्वारा अलग परिणाम; इसमें ए. करत्सुबा और यू. लेखक के रूप में ऑफमैन। करत्सुबा को केवल कागज के बारे में पता चला जब उन्हें प्रकाशक से पुनर्मुद्रण प्राप्त हुआ।<ref name="kara1995"/>
+में, कोलमोगोरोव ने [[मॉस्को स्टेट यूनिवर्सिटी]] में [[साइबरनेटिक्स]] में गणितीय समस्याओं पर संगोष्ठी का आयोजन किया, जहाँ उन्होंने कहा कि <math>\Omega(n^2)\,\!</math> [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्र सिद्धांत]] में अनुमान और अन्य समस्याओं को बताया है। सप्ताह के अन्दर, 23 वर्षीय छात्र करत्सुबा ने एल्गोरिदम पाया जो दो एन-अंकीय संख्याओं को <math>O(n^{\log_2 3})</math>से गुणा करता है, प्रारंभिक चरण, इस प्रकार अनुमान को अस्वीकार करते हैं। कोलमोगोरोव इस खोज को लेकर बहुत उत्साहित थे; उन्होंने संगोष्ठी की अगली बैठक में इसकी सूचना दी, जिसे तब समाप्त कर दिया गया था। कोलमोगोरोव ने दुनिया भर के सम्मेलनों में करात्सुबा परिणाम पर कुछ व्याख्यान दिए (उदाहरण के लिए देखें, गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस की कार्यवाही 1962, पीपी है। 351-356, और स्टॉकहोम में गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस में दिए गए 6 व्याख्यान, 1962) और [[यूएसएसआर एकेडमी ऑफ साइंसेज की कार्यवाही]] में 1962 में विधि प्रकाशित किया था। लेख कोल्मोगोरोव द्वारा लिखा गया था और इसमें गुणन पर दो परिणाम, करात्सुबा के कलनविधि और [[यूरी पेट्रोविच ऑफमैन]] द्वारा अलग परिणाम; इसमें ए. करत्सुबा और यू. लेखक के रूप में ऑफमैन सम्मिलित थे। करत्सुबा को केवल कागज के बारे में पता चला जब उन्हें प्रकाशक से पुनर्मुद्रण प्राप्त हुआ है।<ref name="kara1995"/>
 == एल्गोरिथम ==
-=== बुनियादी कदम ===
+=== मूलभूत चरण ===
-करात्सुबा के एल्गोरिथ्म का मूल सिद्धांत विभाजित और जीत एल्गोरिथ्म है | फूट डालो और जीतो, सूत्र का उपयोग करके जो दो बड़ी संख्याओं के उत्पाद की गणना करने की अनुमति देता है <math>x</math> और <math>y</math> छोटी संख्याओं के तीन गुणन का उपयोग करते हुए, प्रत्येक में लगभग आधे अंक होते हैं <math>x</math> या <math>y</math>, साथ ही कुछ जोड़ और अंक बदलाव। यह बुनियादी कदम, वास्तव में, गुणा एल्गोरिथम#जटिल संख्या गुणन का सामान्यीकरण है, जहां [[काल्पनिक इकाई]] {{mvar|i}} [[मूलांक]] की शक्ति द्वारा प्रतिस्थापित किया जाता है।
+करात्सुबा के कलनविधि का मूल सिद्धांत एक सूत्र का उपयोग करके विभाजित और जीतना है, जो किसी को दो बड़ी संख्याओं <math>x</math> और <math>y</math> के उत्पाद की गणना करने की अनुमति देता है, छोटी संख्याओं के तीन गुणन का उपयोग करके, प्रत्येक में <math>x</math> या <math>y</math> के रूप में लगभग आधे अंक साथ ही कुछ जोड़ और अंक बदलाव होते हैं। यह मूलभूत चरण, वास्तविक में, एक समान जटिल गुणन कलनविधि का एक सामान्यीकरण है, जहां [[काल्पनिक इकाई]] {{mvar|i}} [[मूलांक]] की घात द्वारा प्रतिस्थापित किया जाता है।
-होने देना <math>x</math> और <math>y</math> के रूप में प्रतिनिधित्व किया जाए <math>n</math>-डिजिट तार कुछ आधार में <math>B</math>. किसी भी सकारात्मक पूर्णांक के लिए <math>m</math> से कम <math>n</math>, दी गई दो संख्याओं को इस प्रकार लिख सकते हैं
+होने देना <math>x</math> और <math>y</math> के रूप में प्रतिनिधित्व किया जाए <math>n</math>-संख्या रेखा कुछ आधार में <math>B</math>, किसी भी सकारात्मक पूर्णांक के लिए <math>m</math> से कम <math>n</math>, दी गई दो संख्याओं को इस प्रकार लिख सकते हैं
 :<math>x = x_1 B^m + x_0,</math>
 :<math>y = y_1 B^m + y_0,</math>
-कहाँ <math>x_0</math> और <math>y_0</math> से कम हैं <math>B^m</math>. उत्पाद तो है
+जहाँ <math>x_0</math> और <math>y_0</math> से कम  <math>B^m</math>. उत्पाद है तो
 <math>
@@ Line 52: / Line 52: @@
 \end{align}
 </math>
-कहाँ
+जहाँ
 :<math>z_2 = x_1 y_1,</math>
 :<math>z_1 = x_1 y_0 + x_0 y_1,</math>
 :<math>z_0 = x_0 y_0.</math>
-इन सूत्रों के लिए चार गुणन की आवश्यकता होती है और वे [[चार्ल्स बैबेज]] के लिए जाने जाते थे।<ref>Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, [https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n142 <!-- pg=125 --> Passages from the Life of a Philosopher], Longman Green, London, 1864; page 125.</ref> करत्सुबा ने देखा <math>xy</math> कुछ अतिरिक्त परिवर्धन की कीमत पर, केवल तीन गुणा में गणना की जा सकती है। साथ <math>z_0</math> और <math>z_2</math> जैसा कि पहले कोई देख सकता है
+इन सूत्रों के लिए चार गुणन की आवश्यकता होती है और वे [[चार्ल्स बैबेज]] के लिए जाने जाते थे।<ref>Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, [https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n142 <!-- pg=125 --> Passages from the Life of a Philosopher], Longman Green, London, 1864; page 125.</ref> करत्सुबा ने देखा <math>xy</math> कुछ अतिरिक्त परिवर्धन की मान पर, केवल तीन गुणा में गणना की जा सकती है। साथ में <math>z_0</math> और <math>z_2</math> जैसा कि पहले कोई देख सकता है
 :<math>
@@ Line 72: / Line 73: @@
 === उदाहरण ===
-और 6789 के उत्पाद की गणना करने के लिए, जहां बी = 10, एम = 3 चुनें। हम परिणामी आधार (बी) का उपयोग करके इनपुट ऑपरेंड को विघटित करने के लिए एम राइट शिफ्ट का उपयोग करते हैं<sup>m</sup> = 1000), जैसा:
+और 6789 के उत्पाद की गणना करने के लिए, जहां b = 10, M = 3 चुनें। हम परिणामी आधार (b) का उपयोग करके इनपुट ऑपरेंड को विघटित करने के लिए M<sup>m</sup>  = 1000) राइट शिफ्ट का उपयोग करते हैं, जैसा:
 : 12345 = '12' · 1000 + '345'
 : 6789 = '6' · 1000 + '789'
 केवल तीन गुणन, जो छोटे पूर्णांकों पर संचालित होता है, का उपयोग तीन आंशिक परिणामों की गणना करने के लिए किया जाता है:
-: जेड<sub>2</sub> = 12 × 6 = 72
+: Z<sub>2</sub> = 12 × 6 = 72
-: ''साथ''<sub>0</sub> = 345 × 789 = 272205
+: ''Z''<sub>0</sub> = 345 × 789 = 272205
-: ''साथ''<sub>1</sub> = (12 + 345) × (6 + 789) - ''जेड''<sub>2</sub> - जेड<sub>0</sub> = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538
+: ''Z''<sub>1</sub> = (12 + 345) × (6 + 789) - ''Z''<sub>2</sub> - Z<sub>0</sub> = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538
 हम केवल इन तीन आंशिक परिणामों को जोड़कर परिणाम प्राप्त करते हैं, तदनुसार स्थानांतरित कर दिया जाता है (और फिर इनपुट ऑपरेंड के लिए इन तीन इनपुटों को आधार ''1000'' में विघटित करके ध्यान में रखा जाता है):
-: परिणाम = ''जेड''<sub>2</sub> · (बी<sup>मी</sup>)<sup>2</sup> + के साथ<sub>1</sub> · (बी<sup>मी</sup>)<sup>1</sup> + के साथ<sub>0</sub> · (बी<sup>मी</sup>)<sup>0</sup>, यानी
+: परिणाम = ''Z''<sub>2</sub> · (B<sup>m</sup>)<sup>2</sup> + के Z<sub>1</sub> · (B<sup>m</sup>)<sup>1</sup> + के Z<sub>0</sub> · (B<sup>m</sup>)<sup>0</sup>, अर्थात्
 : परिणाम = 72 · 1000<sup>2</sup> + 11538 · 1000 + 272205 = '83810205'।
-ध्यान दें कि मध्यवर्ती तीसरा गुणन इनपुट डोमेन पर संचालित होता है जो पहले दो गुणाओं की तुलना में दो गुना बड़ा होता है, इसका आउटपुट डोमेन चार गुना से कम बड़ा होता है, और पहले दो गुणाओं से गणना की गई आधार-1000 कैरी को इसमें लिया जाना चाहिए इन दो घटावों की गणना करते समय खाता।
+ध्यान दें कि मध्यवर्ती तीसरा गुणन इनपुट डोमेन पर संचालित होता है जो पहले दो गुणाओं की तुलना में दो गुना बड़ा होता है, इसका आउटपुट डोमेन चार गुना से कम बड़ा होता है, और इन दो घटावों की गणना करते समय पहले दो गुणाओं से गणना की गई आधार-1000 को ध्यान में रखा जाना चाहिए।
 === पुनरावर्ती अनुप्रयोग ===
-यदि n चार या अधिक है, तो करात्सुबा के मूल चरण में तीन गुणन में n अंकों से कम वाले ऑपरेंड शामिल हैं। इसलिए, उन उत्पादों की गणना करत्सुबा एल्गोरिथम की पुनरावर्ती कॉल द्वारा की जा सकती है। पुनरावर्तन तब तक लागू किया जा सकता है जब तक कि संख्याएं इतनी छोटी न हों कि उन्हें सीधे (या आवश्यक) गणना की जा सके।
+यदि n चार या अधिक है, तो करात्सुबा के मूल चरण में तीन गुणन में n अंकों से कम वाले ऑपरेंड शामिल हैं। इसलिए, उन उत्पादों की गणना करत्सुबा एल्गोरिथम की पुनरावर्ती कॉल द्वारा की जा सकती है। पुनरावर्तन तब तक प्रायुक्त किया जा सकता है जब तक कि संख्याएं इतनी छोटी न हों कि उन्हें सीधे (या आवश्यक) गणना की जा सके।
-पूर्ण 32-बिट गुणा 32-बिट [[बाइनरी गुणक]] वाले कंप्यूटर में, उदाहरण के लिए, कोई B = 2 चुन सकता है<sup>31</sup> और प्रत्येक अंक को अलग 32-बिट बाइनरी शब्द के रूप में संग्रहीत करें। फिर योग x<sub>1</sub> + एक्स<sub>0</sub> और वाई<sub>1</sub> + और<sub>0</sub> कैरी-ओवर डिजिट ([[कैरी-सेव योजक]] के रूप में) को स्टोर करने के लिए अतिरिक्त बाइनरी शब्द की आवश्यकता नहीं होगी, और करत्सुबा रिकर्सन को तब तक लागू किया जा सकता है जब तक कि संख्याओं को गुणा करने के लिए केवल अंक लंबा न हो।
+पूर्ण 32-बिट गुणा 32-बिट [[बाइनरी गुणक]] वाले कंप्यूटर में, उदाहरण के लिए, कोई B = 2<sup>31</sup> चुन सकता है और प्रत्येक अंक को अलग 32-बिट बाइनरी शब्द के रूप में संग्रहीत करें। फिर योग x<sub>1</sub> + x<sub>0</sub> और y<sub>1</sub> + y<sub>0</sub> कैरी-ओवर डिजिट ([[कैरी-सेव योजक]] के रूप में) को स्टोर करने के लिए अतिरिक्त बाइनरी शब्द की आवश्यकता नहीं होगी, और करत्सुबा रिकर्सन को तब तक प्रायुक्त किया जा सकता है जब तक कि संख्याओं को गुणा करने के लिए केवल अंक लंबा न हो।
-=== [[समय जटिलता]] विश्लेषण ===
+=== समय सम्मिश्र विश्लेषण ===
-करात्सुबा का मूल चरण किसी भी आधार बी और किसी भी एम के लिए काम करता है, लेकिन पुनरावर्ती एल्गोरिथ्म सबसे अधिक कुशल होता है जब एम एन / 2 के बराबर होता है, गोल होता है। विशेष रूप से, यदि n 2 है<sup>k </sup>, कुछ पूर्णांक k के लिए, और पुनरावर्तन केवल तभी रुकता है जब n 1 हो, तो एकल-अंक गुणन की संख्या 3 है<sup>k</sup>, जो कि n है<sup>c</sup> जहाँ c = लॉग<sub>2</sub>3.
+करात्सुबा का मूल चरण किसी भी आधार b और किसी भी m के लिए काम करता है, लेकिन पुनरावर्ती कलनविधि सबसे अधिक कुशल होता है जब MN / 2 के बराबर होता है, और गोल होता है। विशेष रूप से, यदि n 2<sup>k</sup> है , कुछ पूर्णांक k के लिए, और पुनरावर्तन केवल तभी रुकता है जब n 1 हो, तो एकल-अंक गुणन की संख्या 3<sup>k</sup> है, जो कि n<sup>c</sup> है जहाँ c = log<sub>2</sub>3.
-चूंकि कोई भी इनपुट शून्य अंकों के साथ बढ़ा सकता है जब तक कि उनकी लंबाई दो की शक्ति न हो, यह निम्नानुसार है कि किसी भी एन के लिए प्राथमिक गुणन की संख्या अधिकतम है <math>3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}\,\!</math>.
+चूंकि कोई भी इनपुट शून्य अंकों के साथ बढ़ा सकता है जब तक कि उनकी लंबाई दो की घात न हो, यह निम्नानुसार है कि किसी भी एन के लिए प्राथमिक गुणन की संख्या अधिकतम है <math>3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}\,\!</math>.
-चूंकि करात्सुबा के बुनियादी कदम में जोड़, घटाव और अंकों की शिफ्ट (बी की शक्तियों से गुणा) n के अनुपात में समय लेती है, इसलिए n बढ़ने पर उनकी लागत नगण्य हो जाती है। अधिक सटीक रूप से, यदि टी (एन) प्राथमिक संचालन की कुल संख्या को दर्शाता है जो एल्गोरिदम दो एन-अंकीय संख्याओं को गुणा करते समय करता है, तो
+चूंकि करात्सुबा के मूलभूत चरण में जोड़, घटाव और अंकों की शिफ्ट (b की घातयों से गुणा) n के अनुपात में समय लेती है, इसलिए n बढ़ने पर उनकी लागत नगण्य हो जाती है। अधिक सटीक रूप से, यदि T (n) प्राथमिक संचालन की कुल संख्या को दर्शाता है जो एल्गोरिदम दो एन-अंकीय संख्याओं को गुणा करते समय करता है, तो
 :<math>T(n) = 3 T(\lceil n/2\rceil) + cn + d</math>
-कुछ स्थिरांक c और d के लिए। इस पुनरावर्तन संबंध के लिए, [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] | डिवाइड-एंड-कॉनकर [[पुनरावृत्ति संबंध]] लिए मास्टर प्रमेय [[बिग ओ नोटेशन]] बाउंड देता है <math>T(n) = \Theta(n^{\log_2 3})\,\!</math>.
+कुछ स्थिरांक c और d के लिए। इस पुनरावर्तन संबंध के लिए, [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] [[पुनरावृत्ति संबंध]] लिए मास्टर प्रमेय [[बिग ओ नोटेशन]] सीमा देता है
+<math>T(n) = \Theta(n^{\log_2 3})\,\!</math>.
+यह इस प्रकार है कि, पर्याप्त रूप से बड़े n के लिए, करत्सुबा का कलनविधि लांगहैंड गुणन की तुलना में कम बदलाव और एकल-अंक जोड़ देगा, भले ही इसका मूल चरण सीधे सूत्र की तुलना में अधिक जोड़ और बदलाव का उपयोग करता है। n के छोटे मूल्यों के लिए, हालांकि, अतिरिक्त शिफ्ट और ऐड ऑपरेशंस इसे लांगहैंड विधि से धीमा कर सकते हैं। सकारात्मक रिटर्न का बिंदु [[कंप्यूटर मंच]] और संदर्भ पर निर्भर करता है। थंब के नियम के रूप में, करात्सुबा की विधि सामान्यतः तेज़ होती है जब गुणक 320-640 बिट्स से अधिक होते हैं।<ref>{{Cite web|url=http://www.cburch.com/proj/karat/comment1.html|title=Karatsuba multiplication|website=www.cburch.com}}</ref>
-यह इस प्रकार है कि, पर्याप्त रूप से बड़े n के लिए, करत्सुबा का एल्गोरिथ्म लांगहैंड गुणन की तुलना में कम बदलाव और एकल-अंक जोड़ देगा, भले ही इसका मूल चरण सीधे सूत्र की तुलना में अधिक जोड़ और बदलाव का उपयोग करता है। एन के छोटे मूल्यों के लिए, हालांकि, अतिरिक्त शिफ्ट और ऐड ऑपरेशंस इसे लांगहैंड विधि से धीमा कर सकते हैं। सकारात्मक रिटर्न का बिंदु [[कंप्यूटर मंच]] और संदर्भ पर निर्भर करता है। अंगूठे के नियम के रूप में, करात्सुबा की विधि आमतौर पर तेज़ होती है जब गुणक 320-640 बिट्स से अधिक होते हैं।<ref>{{Cite web|url=http://www.cburch.com/proj/karat/comment1.html|title=Karatsuba multiplication|website=www.cburch.com}}</ref>
@@ Line 107: / Line 111: @@
 यहाँ इस एल्गोरिथम के लिए स्यूडोकोड है, आधार दस में प्रदर्शित संख्याओं का उपयोग करते हुए। पूर्णांकों के द्विआधारी प्रतिनिधित्व के लिए, यह हर जगह 10 को 2 से बदलने के लिए पर्याप्त है।<ref>{{cite book |last= Weiss |first= Mark A. |date= 2005 |title= Data Structures and Algorithm Analysis in C++ |publisher= Addison-Wesley|page= 480|isbn= 0321375319}}</ref>
-split_at फ़ंक्शन का दूसरा तर्क दाईं ओर से निकाले जाने वाले अंकों की संख्या निर्दिष्ट करता है: उदाहरण के लिए, split_at( 12345 , 3) 3 अंतिम अंक निकालेगा, जो देगा: high= 12 , low= 345 ।
-<वाक्यविन्यास प्रकाश लैंग = सी>
+विभाजन पर फलन का दूसरा तर्क दाईं ओर से निकाले जाने वाले अंकों की संख्या निर्दिष्ट करता है: उदाहरण के लिए, विभाजन_पर( 12345 , 3) 3 अंतिम अंक, जो देगा: उच्च= 12 , निम्न= 345 निकालेगा।<syntaxhighlight lang="d">
-समारोह करात्सुबा (संख्या 1, संख्या 2)
+function karatsuba(num1, num2)
-     अगर (संख्या 1 <10 या संख्या 2 <10)
+     if (num1 < 10 or num2 < 10)
-         वापसी num1 × num2 /* पारंपरिक गुणन पर वापस जाएँ */
+         return num1 × num2 /* fall back to traditional multiplication */
-     / * संख्याओं के आकार की गणना करता है। */
+     /* Calculates the size of the numbers. */
-     एम = अधिकतम (आकार_बेस 10 (संख्या 1), आकार_बेस 10 (संख्या 2))
+     m = max(size_base10(num1), size_base10(num2))
-     एम 2 = मंजिल (एम / 2)
+     m2 = floor(m / 2)
-     /* एम2 = छत (एम/2) भी काम करेगा */
+     /* m2 = ceil (m / 2) will also work */
-     /* अंकों के क्रम को बीच में विभाजित करें। */
+     /* Split the digit sequences in the middle. */
-     हाई1, लो1 = स्प्लिट_एट (संख्या1, एम2)
+     high1, low1 = split_at(num1, m2)
-     हाई2, लो2 = स्प्लिट_एट (संख्या2, एम2)
+     high2, low2 = split_at(num2, m2)
-     /* 3 पुनरावर्ती कॉल लगभग आधे आकार के नंबरों पर किए गए। */
+     /* 3 recursive calls made to numbers approximately half the size. */
-     z0 = करात्सुबा (low1, low2)
+     z0 = karatsuba(low1, low2)
-     z1 = करात्सुबा (low1 + high1, low2 + high2)
+     z1 = karatsuba(low1 + high1, low2 + high2)
-     z2 = करात्सुबा (हाई1, हाई2)
+     z2 = karatsuba(high1, high2)
-     वापसी (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0
+     return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0
-</वाक्यविन्यास हाइलाइट>
+</syntaxhighlight>समस्या जो तब होती है जब कार्यान्वयन यह है कि उपरोक्त गणना <math>(x_1 + x_0)</math> और <math>(y_1 + y_0)</math> के लिए <math>z_1</math> परिणाम अतिप्रवाह हो सकता है (परिणाम श्रेणी में उत्पन्न करेगा <math>B^m \leq \text{result} < 2 B^m</math>), जिसके लिए अतिरिक्त बिट वाले गुणक की आवश्यकता होती है। इसका ध्यान रखकर इससे बचा जा सकता है
-समस्या जो तब होती है जब कार्यान्वयन यह है कि उपरोक्त गणना <math>(x_1 + x_0)</math> और <math>(y_1 + y_0)</math> के लिए <math>z_1</math> परिणाम अतिप्रवाह हो सकता है (परिणाम श्रेणी में उत्पन्न करेगा <math>B^m \leq \text{result} < 2 B^m</math>), जिसके लिए अतिरिक्त बिट वाले गुणक की आवश्यकता होती है। इसका ध्यान रखकर इससे बचा जा सकता है
 :<math>z_1 = (x_0 - x_1)(y_1 - y_0) + z_2 + z_0.</math>
-यह गणना <math>(x_0 - x_1)</math> और <math>(y_1 - y_0)</math> की सीमा में परिणाम देगा <math>-B^m < \text{result} < B^m</math>. यह विधि ऋणात्मक संख्याओं का उत्पादन कर सकती है, जिसके लिए अतिरिक्त बिट की आवश्यकता होती है, और फिर भी गुणक के लिए अतिरिक्त बिट की आवश्यकता होगी। हालाँकि, इससे बचने का तरीका यह है कि चिन्ह को रिकॉर्ड किया जाए और फिर के निरपेक्ष मान का उपयोग किया जाए <math>(x_0 - x_1)</math> और <math>(y_1 - y_0)</math> अहस्ताक्षरित गुणन करने के लिए, जिसके बाद दोनों संकेतों के मूल रूप से भिन्न होने पर परिणाम को नकारा जा सकता है। और फायदा यह है कि भले ही <math>(x_0 - x_1)(y_1 - y_0)</math> नकारात्मक हो सकता है, की अंतिम गणना <math>z_1</math> केवल जोड़ शामिल है।
+यह गणना <math>(x_0 - x_1)</math> और <math>(y_1 - y_0)</math> की सीमा <math>-B^m < \text{result} < B^m</math> में परिणाम देगा. यह विधि ऋणात्मक संख्याओं का उत्पादन कर सकती है, जिसके लिए अतिरिक्त बिट की आवश्यकता होती है, और फिर भी गुणक के लिए अतिरिक्त बिट की आवश्यकता होगी। हालाँकि, इससे बचने का तरीका यह है कि चिन्ह को रिकॉर्ड किया जाए और फिर के निरपेक्ष मान <math>(x_0 - x_1)</math> और <math>(y_1 - y_0)</math> अहस्ताक्षरित गुणन करने के लिए का उपयोग किया जाए, जिसके बाद दोनों संकेतों के मूल रूप से भिन्न होने पर परिणाम को नकारा जा सकता है। और लाभ यह है कि चाहे <math>(x_0 - x_1)(y_1 - y_0)</math> ऋणात्मक हो सकता है, की अंतिम गणना <math>z_1</math> केवल जोड़ शामिल है।
 ==संदर्भ==
@@ Line 145: / Line 146: @@
 * Bernstein, D. J., "[http://cr.yp.to/papers/m3.pdf Multidigit multiplication for mathematicians]". Covers Karatsuba and many other multiplication algorithms.
-{{Number-theoretic algorithms}}
+[[Category:CS1 maint]]
-[[Category: कंप्यूटर अंकगणितीय एल्गोरिदम]] [[Category: गुणा]] [[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: फूट डालो और जीतो एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 13/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कंप्यूटर अंकगणितीय एल्गोरिदम]]
+[[Category:गुणा]]
+[[Category:फूट डालो और जीतो एल्गोरिदम]]
+[[Category:स्यूडोकोड के उदाहरण वाले लेख]]

Anonymous

Search

करत्सुबा एल्गोरिथम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 13:04, 13 September 2023

Contents

इतिहास