Prev: how to generate random numbers that satisfy certain distribution
Next: image processing  inverse filtering
From: kj on 23 Jan 2010 17:55 Before I go off to reinvent a thoroughly invented wheel, I thought I'd ask around for some existing module for computing binomial coefficient, hypergeometric coefficients, and other factorialbased combinatorial indices. I'm looking for something that can handle fairly large factorials (on the order of 10000!), using floatingpoint approximations as needed, and is smart about optimizations, memoizations, etc. TIA! ~K
From: idrevetnom on 24 Jan 2010 03:09 Maybe this could be of interest : http://tnt.math.metrou.ac.jp/nzmath/manual/modules/combinatorial.html hope this helps Id
From: Dave Angel on 24 Jan 2010 07:07 kj wrote: > Before I go off to reinvent a thoroughly invented wheel, I thought > I'd ask around for some existing module for computing binomial > coefficient, hypergeometric coefficients, and other factorialbased > combinatorial indices. I'm looking for something that can handle > fairly large factorials (on the order of 10000!), using floatingpoint > approximations as needed, and is smart about optimizations, > memoizations, etc. > > TIA! > > ~K > > You do realize that a standard. python floating point number cannot possibly approximate a number like 10000! Better use longs. I'd check out the gamma function, which matches factorial for integer arguments (plus or minus 1). DaveA
From: Alf P. Steinbach on 24 Jan 2010 07:55 * Dave Angel: > kj wrote: >> Before I go off to reinvent a thoroughly invented wheel, I thought >> I'd ask around for some existing module for computing binomial >> coefficient, hypergeometric coefficients, and other factorialbased >> combinatorial indices. I'm looking for something that can handle >> fairly large factorials (on the order of 10000!), using floatingpoint >> approximations as needed, and is smart about optimizations, >> memoizations, etc. >> >> TIA! >> >> ~K >> >> > You do realize that a standard. python floating point number cannot > possibly approximate a number like 10000! I think what kj is looking for, provided she/he is knowledgable about the subject, is code that does something like >>> from math import * >>> log_fac = 0 >>> for i in range( 1, 10000+1 ): ... log_fac += log( i, 10 ) ... >>> print( "10000! = {}e{}".format( 10**(log_fac % 1), int( log_fac ) ) ) 10000! = 2.84625968062e35659 >>> _ which turned out to be accurate to 10 digits. > Better use longs. That would involve incredible overhead. E.g., how many bytes for the number above? Those bytes translate into arithmetic overhead. > I'd check out the gamma function, which matches factorial for integer > arguments (plus or minus 1). Or, e.g., logarithms... ;) Cheers & hth.,  Alf
From: Dave Angel on 24 Jan 2010 16:11 Alf P. Steinbach wrote: > <div class="moztextflowed" style="fontfamily: mozfixed">* Dave > Angel: >> kj wrote: >>> Before I go off to reinvent a thoroughly invented wheel, I thought >>> I'd ask around for some existing module for computing binomial >>> coefficient, hypergeometric coefficients, and other factorialbased >>> combinatorial indices. I'm looking for something that can handle >>> fairly large factorials (on the order of 10000!), using floatingpoint >>> approximations as needed, and is smart about optimizations, >>> memoizations, etc. >>> >>> TIA! >>> >>> ~K >>> >>> >> You do realize that a standard. python floating point number cannot >> possibly approximate a number like 10000! > > I think what kj is looking for, provided she/he is knowledgable about > the subject, is code that does something like > > >>> from math import * > >>> log_fac = 0 > >>> for i in range( 1, 10000+1 ): > ... log_fac += log( i, 10 ) > ... > >>> print( "10000! = {}e{}".format( 10**(log_fac % 1), int( log_fac > ) ) ) > 10000! = 2.84625968062e35659 > >>> _ > > which turned out to be accurate to 10 digits. > > >> Better use longs. > > That would involve incredible overhead. E.g., how many bytes for the > number above? Those bytes translate into arithmetic overhead. > About 14k. > >> I'd check out the gamma function, which matches factorial for integer >> arguments (plus or minus 1). > > Or, e.g., logarithms... ;) > > > Cheers & hth., > >  Alf > I didn't think of simply summing the logs. I did have some optimizations in mind for the multiply of the longs. If you do lots of partial products, you can do a good bit of the work with smaller numbers, and only get to longs when those partial products get big enough. You could also use scaling when the numbers do start getting bigger. But I still think there must be code for the gamma function that would be quicker. But I haven't chased that lead. DaveA

Next

Last
Pages: 1 2 Prev: how to generate random numbers that satisfy certain distribution Next: image processing  inverse filtering 