Binomial Distribution of Bignumber

HI,
 I hope some of you can help in this.
 Actually my problem is I need to solve the following problem.
(1 + x)^m (mod n, x^r-a)
i.e. mod the coefficient with 'n' and the polynomial with x^r-a


I should be able to tell the coefficient of some x^i, i is any
constant

m,n,a are 30 digits long. Quite big I guess

So, if I try to solve it, first I jump into binomial Coefficient, How
do I solve the binomial coeffiecient for such big numbers,. Lets say I
need to solve

465465464665464646!/245425545533453! I hope you understand what it
is.. that is a big number's factorial divided by another big numbre
factorial.. Humongous task . isnt it..

I am sure there should be a way around to solve this problem.. Do you
guys have any idea, how to solve this division.. I am not supposed to
use any packages. I am supposed to write my own program.. so please
tell me an algorithm, or any sample code..

thanks
LVL 6
ryerrasAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
SpideyModConnect With a Mentor Commented:
PAQ'd and points refunded.

SpideyMod
Community Support Moderator @Experts Exchange
0
 
Mayank SAssociate Director - Product EngineeringCommented:
Try using 'long double' in C/C++. Its got a range till 1.1E+4932.

Mayank.
0
 
pjknibbsCommented:
mayankeagle: Even so, it's never going to be able to cover a factorial of the sort of magnitude reyerras is dealing with.

ryerras: You will probably need to use a specialist maths library to handle numbers of this magnitude--standard C simply won't cut it.
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
benfield1Commented:

Use asymptotic analysis:

when n is large n! ~ (n/e)^n * (2(pi)n)^(1/2)

this should make your programming a lot easier.

Andy
0
 
ryerrasAuthor Commented:
Sorry guys, no one has answered my questions to my satisfaction and infact I found a solution.
 The solution is one has to do repeated squaring starting from a small power and do modular division as you go by recursively, that would always keep the number in manageable condition.
Infact I did finish coding for this problem and successful in obtaining the result in fairly faster time using repeated squaring..

Anyway thanks for the people who took pains to give their opinions.. thanks

0
 
ryerrasAuthor Commented:
To moderator,
 since no one has answered my question, can I cancel the question and preserve my points..?
0
 
pjknibbsCommented:
ryerras: The moderators don't often trawl through questions unless they're very old--if you want them to do something about this question, post a zero-point question in Community Support including a link back here.
0
 
SpideyModCommented:
A request for a refund has been made.  Experts, you have 72 hours to object.

SpideyMod
Community Support Moderator @Experts Exchange
0
All Courses

From novice to tech pro — start learning today.