c++ - GMP-无模功率

Question

我试图将任意大的数字提高到任意大的功率。据我所见，GMP 有一个函数可以做到这一点，但对结果进行模运算，还有一个函数可以让我将任意数字提升为unsigned int指数。有没有解决的办法？

Answer 1

和一个让我将任意数字提高到unsigned int指数的函数

这是一个unsigned long int指数，所以如果你在一个unsigned long64 位（或更多）的系统上，这将使你在接下来的几年中超出可用内存（2^(2^64-1)需要几个艾字节存储）。

如果您使用的是 32-bit 系统unsigned long，则可以将指数分成两部分，

if (exponent >= (1u << 31)) {
    mpz_pow_ui(base, base, exponent >> 31);
    mpz_pow_ui(base, base, 1u << 31);
}
mpz_pow_ui(base, base, exponent & ((1u << 31) - 1));

这很有可能需要比你更多的内存。

另一个问题是 GMP 使用ints 来计算肢体，所以通常你不能使用超过(2^31 - 1)*BITS_PER_LIMB位的数字（BITS_PER_LIMB通常是 32 或 64，具体取决于平台）。

如果你认为你需要a^bwherea > 1并且b不适合 in unsigned long (long)，那么无论如何你都会遇到 GMP 和你的记忆问题。

Answer 2

通过将一个非常大的数提高到非常大的幂，您会得到非常多的位数。

可能比计算机内存空间更多的数字。

例如，这台笔记本电脑有一个 6 GB 的主内存，这意味着 6*2^30 位。现在，如果将 (2^10) 提高到 (2^10) 次方，则得到 2^(10*(2^10)) = 2^10240。这比 6*2^30 多很多倍。

简而言之，如果您想要一个一般情况的确切答案，就没有办法了。

但是，对于特定情况，您可能能够将答案表达为例如 2^10240 之类的干净幂，但这意味着仅使用人脑或计算机代数系统，例如 Macsyma 或 Matehmatica（我不确定所有这些的名称，但谷歌它）。