लंबे डबल बनाम लंबे int

Question

मैं एक प्रोग्राम कर रहा हूं जो लॉटरी की संभावना की गणना करता है।

#include <iostream> 

long int choose(unsigned n, unsigned k); 
long int factorial(unsigned n); 

int main(){ 
    using namespace std; 
    long int regularProb, megaProb; 
    regularProb = choose(47, 5); 
    megaProb = choose(27, 1); 
    cout << "The probability of the correct number is 1 out of " << (regularProb * megaProb) << endl; 

    return 0; 
} 

long int choose(unsigned n, unsigned k){  
    return factorial(n)/(factorial(k) * factorial(n-k)); 
} 

long int factorial(unsigned n){ 
    long int result = 1; 
    for (int i=2;i<=n;i++) result *= i; 
    return result; 
} 

हालांकि कार्यक्रम काम नहीं करता: विशिष्टता 47 और 1 से 5 संख्या निम्नलिखित बाहर के 27

तो मैंने किया था चुनना है। कार्यक्रम 30 सेकंड के लिए गणना करता है, फिर मुझे Process 4 exited with code -1,073,741,676 देता है मुझे सभी लंबे int को लंबे समय तक बदलना होगा, लेकिन यह सटीकता खो देता है। क्या ऐसा इसलिए है क्योंकि बड़े मूल्यों के लिए लंबी int बहुत कम है? हालांकि मैंने सोचा था कि आजकल लंबे समय तक इंट 64 बिट हैं? मेरा कंपाइलर जी ++ win32 (64 बिट होस्ट) है।

Answer 1

चाहे long 64-बिट है या नहीं मॉडल पर निर्भर करता है। Windows uses a 32-bit long। int64_t from <stdint.h> का उपयोग करें यदि आपको यह सुनिश्चित करना है कि यह 64-बिट है।

लेकिन अगर long 64-बिट है तो भी factorial(47) पकड़ने के लिए अभी भी बहुत छोटा है।

47! == 2.58623242e+59 
2^64 == 1.84467441e+19 

हालांकि सी तरीका है कि तुलना में छोटी है। के रूप में यह आसानी से overflows

आप _n सी _आर == n का उपयोग कभी नहीं करना चाहिए!/(r! (एन-आर)!) सीधे गणना करते हैं। इसके बजाय, एन कारक बाहर!/(एन-आर)! get रहे हैं:

 47 * 46 * 45 * 44 * 43 
    C = ---------------------- 
47 5 5 * 4 * 3 * 2 * 1 

इस यहाँ तक कि एक 32-बिट पूर्णांक द्वारा प्रबंधित किया जा सकता है।

---

Btw, के लिए @ कॉफी के सवाल: एक double केवल परिशुद्धता के 53-बिट है, जहां 47! 154 बिट्स की आवश्यकता है। 47! और 42! double में

47! = (0b10100100110011011110001010000100011110111001100100100 << 145) ± (1 << 144) 
42! = (0b11110000010101100000011101010010010001101100101001000 << 117) ± (1 << 116) 

तो 47 होगा!/(42! × 5!) के मूल्य के संभावित रेंज

 0b101110110011111110011 = 1533939      53 bits 
                   v 
max = 0b101110110011111110011.000000000000000000000000000000001001111... 
val = 0b101110110011111110010.111111111111111111111111111111111010100... 
min = 0b101110110011111110010.111111111111111111111111111111101011010... 

सही मूल्य सी प्राप्त करने के लिए काफी है कि हो जाएगा।

Answer 2

64 बिट लंबा उपयोग करने के लिए, आपको long long का उपयोग करना चाहिए। (as mentioned here)

Answer 3

केनीटीएम के पास यह सही है, आप किस प्रकार का उपयोग करते हैं इससे कोई फर्क नहीं पड़ता। आपको समस्या से अधिक बुद्धिमानी से संपर्क करने और बहुत सारे काम करने की आवश्यकता है।आप एक अनुमानित जवाब के साथ ठीक कर रहे हैं, तो स्टर्लिंग के सन्निकटन पर एक नज़र डालें:

Ln(n!) ~ n Ln(n) - n 

तो अगर आप

n!/(k!*(n-k)!) 

आपको लगता है कि

e(ln(n!/(k!*(n-k)!))) 

है कह सकते है जो कुछ के बाद गणित (यह सुनिश्चित करने के लिए दो बार जांचें कि मुझे यह सही मिला है)

e(n*ln(n)-k*ln(k)-(n-k)*ln(n-k)) 

और वह अतिप्रवाह नहीं करना चाहिए (लेकिन यह एक अनुमानित जवाब)

Answer 4

यह अतिप्रवाह बिना 47C5 के लिए और उससे आगे तक द्विपद गुणांक की गणना करने के मानक unsigned long 32-बिट अंकगणित का प्रयोग कर आसान है। इस प्रश्न का मेरा जवाब देखें: https://math.stackexchange.com/questions/34518/are-there-examples-where-mathematicians-needs-to-calculate-big-combinations/34530#comment-76389