Fast algorithm to calculate large n! mod 2³²

Question

I want to calculate the exact value of N! mod 2³². N can be up to 2³¹

Any language is fine but I would appreciate detailed explanation of algorithm. Time limit is < 1 sec

Answer 1

In python:

if n > 33:
  return 0
else
  return reduce(lambda x, y: x*y, range(1, n+1)) % 2**32

Justification:

We know that 34! is divisible by 2³² because in the sequence:

1 * 2 * 3 * 4 * ... * 34

there are:

17 multiples of 2
 8 multiples of 4
 4 multiples of 8
 2 multiples of 16
 1 multiple  of 32
--
32 multiplications by 2

It's a factor of every larger factorial, so all the larger ones are 0 mod 2³²

For small values of N, if you don't have bignum arithmetic available, you can do the individual multiplications mod 2³², and/or you can prefactor the power of 2 in the factorial, which is easy to compute (see above).

Answer 2

Calculate the factorial normally (multiply the numbers 1,2,3,...), performing the modulo after each multiplication. This will give you the result for small values of N.

For larger values of N, do the same. Pretty soon, your intermediate result will be 0, and then you can stop the loop immediately and return 0. The point at which you stop will be relatively fast: For N == 64 the result will already be 0 because the product of 1..64 contains 32 even numbers and is therefore divisible by 2^32. The actual minimal value of N where you get 0 will be less than 64.

Answer 3

In general, you can implement algorithms modulo small powers of two without bignums or modular reduction using the integer types (int, long) available in most programming languages. For modulo 2³² you would use a 32-bit int. "Integer overflow" takes care of the modular arithmetic.

In this case, since there are only 34 distinct results, a lookup table may be faster than computing the factorial, assuming the factorials are used often enough that the table gets loaded into the CPU cache. The execution time will be measured in microseconds.

Answer 4

When multiplying 2 numbers of arbitrary length, the lower bits are always exact because it doesn't depend on high order bits. That's how 2-adic or p-adic multiplication works. Basically a×b mod m = [(a mod m)×(b mod m)] mod m so to do N! mod m just do

1×2×...×N mod m = (...(((1×2 mod m)×3 mod m)×4 mod m)...)×N mod m

Modulo 2ⁿ is a special case because getting the modulus is rather easy with an AND operation. Modulo 2³² is even more special because all unsigned operations in C and most C-like languages are reduced modulo 2³² for a 32-bit unsigned type

As a result you can just multiply the numbers in a twice-as-wide type then after that AND with 2³² - 1 to get the modulus

uint32_t p = 1;
for (uint64_t i = 1; i <= n && p /* early exit because product = 0 */; i++)
    p = uint32_t(p*i); // or p = p*i & 0xFFFFFFFFU;
return p;

Answer 5

Calculating a modulo is a very fast operation, especially the modulo of a power of 2. A multiplication is very costly in comparison.

The fastest algorithm would factorize the factors of the factorial in prime numbers (which is very fast since the numbers are smaller than 33). And get the result by multiplying all of them together, by taking the modulo in between each multiplication, and starting with the big numbers.

E.g.: to calculate 10! mod 2³²: use de Polignac's formula, to get the prime factors of 10! which gives you :

10! = 7 * 5 * 5 * 3 * 3 * 3 * 3 * 2 ...

this would be faster than the basic algorithm, because calculating (29! mod 2³²) X 30 is much harder than multiplying by 5, 3 and 2, and taking the modulo in between each time.