long double vs long int

Question

我在做一個計算彩票概率的程序。 規格是選擇5個號碼進行的47進1出的27

所以我做了以下內容：

#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; 
} 

然而，程序不能正常工作。該程序計算30秒，然後給我Process 4 exited with code -1,073,741,676我必須將所有long int更改爲long double，但是失去精度。是否因爲long int對於大值太短？儘管現在我認爲long int是64bit？我的編譯器是g ++ win32（64位主機）。

Answer 1

long是否爲64位取決於型號。 Windows uses a 32-bit long。如果您需要確保它是64位的，請使用int64_t from <stdint.h>。

但即使long是64位，它仍然太小，以至於不能容納factorial(47)。

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

雖然Ç比方式小。

你永遠不應該使用_ňÇ _[R == N！/（R！（N-R）！）直接進行計算，因爲它很容易溢出。相反，將n！/（n-r）！到get：

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

這甚至可以用一個32位整數來管理。

---

順便說一句，對於@咖啡的問題：一個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

要使用64bit長，您應該使用long long。 (as mentioned here)

Answer 3

KennyTM沒錯，不管你使用什麼類型，你都會溢出。你需要更巧妙地處理這個問題，並將大量工作分解出來。如果你確定有大概的答案，然後看看斯特靈公式：

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