how to compute binomial distribution without overflow?

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

re: how to compute binomial distribution without overflow?

On Mar 19, 11:38 pm, gracia <graciaw...@gmail.comwrote: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

re: how to compute binomial distribution without overflow?

gracia <graciawang@gmail.comwrites: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.

re: how to compute binomial distribution without overflow?

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

re: how to compute binomial distribution without overflow?

On Mar 20, 12:38 am, gracia <graciaw...@gmail.comwrote: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:james.kanze@gmail.com
Conseils en informatique orient�e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S�mard, 78210 St.-Cyr-l'�cole, France, +33 (0)1 30 23 00 34

re: how to compute binomial distribution without overflow?

On 19 Mar, 23:38, gracia <graciaw...@gmail.comwrote: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