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

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

दीर्घ गुणन

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

आधार 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: गुणा करने की ग्रिड विधि

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

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

उदाहरण के लिए 34 × 13 की गणना, ग्रिड का उपयोग करके की जा सकती है:

  40
  90
+ 12
————

442

×	30	4
10	300	40
3	90	12

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

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

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

जाली गुणन

Main article: जालक गुणन

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

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

जाली, या छलनी, गुणन कलनविधि रूप से दीर्घ गुणन के समान है। इसके लिए एक जाली अर्थात कागज पर खींची गई एक ग्रिड तैयार करने की आवश्यकता होती है जो गणना को निर्देशित करती है और सभी गुणाओं को जोड़ से अलग करती है। इसे यूरोप में 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: किसान गुणन

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

विवरण

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

उदाहरण

यह उदाहरण 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 के आंकड़ों का उपयोग करते हुए एक अधिक जटिल उदाहरण निमलिखित है :

Decimal:             Binary:
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 (before carry)
  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 प्रविष्टियां होंगी , प्रत्येक प्रविष्टि 16-बिट चौड़ी है (0²/4)=0 से (510²/4)=65025।

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

गुणन की संगणनीय जटिलता

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

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

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

Main article: करत्सुबा गुणन

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

1. x₁ · y₁ की गणना करें और, परिणाम F पर आवाहन करें
2. x₂ · y₂ की गणना करें और, परिणाम G को आवाहन करें
3. (x₁ + x₂) · (y₁ + y₂) की गणना करे और परिणाम H आवाहन करें
4. H − F − G की गणना करे , परिणाम K को आवाहन करें; यह संख्या x₁ · y₂ + x₂ · y₁ के बराबर है
5. F · m² + K · m + G .की गणना करे ।

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

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

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

टूम-कुक

Main article: टूम-कुक गुणन

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

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

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

Main article: शॉनहेज–स्ट्रैसन कलनविधि

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

वोल्कर स्ट्रास के कारण मूल विचार तेजी से पूर्णांक गुणन करने के लिए बहुपद गुणन का उपयोग करना है। कलनविधि को व्यावहारिक बनाया गया था और 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 करते हैं । इसके अतिरिक्त , एन को चुना जाना चाहिए ताकि कोई 'चारों ओर लपेट' न हो, अनिवार्य रूप से, मॉड्यूलो एन घटित न हो। इस प्रकार, N का चुनाव महत्वपूर्ण है। उदाहरण के लिए, यह $N=2^{3m}+1.$ के रूप में किया जा सकता है,

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

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

आगे के सुधार

2007 में पेन्सिलवेनिया राज्य विश्वविद्यालय के स्विस गणितज्ञ मार्टिन फ्यूरर ने पूर्णांक गुणन की स्पर्शोन्मुख जटिलता को n log(n) 2 में सुधारा था फूरियर का उपयोग सम्मिश्र संख्याओं पर रूपांतरण करता है। अनिंद्य डे, चंदन साहा, पीयूष कुरूर और रामप्रसाद सप्तर्षि ने 2008 में मॉड्यूलर अंकगणित का उपयोग करते हुए समान चालन समय प्राप्त करने के लिए एक समान कलनविधि दिया।. उपरोक्त सामग्री के संदर्भ में, इन बाद के लेखकों ने N को 23k + 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})$ प्राप्त करता है लेकिन जिसकी वैधता मेर्सन प्राइम्स के वितरण के बारे में मानक अनुमानों पर निर्भर करती है। 2016 में, कोवनोव और थोम ने फर्मेट प्राइम्स के सामान्यीकरण के आधार पर एक पूर्णांक गुणन कलनविधि प्रस्तावित किया, जो अनुमानित रूप से $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 एक अभाज्य है और 2 की घात में रूपांतरण आकार के उपयोग की अनुमति देता है; उदाहरण के लिए k = 2³¹ − 1, 32² तक आकार बदलने का समर्थन करता है

निचली सीमा

एक प्रोसेसर पर दो एन-बिट संख्याओं को गुणा करने के लिए Ω(n) की एक निचली सीमा है #बचमान-लैंडौ नोटेशन का परिवार|Ω(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 में पीटर उंगर द्वारा देखा गया था, करत्सुबा के कलनविधि के रूप में अनिवार्य रूप से समान गणना का उपयोग करके, गुणन की संख्या को घटाकर तीन कर सकते हैं। गुणन (a + bi) · (c + di) की गणना निम्न विधि से की जा सकती है।

k₁ = c · (a + b)

k₂ = a · (d − c)

k₃ = b · (c + d)

वास्तविक भाग = k₁ − k₃

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

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

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

बहुपद गुणन

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

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

 14ac  -3ab   2
   ac   -ab   1
 ————————————————————
 14a2c2  -3a2bc   2ac
        -14a2bc         3 a2b2  -2ab
                 14ac           -3ab   2
 ———————————————————————————————————————
 14a2c2 -17a2bc   16ac  3a2b2    -5ab  +2

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

   23     12    2
               47 x
 ————————————————
  141     94   94
  940    470
   29     23
 ————————————————
 1110    587   94
 ————————————————
 1110      7    2

 =================  उत्तर: 1110 ton 7 cwt 2 qtr
 <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 द्वारा उपयोग किया जाता है