Repeat Swap: Overflow Prevention

Question

Background:

Given n balls such that:

 'a' balls are of colour GREEN 'b' balls are of colour BLUE 'c' balls are of colour RED ... 

(of course a + b + c + ... = n )

The number of permutations in which these balls can be located is determined as follows:

 perm = n! / (a! b! c! ..) 

Question 1: How can I "gracefully" calculate perm to avoid integer overflow for as long as possible, and make sure that when I finish the calculation, I either have the correct perm value, or do I know that the final result will overflow?

Basically, I want to avoid using something like the GNU GMP.

Optional, question 2: Is this a really bad idea, and should I just go and use GMP?

Answer 1

If you have processor time globes, you can create lists from all factorials, and then find the primary factorization of all numbers in the lists, and then undo all the numbers on the top with those at the bottom, until the numbers are completely reduced.

Answer 2

They are known as polynomial coefficients, which I will denote by m(a,b,...) .

And you can efficiently compute them, avoiding overflow, using this identity (which should be pretty simple to prove):

 m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ... m(0,0,0,...) = 1 // base case m(anything negative) = 0 // base case 2 

Then it's just a matter of using recursion to compute the coefficients. Note that in order to avoid exponential runtimes, you need to either cache your results (to avoid recalculation) or use dynamic programming.

To check for overflow, just make sure the amounts will not be overflow.

And yes, it is a very bad idea to use arbitrary precision libraries to accomplish this simple task.

Answer 3

The most crowded way is the one suggested by Dave. You will find the exponent with which the prime p divides n! on summation

 m = n; e = 0; do{ m /= p; e += m; }while(m > 0); 

Subtract the exponents p in the factorizations a! etc. Do this for all primes <= n , and you have factorization of the multinomial coefficient. This calculation overflows if and only if the end result is overflowed. But polynomial coefficients grow quite quickly, so you will already have overflow for quite small n . For substantial calculations, you will need the bignum library (if you do not need accurate results, you can get a little longer using double s).

Even if you use the bignum library, you should keep the intermediate results too large, so instead of calculating factorials and dividing huge numbers, it's better to calculate the parts in a sequence,

 n!/(a! * b! * c! * ...) = n! / (a! * (na)!) * (na)! / (b! * (nab)!) * ... 

and calculate each of these factors, take the second to illustrate,

 (na)! / (b! * (nab)!) = \prod_{i = 1}^b (n-a+1-i)/i 

calculated using

 prod = 1 for i = 1 to b prod = prod * (n-a+1-i) prod = prod / i 

Finally, multiply the parts. This requires n divisions and n + number_of_parts - 1 multiplications, keeping intermediate results moderately small.

Answer 4

According to this link, you can calculate polynomial coefficients as the product of several binomial coefficients, controlling the overflow of integers on the way.

This reduces the initial task to a binomial coefficient controlled by overflow.

Answer 5

Designations: n! = prod(1,n) n! = prod(1,n) , where prod you can guess what it does.

It is very simple, but first you should know that for any 2 positive integers (i, n > 0) this expression is a positive integer:

 prod(i,i+n-1)/prod(1,n) 

So the idea is to slice the computation of n! in small pieces and split as soon as possible.

With a , than with b and so on.

 perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!) 

Each of these factors is an integer, therefore, if perm will not overflow, none of its factors will do.

Although when calculating such a factor there may be an overflow in the numerator or denominator, but this avoids multiplication in the numerator, and then on the alternative:

 prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b 

Thus, each division will give an integer.