在进行大量计算时提高性能 (BigInteger)

Question

我是一个经验不足的编码员，我正在做一个练习，我需要为 0 和 5000 之间的每个 n 值计算两个 catalan sequences 的乘积然后总结那些产品。

代码当前输出正确答案，但需要 2.9-3.3 秒才能运行，n 值为 5000。我的目标是让代码每次都在 3 秒内达到运行，所以我需要获得大约半秒的时间。

计算中的最大数字 (10,000!) 超过 35,000 位，因此 int 或 long 不能用于任何较重的计算，我也不能使用任何外部库，这让我几乎只剩下 BigInteger.

通过测试，我发现下面显示的 sum() 中的 for-loop 是迄今为止完成时间最长的部分（约占运行时间的 85%），所以这就是性能提升可能是最需要的。任何有关如何优化它的提示都将受到赞赏。

// For all n-values
for (int k=0; k < n/2 + rest; k++) {
    result = result.add(catalan(k).multiply(catalan(n-k)));
}

完整代码如下：

import java.math.BigInteger;
import java.util.Scanner;

public class FactorialSum {

    static BigInteger[] bigInt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            int n = sc.nextInt();

            // Creates a new array and initializes the default values
            bigInt = new BigInteger[n*2+1];
            bigInt[0] = BigInteger.ONE;
            if (n > 0)
                bigInt[1] = BigInteger.ONE;

            calcFactorials(n);

            // Calculates and prints the results
            System.out.println(sum(n));
        } finally {
            sc.close();
        }
    }

    // Calculates and stores all the factorials up to and including the specified n-value
    private static void calcFactorials(int n) {
        for (int factor = 2; factor <= n*2; factor++) {
            bigInt[factor] = bigInt[factor-1].multiply(BigInteger.valueOf(factor));
        }
    }

    // Calculates the catalan number using the binomial coefficient for the
    // specified n-value
    private static BigInteger catalan(int n) {
        BigInteger binomial = bigInt[n*2].divide(bigInt[n].pow(2));
        BigInteger cn = binomial.divide(BigInteger.valueOf(n+1));
        return cn;
    }

    // Calculates the sum for the specified range 0-n
    private static BigInteger sum(int n) {
        if (n > 0) {
            BigInteger result = BigInteger.ZERO;
            int rest = n % 2;

            // For all n-values
            for (int k=0; k < n/2 + rest; k++) {
                result = result.add(catalan(k).multiply(catalan(n-k)));
            }
            result = result.multiply(BigInteger.valueOf(2));

            // For even n-values
            if (rest == 0) {
                BigInteger lastNumber = catalan(n/2);
                result = result.add(lastNumber.pow(2));
            }
            return result;
        } else {
            return BigInteger.ONE;
        }
    }
}

Answer 1

I need to calculate the product of two catalan sequences for every single n-value between 0 and 5000 and then summarize those products.

嗯，这正是 Catalan number 的另一种定义。

C_n+1 = SUM_i=0..n ( C_i * C_n-i )

所以，你基本上需要的是计算C₅₀₀₁。为了快速计算它，您可以使用另一个递归关系：

C_n+1 = 2*(2n+1) / (n+2) * C_n

程序如下：

public static void main(String[] args) {
    int n = 5000;

    BigInteger Cn = BigInteger.ONE;
    for (int i = 0; i <= n; i++) {
        Cn = Cn.multiply(BigInteger.valueOf(4 * i + 2)).divide(BigInteger.valueOf(i + 2));
    }

    System.out.println(Cn);
}

在我的笔记本电脑上运行不到 0.04 秒。享受吧！

在进行大量计算时提高性能 (BigInteger)

Increasing performance when doing calculations with huge numbers (BigInteger)

java

performance

biginteger

factorial

catalan