Вычисление произведения больших чисел

Question

Я пытаюсь вычислить

,

, где C _i - это i-й каталонский номер.

Чтобы решитьпроблема, я делаю петлю от 0 до n и суммирую произведение двух каталонских чисел:

BigInteger catalanSum = 0;
            for (int i = 0; i <= n; i++)
                catalanSum += catalan(i) * catalan(n - i);

Функция каталона возвращает биномиальный коэффициент, деленный на n + 1:

    BigInteger catalan(int n)
    {
        return NchooseK(2 * n, n) / (n + 1);
    }

И для вычисления биномиального коэффициента я использую эту функцию:

    BigInteger NchooseK(int n, int k)
    {
        BigInteger res = 1;

        if (k > n - k)
            k = n - k;

        for (int i = 0; i < k; ++i)
        {
            res *= (n - i);
            res /= (i + 1);
        }
        return res;
    }

Он отлично работает до n = 1000, но как только он становится выше, он действительно сильно замедляется.Можно ли как-нибудь оптимизировать этот расчет?

РЕДАКТИРОВАТЬ:

Я ускорил вычисления, сначала сохранив каталонцы, используя следующий фрагмент кода, благодаря ответу xanatos:

BigInteger[] catalans = new BigInteger[n+1];
            BigInteger catalanSum = 0;
            for (int i = 0; i <= n; i++)
                catalans[i] = catalan(i); 
            for (int i = 0; i <= n; i++)
                catalanSum += catalans[i] * catalans[n - i];

РЕДАКТИРОВАТЬ 2: Когда каталанский [i] == каталанский [n - i], разве оставшаяся половина вычислений не будет иметь тот же продукт, что и первая половина?

Answer 1

Вычисление, которое вы описываете, похоже на первое рекуррентное соотношение для вычисления n th каталонского числа (и вы также без необходимости применяете биномиальное вычисление, когда можете просто использовать сами каталонские числав повторении).Это сложность O (n ^ 2) плюс сложность для всех биномиальных вычислений.Почему бы не использовать второе отношение повторения?

catalan(0) = 1
catalan(n + 1) = 2*(2*n + 1) / (n + 2) * n

Answer 2

Вы можете сделать две вещи:

Сначала проверьте OEIS для своей последовательности.Вы обнаружите, что последовательность имеет запись .И эта запись имеет полезную формулу:

2*(2*n-1)*a(n-1) = (n+1)*a(n)

Итак, вычисление каталонских чисел может быть сделано гораздо эффективнее:

BigInteger lastCatalan = 1;
catalans[0] = lastCatalan;    
for(int i = 1; i <= n; ++i)
{
    lastCatalan = (2 * (2 * i - 1) * lastCatalan) / (i + 1);
    catalans[i] = lastCatalan;
}

Второе - то, что ваше суммирование симметрично.То есть, вам просто нужно сложить половину записей:

BigInteger catalanSum = 0;
for (int i = 0; i < (n + 1) / 2; i++)
    catalanSum += catalans[i] * catalans[n - i];
catalanSum = 2 * catalanSum;
if (n % 2 == 0)
    catalanSum += catalans[n / 2] * catalans[n / 2];

После того, как גלעד ברקן указал, что сумма, которую вы ищете, является n+1 -ым каталонским числом, это может быть существенно упрощено:

BigInteger catalanSum= 1;
for(int i = 1; i <= n + 1; ++i)
    catalanSum = (2 * (2 * i - 1) * catalanSum) / (i + 1);

Answer 3

Вы также можете кэшировать факториалы.