On Mar 28, 4:06 am, gsgs <ster...@aol.com> wrote: > how do I efficiently calculate or approximate > > SUM [i=0..k] hypergeometrical(i;r,n,w) > > ? > > hypergeometrical(i;r,n,w)=binomia(w,i)*binomial(n-w,r-i)/binomial(n,r) > > this is for testing large gene-databases for recombinations
I am assuming that all values are integral and that you have a mathematics system that can compute the answers without overflow (not always an easy task if the inputs are large).
Precompute the binomail coefficients and store them in a table. Then you will have this: binomial[w][i] * binomial[n-w][r-i]/binomial[n][r] which is O(1).