By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,491 Members | 3,273 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,491 IT Pros & Developers. It's quick & easy.

how to compute binomial distribution without overflow?

P: n/a
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
Mar 19 '08 #1
Share this Question
Share on Google+
5 Replies


P: n/a
On Mar 19, 11:38 pm, gracia <graciaw...@gmail.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
Mar 20 '08 #2

P: n/a
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.

Mar 20 '08 #3

P: n/a
"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.
Mar 20 '08 #4

P: n/a
On Mar 20, 12:38 am, gracia <graciaw...@gmail.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:ja*********@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
Mar 20 '08 #5

P: n/a
On 19 Mar, 23:38, gracia <graciaw...@gmail.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/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
Mar 20 '08 #6

This discussion thread is closed

Replies have been disabled for this discussion.