私に間違った結果を与えるバイナリ・パワー化

Question

バイナリ・パワー・オン機能に問題があります。乗算の実行中に結果を含む変数がオーバーフローし、誤った結果が返されます。ソース値が4,312,952,827より大きい場合に発生します。だから私はこの問題をどのように解決するのですか？ここに私の機能のコードがあります。

unsigned long long binpow(unsigned long long a, unsigned long long n, unsigned long long m) 
{ 
    unsigned long long res; 
    res=1; 
    while (n) 
    { 
     if (n & 1) 
     { 
      res=(res*a)%m; 
      n--; 
     } 
     a=(a*a)%m; 
     n >>= 1; 
    } 
    return res; 
} 

Answer 1

あなたの残基及び弾性率の両方が（mだけシフト）unsigned long longの幅を超えています。

unsigned __int128のようなコンパイラ拡張タイプを使用すると問題が解決され、4,312,952,827に対して正しい結果が得られます。

unsigned __int128 binpow(unsigned __int128 a, unsigned __int128 n, unsigned __int128 m) 
{ 
    unsigned __int128 res; 
    res = 1; 
    while (n) 
     { 
      if (n & 1) 
       { 
        res = (res*a)%m; 
        n--; 
       } 
      a = (a*a) % m; 
      n >>= 1; 
     } 
    return res; 
} 

また、あなたは安全な方法で大量に仕事をしたい場合は、gmplib

Answer 2

のような汎用BIGNUMライブラリがある表現a*aは元のサイズの2倍である部屋が必要です。あなたのシナリオでは4,312,952,827 > 2^32-1、従ってあなたはunsigned long longの範囲外です。

モジュラ指数のバイナリラダーを実装するための経験則は、引数のデータ型の少なくとも2倍の範囲で算術演算を実行できるため、場合によっては128ビットです。