CODEWITHSUNDEEP
c++mathmodulo
cosmin-andrei paraschiv
cosmin-andrei paraschiv

Reputation: 35

N! modulo algorithm

So , from what i have read on the internet , modulo can do this:

(a*b) % n = (a % n * b % n)%n;

Which i understand because a%n * b%n can be bigger than n , so we have to take modulo n again.But i don't get n! mod p.Algorithm from internet:

int result = 1;
for (int i = 1 ; i <= n ; i++)
{
   result = (result * i ) % p;
}
cout<<result;
  Let's say n = 3 , and p is 7.
When i = 1 , result = 1 % 7 ,
when i = 2 , result = (1%7 * 2) % 7 , and when i = 3 ,
result =((1%7*2) % 7 * 3) % 7.

I don't really see the connection between my first statement and this result.From what i see , for n = 2 , n! % 7 should be (1 % 7 * 2 % 7 ) % 7 , not as the algorithm would do it:(1 % 7 * 2 ) % 7. I know the algorithm is right and i am missing something...Can anyone help me?

Upvotes: 0

Views: 104

Answers (1)

vmp
vmp

Reputation: 2420

Mathematically they are the same but the computer has a limited number of bits to represent numbers and if you exceed that limit you will get unexpected results.

See the following example:

Imagine the maximum value that could be stored is 200 and you wanted to compute X * Y % 100.

Lets try some values for X and Y:

  1. X = 103 and Y = 98 ==> 3 * 98 > 296 OVERFLOW
  2. X = 103 and Y = 103 ==> 3 * 3 > 9 OK

In case 2, if you take the modulus of both before multiplying, you get a result below 200. But if you only take from one variable, you would have 309 % 200, but 309 would become some twisted value since the type can only represent up to 200.

In case 1, you would have to come up with another strategy (maybe a bigger type or transform your multiplication into sums) because the result of the multiplication would extrapolate the 200 limit.

Upvotes: 1

Related Questions