从 (n^j) 计算 (n + 1)^j 的最快方法

Question

我需要为一些非常大的 k 和 j（都在几百万级）计算 0^j、1^j、...、k^j。我正在使用 GMP 来处理大整数（是的，我需要整数，因为我需要完全精确）。现在，我想知道，当我完成 n^j 的计算后，是否有一种方法可以加快 (n + 1)^j 的计算速度，而不是从头开始？

这是我目前用来计算功率的算法：

mpz_class pow(unsigned long int b, unsigned long int e)
{
    mpz_class res = 1;
    mpz_class m = b;

    while(e)
    {
        if(e & 1)
        {
            res *= m;   
        }

        e >>= 1;
        m *= m;
    }

    return res;
}

正如你所看到的，我每次都从头开始，这需要很多时间。

Answer 1

您可能希望将 (n+1)^j 的二项展开式用作 n^j + jn^(j-1)+j(j-1 )/2 * n^(j-2) +... + 1 并记住已计算的较低幂次，并通过加法在 O(n) 时间内重新使用它们来计算 (n+1)^j 。如果您在添加每个项时递增地计算系数 j、j*(j-1)/2,...，也可以在 O(n) 中完成。

Answer 2

要计算 n^j，为什么不至少找到 n 的一个因子，比如说 k 执行 n^j = k^j * (n/k)^j？在计算 n^j 时，k^j 和 (n/k)^j 都应该是已知的。

然而，上述 n 可能需要 O(sqrt(n)) 时间。正如您在上面的代码中提到的，我们在 O(log(j)) 时间内通过 Exponentiation by Squaring 独立计算了 n^j。

因此，您可以混合使用以上各项，具体取决于哪个较大：

如果 n 比 log(j) 小很多，通过因式分解计算 n^j。
每当 n^j 已知时计算 {(2*n)^j, (3*n)^j, ..., ((n-1)*n)^j, n * n^j} 并将其保存在查找中 table.
如果n大于log(j)，并且无法按上述方法进行计算，请使用对数法，然后按上述方法计算其他相关幂。
如果n是2的纯次方（可能const time computation），通过移位计算j次方并计算相关求和。
如果n是偶数（再次计算常量时间），使用因式分解法并计算相关积。

以上内容应该会很快。例如，偶数本身的识别应该将一半的幂计算转换为乘法。可以找到更多关于因式分解的经验法则，可以进一步减少计算量（特别是对于被 3、7 等整除）

从 (n^j) 计算 (n + 1)^j 的最快方法

Fastest way to compute (n + 1)^j from (n^j)

algorithm

pow