Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17


Binomial Distribution of Bignumber

Posted on 2003-03-17
Medium Priority
Last Modified: 2010-04-17
 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

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..

Question by:ryerras
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
  • +2
LVL 30

Expert Comment

by:Mayank S
ID: 8157686
Try using 'long double' in C/C++. Its got a range till 1.1E+4932.

LVL 12

Expert Comment

ID: 8158891
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.

Expert Comment

ID: 8159729

Use asymptotic analysis:

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

this should make your programming a lot easier.

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.


Author Comment

ID: 8266126
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


Author Comment

ID: 8266131
To moderator,
 since no one has answered my question, can I cancel the question and preserve my points..?
LVL 12

Expert Comment

ID: 8267500
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.

Expert Comment

ID: 8271730
A request for a refund has been made.  Experts, you have 72 hours to object.

Community Support Moderator @Experts Exchange

Accepted Solution

SpideyMod earned 0 total points
ID: 8292798
PAQ'd and points refunded.

Community Support Moderator @Experts Exchange

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

722 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question