计算nCr模142857的最有效方法

Question

我想计算在模142857下的nCr。以下是我在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);
}

这个算法可以在O(r)时间内计算nCr。我希望能有一个比这更快的算法来得到结果。是否有这样的算法？

- Jainendra

---

http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficientDouble%28int,%20int%29 - jrey

你可能想查看这个链接：https://dev59.com/_3A65IYBdhLWcg3w-jum。如果你使用`double`进行计算，当`n`足够大时，你将失去精度并得到错误的答案，而在模算术下应该有一个确切的答案。使用`BigInteger`会更好，但是该链接可能提供了一种更有效的方法。 - ajb

@Jaguar 哇，如果 n 可以变得那么大，我甚至认为 double 已经不足以容纳中间结果了。 - ajb

@JasonC 142857不是质数，标记为重复的问题假设这个数字是质数。 - Jainendra

我找不到任何输入值，使得在达到无穷大之前计算需要显著的时间。因此优化是毫无意义的。特别是当Math.ulp(l)比142857更大时，取模运算将更早地失去有用的结果。 - Holger

Answer 1

你可以预先计算给定的n和r对应的结果，并将其硬编码在表格int t[][]中。

后来，在运行时，当您需要nCr(n, r)时，只需查找此表：t[n][r]。

这在运行时是O(1)。

- Adam Stelmaszczyk

---

我的猜测是，这个值的范围太大了，不太可行。 - Bernhard Barker

Answer 2

由于您的数字不是质数，this answer 不适用。但是您可以轻松地将 142857 分解为质数，计算相应的模数，并使用中国剩余定理来获得您的结果。对于您正在处理的数字，这可能有意义，也可能没有意义。

在任何情况下，您必须避免双倍，除非您可以确定所有中间结果都可以用仅有 53 位表示（否则会失去精度并得到一个无意义的结果）。

- maaartinus

---

非常好的回答！您能详细说明如何使用中国剩余定理来解决这个问题吗？您有关于如何使用它来解决这个问题的任何来源吗？ - PlsWork

Answer 3

你已经在提到的函数中有大部分答案了。如果n是固定的，r是可变的，那么可以使用nCr = nC(r-1) * (n - r + 1) / r。因此，您可以使用一个表格来存储nCr并递增地构建它（与其他答案提到的预计算不同）。

因此，您的新函数可以通过传递一个表格来进行递归调用。

- user1952500