我們如何有效地從 T1 = T2 * N 中提取 T2 項！使用素指數分析？

在本文中，作者討論了一種使用定點大數庫快速準確地計算大數階乘的方法。關於實現的一個反覆出現的問題是從乘積 T1 = T2 * N! 中提取 T2 項，其中 T1 和 N!是已知的。為了找到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中文網其他相關文章！