@Dipit: Here's how you would do it by hand:
B(1000,10) = 1000*999*998*997*996*995*994*993*992*991 /
(1*2*3*4*5*6*7*8*9*10).
We know that the result is an integer, so all of the terms in the
denominator are factors of the numerator. Do some cancelling: 10
cancels 1000 to 100, 9 cancels 999 to 111, 8 cancels 992 to 124, 7
cancels 997 to 142, etc. One way to do the cancelling gives the
result
B(1000,10) = 25*37*499*997*83*199*71*993*496*991.
Thus B(1000,10) mod P = (25*37*499*997*83*199*71*993*496*991) mod P
= ((((((((25*37) mod P)*499) mod P)*997) mod P)...)*991) mod P
Here is some pseudocode to calculate B(m,n) mod P
declare arrays num[n] and den[n]
for i = 1 to n do
num[i] = n + 1 - i
den[i] = i
end for i
for i = 2 to n do
for j = 1 to n do
k = GCD(num[j],den[i]) // GCD = Greatest common divisor
num[j] = num[j] / k
den[i] = den[i] / k
if( den[i] = 1 ) break out of the for j loop
end for j
end for i
result = num[1]
for j = 2 to n do
result = (result * num[j]) mod P
end for j
In the above, I'm assuming that m*P and result will fit in an integer.
Dave
On Nov 2, 8:08 am, Dipit Grover <[email protected]> wrote:
> Hi everyone, I am stuck at places where I need to find lets say
> Binomial_coefficient(1000,10) mod 1000 000 007 . What is the best way to do
> this, assuming we donot have sufficient memory to use the naive approach :
> (n,r) = (n-1,r) + (n-1,r-1) .
>
> --
> Dipit Grover
> B.Tech in Computer Science and Engineering - lllrd year
> IIT Roorkee, India
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
