c++ - C/C++ 大数計算

Question

Cプログラムで次の数値を計算しようとしています:

result = (3 * pow(2,500000000) - 2 ) % 1000000000

2 の累乗は、適切に処理するには大きすぎます => 結果のサイズを小さくするために、モジュロを使用して計算を多くのステップに分割できるという印象を受けました。誰かがそうするための戦略を持っていますか? 他のアイデアはありますか？

事前にサンクス

マヌー

Answer 1

最も簡単な方法は、各ステップでモジュラスによって減少する二乗を繰り返すことによる累乗です。

unsigned long long mod_pow(unsigned long long base, unsigned long long exponent, unsigned long long modulus)
{
    if (exponent == 0) return 1;
    unsigned long long aux = 1;
    while(exponent > 1) {
        if (exponent % 2 != 0) {
            aux *= base;
            aux %= modulus;
        }
        base *= base;
        base %= modulus;
        exponent /= 2;
    }
    return (base*aux) % modulus;
}

その後、それを使用して計算できます

result = (3*mod_pow(2,500000000,1000000000) - 2) % 1000000000;

この関数は、モジュラスの 2 乗が 64 ビットの範囲を超えないことを前提としています。弾性率が大きいほど、事態はより複雑になります。