20160815, 09:31  #1 
Apr 2014
Marlow, UK
70_{8} Posts 
Fast calculation of binomial coefficients
If I know (mod m), is there a way of calculating (mod m) with time complexity better than ?
m <= n p <= n/2 Last fiddled with by mickfrancis on 20160815 at 09:44 Reason: (mod n) should be (mod m), also added constraints 
20160815, 12:05  #2 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
I don't know but is their ratio ((n+p)!*(2p)!)/(n!*p!) easily calculated mod m ? if so it's a modular multiply away. doh that ratio ( if I've done the math correctly to get it is (2p)! * (n+p choose p) ) okay I see an error I did I forgot to flip one of the fractions in their ratio when multiplying. (n+p)!/(((n+p)(2p))!2p!) /( n!/((np)!p!)) = (n+p)!/(((np)!2p!) /( n!/((np)!p!)) =((n+p)!/(2p!)) /( n!/(p!)) = ((n+p)!p!)/((2p)!n!) doh!!!
Last fiddled with by science_man_88 on 20160815 at 12:18 
20160815, 12:23  #3 
Apr 2014
Marlow, UK
2^{3}·7 Posts 
Good thought. I think the p and 2p are transposed in that ratio? I get: ((n+p)! * p!)/((2p)! * n!), which can be written as , and I can't see how to calculate this in better than  maybe there is a closed form for this?

20160815, 12:31  #4  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
I think there's a simpler form of that product division as in each case of i there's n/(p+i) +(1/(p/i+1)) no ? and this can be put into fractional form of ((n+1)*(p+i))/((p^2+p*i)/i+(p+i)) I think. doh I'm an idiot not sure why I thought it could be done like that for some reason. Last fiddled with by science_man_88 on 20160815 at 12:43 

20160815, 13:08  #5  
Apr 2014
Marlow, UK
2^{3}×7 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Coefficients Integer Sets  carpetpool  carpetpool  1  20170222 08:37 
Do normal adults give themselves an allowance? (...to fast or not to fast  there is no question!)  jasong  jasong  35  20161211 00:57 
Binomial Primes  Lee Yiyuan  Miscellaneous Math  31  20120506 17:44 
Recovering Fourier coefficients of modular forms  Robert Holmes  Math  2  20100922 22:10 
No Notice Binomial Coefficients, Pascal's triangle  Vijay  Miscellaneous Math  5  20050409 20:36 