计算大数的乘积

Question

我正在尝试计算

,

其中 C_i 是第 i 个加泰罗尼亚数字。

为了解决这个问题，我从 0 循环到 n 并对两个加泰罗尼亚数字的乘积求和：

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

catalan 函数返回二项式系数除以 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：当catalan[i] == catalan[n - i]时，剩下的一半计算结果不会和前半部分一样吗？

Answer 1

您还可以缓存阶乘。

Answer 2

您所描述的计算似乎是计算第 n 个 Catalan Number 的第一个递推关系（而且您也不必要地应用二项式计算，而您可以只使用加泰罗尼亚数字自己在复发）。这是 O(n^2) 复杂度加上所有二项式计算的复杂度。为什么不使用第二个递归关系？

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

Answer 3

您可以做两件事：

首先，检查您序列的 OEIS。你会发现序列有an entry。这个条目有一个有用的公式：

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);

计算大数的乘积

Computing the product of big numbers

c#

algorithm

complexity-theory