mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-08-15, 09:31   #1
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default 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
mickfrancis is offline   Reply With Quote
Old 2016-08-15, 12:05   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-08-15, 12:23   #3
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
mickfrancis is offline   Reply With Quote
Old 2016-08-15, 12:31   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-08-15, 13:08   #5
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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...
mickfrancis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial Coefficients Integer Sets carpetpool carpetpool 1 2017-02-22 08:37
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
Binomial Primes Lee Yiyuan Miscellaneous Math 31 2012-05-06 17:44
Recovering Fourier coefficients of modular forms Robert Holmes Math 2 2010-09-22 22:10
No Notice- Binomial Coefficients, Pascal's triangle Vijay Miscellaneous Math 5 2005-04-09 20:36

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

Tue Dec 1 14:55:33 UTC 2020 up 82 days, 12:06, 2 users, load averages: 1.69, 1.89, 1.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.