Hi

I am looking for an efficient way to calculate ((a+b)!/a!b!) mod p. p is prime.

for example if a=10 and b=7 and p=3 then we need to find (17!/10!.7!) mod 3
answer =2

The above can be reduced to (17.16.15.14.13.12.11/7.6.5.4.3.2.1) mod 3

The problem i am facing is a and b can have a very high value i.e 1<=a<=1000000000 and 1<=b<=1000000000 and value of p is say 531169.
So how would i programmatically calculate the value, since intermediary calculations might overflow an int variable( i am using c++).
Since (a/b)mod p != ((a%p)/(b%p)) mod p. Right ?

Is there a trick involved ?

Thanks for your patience
Regards
lali

Sounds like homework.

1000000000! is a pretty big number. none of the basic data types in c/c++ can handle big value. consider using a library for that, here http://gmplib.org/

You might find some of the ideas here to be useful.

You definitely need a big number library for C/C++, or use bc which has arbitrary precision. Hint: Think of the difference in results between using libraries which support arbitrary number SIZE, and using a floating point library which would introduce a limit on PRECISION... (did I get that right?).

My first thoughts as programmer would be to craft a carefully designed recursive algorithm for the job... good luck!

EDIT:
Thinking about this has stirred a few brain cells that I have not recently used, but the key for such a problem (once you have the right numeric types libraries in place) will be a tail-recursive algorithm as explained in this article on Tail Recursion. This is what I had in mind with my comment about using a carefully designed recursive algorithm for the job. And it should be simple for a factorial calculation - I thinks...

If you write a tail-recursive algorithm for the factorials using the big number libraries, it will be optimized into a very efficient iterative function by the compiler (gcc can handle this AFAIK).
Hope this points you in a good direction!
/EDIT: