在編譯時計算一個小整數的階乘

我剛剛實現（再次）一個遞歸模板，用於在編譯時計算一個整數的階乘（誰曾想過有一天我真的需要它！）。儘管如此，我並沒有自己動手，而是去Boost尋找答案。然而，特殊數學中的階乘函數特別禁止使用整數類型，所以我只寫了自己的。在編譯時計算一個小整數的階乘

不過，我應該使用Boost中的另一個函數嗎？我應該投我的整數double並使用boost::factorial函數？計算是在編譯時執行的嗎？

來源

2012-07-31 gnzlbg

有將在哪個模板可以在編譯時計算階乘改乘，所以IRL增速有限的深度不是很大（尤其是如果你使用動態編程）。 – 2012-07-31 17:59:13

參見「R ..」的下這個問題的迴應：http://stackoverflow.com/questions/3786207/howto-compute-the-factorial-of-x。溢出很可能爲什麼Boost不希望你爲此使用int。 – mwigdahl 2012-07-31 18:02:16

@mwigdahl我最多可以容納20人！爲unsigned long int類型，比什麼，我需要更多的（但是，檢查溢出將是這促使我使用的庫函數喜歡的原因之一，我的實現不檢查的話）。 – gnzlbg 2012-07-31 18:23:49

你不需要加速，這僅僅是1班輪，如果你有C++ 11：

constexpr uint64_t factorial(uint64_t n) { 
    return n == 0 ? 1 : n * factorial(n-1); 
}

即使你的arg是不編譯時間常數過它會奏效。如果你在編譯時使用浮點值並且乘以浮點值 - 不會有轉換開銷（轉換也是在編譯時）。

來源

2012-07-31 18:20:49

由於有可以容納一個整數內部階乘的有限數量的，可以簡單地用手預先計算第一20個值，並將它們存儲在全局或靜態陣列。然後使用一個全局或靜態函數查找數組中的階乘：

#include <iostream> 

const int factorials[] = 
{ 
    1, 
    1, 
    2, 
    6, 
    24, 
    // etc... 
}; 

inline const int factorial(int n) {return factorials[n];} 

int main() 
{ 
    static const int fourFactorial = factorial(4); 
    std::cout << "4! = " << fourFactorial << "\n"; 
}

如果您使用文字作爲參數傳遞給factorial，則編譯器應該簡單地與結果替代函數調用（在啓用優化之後）。不是通過使用遞歸編譯時

.loc 1 20 38 ## /Users/emile/Dev/sandbox/sandbox/main.cpp:20:38 
movl $24, __ZZ4mainE13fourFactorial(%rip)

該方法可以導致更快的彙編：我試圖在XCode中4.4（在Mac）上面的例子中，我的，因爲它與所述恆定24初始化fourFactorial組裝見招數。

來源

2012-07-31 20:43:15

在編譯時計算一個小整數的階乘

回答

相關問題