how to compute binomial distribution without overflow?

[gracia]

I need to compute the value of binomial(n, k)=n!/k!(n-k)! * (1-p)^n *
p^k.

When n and k is very big (e.g. n 160), the step to compute n!/k!(n-
k)! is always overflow even when I used unsigned long long.

Can anyone help me?

Thank you
Gracia

[tommy.hinks]

On Mar 19, 11:38 pm, gracia <[e-mail]:

I need to compute the value of binomial(n, k)=n!/k!(n-k)! * (1-p)^n *
p^k.

When n and k is very big (e.g. n 160), the step to compute n!/k!(n-
k)! is always overflow even when I used unsigned long long.

Can anyone help me?

Thank you

Gracia

Did you try using double or long double?

I am no expert in this field, but it seems you might be able to cancel
some of the terms:

e.g.

n = 10
k = 5

1*2*3*4*5*6*7*8*9*10
--------------------- = 6*7*8*9*10
1*2*3*4*5

T

[Michal Spalinski]

gracia <gr********@gmail.comwrites:

I need to compute the value of binomial(n, k)=n!/k!(n-k)! * (1-p)^n *
p^k.

When n and k is very big (e.g. n 160), the step to compute n!/k!(n-
k)! is always overflow even when I used unsigned long long

You can use a recurrence relation which is equivalent to the definition you
cite:

long bino(int n, int k)
{
if (k==0 || n == k) return 1;
return bino(n-1,k-1) + bino(n-1,k);
}

You can speed this up considerably by caching.

[osmium]

"gracia" writes:

>I need to compute the value of binomial(n, k)=n!/k!(n-k)! * (1-p)^n *
p^k.

When n and k is very big (e.g. n 160), the step to compute n!/k!(n-
k)! is always overflow even when I used unsigned long long.

The easiest, but probably not the best in terms of accuracy and speed, way
would be to use logarithms.

[James Kanze]

On Mar 20, 12:38 am, gracia <[e-mail]:

I need to compute the value of binomial(n, k)=n!/k!(n-k)! *
(1-p)^n * p^k.

When n and k is very big (e.g. n 160), the step to compute
n!/k!(n- k)! is always overflow even when I used unsigned long
long.

Can anyone help me?

If you have access to the C99 math functions (which will be part
of the next version of C++ as well), you can use something like:

double
fact(
double i )
{
return round( exp( gamma( (double)( i + 1 ) ) ) ) ;
}

long
binom(
long i,
long j )
{
return round( fact( i ) / ( fact( j ) * fact( i - j ) ) ) ;
}

On the other hand, I'm not sure that it will be really correct
for very large values. Typically, a double will not be able to
represent all of the needed values exactly.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orient�e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S�mard, 78210 St.-Cyr-l'�cole, France, [phone]

[iandjmsmith]

On 19 Mar, 23:38, gracia <[e-mail]:

I need to compute the value ofbinomial(n, k)=n!/k!(n-k)! * (1-p)^n *
p^k.

When n and k is very big (e.g. n 160), the step to compute n!/k!(n-
k)! is always overflow even when I used unsigned long long.

Can anyone help me?

Thank you

Gracia

See
http://groups.google.co.uk/group/com...=en&lr=&rnum=8
for details of how to perform accurate calculations for the binomial
distribution. VBA code for these calculations can be found in
http://members.aol.com/iandjmsmith/Examples.xls

A Javascript binomial distribution calculator can be found at
http://members.aol.com/iandjmsmith/EXAMPLES.HTM
Ian Smith