回覆列表
  • 1 # 使用者185057792109

    4500太小了,不必動用近似,直接暴力算也不到一秒。(實踐表明,不僅不用一秒,連0.1秒都不用,人都反應不過來手機就能算出來……另一位答主跑了個13ms)

    如果是(10^8)!那有近似的價值

    借另一位答主的公式

    這個θ其實與n有關,先暴力算0~10000的階乘打個θ~n表,然後擬合一下,再反代,大概能有幾十位的精度。

    當然也可以理論分析得到θ~n的關係

    前幾項是θ=

    1-1/(30*n^2)+1/(105*n^4)

    -1/(140*n^6)+……

    既然知道是多項式,當然可以直接用拉格朗日差值法去插θ~1/n的關係

    如果記θ~n關係為函式θ(x)的話,

    θ(x)/12x=

    B是伯努利數。

    不過這交錯級數收斂速度真令人難受(其實還行,多算一項大概能多logn位至2logn位的精度吧),有沒有大佬給變成不交錯的……

    ……然而,由於要算(1/n)的若干次方(雖然也可以只取前若干位,這樣這部分的複雜度是“常數”),這個演算法在精度和時間複雜度的綜合性能上恐怕還沒有每次乘法都只保留前若干位好(答主HOOCCOOH)……容易證明大約每次保留前m+logn位即可(m是精度位數,n是n!的n)。

    這樣每次只需要計算(m+logn)位與logn位的乘法,複雜度(用fft)是約(m+2logn)*log(m+2logn),和差不多o(loglogn)的指數上的加法,姑且算成o(1)好了。這樣總的複雜度是n*(m+2logn)*log(m+2logn)吧。這樣只要不是超大數階乘(10^1000+),計算前一千位大概只用o(n)的時間誒。

    另有用logi求和得到log(n!)進而得到n!的演算法(答主sam),如果要求m位的精度,logi應保留到m+logn位,這樣要進行n次m+logn位與m+logn位的加法,單次複雜度m+logn,總複雜度約n*(m+logn),不過求logi的前m+logm位應該也不是o(1)吧。

  • 中秋節和大豐收的關聯?
  • 如何培養創造能力?