T1 = T2 * N から T2 項を効率的に抽出するにはどうすればよいでしょうか。素数指数分析を使用しますか?

この記事では、著者は、固定小数点 bignumber ライブラリを使用して大きな数の階乗を計算する高速かつ正確な方法について説明します。実装に関する繰り返しの質問は、積 T1 = T2 * N! (T1 と N!) からの T2 項の抽出でした。はすでに知られています。 T2 項を見つけるために、著者は素数指数の分析を実施し、それを計算する式を提案しました。

T2(4N) = multiplication(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N/(i^j)) of [(4N/(i^j))%2]]

T2 の部分項には、T2(N) 項内の素数 i に対する指数 e があります。次のように計算されます:

for (e=0,j=N4;j;e+=j&1,j/=p);

ここで、e は指数、p は素数、N4 は4*N

計算された T2 項は階乗の計算を最適化するために使用され、結果として得られるアルゴリズムは ~ O(log(n)) に近い計算量を示します。

最初の 128 階乗についての大まかな時間測定値が提供されます。著者は、この実装をこれ以上単純化することはできず、すでに高度に最適化されていることを認めています。

以上がT1 = T2 * N から T2 項を効率的に抽出するにはどうすればよいでしょうか。素数指数分析を使用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。