बहुत लंबे पूर्णांक का गुण

Question

क्या दो मनमाने ढंग से लंबे पूर्णांक को एक साथ सटीक रूप से गुणा करने के लिए कोई एल्गोरिदम है? जिस भाषा के साथ मैं काम कर रहा हूं वह 64-बिट हस्ताक्षरित पूर्णांक लंबाई तक सीमित है (1844674407370 9 551615 का अधिकतम पूर्णांक आकार)। वास्तव में, मैं प्रत्येक नंबर को तोड़कर, बिना किसी हस्ताक्षर किए 64-बिट पूर्णांक का उपयोग करके उन्हें संसाधित करने में सक्षम होना चाहता हूं, और उसके बाद उन्हें एक स्ट्रिंग में एक साथ वापस रखने में सक्षम होना (जो गुणा परिणाम के मुद्दे को हल करेगा भंडारण)।

कोई विचार?

Answer 1

अधिकांश भाषाओं कार्यों या पुस्तकालयों कि ऐसा करते हैं, आम तौर पर एक bignum पुस्तकालय कहा जाता है (GMP एक अच्छा एक है।)

है, मैं इसे उसी तरह है कि लोगों को लंबे समय तक ऐसा करना होगा कागज पर गुणा। ऐसा करने के लिए आप या तो संख्या वाले तारों के साथ काम कर सकते हैं, या बिटवाई ऑपरेशंस का उपयोग करके इसे बाइनरी में कर सकते हैं।

उदाहरण:

45 
x67 
--- 
315 
+270 
---- 
585 

या बाइनरी में:

101 
    x101 
    ---- 
    101 
    000 
+101 
------ 
11001 

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

उत्पाद को स्टोर करने के लिए, आपको दो 64-बिट संख्याएं होनी चाहिए और कल्पना करें कि उनमें से एक पहले 64 बिट्स और दूसरा उत्पाद की दूसरी 64 बिट्स है। आपको कोड लिखना होगा जिसमें दूसरे नंबर के बिट 63 से पहले नंबर के बिट 0 को जोड़ना होगा।

Answer 2

हां, आप इसे डेटाटाइप का उपयोग करते हैं जो प्रभावी रूप से अंकों की एक स्ट्रिंग है (जैसे कि सामान्य 'स्ट्रिंग' वर्णों की एक स्ट्रिंग है)। आप यह कैसे करते हैं अत्यधिक भाषा-निर्भर है। उदाहरण के लिए, जावा BigDecimal का उपयोग करता है। आप किस भाषा का उपयोग कर रहे हैं?

Answer 3

इसे अक्सर होमवर्क असाइनमेंट के रूप में दिया जाता है। ग्रेड स्कूल में सीखा एल्गोरिदम काम करेगा। यदि आपको वास्तविक एप्लिकेशन के लिए इसकी आवश्यकता है तो लाइब्रेरी का उपयोग करें (कई पदों में कई का उल्लेख किया गया है)। आप इसे खुद करना चाहते हैं तो

Answer 4

स्कूलीबुक तंत्र का उपयोग करने का सबसे आसान तरीका होगा, अपनी मनमाने ढंग से आकार की संख्या को प्रत्येक 32-बिट के हिस्सों में विभाजित करना होगा।

ए बी सी डी * ई एफ जी एच (कुल 128 बिट के लिए प्रत्येक खंड 32-बिट) दिया गया
आपको आउटपुट सरणी 9 dwords चौड़े की आवश्यकता है। सेट [0..8] से 0

आप ऐसा करके शुरू करेंगे: एच * डी + आउट [8] => 64 बिट परिणाम।
कम 32-बिट्स को बाहर निकालें [8] और ले जाने के रूप में उच्च 32-बिट्स ले जाएं अगला: (एच * सी) + आउट [7] +
फिर से, 32-बिट में कम स्टोर करें [ 7], एच * ए + आउट [4] + वाह करने के बाद उच्च 32-बिट्स को
ले जाने के रूप में उपयोग करें, आपको लूपिंग जारी रखने की आवश्यकता है जब तक कि आपके पास कोई लेयर न हो।

फिर जी, एफ, ई के साथ दोहराएं।
जी के लिए, आप [8] के बजाय बाहर [7] शुरू करेंगे, और आगे।

अंत में, के माध्यम से चलना और अंकों में बड़े पूर्णांक (जो एक नियमित "एक शब्द से बड़ी संख्या में विभाजित करें" की आवश्यकता होगी) कन्वर्ट

Answer 5

आप जीएमपी की तरह एक मौजूदा bignum पुस्तकालय का उपयोग नहीं कर सकते हैं, बाहर की जाँच Wikipedia's article on binary multiplication with computers। इसके लिए कई अच्छे, कुशल एल्गोरिदम हैं।

Answer 6

यहां सी अच्छा वर्ष गुणा विधि

char *multiply(char s1[], char s2[]) { 
    int l1 = strlen(s1); 
    int l2 = strlen(s2); 
    int i, j, k = 0, c = 0; 
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string 
    int temp; 

    strrev(s1); 
    strrev(s2); 
    for (i = 0;i <l1+l2; i++) { 
     r[i] = 0 + '0'; 
    } 

    for (i = 0; i <l1; i ++) { 
     c = 0; k = i; 
     for (j = 0; j < l2; j++) { 
      temp = get_int(s1[i]) * get_int(s2[j]); 
      temp = temp + c + get_int(r[k]); 
      c = temp /10; 
      r[k] = temp%10 + '0'; 

      k++; 
     } 
     if (c!=0) { 
      r[k] = c + '0'; 
      k++; 
     } 
    } 

    r[k] = '\0'; 
    strrev(r); 
    return r; 
}