बड़े पूर्णांक पर काम कैसे करें जो किसी भी भाषा के डेटा संरचनाओं में फिट नहीं है

Question

मैं एक प्रोग्रामिंग प्रतियोगिता की प्रारंभिक समस्याओं को हल करने की कोशिश कर रहा हूं और 2 समस्याओं के लिए मुझे कुछ बहुत बड़े पूर्णांक की गणना और प्रिंट करना है (जैसे 100 !, 2^100)।

मुझे इस बड़े पूर्णांक की शक्तियों की गणना करने के लिए एक तेज़ तरीका भी चाहिए। ?

क्या आप मुझे कुछ एल्गोरिदम या इस के लिए डेटा संरचनाओं सलाह कर सकते हैं (btw, मैं सी इंटरफेस और क्रियान्वयन 'मनमाना परिशुद्धता गणित' अनुभाग पढ़ें लेकिन यह पॉव के लिए() मदद नहीं करता है)

संपादित करें: मुझे लगता है स्क्वायरिंग विधि और बिट-स्थानांतरण द्वारा एक्सपोनेंटिएशन बिजली के लिए काम करेगा लेकिन मुझे इन चींटियों के लिए फैक्टोरियल की गणना करने के लिए एक तेज़ तरीका भी चाहिए। धन्यवाद।

EDIT2: रुचि रखने वालों के लिए;

सबसे छोटी बिट स्ट्रिंग लंबाई खोजें जिसमें लम्बाई के साथ सभी बिट स्ट्रिंग शामिल हैं (मेरी अंग्रेजी के लिए खेद है, मैं एक उदाहरण दूंगा)। एन < = 10000

उदाहरण के लिए, सबसे छोटी बिट स्ट्रिंग लंबाई जिसमें लम्बाई 2 (00, 01, 10, 11) के सभी स्ट्रिंग्स शामिल हैं 5 (11001) है।

इस समस्या के लिए मेरे समाधान 2 था^n + n - 1. (तो मैं 2 की शक्तियों की गणना करना चाहिए, मुझे लगता है कि मैं थोड़ा-स्थानांतरण का उपयोग करेंगे)

अन्य समस्या यह है 2 लंबाई को देखते हुए, यह पता लगाएं कि आप लंबाई एन तक कितने अलग-अलग तरीकों तक पहुंच सकते हैं। उदाहरण के लिए, इनपुट 10, 2, 3 है। फिर आपको 2 और 3 के साथ 10 तक पहुंचना चाहिए (उदाहरण के लिए, 2 + 2 + 2 + 2 + 2, 2 + 2 + 3 + 3, 3 + 2 + 2 + 3, 3 + 3 + 2 + 2 ...)। 1 < = एन < 2^63। हम मॉड 1000000007 में anwser की गणना करेंगे।

मेरा समाधान था, 2x + 3y = N, तो x = (N - 3y)/2। वाई से 0 से 2 * एन/3 तक, यदि एक्स एक पूर्णांक है, तो मुझे इस एक्स और वाई, कुल + = (x + y) के लिए सामान्यीकृत क्रमपरिवर्तन की गणना करनी चाहिए!/(एक्स! * वाई!)।

Answer 1

सी के लिए this कुछ ऐसा करने के लिए, या एक अंक का प्रतिनिधित्व करने वाले सरणी में एक स्थान के साथ int या char arrays का उपयोग करके अपना स्वयं का रोल करेगा। [1 | 0 | 1] या 101 के लिए ['1'|'0'|'1'], आदि

Answer 2

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

Answer 3

पूर्णांकों के साथ pow के लिए की एक सरणी, exponentiation by squaring

Answer 4

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

GPG खुला स्रोत है, बस एक नजर है यह :) पर

Answer 5

आप folowing प्रारूप में संग्रहीत कर सकते हैं: अंक हैं और इस संख्या के अंकों की सरणी की संख्या। प्रोग्रामिंग प्रतियोगिताओं में बड़ी संख्याओं से निपटने का यह एक आम तरीका है।

यहां संख्या और गुणा को संग्रहित करने की तुलना में एक कक्षा है। संख्याओं के इनपुट और आउटपुट को जोड़ा जा सकता है जो तुच्छ हैं।

class huge { 
public: 
    int size; 
    int data[1000]; 

    friend void mul(const huge &a, int k, huge &c) { 
     c.size = a.size; 
     int r = 0; 
     for (int i = 0; i < a.size; i++) { 
      r += a.data[i] * k; 
      c.data[i] = r % 10; 
      r = r/10; 
     } 
     if (r > 0) { 
      c.size++; 
      c.data[c.size - 1] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 

    friend void mul(const huge &a, const huge &b, huge &c) { 
     c.size = a.size + b.size; 
     memset(c.data, 0, c.size * sizeof(c.data[0])); 
     for (int i = 0; i < a.size; i++) { 
      int r = 0; 
      for (int j = 0; j < b.size; j++) { 
       r += a.data[i] * b.data[j] + c.data[i + j]; 
       c.data[i + j] = r % 10; 
       r /= 10; 
      } 
      if (r > 0) 
       c.data[i + b.size] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 
}; 

Answer 6

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

Answer 7

बुनियादी गणित डबल के साथ किसी भी डबल के गुणन कर सकते हैं ...

def biginteger(num1, num2): 
result = [] 
lnum1 = len(num1) 
lnum2 = len(num2) 

k = x = remainder = 0 
while len(result) < lnum1: 
    result.append(0) 
for i in range(lnum1, 0, -1): 
    multiplier = int(num1[i - 1]) 
    for j in range(lnum2, 0, -1): 
     temp = (int(num2[j - 1]) * multiplier) + remainder + int(result[k]) 
     result[k] = str(temp % 10) 
     remainder = temp/10 
     k += 1 
    result.append(str(remainder)) 
    if remainder != 0: 
     remainder = 0 
    x += 1 
    k = x 

return ''.join([result[i - 1] for i in range(len(result), 0, -1)]) 

num1 = '37234234234234' 
num2 = '43234234234232' 
print biginteger(num1, num2)