गुणन एल्गोरिथ्म

गुणा कलन विधि दो संख्याओं को गुणा करने के लिए एक विधि है। संख्याओं के आकार के आधार पर, अलग-अलग कलनविधिया दूसरों की तुलना में अधिक कुशल हों सकते हैं। दशमलव प्रणाली के आगमन के उपरांत अत्यंत कुशल गुणा कलनविधिया उपलब्ध हैं।

दीर्घ गुणन

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

आधार 10 में हाथ से बड़ी संख्याओं को गुणा करने के लिए यह सामान्य कलनविधि है। कागज पर दीर्घ गुणा करने वाला व्यक्ति सभी गुणनफलों को लिखेगा और फिर उन्हें एक साथ जोड़ देगा; एबेकस-उपयोगकर्ता किसी की गणना होते ही गुणनो का योग कर देगा।

उदाहरण

यह उदाहरण 23,958,233 को 5,830 से गुणा करने के लिए लंबे गुणन का उपयोग करता है और परिणाम के लिए 139,676,498,390 पर पहुंचता है।

      23958233
× 5830
————————————————
      00000000 (= 23,958,233 × 0)
     71874699 (= 23,958,233 × 30)
   191665864 (= 23,958,233 × 800)
+ 119791165 (= 23,958,233 × 5,000)
————————————————
  139676498390 (= 139,676,498,390)

अन्य संकेतन

जर्मनी जैसे कुछ देशों में, उपरोक्त गुणन को समान रूप से दर्शाया गया है, लेकिन मूल गुणनो को क्षैतिज रूप मे रखा गया है और गणना, गुणक के पहले अंक से शुरू होती है:

23958233 * 5830

————————————————
   119791165
    191665864
      71874699
       00000000
————————————————
   139676498390

नीचे दिया गया छद्म कूट उपरोक्त गुणन की प्रक्रिया का वर्णन करता है। योग बनाए रखने के लिए यह केवल पंक्ति रखता है जो अंत में परिणाम बन जाता है। ध्यान दें कि '+ =' संकार्य का उपयोग संहतता के लिए उपस्थित मूल्य और स्टोर संक्रिया के योग को दर्शाने के लिए किया जाता है।

 multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1

  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product

कंप्यूटर में उपयोग

कुछ एकीकृत परिपथ विभिन्न पूर्णांक और चर बिन्दु परिकलन आकारों के लिए कंप्यूटर हार्डवेयर या माइक्रोकोड में लंबे गुणन को लागू करते हैं। यादृच्छिक-परिशुद्धता अंकगणित में, आधार सेट 2^w के साथ लंबे गुणन का उपयोग करना साधारण है जहाँ w अपेक्षाकृत छोटी संख्याओं को गुणा करने के लिए शब्द में बिट्स की संख्या है। इस पद्धति का उपयोग करके दो संख्याओं को n अंकों से गुणा करने के लिए, लगभग n² संचालन की आवश्यकता होती है। औपचारिक रूप से, लंबे गुणन का उपयोग करके दो एन-अंकीय संख्याओं को गुणा करने के लिए बछमन-लैंडौ संकेतन Θ(n²) की आवश्यकता होती है।

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

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

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

((x << 2) + x) << 1 # यहां 10*x की गणना (x*2^2 + x)*2 के रूप में की जाती है
(x << 3) + (x << 1) # यहाँ 10*x की गणना x*2^3 + x*2 के रूप में की जाती है

कुछ संदर्भों में बदलाव और जोड़ या घटाव के ऐसे क्रम हार्डवेयर गुणकों और विशेष रूप से भाजक से उन्नत प्रदर्शन करेंगे। एक संख्या के रूप में विभाजक $2^{n}$ या $2^{n}\pm 1$ को प्रायः इतने छोटे अनुक्रम में परिवर्तित किया जा सकता है।

हाथ से गुणा करने के लिए कलनविधि

मानक दीर्घ गुणन के अलावा, हाथ से गुणन करने के लिए कई अन्य विधियों का उपयोग किया जाता है। इस तरह के कलनविधि गति, गणना में आसानी, या शैक्षिक मूल्य के लिए तैयार किए जा सकते हैं, विशेषतः जब कंप्यूटर या गुणन सारणी अनुपलब्ध हों।

ग्रिड विधि

Main article: Grid method multiplication

ग्रिड विधि गुणन (या बॉक्स विधि) बहु-अंकीय गुणन के लिए एक परिचयात्मक विधि है जिसे प्रायः प्राथमिक विद्यालय या प्राथमिक विद्यालय में विद्यार्थियों को पढ़ाया जाता है। यह 1990 के दशक के अंत से इंग्लैंड और वेल्स में राष्ट्रीय प्राथमिक विद्यालय के गणित पाठ्यक्रम का एक मानक हिस्सा रहा है। दोनों कारकों को उनके सैकड़ों, दसियों और इकाई भागों में विभाजित (विभाजित) किया जाता है, और भागों के उत्पादों की गणना अपेक्षाकृत सरल गुणा-मात्र चरण में स्पष्ट रूप से की जाती है, इससे पहले कि इन योगदानों को एक अलग में अंतिम उत्तर देने के लिए जोड़ा जाता है अतिरिक्त चरण।

गणना 34 × 13, उदाहरण के लिए, ग्रिड का उपयोग करके गणना की जा सकती है: <डिव स्टाइल = फ्लोट: राइट> <पूर्व> 300

  40
  90
+ 12
————

442

×	30	4
10	300	40
3	90	12

इसके बाद 442 प्राप्त करने के लिए जोड़, या तो एक योग में (दाएं देखें), या पंक्ति-दर-पंक्ति योग बनाकर (300 + 40) + (90 + 12) = 340 + 102 = 442।

यह गणना दृष्टिकोण (हालांकि जरूरी नहीं कि स्पष्ट ग्रिड व्यवस्था के साथ) को आंशिक उत्पाद कलनविधि के रूप में भी जाना जाता है। इसका सार सरल गुणन की अलग से गणना करना है, जिसमें सभी जोड़ को अंतिम इकट्ठा करने के चरण में छोड़ दिया जाता है।

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

जाली गुणन

Main article: Lattice multiplication

File:Hindu lattice.svg

सबसे पहले, गुणा की जाने वाली संख्याओं के साथ इसकी पंक्तियों और स्तंभों को चिह्नित करके ग्रिड को सेट करें। फिर, ऊपर के त्रिकोणों में दहाई अंकों और तल पर इकाइयों के अंकों वाले बक्सों को भरें।

File:Hindu lattice 2.svg

अंत में, विकर्ण पथों के साथ योग करें और उत्तर प्राप्त करने के लिए आवश्यकतानुसार आगे बढ़ें

जाली, या छलनी, गुणन एल्गोरिथम रूप से लंबे गुणन के बराबर है। इसके लिए एक जाली (कागज पर खींची गई एक ग्रिड) तैयार करने की आवश्यकता होती है जो गणना को निर्देशित करती है और सभी गुणाओं को जोड़ से अलग करती है। इसे यूरोप में 1202 में फिबोनाची के अबेकस की किताब में पेश किया गया था। फाइबोनैचि ने ऑपरेशन को मानसिक बताया, मध्यवर्ती गणना करने के लिए अपने दाएं और बाएं हाथों का उपयोग किया। मातृककी नासुह ने 16वीं सदी की इस किताब, उम्दत-उल हिसाब में इस पद्धति के 6 अलग-अलग रूपों को प्रस्तुत किया। यह ओटोमन साम्राज्य के एंडरुन स्कूलों में व्यापक रूप से इस्तेमाल किया गया था। नेपियर की हड्डियों, या नेपियर की छड़ों ने भी इस पद्धति का उपयोग किया, जैसा कि उनकी मृत्यु के वर्ष 1617 में नेपियर द्वारा प्रकाशित किया गया था।

जैसा कि उदाहरण में दिखाया गया है, गुण्य और गुणक ऊपर और जाली या छलनी के दाईं ओर लिखे गए हैं। यह मुहम्मद इब्न मूसा अल-ख्वारिज्मी के अंकगणित में पाया जाता है, जो लियोनार्डो के स्रोतों में से एक है, जिसका उल्लेख सिगलर ने किया है, जो फिबोनाची के लिबर अबाची, 2002 के लेखक हैं।

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

उदाहरण

दाईं ओर के चित्र दिखाते हैं कि जाली गुणन का उपयोग करके 345 × 12 की गणना कैसे करें। अधिक जटिल उदाहरण के रूप में, नीचे दी गई तस्वीर पर विचार करें जो 23,958,233 की गणना को 5,830 (गुणक) से गुणा करती है; परिणाम 139,676,498,390 है। सूचना 23,958,233 जाली के शीर्ष के साथ है और 5,830 दाईं ओर है। उत्पाद जाली को भरते हैं और उन उत्पादों का योग (विकर्ण पर) बाईं ओर और नीचे की ओर होते हैं। फिर उन योगों को दिखाया गया है जैसा कि दिखाया गया है।

2 3 9 5 8 2 3 3 +---+---+---+---+---+---+---+---+- |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /| | / | / | / | / | / | / | / | / | 5 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5| +---+---+---+---+---+---+---+---+- |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /| | / | / | / | / | / | / | / | / | 8 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4| +---+---+---+---+---+---+---+---+- |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 3 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9| +---+---+---+---+---+---+---+---+- |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 0 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0| +---+---+---+---+---+---+---+---+- 26 15 13 18 17 13 09 00

01 002 0017 00024 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390

= 139,676,498,390

रूसी किसान गुणन

Main article: Peasant multiplication

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

विवरण

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

उदाहरण

यह उदाहरण 33 के परिणाम पर पहुंचने के लिए 11 को 3 से गुणा करने के लिए किसान गुणन का उपयोग करता है।

दशमलव: बाइनरी:
11 3 1011 11
5 6 101 110
2 12 10 1100
1 24 1 11000
    —— ——————
    33 100001

स्पष्ट रूप से चरणों का वर्णन:

• सबसे ऊपर 11 और 3 लिखे होते हैं
• 11 को आधा (5.5) और 3 को दोगुना (6) किया गया है। भिन्नात्मक भाग को छोड़ दिया जाता है (5.5 5 हो जाता है)।
• 5 को आधा (2.5) और 6 को दोगुना (12) किया जाता है। भिन्नात्मक भाग को छोड़ दिया जाता है (2.5 2 हो जाता है)। बाएँ स्तंभ (2) का अंक सम है, इसलिए दाएँ स्तंभ (12) का अंक हटा दिया गया है।
• 2 को आधा (1) और 12 को दोगुना (24) किया जाता है।
• सभी गैर-स्क्रैच-आउट मानों का योग किया जाता है: 3 + 6 + 24 = 33।

विधि काम करती है क्योंकि गुणन वितरण है, इसलिए:

${\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^{3})\\&=3\times (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}$

पहले के उदाहरणों (23,958,233 और 5,830) के आंकड़ों का उपयोग करते हुए एक अधिक जटिल उदाहरण:

दशमलव: बाइनरी:
5830 23958233 1011011000110 1011011011001001011011001
2915 47916466 101101100011 10110110110010010110110010
1457 95832932 10110110001 101101101100100101101100100
728 191665864 1011011000 1011011011001001011011001000
364 383331728 101101100 10110110110010010110110010000
182 766663456 10110110 101101101100100101101100100000
91 1533326912 1011011 1011011011001001011011001000000
45 3066653824 101101 10110110110010010110110010000000
22 6133307648 10110 101101101100100101101100100000000
11 12266615296 1011 1011011011001001011011001000000000
5 24533230592 101 10110110110010010110110010000000000
2 49066461184 10 101101101100100101101100100000000000
1 98132922368 1 <यू>1011011011001001011011001000000000000</यू>
  ————————————— 1022143253354344244353353243222210110 (ले जाने से पहले)
  139676498390 10000010000101010111100011100111010110

चौथाई वर्ग गुणन

दो मात्राओं को चौथाई वर्गों का उपयोग करके गुणा किया जा सकता है, जिसमें कुछ स्रोतों के तल और छत के कार्यों को शामिल करते हुए निम्नलिखित पहचान को नियोजित किया गया है बेबीलोनियन गणित (2000-1600 ईसा पूर्व) की विशेषता।

$\left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(x-y\right)^{2}}{4}}\right\rfloor ={\frac {1}{4}}\left(\left(x^{2}+2xy+y^{2}\right)-\left(x^{2}-2xy+y^{2}\right)\right)={\frac {1}{4}}\left(4xy\right)=xy.$

अगर एक x+y या x−y विषम है, दूसरा भी विषम है, इस प्रकार उनके वर्ग 1 मॉड 4 हैं, फिर मंजिल लेने से दोनों एक चौथाई कम हो जाते हैं; घटाव तब क्वार्टर को रद्द कर देता है, और अवशेषों को हटाने से फर्श कार्यों के बिना समान अभिव्यक्ति की तुलना में कोई अंतर नहीं आता है। नीचे चौथाई वर्गों की एक लुकअप तालिका है जिसमें शेष 0 से 18 अंकों के लिए हटा दिया गया है; यह संख्याओं के गुणा के लिए अनुमति देता है 9×9.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
⌊n2/4⌋	0	0	1	2	4	6	9	12	16	20	25	30	36	42	49	56	64	72	81

यदि, उदाहरण के लिए, आप 9 को 3 से गुणा करना चाहते हैं, तो आप देखते हैं कि योग और अंतर क्रमशः 12 और 6 हैं। तालिका में उन दोनों मानों को देखने पर 36 और 9 प्राप्त होते हैं, जिनका अंतर 27 है, जो 9 और 3 का गुणनफल है।

एंटोनी वोइसिन ने गुणन में सहायता के रूप में 1817 में 1 से 1000 तक चौथाई वर्गों की तालिका प्रकाशित की। 1856 में सैमुअल लॉन्डी द्वारा 1 से 100000 तक चौथाई वर्गों की एक बड़ी तालिका प्रकाशित की गई थी। और 1888 में जोसेफ ब्लैटर द्वारा 1 से 200000 तक की तालिका। एनालॉग कंप्यूटर में क्वार्टर स्क्वायर मल्टीप्लायर का उपयोग एनालॉग संकेत बनाने के लिए किया गया था जो दो एनालॉग इनपुट सिग्नल का उत्पाद था। इस एप्लिकेशन में, ऑपरेशनल एंप्लीफायर का उपयोग करके दो इनपुट वोल्टेज का योग और अंतर बनता है। इनमें से प्रत्येक का वर्ग टुकड़ावार रैखिक फ़ंक्शन परिपथ का उपयोग करके अनुमानित है। अंत में दो वर्गों का अंतर बनता है और एक चौथाई के कारक द्वारा एक और परिचालन प्रवर्धक का उपयोग करके बढ़ाया जाता है।

1980 में, एवरेट एल। जॉनसन ने डिजिटल डेटा गुणक में क्वार्टर स्क्वायर विधि का उपयोग करने का प्रस्ताव दिया। दो 8-बिट पूर्णांकों का गुणनफल बनाने के लिए, उदाहरण के लिए, डिजिटल उपकरण योग और अंतर बनाता है, वर्गों की तालिका में दोनों मात्राओं को देखता है, परिणामों के अंतर को लेता है, और दो बिट्स को एक में स्थानांतरित करके चार से विभाजित करता है। सही। 8-बिट पूर्णांकों के लिए चौथाई वर्गों की तालिका में 2 होंगे⁹−1=511 प्रविष्टियां (संभावित राशियों की पूर्ण श्रेणी 0..510 के लिए एक प्रविष्टि, श्रेणी 0..255 में केवल पहली 256 प्रविष्टियों का उपयोग करने वाले अंतर) या 2⁹−1=511 प्रविष्टियां (नकारात्मक अंतरों के लिए 2-पूरकों और 9-बिट मास्किंग की तकनीक का उपयोग करते हुए, जो मतभेदों के संकेत का परीक्षण करने से बचती हैं), प्रत्येक प्रविष्टि 16-बिट चौड़ी है (प्रविष्टि मान निम्न से हैं) 0²/4)=0 से (510²/4)=65025)।

चौथाई वर्ग गुणक तकनीक ने 8-बिट सिस्टमों को लाभान्वित किया है जिनके पास हार्डवेयर गुणक के लिए कोई समर्थन नहीं है। चार्ल्स पुटनी ने एमओएस टेक्नोलॉजी 6502 के लिए इसे लागू किया।

गुणन की कम्प्यूटेशनल जटिलता

Unsolved problem in computer science:

What is the fastest algorithm for multiplication of two $n$-digit numbers?

(more unsolved problems in computer science)

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

वर्तमान में, सर्वश्रेष्ठ कम्प्यूटेशनल जटिलता वाला कलनविधि डेविड हार्वे (गणितज्ञ) और जॉर्ज वैन डेर होवेन का 2019 कलनविधि है, जो शॉनहेज-स्ट्रैसन कलनविधि के साथ पेश किए गए संख्या-सैद्धांतिक परिवर्तनों का उपयोग करने की रणनीतियों का उपयोग करके केवल पूर्णांक का उपयोग करके पूर्णांक गुणा करता है। $O(n\log n)$ संचालन। यह सबसे अच्छा संभव एल्गोरिथम होने का अनुमान लगाया गया है, लेकिन इसकी सीमा कम है $\Omega (n\log n)$ ज्ञात नहीं हैं।

करत्सुबा गुणन

Main article: Karatsuba algorithm

उन प्रणालियों के लिए जिन्हें कई हज़ार अंकों की सीमा में संख्याओं को गुणा करने की आवश्यकता होती है, जैसे कि कंप्यूटर बीजगणित प्रणाली और bignum पुस्तकालय, लंबा गुणन बहुत धीमा है। ये प्रणालियाँ करात्सुबा गुणन को नियोजित कर सकती हैं, जिसे 1960 में खोजा गया था (1962 में प्रकाशित)। अनातोली करत्सुबा की विधि का दिल इस अवलोकन में निहित है कि शास्त्रीय रूप से आवश्यक चार गुणाओं के बजाय दो अंकों का गुणा केवल तीन के साथ किया जा सकता है। यह एक उदाहरण है जिसे अब 'फूट डालो और जीतो एल्गोरिथम' कहा जाता है। मान लीजिए हम दो 2-अंकीय आधार-m संख्याओं को गुणा करना चाहते हैं: x₁एम + एक्स₂ और वाई₁एम + वाई₂:

1. एक्स की गणना करें₁ · और₁, परिणाम F पर कॉल करें
2. एक्स की गणना करें₂ · और₂, परिणाम जी को कॉल करें
3. गणना (एक्स₁ + एक्स₂) · (और₁ + और₂), परिणाम एच कॉल करें
4. गणना एच - एफ - जी, परिणाम के कॉल करें; यह संख्या x के बराबर है₁ · और₂ + एक्स₂ · और₁
5. गणना एफ · एम² + क · म + जी।

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

करात्सुबा गुणा में बिग ओ नोटेशन की समय जटिलता है (एन^{लकड़ी का लट्ठा₂3}) ≈ ओ (एन^1.585), इस विधि को लंबे गुणन की तुलना में काफी तेज़ बनाता है। पुनरावर्तन के ऊपरी भाग के कारण, करात्सुबा का गुणन n के छोटे मानों के लिए दीर्घ गुणन की तुलना में धीमा है; विशिष्ट कार्यान्वयन इसलिए n के छोटे मूल्यों के लिए लंबे गुणन पर स्विच करते हैं।

करात्सुबा का कलनविधि गुणन के लिए पहला ज्ञात एल्गोरिथम था जो लंबे गुणन की तुलना में विषम रूप से तेज़ है, और इस प्रकार तेजी से गुणन के सिद्धांत के लिए शुरुआती बिंदु के रूप में देखा जा सकता है।

टूम-कुक

Main article: Toom–Cook multiplication

गुणन की एक अन्य विधि को टूम-कुक या टूम-3 कहा जाता है। टूम-कुक विधि प्रत्येक संख्या को कई भागों में गुणा करने के लिए विभाजित करती है। टूम-कुक विधि करात्सुबा पद्धति के सामान्यीकरणों में से एक है। एक तीन-तरफा टूम-कुक पांच आकार-एन गुणन की लागत के लिए आकार-3N गुणन कर सकता है। यह ऑपरेशन को 9/5 के कारक से तेज करता है, जबकि करात्सुबा विधि इसे 4/3 से तेज करती है।

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

शॉनहेज–स्ट्रैसन

Main article: Schönhage–Strassen algorithm

File:Integer multiplication by FFT.svg

तेजी से फूरियर ट्रांसफॉर्म (एफएफटी) का उपयोग करके 1234 × 5678 = 7006652 गुणा करने का प्रदर्शन। पूर्णांक मॉड्यूलो 337 में संख्या-सैद्धांतिक परिवर्तन का उपयोग किया जाता है, 85 को एकता की 8 वीं जड़ के रूप में चुना जाता है। बेस 2 के स्थान पर बेस 10 का उपयोग किया जाता है^w व्याख्यात्मक उद्देश्यों के लिए।

वोल्कर स्ट्रास (1968) के कारण मूल विचार तेजी से पूर्णांक गुणन करने के लिए तेजी से बहुपद गुणन का उपयोग करना है। एल्गोरिथम को व्यावहारिक बनाया गया था और 1971 में अर्नोल्ड शॉनहेज|शॉनहेज और स्ट्रैसन द्वारा सैद्धांतिक गारंटी प्रदान की गई थी, जिसके परिणामस्वरूप शॉनहेज-स्ट्रैसन एल्गोरिथम हुआ। विवरण निम्नलिखित हैं: हम सबसे बड़ा पूर्णांक डब्ल्यू चुनते हैं जो नीचे उल्लिखित प्रक्रिया के दौरान पूर्णांक अतिप्रवाह का कारण नहीं बनेगा। फिर हम दो नंबरों को डब्ल्यू बिट्स के एम समूहों में निम्नानुसार विभाजित करते हैं

$a=\sum _{i=0}^{m-1}{a_{i}2^{wi}}{\text{ and }}b=\sum _{j=0}^{m-1}{b_{j}2^{wj}}.$

हम इन संख्याओं को x में बहुपद के रूप में देखते हैं, जहाँ x = 2^w, पाने के लिए,

$a=\sum _{i=0}^{m-1}{a_{i}x^{i}}{\text{ and }}b=\sum _{j=0}^{m-1}{b_{j}x^{j}}.$

तब हम कह सकते हैं कि,

$ab=\sum _{i=0}^{m-1}\sum _{j=0}^{m-1}a_{i}b_{j}x^{(i+j)}=\sum _{k=0}^{2m-2}c_{k}x^{k}.$

स्पष्ट रूप से उपरोक्त सेटिंग दो बहुपद a और b के बहुपद गुणन द्वारा महसूस की जाती है। महत्वपूर्ण कदम अब असतत फूरियर रूपांतरण # बहुपदों के बहुपद गुणन का उपयोग करना है ताकि ऊपर के गुणन को भोले ओ (एम) की तुलना में तेजी से महसूस किया जा सके²) समय।

फूरियर रूपांतरण की मॉड्यूलर सेटिंग में बने रहने के लिए, हम एकता के (2m) वें रूट के साथ एक रिंग की तलाश करते हैं। इसलिए हम गुणन मोडुलो N करते हैं (और इस प्रकार Z/NZ रिंग (गणित) में)। इसके अलावा, एन को चुना जाना चाहिए ताकि कोई 'चारों ओर लपेट' न हो, अनिवार्य रूप से, मॉड्यूलो एन घटित न हो। इस प्रकार, N का चुनाव महत्वपूर्ण है। उदाहरण के लिए, यह के रूप में किया जा सकता है,

$N=2^{3m}+1.$

इस प्रकार वलय Z/NZ में एकता का (2m) वाँ मूल अर्थात् 8 होगा। साथ ही, यह भी जाँचा जा सकता है कि c_k<एन, और इस प्रकार कोई रैप अराउंड नहीं होगा।

एल्गोरिथम में बैचमैन-लैंडौ नोटेशन|Θ(n log(n) log(log(n))) की समय जटिलता है और 10,000 से 40,000 दशमलव अंकों से अधिक संख्या के लिए अभ्यास में उपयोग किया जाता है।

आगे के सुधार

2007 में पेन्सिलवेनिया स्टेट यूनिवर्सिटी के स्विस गणितज्ञ मार्टिन फ्यूरर ने पूर्णांक गुणन की स्पर्शोन्मुख जटिलता को n log(n) 2 में सुधारा था^{Θ(पुनरावृत्त लघुगणक|log*(n))} फूरियर का उपयोग सम्मिश्र संख्याओं पर रूपांतरण करता है। Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi gave a similar algorithm using modular arithmetic in 2008 achieving the same running time. रेफरी>De, A.; Saha, C.; Kurur, P.; Saptharishi, R. (2008). "Fast integer multiplication using modular arithmetic". कम्प्यूटिंग के सिद्धांत (एसटीओसी) पर 40वें वार्षिक एसीएम संगोष्ठी की कार्यवाही. pp. 499–506. arXiv:0801.1416. doi:10.1145/1374376.1374447. ISBN 978-1-60558-047-0. S2CID 3264828.</ रेफ> उपरोक्त सामग्री के संदर्भ में, इन बाद के लेखकों ने जो हासिल किया है वह एन को 2 से बहुत कम खोजना है^3k + 1, ताकि Z/NZ में एकता का (2m)वां मूल हो। यह गणना को गति देता है और समय की जटिलता को कम करता है। हालांकि, ये बाद वाले कलनविधि केवल अव्यावहारिक रूप से बड़े इनपुट के लिए शॉनहेज-स्ट्रैसन से तेज़ हैं।

2015 में, हार्वे, जोरिस वैन डेर होवेन और लेसेर्फ़ एक नया एल्गोरिथम दिया जो एक रनिंग टाइम प्राप्त करता है $O(n\log n\cdot 2^{3\log ^{*}n})$, में निहित स्थिरांक को स्पष्ट करता है $O(\log ^{*}n)$ प्रतिपादक। उन्होंने अपने कलनविधि का एक संस्करण भी प्रस्तावित किया जो प्राप्त करता है $O(n\log n\cdot 2^{2\log ^{*}n})$ लेकिन जिसकी वैधता Mersenne primes के वितरण के बारे में मानक अनुमानों पर निर्भर करती है। 2016 में, Covanov और Thomé ने Fermat primes के सामान्यीकरण के आधार पर एक पूर्णांक गुणन एल्गोरिथम प्रस्तावित किया, जो अनुमानित रूप से एक जटिलता को प्राप्त करता है $O(n\log n\cdot 2^{2\log ^{*}n})$. यह हार्वे, वैन डेर होवेन और लेसेर्फ़ के 2015 के सशर्त परिणाम से मेल खाता है लेकिन एक अलग कलनविधि का उपयोग करता है और एक अलग अनुमान पर निर्भर करता है। 2018 में, हार्वे और वैन डेर होवेन ने मिंकोव्स्की के प्रमेय द्वारा गारंटीकृत लघु जाली वैक्टर के अस्तित्व के आधार पर एक बिना शर्त जटिलता को साबित करने के लिए एक दृष्टिकोण का उपयोग किया $O(n\log n\cdot 2^{2\log ^{*}n})$. मार्च 2019 में, डेविड हार्वे (गणितज्ञ) और जोरिस वैन डेर होवेन ने एक की अपनी खोज की घोषणा की O(n log n) गुणन कलनविधि। यह 2021 में गणित के इतिहास में प्रकाशित हुआ था। क्योंकि शॉनहेज और स्ट्रासेन ने भविष्यवाणी की थी कि n log(n) 'सर्वश्रेष्ठ संभव' परिणाम है, हार्वी ने कहा: "...इस समस्या के लिए हमारा काम सड़क का अंत होने की उम्मीद है, हालांकि हम अभी तक नहीं जानते कि कैसे साबित किया जाए यह सख्ती से। असतत फूरियर रूपांतरण के बजाय संख्या-सैद्धांतिक रूपांतरणों का उपयोग फ़्लोटिंग-पॉइंट अंकगणित के बजाय मॉड्यूलर अंकगणितीय का उपयोग करके गोल त्रुटि समस्याओं से बचा जाता है। फैक्टरिंग को लागू करने के लिए जो एफएफटी को काम करने में सक्षम बनाता है, परिवर्तन की लंबाई छोटे अभाज्यों के लिए कारक होनी चाहिए और इसका एक कारक होना चाहिए N − 1, जहाँ N क्षेत्र का आकार है। विशेष रूप से, गैलोज फील्ड GF(k²), जहां k एक Mersenne अभाज्य है, 2 की घात में रूपांतरण आकार के उपयोग की अनुमति देता है; उदा. k = 2³¹ − 1 2 तक आकार बदलने का समर्थन करता है^{32</उप>।}

निचली सीमा

बिग ओ नोटेशन की एक तुच्छ निचली सीमा है #बचमान-लैंडौ नोटेशन का परिवार|Ω(n) एक प्रोसेसर पर दो एन-बिट संख्याओं को गुणा करने के लिए; कोई मिलान कलनविधि (परंपरागत मशीनों पर, जो ट्यूरिंग समतुल्य मशीनों पर है) और न ही कोई तेज निचली सीमा ज्ञात है। गुणन ACC0|AC के बाहर स्थित है⁰[p] किसी भी अभाज्य p के लिए, जिसका अर्थ है कि AND, OR, NOT और MOD का उपयोग करने वाले स्थिर-गहराई, बहुपद (या यहां तक ​​कि उप-घातीय) आकार के परिपथ का कोई परिवार नहीं है_p गेट्स जो किसी उत्पाद की गणना कर सकते हैं। यह एमओडी की निरंतर गहराई में कमी से आता है_q गुणा करने के लिए। गुणन के लिए निचली सीमाएं शाखा कार्यक्रमों के कुछ वर्गों के लिए भी जानी जाती हैं।

जटिल संख्या गुणा

जटिल गुणन में आम तौर पर चार गुणन और दो जोड़ शामिल होते हैं।

$(a+bi)(c+di)=(ac-bd)+(bc+ad)i.$

या

${\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}$

जैसा कि 1963 में पीटर उंगर द्वारा देखा गया था, करत्सुबा के कलनविधि के रूप में अनिवार्य रूप से समान गणना का उपयोग करके, गुणन की संख्या को घटाकर तीन कर सकते हैं। उत्पाद (ए + द्वि) · (सी + डी) की गणना निम्न तरीके से की जा सकती है।

क₁ = सी · (ए + बी)

क₂ = ए · (डी - सी)

क₃ = बी · (सी + डी)

वास्तविक भाग = के₁ - के₃

काल्पनिक भाग = के₁ + के₂.

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

तेज़ फूरियर रूपांतरण (FFTs) (या किसी भी रैखिक मानचित्र) के लिए जटिल गुणन निरंतर गुणांक c + di (FFTs में घुमाव कारक कहा जाता है) द्वारा किया जाता है, इस स्थिति में दो अतिरिक्त (d−c और c+d) पूर्व-गणना की जा सकती हैं . इसलिए, केवल तीन गुणा और तीन जोड़ आवश्यक हैं। हालांकि, इस तरह से जोड़ने के लिए गुणन का व्यापार करना अब आधुनिक फ्लोटिंग-पॉइंट यूनिट के साथ फायदेमंद नहीं हो सकता है।

बहुपद गुणन

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

 14ac - 3ab + 2 गुणा ac - ab + 1

 14एसी -3एबी 2
   एसी-अब 1
 ——————————————————————
 14अ2</सुप>सीए2बीसी 2एसी
        -14ए2 बीसी 3 ए2</सुप>ख2 -2ab
                 14ac-3ab2
 ————————————————————————————————————————
 14अ2</सुप>सी2 -17a2बीसी 16एसी 3ए2</सुप>ख2 -5ab +2
 <nowiki>

यह भी देखें

• बाइनरी गुणक
• दद्दा गुणक
• डिवीजन कलनविधि
• बहुपद के मूल्यांकन के लिए हॉर्नर योजना
• लघुगणक
• मानसिक गणना
• संख्या-सैद्धांतिक परिवर्तन
• प्रोस्थफेरेसिस
• स्लाइड नियम
• ट्रेचेनबर्ग प्रणाली
• Residue number system § Multiplication एक और तेज गुणन कलनविधि के लिए, विशेष रूप से कुशल जब कई ऑपरेशन अनुक्रम में किए जाते हैं, जैसे कि रैखिक बीजगणित में
• वालेस का पेड़

अग्रिम पठन

• Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.
• Johansson, Kenny (2008). Low Power and Low Complexity Shift-and-Add Based Computations (PDF) (Dissertation thesis). Linköping Studies in Science and Technology (1 ed.). Linköping, Sweden: Department of Electrical Engineering, Linköping University. ISBN 978-91-7393-836-5. ISSN 0345-7524. No. 1201. Archived (PDF) from the original on 2017-08-13. Retrieved 2021-08-23. (x+268 pages)

बाहरी संबंध

बुनियादी अंकगणित

• UCSMP प्रतिदिन गणित में अंकगणित के कई तरीके
• प्राचीन गणित के बारे में एक पावरपॉइंट प्रस्तुति
• जाली गुणा फ्लैश वीडियो

उन्नत कलनविधि

• गुणन एल्गोरिथम GMP द्वारा उपयोग किया जाता है

श्रेणी:कंप्यूटर अंकगणितीय कलनविधि|* श्रेणी:गुणन श्रेणी:सूडोकोड के उदाहरण वाले लेख