 mersenneforum.org > Math Fast calculation of binomial coefficients
 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 (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 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

838410 Posts Quote:
 Originally Posted by mickfrancis If I know (mod m), is there a way of calculating (mod m) with time complexity better than ? 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

23×7 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 , and I can't see how to calculate this in better than - 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 , and I can't see how to calculate this in better than - 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 , I think, but I'm not sure this helps...  Thread Tools Show Printable Version Email this Page 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:55.

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