Most efficient way to calculate nCr modulo 142857

Question

I want to calculate nCr modulo 142857. Following is my code in Java:

private static int nCr2(int n, int r) {
    if (n == r || r == 0) {
        return 1;
    }
    double l = 1;
    if (n - r < r) {
        r = n - r;
    }
    for (int i = 0; i < r; i++) {
        l *= (n - i);
        l /= (i + 1);
    }
    return (int) (l % 142857);
}

This gives nCr in O(r) time. I want an algorithm to get the result in less time than this. Is there such an algorithm?

http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficientDouble%28int,%20int%29 — jrey, Nov 06 '13 at 17:36
What is your typical range for n and r? Also do you tend to compute many similar n,r pairs in groups, I.e. could you benefit from having a small cache of recently computed values? — Jason C, Nov 06 '13 at 17:42
You might want to check out [this](http://stackoverflow.com/questions/3537360/calculating-binomial-coefficient-nck-for-large-n-k). I'm concerned that if you're using a `double` to do the calculation, you will lose precision and get the wrong answer if `n` is large enough, when an exact answer should be available using modular arithmetic. Using `BigInteger` would be better, but the link may give a more efficient way. — ajb, Nov 06 '13 at 17:46
@Jaguar Wow. If `n` can get that large then I don't even think a `double` is big enough to hold the intermediate results. — ajb, Nov 06 '13 at 17:52
@JasonC 142857 is not prime number, the question marked as duplicate assumes that this number is prime — Jainendra, Nov 06 '13 at 17:57
I can’t find any input value for which the computation will take significant time before infinity is reached. So optimizing is pointless. Especially as `Math.ulp(l)` will be greater than `142857` even earlier so the modulo does not provide useful results then. — Holger, Nov 06 '13 at 18:01
Just to concretize: when `n=1000000000` a value of `r=3` is enough to get a `double` value that is too large to provide a correct integer modulo. For `n=1000` the limit is exceeded for `r=9`. In other words, we are talking about nanoseconds here. — Holger, Nov 06 '13 at 18:31
@Holger: You're right, but using `double` here is the problem. Without it, you can compute results for much bigger values (and it might make sense). — maaartinus, Nov 07 '13 at 08:52
@maaartinus: what do you mean with “without it”? Not using `double` is not a solution; it just means using something else which you didn’t name. I would really like to know which alternative you have in mind for solving the task for `n=1000000000` and a significantly high number for `r`. — Holger, Nov 07 '13 at 09:01
@Holger: You could always use `BigInteger`. It would be pretty slow, but it would help. For really big numbers, you could use the solution from my answer (and you could be sure that all intermediate results fit in long easily). — maaartinus, Nov 07 '13 at 09:08
@maaartinus: using `BigInteger` is not an option if the computation requires more RAM than real-life computers have or just does not complete before the end of the computer’s lifetime. I guess, you never tried the questioner’s simple algorithm with `BigInteger`… However, I did not say that there were no solutions. But the questioner came up with some code which must be considered completely broken regarding the use case he described and asked about *performance*. *That* made no sense. — Holger, Nov 07 '13 at 09:16
With `BigInteger` it seems to take much longer that I'd expect, but the memory is no problem, a few GB must do. I'm actually trying Guava's `BigIntegerMath.binomial` and it takes 3 minutes for 1e6 over 5e5. Here, the CRT solution would rule. And agreed that the OP was computing a complete non-sense! — maaartinus, Nov 07 '13 at 09:30

score 1 · Accepted Answer · answered Nov 06 '13 at 17:41

1

You can precompute results for given n and r pairs and hard-code them in the table int t[][].

Later, during run-time, when you need nCr(n, r), you just make a look-up to this table: t[n][r].

This is O(1) during run-time.

answered Nov 06 '13 at 17:41

Adam Stelmaszczyk

19,665
4
70
110

1

My guess is that the range of values is too large for this to be viable. – Bernhard Barker Nov 06 '13 at 17:46

score 1 · Answer 2 · edited May 23 '17 at 11:51

1

As your number is no prime, this answer doesn't apply. But you could easily decompose 142857 into primes, compute the corresponding moduli, and use the Chinese Remainder Theorem to get your result. This may or may not make sense for numbers you're working with.

In any case you must avoid double, unless you can be sure that all your intermediate results can be represented exactly with only 53 bits (otherwise you lose precision and get a non-sense out).

edited May 23 '17 at 11:51

Community

1
1

answered Nov 07 '13 at 09:05

maaartinus

44,714
32
161
320

Excellent answer! Could you elaborate on how to use the Chinese remainder theorem to solve this problem, do you have any sources on how to use it to solve this problem? – PlsWork Jun 29 '17 at 17:09

score 0 · Answer 3 · answered Nov 06 '13 at 20:20

You already have most of the answer in the function that you mention. If n is fixed and r is variable, you can use nCr = nC(r-1) * (n - r + 1) / r. So you can use a table for nCr and build it incrementally (unlike what the other answer mentions where precomputation is not incremental).

So your new function can be made recursive with a table being passed.

Most efficient way to calculate nCr modulo 142857

3 Answers3