c++ - GMP-モジュロなしの電力

Question

私は任意に大きな数を任意の大きな累乗に上げようとしています。私が見る限り、GMPにはこれを行う関数がありますが、結果にモジュロを適用し、任意の数をunsigned int指数に上げることができる関数があります。これを回避する方法はありますか？

Answer 1

unsigned intそして、任意の数を指数に上げることができる関数

これはunsigned long int指数であるため、unsigned long64ビット（またはそれ以上）のシステムを使用している場合、今後数年間は利用可能なメモリを超えてしまいます（数2^(2^64-1)エクサバイトのストレージが必要です）.

32 ビットのシステムを使用している場合はunsigned long、指数を 2 つの部分に分割できます。

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 が手足を数えるのに s を使用することです。そのため、通常、いずれにせよビットintを超える数を使用することはできません (プラットフォームに応じて、通常は 32 または 64 です)。(2^31 - 1)*BITS_PER_LIMBBITS_PER_LIMB

a^bwhereが必要でa > 1、bに収まらないと思う場合は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 などのコンピューター代数システムを使用することを意味します (これらすべての名前ですが、ググってください）。