Not at the moment as I'm traveling. Sorry. You could start with
http://en.wikipedia.org/wiki/Modular_arithmetic . The references
might be helpful.
I'll illustrate what I"m talking about. Let M=7. Then here is a
table of inverses and checks:
All mod 7 arithmetic
Inverse Check
1 ^ 5 = 1 1 * 1 = 1
2 ^ 5 = 4 4 * 2 = 1
3 ^ 5 = 5 5 * 3 = 1
4 ^ 5 = 2 2 * 4 = 1
5 ^ 5 = 3 3 * 5 = 1
6 ^ 5 = 6 6 * 6 = 1
So if you want to compute say 4 choose 2, it's 4!/(2!2!) = 24 / (2 *
2) = 6 .
The corresponding computation mod 7 is
3 * inv(2) * inv(2) = 3 * 4 * 4 (mod 7) = 5 * 4 (mod 7) = 6
The code is doing this with a modulus of 1000000007 and storing the
first 5000 factorials (mod M) and their inverses in tables to avoid
computing them repeatedly.
On Mar 6, 12:35 am, amrit harry <dabbcomput...@gmail.com> wrote:
> could you refer a number theory book..?
>
> On Tue, Mar 6, 2012 at 7:01 AM, Gene <gene.ress...@gmail.com> wrote:
> > It's a fact from number theory that
>
> > x * (x^(M-2)) = 1 (mod M)
>
> > if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
> > M). It follows by identities of modulo arithmetic that
>
> > n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
>
> > This is what the code is computing. A basic number theory book will
> > cover this stuff in the early chapters.
>
> > On Mar 5, 5:13 am, amrit harry <dabbcomput...@gmail.com> wrote:
> > > #include <cstdio>
>
> > > #define MOD 1000000007
>
> > > int powmod(int base, int expo){
> > > if(expo==0)
> > > return 1;
> > > else if(expo&1)
> > > return (long long)base*powmod(base, expo-1)%MOD;
> > > else{
> > > int root=powmod(base, expo>>1);
> > > return (long long)root*root%MOD;
> > > }
>
> > > }
>
> > > int inverse(int x){
> > > return powmod(x, MOD-2);
>
> > > }
>
> > > void init(){
> > > fact[0]=1;
> > > for(int i=1; i<=5000; i++)
> > > fact[i]=(long long)i*fact[i-1]%MOD;
> > > invfact[5000]=inverse(fact[5000]);
> > > for(int i=5000; i>0; i--)
> > > invfact[i-1]=(long long)i*invfact[i]%MOD;
>
> > > }
>
> > > int nCr(int n, int r){
> > > if(r>n || r<0)
> > > return 0;
> > > return (long long)((long
> > long)fact[n]*invfact[r]%MOD)*invfact[n-r]%MOD;
>
> > > }
>
> > > int main(){
> > > init();
> > > int N, K;
> > > while(scanf("%d %d", &N, &K) && (N||K)){
>
> > > print("%d",nCr(N,K));
> > > }
>
> > > }
>
> > > This is code for calculating binomial cofficient =
> > fact(n)/fact(n-r)*fact(r) value of fact(r)*fact(n-r) lead to overflow so in
> > this code they use a method of calculating inverse of fact. i could not
> > able to understand how inverse function work please explain.
>
> > > Thanks.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> AMRIT
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
