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@gmail.com]

Re: how to compute binomial distribution without overflow?

On Mar 19, 11:38 pm, gracia <graciaw...@gma il.comwrote:

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]

Re: how to compute binomial distribution without overflow?

gracia <graciawang@gma il.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]

Re: how to compute binomial distribution without overflow?

"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]

Re: how to compute binomial distribution without overflow?

On Mar 20, 12:38 am, gracia <graciaw...@gma il.comwrote:

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:james.kan ze@gmail.com
Conseils en informatique orient�e objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place S�mard, 78210 St.-Cyr-l'�cole, France, +33 (0)1 30 23 00 34

[iandjmsmith@aol.com]

Re: how to compute binomial distribution without overflow?

On 19 Mar, 23:38, gracia <graciaw...@gma il.comwrote:

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/comp.lang.javascript/msg/ebaefcd0d790545b?hl=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