On Mar 28, 1:31 pm, user923005 <dcor...@connx.com> wrote: > 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).
I have a very large Pascal's triangle precomputed, if you would like a copy. I can also generate one for whatever size you need (I have a program that generates the programs).