用於計算階乘的快速算法

我發現this page描述了用於計算階乘的多種算法。不幸的是，解釋很簡單，我不想通過逐行掃描源代碼來理解算法背後的基本原理。用於計算階乘的快速算法

任何人都可以指出我對這些（或其他快速）算法的更詳細的描述來計算階乘嗎？

編輯：This page描述了素因子分解的方法，這是所有性能最好的因子算法通用的技術。它還包含一些Python中很好的示例代碼。作者鏈接到a description of binary splitting，並引用算法雜誌（「關於計算因子的複雜性」）的文章，看起來很有前途，如果我只能得到它的話。

來源

2009-11-17 ThisSuitIsBlackNot

如果你的因子很大，並且你想要一個近似值，不要忘記斯特林的近似值。我注意到它沒有在該頁面中提及。 http://en.wikipedia.org/wiki/Stirling%27s_approximation – Rooke 2009-11-17 20:02:29

@Rooke：我正在計算大的因式分解......或許我應該在我的問題上更清楚。還是）感謝你的建議！ – ThisSuitIsBlackNot 2009-11-17 21:16:43

你也可以試試我的[Fast exact bigint factorial]（https://stackoverflow.com/a/18333853/2521214） – Spektre 2017-12-28 09:47:31

查看Richard Fateman的paper (PDF link)。代碼示例在Lisp中，但是在任何情況下，大部分祕密歸結爲最小化必須完成的bignum（任意精度整數）計算的次數。

當然，如果你不需要/有白葡萄酒，它是微不足道的;查找表或簡單的循環都可以。

編輯：如果你可以使用一個大概的答案，您可以直接通過總結log(k)爲k = 2 ... n，或使用古老的Stirling approximation計算階乘的對數。您希望儘可能使用對數來避免溢出;特別是斯特林近似的天真應用會在許多不需要的地方溢出。

來源

2009-11-17 20:03:44 Pillsy

+1：這篇文章非常有幫助（雖然我的Lisp有點生疏）。不幸的是，看起來Luschny是更復雜算法的首選人員，所以我可能會被困在他的源代碼中。 – ThisSuitIsBlackNot 2009-11-17 21:13:56

還有另一種方法。這種方法是詳細的here，減半乘以一點點的加法和減法。你可能想要顯示第一個方法，如果你能理解，顯示的第二個方法是一個有趣的閱讀。

來源

2013-04-15 02:01:36 user2035846

用於計算階乘的快速算法

回答

相關問題