CODEWITHSUNDEEP
algorithmbigintegermodulofactorial
user2129227
user2129227

Reputation: 97

Fast algorithm to calculate large n! mod 2³²

I want to calculate the exact value of N! mod 232. N can be up to 231

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

Upvotes: 4

Views: 3365

Answers (5)

phuclv
phuclv

Reputation: 41753

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 2n is a special case because getting the modulus is rather easy with an AND operation. Modulo 232 is even more special because all unsigned operations in C and most C-like languages are reduced modulo 232 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 232 - 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;

Upvotes: 0

bruce_ricard
bruce_ricard

Reputation: 771

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 232: 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 232) X 30 is much harder than multiplying by 5, 3 and 2, and taking the modulo in between each time.

Upvotes: -1

Joni
Joni

Reputation: 111219

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 232 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.

Upvotes: 1

rici
rici

Reputation: 241671

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 232 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 232

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

Upvotes: 22

interjay
interjay

Reputation: 110059

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.

Upvotes: 6

Related Questions