दूसरे दिन, इस एल्गोरिथ्म से निपटने के लिए आवश्यक था, लेकिन Google में एक त्वरित खोज ने कुछ भी सार्थक नहीं दिया। केवल एक लेख हैबे पर पाया गया, जिसने वास्तव में मेरी मदद नहीं की। समझने के बाद, मैं जनता के साथ सुलभ रूप में साझा करने की कोशिश करूंगा:

एल्गोरिथ्म

Karatsuba एल्गोरिथ्म कम्प्यूटेशनल जटिलता एन ^{लॉग ₂ 3 के} साथ एक त्वरित गुणन विधि है। जबकि भोली एल्गोरिथ्म, कॉलम द्वारा गुणा करने के लिए n ² संचालन की आवश्यकता होती है। यह ध्यान दिया जाना चाहिए कि जब संख्याओं की लंबाई कई दसियों वर्णों से छोटी होती है (अधिक सटीक, प्रयोगात्मक रूप से निर्धारित), साधारण गुणक तेजी से काम करता है।
कल्पना करें कि कुछ संख्या प्रणाली B में दो संख्या A और B की लंबाई n है:
ए = एक _{एन -1} ए _{एन -2} ... एक _०
B = b _n-1 a _n-2 ... ₀ , कहाँ a _? बी _? - मान एसीसी। डिस्चार्ज अंक।
उनमें से प्रत्येक को उनके दो हिस्सों के योग के रूप में दर्शाया जा सकता है, लंबाई m = n / 2 के आधे हिस्से (यदि n विषम है, तो एक भाग एक अंक से दूसरे की तुलना में छोटा है:
एक ₀ = एक _{एम -1} एक _{एम -2} ... एक ₀
ए ₁ = ए _{एन -1} ए _{एन -2} ... ए _एम
A = A ₀ + A ₁ * आधार ^मी

B ₀ = b _m-1 b _m-2 ... b ₀
बी ₁ = बी _{एन -1} बी _{एन -2 -2} ... बी _एम
बी = बी ₀ + बी ₁ * आधार ^मी

तब: A * B = (A ₀ + A ₁ * BASE ^m ) * (B ₀ + B ₁ * BASE ^m ) = A ₀ * B ₀ + A ₀ * B ₁ * BASE ^m + A ₁ * B ₀ * BASE ^m + A ₁ * B ₁ * BASE ^{2 * m} = A ₀ * B ₀ + ( A ₀ * B ₁ + A ₁ * B ₀ ) * BASE ^m + A ₁ * B ₁ * BASE ^{2 * m}
यहां आपको गुणन के 4 संचालन की आवश्यकता है (सूत्र के भाग * आधार ^{? * M} गुणा नहीं है, वास्तव में परिणाम की रिकॉर्डिंग की जगह का संकेत है, निर्वहन)। लेकिन दूसरी ओर:
(A ₀ + A ₁ ) * (B ₀ + B ₁ ) = A ₀ * B ₀ + A ₀ * B ₁ + A ₁ * B ₀ + A ₁ * B ₁
दोनों सूत्रों में हाइलाइट किए गए भागों को देखकर। सरल परिवर्तनों के बाद, गुणन कार्यों की संख्या 3 तक घटाई जा सकती है, दो गुणाओं को एक और कई जोड़ और घटाव संचालन के साथ बदल दिया जा सकता है, जिसका निष्पादन समय परिमाण का एक क्रम कम है:
A ₀ * B ₁ + A ₁ * B ₀ = (A ₀ + A ₁ ) * (B ₀ + B ₁ ) - A ₀ * B ₀ - A ₁ * B ₁

अभिव्यक्ति का अंतिम रूप:
A * B = A ₀ * B ₀ + ((A ₀ + A ₁ ) * (B ₀ + B ₁ ) - A ₀ * B ₀ - A ₁ * B ₁ ) * BASE ^m + A ₁ * B ₁ * BASE ^{2 * मी}

चित्रमय प्रतिनिधित्व:

उदाहरण

उदाहरण के लिए, हम दशमलव प्रणाली 12345 और 98765 में दो आठ अंकों की संख्या को गुणा करते हैं:

एल्गोरिथ्म की पुनरावर्ती प्रकृति छवि से स्पष्ट रूप से दिखाई देती है। चार अंकों से कम की संख्या के लिए, भोले गुणन का उपयोग किया गया था।

C ++ कार्यान्वयन

संभवतया इससे शुरू होना चाहिए कि कितनी लंबी संख्या संग्रहीत है। सरणियों के रूप में लंबी संख्या का प्रतिनिधित्व करना सुविधाजनक है, जहां प्रत्येक तत्व एक अंक से मेल खाता है, और निचले अंक कम सूचकांकों (यानी, बैक-टू-बैक) वाले तत्वों में संग्रहीत होते हैं - उन्हें इस तरह से संसाधित करना अधिक सुविधाजनक है। उदाहरण के लिए:
int long_value[] = { 9, 8, 7, 6, 5, 4} // 456789
प्रदर्शन बढ़ाने के लिए, आधार प्रकार के भीतर अधिकतम संख्या का चयन करना उचित है जैसा कि संख्या प्रणाली के आधार पर होता है। लेकिन एक ही समय में, इस पर निम्नलिखित शर्तें लगाई जाती हैं:

1. चयनित संख्या प्रणाली में अधिकतम संख्या का वर्ग चयनित आधार प्रकार में फिट होना चाहिए। मध्यवर्ती गणना में एक श्रेणी के उत्पाद को दूसरे पर संग्रहीत करना आवश्यक है।
2. चयनित आधार प्रकार का संकेत लेने की सलाह दी जाती है। यह आपको कई मध्यवर्ती सामान्यताओं से छुटकारा पाने की अनुमति देगा।
3. यह बेहतर है कि अधिकतम संख्या के कई वर्गों के योग को निर्वहन में रखा जाए। इससे कई मध्यवर्ती सामान्यताओं से छुटकारा मिलेगा।

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

1. # अलग करना <cstring>
3. #define आधार 10 // संख्या प्रणाली
4. #define MIN_LENGTH_FOR_KARATSUBA 4 // छोटी संख्या को द्विघात एल्गोरिथ्म से गुणा किया जाता है
5. typedef int digit; // केवल एक संख्या के अंकों के लिए लिया गया
6. typedef अहस्ताक्षरित लंबे int size_length; // लंबी संख्या के लिए टाइप करें
8. नाम स्थान std का उपयोग करना ;
10. संरचना long_value { // लंबी संख्या के लिए टाइप करें
11. अंक * मान; // उल्टे क्रम में लिखी संख्या के अंकों के साथ सरणी
12. size_length लंबाई; // संख्या लंबी है
13. };
15. long_value sum (long_value a, long_value b) {
16. / * दो लंबी संख्या जोड़ने के लिए कार्य करते हैं। यदि अलग-अलग लंबाई की संख्याएं सम्‍मिलित हैं
17. * फिर लंबे समय तक पहले तर्क के रूप में पारित किया जाता है। नया लौटाता है
18. * अप्राकृतिक संख्या।
19. * /
20. long_value s;
21. s.length = a.length + 1;
22. s.values ​​= नया अंक [s.length];
24. s.values ​​[a.length - 1] = a.values ​​[a.length - 1];
25. s.values ​​[a.length] = 0;
26. for (size_length i = 0; मैं <b.length; ++ i)
27. s.values ​​[i] = a.values ​​[i] + b.values ​​[i];
28. वापसी ;
29. }
31. long_value और उप (long_value & a, long_value b) {
32. / * एक दूसरे से एक लंबी संख्या को घटाने का कार्य। पहले की सामग्री को बदल देता है
33. * संख्या। पहले नंबर पर एक संदर्भ देता है। परिणाम सामान्यीकृत नहीं है।
34. * /
35. for (size_length i = 0; मैं <b.length; ++ i)
36. a.values ​​[i] - = b.values ​​[i];
37. एक वापसी ;
38. }
40. शून्य को सामान्य करें (long_value l) {
41. / * संख्याओं का सामान्यीकरण - संख्या प्रणाली के अनुसार प्रत्येक अंक लाना।
42. *
43. * /
44. for (size_length i = 0; i <l.length - 1; ++ i) {
45. अगर (l.values ​​[i]> = BASE) { // यदि संख्या अधिकतम से अधिक है, तो स्थानांतरण का आयोजन किया गया है
46. डिजिट कैरीओवर = l.values ​​[i] / BASE;
47. l.values ​​[i + 1] + = वहन;
48. l.values ​​[i] - = carryover * आधार;
49. } और अगर (l.values ​​[i] <0) { // अगर कम है, तो एक ऋण
50. डिजिट कैरीओवर = (l.values ​​[i] + 1) / BASE - 1;
51. l.values ​​[i + 1] + = वहन;
52. l.values ​​[i] - = carryover * आधार;
53. }
54. }
55. }
57. long_value karatsuba (long_value a, long_value b) {
58. long_value उत्पाद; // परिणामी उत्पाद
59. product.length = a.length + b.length;
60. product.values ​​= new digit [product.length];
62. यदि (a.length <MIN_LENGTH_FOR_KARATSUBA) { // यदि संख्या छोटी है तो भोले गुणन लागू करें
63. मेमसेट (उत्पाद.वैल्यूज़, 0, साइज़ोफ़ (अंक) * उत्पाद.लिफ्ट)
64. for (size_length i = 0; मैं <a.length; ++ i)
65. for (size_length j = 0; j <b.length; ++ j) {
66. product.values ​​[i + j] + = a.values ​​[i] * b.values ​​[j];
67. / * यदि आप MIN_LENGTH_FOR_KARATSUBA या BASE बदलते हैं, तो निम्नलिखित को अनइंस्टॉल करें
68. * लाइनों और एसीसी उठा। मान बिट्स के अतिप्रवाह से बचने के लिए।
69. * उदाहरण के लिए, दशमलव प्रणाली के लिए, संख्या 100 का मतलब है कि यह व्यवस्थित है
70. * एक डिस्चार्ज के माध्यम से 1 स्थानांतरण, 200 - 2 स्थानांतरण एक डिस्चार्ज के माध्यम से, 5000 - 5 दो के बाद।
71. * अगर (product.values ​​[i + j]> = 100) {
72. * product.values ​​[i + j] - = 100;
73. * product.values ​​[i + j + 2] + = 1;
74. *}
75. * /
76. }
77. } और { // करत्सुबा गुणन
78. long_value a_part1; // का निचला हिस्सा
79. a_part1.values ​​= a.values;
80. a_part1.length = (a.length + 1) / 2;
82. long_value a_part2; // उच्च भाग ए
83. a_part2.values ​​= a.values ​​+ a_part1.length;
84. a_part2.length = a.length / 2;
86. long_value b_part1; // बी का निचला हिस्सा
87. b_part1.values ​​= b.values;
88. b_part1.length = (b.length + 1) / 2;
90. long_value b_part2; // उच्च भाग b
91. b_part2.values ​​= b.values ​​+ b_part1.length;
92. b_part2.length = b.length / 2;
94. long_value sum_of_a_parts = sum (a_part1, a_part2); // एक के भागों का योग
95. सामान्य करें (sum_of_a_parts);
96. long_value sum_of_b_parts = sum (b_part1, b_part2); // संख्या बी के भागों का योग
97. सामान्य करें (sum_of_b_parts);
98. long_value product_of_sums_of_parts = karatsuba (sum_of_a_parts, sum_of_b_parts);
99. // भागों की रकम का उत्पाद
101. long_value product_of_first_parts = karatsuba (a_part1, b_part1); // जूनियर सदस्य
102. long_value product_of_second_parts = karatsuba (a_part2, b_part2); // वरिष्ठ सदस्य
103. long_value sum_of_middle_terms = उप (उप (product_of_sums_of_parts, product_of_first_parts), product_of_second_parts);
104. // मध्य सदस्यों के योग का पता लगाना
106. / *
107. * बहुपद का योग
108. * /
109. memcpy (product.values, product_of_first_parts.values)
110. product_of_first_parts.length * sizeof (अंक));
111. memcpy (product.values ​​+ product_of_first_parts.length,
112. product_of_second_parts.values, product_of_second_parts.length
113. * आकार (अंक);
114. for (size_length i = 0; मैं <sum_of_middle_terms.length; ++ i)
115. product.values ​​[a_part1.length + i] + = sum_of_middle_terms.values ​​[i];
117. / *
118. * धारीदार
119. * /
120. हटाएं [] sum_of_a_parts.values;
121. हटाएं [] sum_of_b_parts.values;
122. हटाएं [] product_of_sums_of_parts.values;
123. हटाएं [] product_of_first_parts.values;
124. हटाएं [] product_of_second_parts.values;
125. }
127. सामान्य करें (उत्पाद); // संख्या का अंतिम सामान्यीकरण
129. वापसी उत्पाद;
130. }

* इस सोर्स कोड को सोर्स कोड हाइलाइटर के साथ हाइलाइट किया गया था।