दो संख्याओं को गुणा करने के लिए Karatsuba एल्गोरिथम

किसी तरह मुझे C ++ में उनके प्रतिनिधित्व के हिस्सों के माध्यम से, लंबी संख्याओं के गुणन को लागू करना था। 128-बिट संख्याओं को 64-बिट संख्याओं की एक जोड़ी के रूप में प्रस्तुत किया गया था। यह पता चला कि दो 128-बिट संख्याओं को गुणा करने और जटिलता में परिणाम के सभी 256 बिट्स प्राप्त करने के लिए 64-बिट हिस्सों के 4 उत्पादों की तुलना में है। यह कैसे काम करता है ...



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

// // Karatsuba multiplication algorithm // // +------+------+ // | x1 | x0 | // +------+------+ // * // +------+------+ // | y1 | y0 | // +------+------+ // = // +-------------+-------------+ // + | x1*y1 | x0*y0 | // +----+-+------+------+------+ // . . . // . . . // +-+------+------+ // + | x0*y1 + x1*y0 | // +-+------+------+ // 

सिद्धांत रूप में, टिप्पणी यह ​​स्पष्ट करती है कि परिणाम की गणना कैसे की जाती है।
विधि का सार समझा जा सकता है यदि निम्न सूत्र प्राप्त होता है:



T इंडेंटेशन का प्रतीक है, क्रमशः T ^ 2 - डबल इंडेंटेशन।
यहाँ कोड है जो इन कार्यों को करता है:

 // // Params: // T - is type of x0, x1, y0 and y1 halves // T2 - is type of x, y and half of res // template<typename T, typename T2> inline void Karatsuba_multiply(T * const x, T * const y, T2 * res) { // Define vars (depending from byte order) #define ptrRes ((T*)res) T2 & lowWord = (T2&)(ptrRes[0]); T2 & midWord = (T2&)(ptrRes[1]); T2 & highWord = (T2&)(ptrRes[2]); T & highByte = (T &)(ptrRes[3]); #undef ptrRes const T & x0 = x[0]; const T & x1 = x[1]; const T & y0 = y[0]; const T & y1 = y[1]; // Multiply action lowWord = x0 * y0; highWord = x1 * y1; T2 m1 = x0 * y1; T2 m2 = x1 * y0; midWord += m1; if (midWord < m1) highByte++; midWord += m2; if (midWord < m2) highByte++; } 

टाइप T एक प्रकार का आधा है, टाइप x0, X1, y0, y1।
टाइप एन 2 आधे परिणाम का प्रकार है, टाइप टी का 2 गुना।

समारोह उपयोग उदाहरण:

 int main() { typedef unsigned char u8; typedef unsigned short u16; typedef unsigned int u32; u16 a = 1000; u16 b = 2000; u32 r = 0; u8 * a_ptr = (u8*)&a; u8 * b_ptr = (u8*)&b; u16 * r_ptr = (u16*)(void*)&r; Karatsuba_multiply(a_ptr, b_ptr, r_ptr); cout << r; } 

निष्पादन के परिणाम वाला कोड यहां पाया जा सकता है: codepad.org/1OTeGqhA
अलग-अलग बाइट ऑर्डर के लिए एक एल्गोरिथ्म के साथ कोड (LE + BE) यहां: codepad.org/f5Pxtiq1

Update1:
उपयोगकर्ता mark_ablov ने देखा कि कोड में #undef का अभाव है।
सही कोड: codepad.org/13U4fuTp
सही पूर्ण कोड (LE + BE): codepad.org/kBazqo8f

UPDATE2:
उपयोगकर्ता ttim ने ध्यान दिया कि उपरोक्त एल्गोरिथ्म बिल्कुल Karatsuba विधि नहीं है और चार के बजाय 3 गुणा का उपयोग करने की संभावना का संकेत दिया।

स्पष्टता सूत्र:



इस प्रकार, केवल 3 उत्पादों की गणना करने की आवश्यकता है:
1. ए * एक्स
2. ब * य
3. (टा + बी) * (टीएक्स + वाई)

दुर्भाग्य से, मैं इस सूत्र का उपयोग नहीं कर पाऊंगा, क्योंकि मेरे पास 128-बिट संख्याओं को गुणा करने की क्षमता नहीं है। दरअसल, मेरा काम 128-बिट संख्या के गुणन को लागू करना था। तथ्य यह है कि संख्या (टा + बी) और (टीएक्स + वाई) 128 बिट्स चौड़े हैं ...

Update3:
उपयोगकर्ता susl ने एल्गोरिथ्म की चर्चा जारी रखी और दिखाया कि 128-बिट संख्याओं को गुणा करने की कोई आवश्यकता नहीं है।

एक और सूत्र:



समारोह को फिर से लिखा जा सकता है:

 // // Params: // T - is type of x0, x1, y0 and y1 halves // T2 - is type of x, y and half of res // template<typename T, typename T2> inline void Karatsuba_multiply(T * const x, T * const y, T2 * res) { // Define vars (depending from byte order) #define ptrRes ((T*)res) T2 & lowWord = (T2&)(ptrRes[0]); T2 & midWord = (T2&)(ptrRes[1]); T2 & highWord = (T2&)(ptrRes[2]); T & highByte = (T &)(ptrRes[3]); #undef ptrRes const T & x0 = x[0]; const T & x1 = x[1]; const T & y0 = y[0]; const T & y1 = y[1]; // Multiply action lowWord = x0 * y0; highWord = x1 * y1; //T2 m1 = x0 * y1; //T2 m2 = x1 * y0; T2 m = (x0+x1)*(y0+y1) - (lowWord + highWord); //midWord += m1; //if (midWord < m1) highByte++; //midWord += m2; //if (midWord < m2) highByte++; midWord += m; if (midWord < m) highByte++; } 

सही उदाहरण: http://codepad.org/w0INBD77
LE और BE के लिए सही उदाहरण: http://codepad.org/nB9HqWt1