mersenneforum.org > Math Fast calculation of binomial coefficients
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-08-15, 09:31 #1 mickfrancis   Apr 2014 Marlow, UK 23×7 Posts Fast calculation of binomial coefficients If I know ${n} \choose {p}$ (mod m), is there a way of calculating ${n+p} \choose {2p}$ (mod m) with time complexity better than $\mathcal{O}(p)$? m <= n p <= n/2 Last fiddled with by mickfrancis on 2016-08-15 at 09:44 Reason: (mod n) should be (mod m), also added constraints
2016-08-15, 12:05   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mickfrancis If I know ${n} \choose {p}$ (mod m), is there a way of calculating ${n+p} \choose {2p}$ (mod m) with time complexity better than $\mathcal{O}(p)$? m <= n p <= n/2
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!/((n-p)!p!)) = (n+p)!/(((n-p)!2p!) /( n!/((n-p)!p!)) =((n+p)!/(2p!)) /( n!/(p!)) = ((n+p)!p!)/((2p)!n!) doh!!!

Last fiddled with by science_man_88 on 2016-08-15 at 12:18

2016-08-15, 12:23   #3
mickfrancis

Apr 2014
Marlow, UK

5610 Posts

Quote:
 Originally Posted by science_man_88 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)
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 $\frac{\displaystyle\prod_{i=1}^{p} {(n+i)}} {\displaystyle\prod_{i=1}^{p} {(p+i)}}$, and I can't see how to calculate this in better than $\mathcal{O}(p)$ - maybe there is a closed form for this?

2016-08-15, 12:31   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mickfrancis 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 $\frac{\displaystyle\prod_{i=1}^{p} {(n+i)}} {\displaystyle\prod_{i=1}^{p} {(p+i)}}$, and I can't see how to calculate this in better than $\mathcal{O}(p)$ - maybe there is a closed form for this?

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 2016-08-15 at 12:43

2016-08-15, 13:08   #5
mickfrancis

Apr 2014
Marlow, UK

23·7 Posts

Quote:
 Originally Posted by science_man_88 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.
It can be rewritten as $\displaystyle\prod_{i=1}^{p} {(1 + \frac{n-p}{i+p})}$, I think, but I'm not sure this helps...

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool carpetpool 1 2017-02-22 08:37 jasong jasong 35 2016-12-11 00:57 Lee Yiyuan Miscellaneous Math 31 2012-05-06 17:44 Robert Holmes Math 2 2010-09-22 22:10 Vijay Miscellaneous Math 5 2005-04-09 20:36

All times are UTC. The time now is 14:45.

Fri Apr 23 14:45:32 UTC 2021 up 15 days, 9:26, 0 users, load averages: 2.47, 2.33, 2.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.