algorithm - 大きなnを計算するための高速アルゴリズム！mod2³²

Question

Nの正確な値を計算したい！mod232 。^_ Nは最大231まで^可能

どの言語でも構いませんが、アルゴリズムの詳細な説明をいただければ幸いです。制限時間は1秒未満です

Answer 1

パイソンでは：

if n > 33:
  return 0
else
  return reduce(lambda x, y: x*y, range(1, n+1)) % 2**32

理由:

私たちは34を知っています！^{は 2 32}で割り切れます。

1 * 2 * 3 * 4 * ... * 34

がある：

17 multiples of 2
 8 multiples of 4
 4 multiples of 8
 2 multiples of 16
 1 multiple  of 32
--
32 multiplications by 2

これはすべてのより大きな階乗の因子であるため、より大きな階乗はすべて 0 mod 2 ^32です。

N の値が小さい場合、bignum 算術が利用できない場合は、個々の乗算 mod 2 ³²を実行するか、階乗で 2 のべき乗を事前に因数分解することができます。これは簡単に計算できます (上記を参照)。

Answer 2

階乗を通常どおりに計算し (数値 1、2、3、... を乗算します)、各乗算の後にモジュロを実行します。これにより、 の値が小さい場合の結果が得られますN。

の値が大きい場合はN、同じことを行います。すぐに中間結果が になり0、すぐにループを停止して を返すことができます0。停止するポイントは比較的速くなります。 の積には 32 個の偶数が含まれ、したがって で割り切れるためN == 64、結果はすでに になります。0 を取得する実際の最小値は64 未満になります。01..642^32N

Answer 3

任意の長さの 2 つの数値を乗算する場合、上位ビットに依存しないため、下位ビットは常に正確です。基本的には a×b mod m = [(a mod m)×(b mod m)] mod mなのでN! 改造するだけ

1×2×...×N mod m = (...(((1×2 mod m)×3 mod m)×4 mod m)...)×N mod m

モジュロ 2 ⁿは特殊なケースです。なぜなら、演算でモジュラスを取得するのはかなり簡単だからANDです。Modulo 2 ³²は、C およびほとんどの C に似た言語のすべての符号なし演算が32 ビット符号なし型のmodulo 2 ³²に縮小されるため、さらに特別です。

その結果、数値を 2 倍の幅の型で乗算し、その後AND2 ³² - 1 を掛けてモジュラスを取得できます。

uint64_t p = 1;
for (uint32_t i = 1; i <= n; i++)
    p = p*i & 0xFFFFFFFFU;
return p;

Answer 4

モジュロの計算、特に 2 の累乗のモジュロは非常に高速です。これに比べて、乗算は非常にコストがかかります。

最速のアルゴリズムは、階乗の因数を素数で因数分解します (数が 33 より小さいため、これは非常に高速です)。そして、それらすべてを掛け合わせ、各掛け算の間にモジュロを取り、大きな数から始めて、結果を取得します。

例: 10 を計算するには! mod 2 ³² : 10 の素因数を取得するには、de Polignac の公式を使用します。あなたを与える：

10！= 7 * 5 * 5 * 3 * 3 * 3 * 3 * 2 ...

^{(29! mod 2 32} ) X 30 を計算するのは、5、3、2 を掛けて、その間にモジュロを入れるよりもはるかに難しいため、これは基本的なアルゴリズムよりも高速です。