查找因子的有效方法

除正常遞歸函數和循環方法之外，找到一個數的階乘的有效方法是什麼？由於常規方法花費的時間太長而無法產生輸出，因此有什麼方法可以比遞歸方法和循環方法減少時間複雜度？如果不是原因？查找因子的有效方法

2013-08-21 Prabu

您試圖使用階乘來解決您的問題？ – 2013-08-21 12:00:55

見http://www.luschny.de/math/factorial/FastFactorialFunctions.htm – Michael

你有多久？ 'gmp'中的簡單實現可以在我的機器上以0.9秒完成（顯然，不同的處理器/機器將具有不同的性能）。 –

由於79！是1.711E98，你只需要79個數字的列表來使用查找表。 http://www.tsm-resources.com/alists/fact.html整數格式或在科學格式http://home.ccil.org/~remlaps/javascript/jstest1.html，所以它只是「剪切和粘貼」

來源

2013-08-21 12:02:12

查找表正是我所建議的。 –

但是我沒有看到他從哪裏得到79。通過我的計算（可能容易出現一個錯誤），對於32位整數，12個條目應該足夠了;對於64位，20，對於IEEE浮點數34和對於IEEE雙精度值170. –

如果你要計算多因子值，然後緩存值，你走是：的階乘在列選項。

如果你只是一個單一的計算factorial(n)，那麼循環可能是最好的，你可以得到。通過一些循環展開（一次計算兩次或四次乘法），你可能會從處理器中獲得更多的效果，但是它不太可能適用於非常大的階乘，因爲乘法本身就是一系列冗長的指令。

據我所知，沒有「神奇」的數學計算一個12 * 13 * 14 * 15或類似的序列比乘以它們更快。

來源

2013-08-21 12:04:19

'gamma（i-1）== fact（i）'。計算'gamma'並不一定很簡單，但對於大型'i'，它比單純乘法要快得多（並且你沒有得到你在循環中累積的舍入誤差：記住每次你得到一個舍入誤差，它乘以以下所有項）。 –

你只能得到浮點四捨五入的錯誤。浮點數不能超過幾百個左右。 –

約170，爲通常的'雙'。但是使用gamma也應該避免這個問題。（我對「gamma」的計算方式不太瞭解，但快速瀏覽一下g ++庫的源代碼給人的印象是它比'O（n）'快得多，這就是循環的結果。 –

您可以使用Stirling's approximation來評估大因子。

來源

2013-08-21 12:07:06 HAL

當n進入1000的數字類型時，指數，對數等變得相當混亂，因爲它們超出了整數的數值範圍。 –

@MatsPetersson但任何擴展的精度/大小包應該已經擁有它們。使用這種或伽瑪函數的東西肯定會比循環更好，儘管它們在編程上顯然更加複雜。 –

由於您的某條評論說您想查找100000 !,因此此答案涵蓋了很多因子。

如果你並不需要一個確切的答案，你可以使用Stirling's Approximation

如果你想你需要使用一個任意精度的數學包像GMP arbitrary precision math package

來源

2013-08-21 12:12:02

我並不完全相信計算大指數和平方根等等，在大數學中更容易。我的天真的字符串數學方法目前進入12分鐘做100000！（10K相對容易，大約5秒鐘，但隨着數量變長，緩存不夠大，複製需要更長時間等等） –

使用ln（n！）= n * ln（n）-n形式對於n = 10000，我們得到ln（10000！）〜= 82103.所以10000！ = = e^82103〜= 10^35657〜=（2^32）^ 3701（假設我的高中數學並沒有讓我失望）。所以很快得到一個非常粗略的近似值。我同意，如果你想要答案的所有35657數字，斯特林的是不是要走的路。但是現在我們知道我們可以使用GMP在〜3701 4字節的內存字中計算答案。 –

沒有，真的沒有一個確切的答案。如果您關心運行時成本，可以使用查找表（這需要您使用預先計算的值）來降低運行時成本。

要存儲每個因子可能需要太多的內存，所以讓我們存儲每個k：th因子。這需要程序在運行時執行多達k次的乘法運算。

比方說，您的運行時性能要求限制您爲每個階乘1000乘法。那麼你需要預先計算並存儲1000 !, 2000 !, 3000！等等直到你想要支持的上限（可用內存將限制你）。

因爲階乘函數快速變得比原生數據類型大，所以您需要一個可以處理大量數據的類。我假定它存在這樣一個類，它被稱爲BigInteger。

BigInteger preCalculatedValues[] = { new BigInteger("1"), new BigInteger("<value of 1000!>"), and so on... } 

BigInteger factorial(int n) { 
    int pre = n/1000; 
    int i; 
    if (pre > LARGEST_VALUE_HANDLED) { 
    // Either throw an exception or let it take longer. I choose to let it take longer. 
    pre = LARGEST_VALUE_HANDLED; 
    } 
    BigInteger result = preCalculatedValues[pre]; 
    for (i = pre * 1000 + 1; i <= n; i++) { 
    result.multiplyWith(i); // This operation is probably overloaded on the * operator 
    } 
}

來源

2013-08-21 12:30:07

計算非常大factorals的最簡單的方法是使用伽瑪功能。另一方面：它不會像表查詢那樣快（如其他人所建議的那樣）;如果您使用內置的類型，你需要的表：

for 32 bits: 12 entries 
for 64 bits: 20 entries 
for float: 34 entries 
for double: 170 entries

（有可能是一個錯誤上表中的關我寫的代碼非常快速地計算出它們。）

對於double和可能的float，通常的循環方法無論如何可能會引入太多舍入誤差。如果你不想使用一個表，並且你有C++ 11, exp( lgamma( i + 1 ) )應該做的伎倆。（如果你不有C++ 11，你可能有lgamma功能無論如何，它是在C99 。）

如果你正在處理一些類型的延伸範圍類型的，你可能必須實施lgamma（和exp）爲您的類型。

來源

2013-08-21 14:14:08

查找因子的有效方法

回答

相關問題