Увеличение производительности при выполнении расчетов с огромными числами (BigInteger)

Question

Я менее опытный программист, выполняющий упражнение, в котором мне нужно рассчитать произведение двух каталонских последовательностей для каждого n-Значение между 0 а также 5000 а затем обобщить эти продукты.

В настоящее время код выводит правильный ответ, но для его запуска требуется 2,9-3,3 секунды. n-ценность 5000, Моя цель - заставить код работать менее чем за 3 секунды каждый раз, поэтому мне нужно набрать около половины секунды.

Наибольшее число в расчете (10,000!) кончено 35,000 цифры так долго int или же long не может быть использован для каких-либо более тяжелых расчетов, а также я не могу использовать какие-либо внешние библиотеки, что в значительной степени оставляет меня с BigInteger,

Из испытаний я обнаружил, что for-loop в sum()ниже показано то, что длится дольше всего (~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

Мне нужно рассчитать произведение двух каталонских последовательностей для каждого отдельного n-значения от 0 до 5000, а затем суммировать эти продукты.

Ну, это как раз альтернативное определение каталонского числа.

C_{n + 1} =_{СУММА i = 0..n} (C_i * C_ni)

Итак, что вам в основном нужно, это рассчитать 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 сек. Наслаждайтесь!