0

I found this snippet of code that calculates $n! \bmod m$ iteratively.

long long x = 1;
for (int i = 2; i <= n; i++) {
x = (x*i)%m;
}
cout << x%m;

Now, I'm still new to modular arithemtic. I know that $(a\cdot b) \bmod m = (a \bmod m \cdot b \bmod m ) \bmod m$.

But the code doesn't seem to be doing this. The code is doing:

$x = (1 \cdot2) \bmod m $

$x = (2 \cdot3) \bmod m $

$x = (6 \cdot4) \bmod m $

etc...

Where does the rule come into play in this code? Shouldn't we be doing x = x * (i % m) ?

user821
  • 124

2 Answers2

1

The code is correct. (Though it is often computationally faster for large $n$ to reduce $i\%m$ then multiply then reduce again $\%m$ again.)

$$ ab \mod(m)=(a \mod(m) \cdot b\mod(m))\mod(m)$$

That is you can do reduction step before the multiplication or after if you prefer. Let me give you an example:

Suppose you wanted to calculate 34*47 mod(10), you can either calculate 34*47=1598 and then reduce mod(10) hence $34*47\equiv 8\mod(10)$

Or you can reduce then multiply then reduce $$34*47\equiv 4*7=28\equiv8\mod(10)$$

Hope this helps

Dan Sheppard
  • 76
1

You are free to use any variant,

$$\begin{align}(ab)\bmod m&=(a(b\bmod m))\bmod m \\&=((a\bmod m)b)\bmod m \\&=((a\bmod m)(b\bmod m))\bmod m.\end{align}$$ You can even take the modulo only every now and then.

Using $x:=x\cdot(i\bmod m)$ would be a double mistake because

  • that does not avoid $x$ becoming large,

  • as, when $n\ge m$, we have $n!\bmod m=0$, $i$ will never exceed $m$ and the modulo is of no use.