常用lisp中計算階乘的最快方法是什麼？

在Common Lisp中計算階乘的最快方法是什麼？首先是尾端遞歸常用lisp中計算階乘的最快方法是什麼？

(defun factorial (n &optional (acc 1)) 
(if (<= n 1) 
    acc 
    (factorial (- n 1) (* acc n))))

但它是最快的方式嗎？

2013-10-01 boucekv

也許你的編譯器足夠聰明，可以將它轉換爲尾遞歸。 – knivil

@knivil：也許編譯器使它成爲一個循環？ –

我懷疑這個問題是特定於Common Lisp的;最快（但是如何定義最快？絕對時間？漸近（O（...））？最少資源密集度？）計算因子的方法在大多數語言/實現中可能是相似的。 –

您已經實現了用於計算階乘的樸素算法。有幾個具有更好的漸進性能，例如參見http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

最快的是基於因子的素因子分解。

2013-10-01 09:16:23 Joni

雖然實際計算的漸近性能是否更好？我瘋狂的猜測是內存分配的成本佔據了足夠大的論據的實際計算量。 –

我不熟悉Lisp;是不是可以在開始時分配必要的內存並使用破壞性操作來修改它？儘管如此，我仍然期望內存分配比整數乘法更便宜，而整數乘法是任何因子算法的緩慢部分。 – Joni

問題是，BigInteger（實際上叫做Lisp中的bignum）是以所需的大小自動分配的，我不知道如何掛鉤到這個過程中。如果你說實際的整數乘法總是慢的部分，我會相信你的，儘管你必須考慮到階乘算法的複雜度計算通常可能對「BigIntegers」/「bignum」的實際成本「盲」秒。 –

回答