アルゴリズムC/C++：最速の方法で計算する（2^n）及びD 32のまたは64ビット整数

Question

付き％dは

私は私がnおよびD 32又は64と(2^n)%dを計算することを可能にするアルゴリズムを探していますビットの整数。

多精度ライブラリでもメモリに2^nを格納することは不可能ですが、おそらく、32または64ビットの整数を使用して(2^n)%dを計算するというトリックが存在する可能性があります。

ありがとうございました。

Answer 1

Modular Exponentiation algorithmをご覧ください。

2^nを計算するのではなく、代わりに、起動時に係数dを複数回減らします。 That keeps the number small.

Exponentiation by Squaringと組み合わせると、O(log(n))ステップで(2^n)%dを計算することができます。

はここで小さな例です：2^130 % 123 = 40

2^1 % 123 = 2 
2^2 % 123 = 2^2  % 123 = 4 
2^4 % 123 = 4^2  % 123 = 16 
2^8 % 123 = 16^2  % 123 = 10 
2^16 % 123 = 10^2  % 123 = 100 
2^32 % 123 = 100^2 % 123 = 37 
2^65 % 123 = 37^2 * 2 % 123 = 32 
2^130 % 123 = 32^2  % 123 = 40