double double vs long int

Question

Estoy haciendo un programa que calcula la probabilidad de loterías. Especificación es elegir 5 números de 47 y 1 de cada 27

Así que hizo lo siguiente:

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

Sin embargo, el programa no funciona. El programa calcula por 30 segundos, luego me da Process 4 exited with code -1,073,741,676 Tengo que cambiar todo el int largo al doble largo, pero eso pierde precisión. ¿Es porque int largo es demasiado corto para los grandes valores? Aunque pensé que int largo hoy en día son 64 bits? Mi compilador es g ++ win32 (host de 64 bits).

Answer 1

Si long es de 64 bits o no depende del modelo. Windows uses a 32-bit long. Use int64_t from <stdint.h> si necesita asegurarse de que sea de 64 bits.

Pero incluso si long es de 64 bits, todavía es demasiado pequeño para contener factorial(47).

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

aunque C es la forma más pequeño que eso.

Nunca se debe utilizar _n C _r == n!/(R! (N-r)!) Ver directamente el cálculo, ya que desborda con facilidad. ¡En cambio, factoriza el n!/(N-r)! a get:

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

este puede ser administrado incluso por un entero de 32 bits.

---

Por cierto, por @ pregunta de café: una double solamente tiene 53 bits de precisión, donde el 47! requiere 154 bits. 47! y 42! representado en double sería

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

so 47!/(42! × 5!) 'S posible rango de valor será

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

que es suficiente para obtener el valor exacto C .

Answer 2

para usar 64bit de largo, debe usar long long. (as mentioned here)

Answer 3

KennyTM tiene razón, se va a desbordar sin importar el tipo que use. Necesita abordar el problema de manera más inteligente y tener en cuenta un montón de trabajo.Si estás bien con una respuesta aproximada, a continuación, echar un vistazo a la aproximación de Stirling:

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

Así que si usted tiene

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

Se podría decir que es

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

el que después de algún matemática (compruebe dos veces para asegurarse de que lo hice bien) es

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

Y eso no debe desbordarse (pero es una respuesta aproximada)

Answer 4

Es fácil calcular los coeficientes binomiales hasta 47C5 y más allá sin rebosadero, utilizando el estándar unsigned long aritmética de 32 bits. Ver mi respuesta a esta pregunta: https://math.stackexchange.com/questions/34518/are-there-examples-where-mathematicians-needs-to-calculate-big-combinations/34530#comment-76389