-2

Does anyone know a method for computing the quantity of 

n! mod M

such that overflow is not an issue? I cannot think of anything where such a large value of n would not cause a problem.

Nathan Hughes
  • 94,330
  • 19
  • 181
  • 276
user3277598
  • 7
  • 3
  • 1
    Well, I didn't until I did a search with google ;) [Stack Overflow: How to Ask](http://stackoverflow.com/questions/how-to-ask). – Andrew Morton May 01 '14 at 17:52

2 Answers2

3

Assuming that n * (n-1) does not overflow, you can just take the product mod M after every multiplication.

Update: As Dukeling very patiently explained to me, the assumption above is not a sufficient condition to ensure that method of applying mod M after each multiplication will guarantee no overflow.

The sufficient condition is that (M-1)*(n mod M) does not overflow, because that is the largest possible product that could result before the mod is taken.

merlin2011
  • 71,677
  • 44
  • 195
  • 329
  • It should be more like `(M-1)*(n mod M)` that shouldn't overflow. Consider `5! mod 30` with an overflow at `50`. `5*4 << 50`, yet it overflows. – Bernhard Barker May 01 '14 at 21:51
  • The biggest number you can get `mod M` is `M-1`. `M` should also be fine. For a more exact bound you can probably replace `n` by `n-1` as well. – Bernhard Barker May 01 '14 at 22:03
  • `M-1` is the biggest number, thus also the biggest product, that can exist post-mod, multiplying that by the biggest single number `n`, gives you the biggest product pre-mod. – Bernhard Barker May 01 '14 at 22:07
  • @Dukeling, Please write a separate answer. I am not following how finding the biggest product pre-mod is going to enable you to compute `n!`. – merlin2011 May 01 '14 at 22:09
  • I don't think I can explain it much better than I already did. I was just pointing out that `n * (n-1)` in your answer is wrong and should be `(M-1)*(n mod M)` instead - it's not an answer in itself, it's a correction to yours. – Bernhard Barker May 01 '14 at 22:12
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/51842/discussion-between-merlin2011-and-dukeling) – merlin2011 May 01 '14 at 22:15
0

If you use a Big Integer library, it will never overflow. However, depending on the algorithm and the number of digits you want, it might take years to execute.

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501