Finding Number of combinations C(n,r) for large n (Precision of decimal representation)

Question

This is a problem from CodeSprint3 https://cs3.interviewstreet.com/challenges/dashboard/#problem/50877a587c389 Basically the problem is to calculate the number of possible combinations,nCr for given n and r.Also, 1 <= n <= 1000000000 and 0 <= r <= n. Output all answers modulo 142857.

 Since 6C4=6!/4! 2!
        =6*5/2!     
        =6*5/2*1

I thought overflow could be avoided using division at every step.That is to start with value of n (n is 6 in this case). Decrement n and multiply it with previous value (so this becomes 6*5) Perform division with denominator and then decrement it ( 6*5 /2 and denominator 2 becomes 1) Repeat the steps until n is less than the of maximum of 2 denominators and in same number of iterations the divisor (Minimum of denominators will become 1)

   int count(int n,int r)
   {int maxDen=r>(n-r)?r:n-r;      //larger number in the denominator
    int minDen=n-maxDen;           //the smaller number in denominator
    double num=1;
    for(int j=n;j>maxDen;j--)     
     {num=j*num;              //for C(6,4) example num=6*5 and so on   
    // System.out.println("num "+num +" minDen "+minDen);
       num=num/minDen;         //divide num 6*5 in this case by 2
       minDen--;
      }
   num=num%142875;           //output the result modulo 142875
  return (int) num;
}

But perhaps due to loss precision as more divisions are performed,it gives wrong values but then it still gives correct output for some values.As it stands correct for 22 17 but not for 24 17.

(22 17) = 26334 //gives Correct value

(24 17)= 60353 //wrong value correct value is 60390

(25,17)=81450 //wrong value correct value is 81576

(16 15)= 16 //gives correct value

(87 28)= 54384 //wrong value correct value is 141525

I tried to use num as a BigDecimal and as a consequence i had to replace everything with a BigDecimal to perform the operations.The output then was the same for the inputs which gave correct results in above code.But for inputs which gave wrong results,the program throws an exception

 Exception in thread "main" **java.lang.ArithmeticException: Non-terminating   decimal  expansion; no exact representable decimal result.**
at java.math.BigDecimal.divide(Unknown Source)
at Combination.NcRcount2.count(NcRcount2.java:16)
at Combination.NcRcount2.main(NcRcount2.java:37)

Line 16 is num=num.divide(minDen); //in replacement to earlier used num/minDen,both num and minDen are BigDecimal in this case

Even though if the number does not have an exact decimal representation,given the arbitrary precision of BigDecimal the error in results would have been minimized if it didn't threw an exception. ** If the result of division on floats or doubles does not have an exact decimal representation then why isn't an exception thrown?**

I verified the results using BigDecimal with the dynamic programming approach as

   C(n,r)=C(n-1,r-1)+C(n-1,r)

This works correctly in all cases as it appears to me but there must be a better way

  BigDecimal Comb (int n, int k)
   {  if(k>n-k)
       k=n-k;
       BigDecimal B[][]=new BigDecimal[n+1] [k+1];

    for (int i = 0; i <= n; i++)
   { int min;
     if(i>=k)
      min=k;
    else
     min=i;
   for (int j = 0; j <= min; j++)
    { if (j == 0 || j == i)
           B[i][j] =new BigDecimal(1);
       else{ 
           if(j>i-j)
            B[i][j]=B[i][i-j];
            else
            B[i][j] = B[i - 1][j - 1].add(B[i - 1] [j]);
          }
    }
 }
BigDecimal div=new BigDecimal(142857);
return B[n][k].remainder(div);
}

Please suggest me a better way to do this without using BigDecimal

Something tells me that "*Output all answers modulo 142857*" is much, much more important here, not only for output. Try to take advantage of it *during* the computation. — Tomasz Nurkiewicz, Nov 05 '12 at 22:14
Duplicate of [Binomial coefficient modulo 142857](http://stackoverflow.com/questions/13106587) which has an adequate answer — James Waldby - jwpat7, Nov 05 '12 at 22:26
Thanks for the link.Yes that's and adequate answer-courtesy of some great mathematicians.But i would like someone to answer how to 'minimize' the loss of precision in general — rakesh99, Nov 05 '12 at 23:01

score 2 · Answer 1 · edited Dec 25 '13 at 21:18

public class Solution {

public static void main(String arg[]) {
    Scanner s = new Scanner(System.in);
    List<BigInteger> ar = new ArrayList<BigInteger>();
    int tot = Integer.parseInt(s.nextLine());
    BigInteger max = BigInteger.ZERO;
    for (int i = 0; i < tot; i++) {
        String str[] = s.nextLine().split(" ");
        Long n1 = Long.parseLong(str[0]);
        Long r1 = Long.parseLong(str[1]);
        Long nr1 = n1 - r1;
        BigInteger n = BigInteger.valueOf(n1);
        BigInteger r = BigInteger.valueOf(r1);
        BigInteger nr = BigInteger.valueOf(nr1);
        ar.add(n);
        ar.add(r);
        ar.add(nr);
        if (n.compareTo(max)==1) {
                max=n;
        }
        if (r.compareTo(max)==1) {
            max=r;
        }
        if (nr.compareTo(max)==1) {
            max=nr;
        }

    }
    HashMap<BigInteger,BigInteger> m=new HashMap<BigInteger,BigInteger>();
    m.put(BigInteger.ZERO, BigInteger.ONE);
    BigInteger fact=BigInteger.ONE;
for(BigInteger i=BigInteger.ONE;i.compareTo(max.add(BigInteger.ONE))==-1;i=i.add(BigInteger.ONE)){
    fact=fact.multiply(i);
    if(ar.contains(i)){
        m.put(i, fact);
    }
}

for(int i=0;i<ar.size();i=i+3){
    BigInteger n=m.get(ar.get(i));
    BigInteger r=m.get(ar.get(i+1));
    BigInteger nr=m.get(ar.get(i+2));
    BigInteger rem=r.multiply(nr);
    BigInteger act=n.divide(rem);
    BigInteger res=act.remainder(BigInteger.valueOf(142857));
    System.out.println(res);
}

}

}

I think this code might will help you .

score 1 · Answer 2 · answered Aug 02 '14 at 21:32

Rather straightforward implementation:

public long combinations(int n, int k) {
    BigInteger factorialN = factorial(n);
    BigInteger factorialK = factorial(k);
    BigInteger factorialNMinusK = factorial(n - k);
    return factorialN.divide(factorialK.multiply(factorialNMinusK)).longValue();;
}

private BigInteger factorial(int n) {
    BigInteger ret = BigInteger.ONE;
    for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i));
    return ret;
}

score 0 · Answer 3 · answered Nov 06 '12 at 03:12

The part of your question about an exception with BigDecimal code isn't clear to me so I won't comment on that.

Regarding a sequence of multiplies and divides to compute nCr, wikipedia shows a formula that's easy to implement. Your first section of code in the question might be equivalent to it, as may be the bit of python code just below. It computes up to 61C30 using 64-bit integer arithmetic; 62C31 requires another bit or two.

def D(n, k):
    c, j, k = 1, n, min(k,n-k)
    for i in range(1,k+1):
        c, j = c*j/i, j-1
    return c

The reason that this order of computation works, with all divisions being exact divisions, is that nC(j+1) = nCj * (n-j)/(j+1) as is easily verified from nCj = n!/j!(n-j)! and some algebra. That is, you can compute nCr for large n and r completely in integer arithmetic without needing any decimal places.

Suppose K=142857. Note that reduction of intermediate terms modulo K will cause problems and may be infeasible. If the numerator is reduced mod K, some divisions won't be exact in ordinary arithmetic. If K were prime, the extended GCD algorithm could be used to find inverses mod K for all numbers. But K=3*9*11*13*37 and inverses mod K will not exist for numbers that are multiples of 3, 11, 13, or 37, as a consequence of Bézout's lemma and some modular algebra.

Yes if we start dividing from 1 instead min(n,n-r) we can always keep the results integral.Since java has 32 bit integers the result overflows for (30,15).The question about BigDecimal was that since it has arbitrarily high precision if it went on with the calculation instead of throwing an exception when the quotient doesn't have an exact decimal representation the final result would have been more closer.So why does it throw an exception in such a case where division of two doubles or two floats doesn't — rakesh99, Nov 06 '12 at 14:53

Suzan Cioc · Answer 4 · 2013-12-25T23:26:19.560

You should not divide.

Draw Pascal triangle in memory. This will require only additions and will easily allow to apply modular arithmetic.

Also, this will last not longer than with divisions, because you can not avoid of calculating factorials.

package tests.StackOverflow;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class q13241166 {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s;
        String[] ss;
        int[] n;
        int[] r;
        int T;

        /*
        System.out.println("Input T:");
        s = in.readLine();
        T = Integer.parseInt(s);

        if( T < 1 || T > 100000) {
            throw new IllegalArgumentException();
        }
        */
        T = 9;

        /*
        n = new int[T];
        r = new int[T];

        System.out.println("Input n r pairs:");
        for(int i=0; i<T; ++i) {
            s = in.readLine();
            ss = s.split("\\s+");

            n[i] = Integer.parseInt(ss[0]);
            if( n[i] < 1 || n[i] > 1000000000) {
                throw new IllegalArgumentException();
            }

            r[i] = Integer.parseInt(ss[1]);
            if( r[i] < 0 || r[i] > n[i]) {
                throw new IllegalArgumentException();
            }

        }
        */
        n = new int[] {2, 4, 5, 10, 22, 24, 25, 16, 87};
        r = new int[] {1, 0, 2, 3, 17, 17, 17, 15, 28};


        int modulobase = 142857;
        int[] answers_old, answers = null;
        System.out.println("Output");
        for(int i=0; i<T; ++i) {
            for( int nn=0; nn<=n[i]; ++nn) {
                answers_old = answers;
                answers = new int[nn+1];
                for( int rr=0; rr<=nn; ++rr) {
                    if( rr == 0 || rr == nn ) {
                        answers[rr] = 1;
                    }
                    else {
                        answers[rr] = answers_old[rr-1] + answers_old[rr];
                    }

                    answers[rr] %= modulobase;
                }
            }

            System.out.println(answers[r[i]]);

        }



    }


}

Output follows:

Finding Number of combinations C(n,r) for large n (Precision of decimal representation)

4 Answers4