在编译时计算小整数的阶乘

Question

我刚刚又一次实现了一个递归模板，用于在编译时计算整数的阶乘（谁能想到有一天我真的需要它！）。不过，与其自己写，我去了Boost寻找答案。然而，特殊数学中的阶乘函数明确禁止使用整数类型，所以我只能自己写。

还有，Boost中是否有其他函数可供使用？我应该将我的整数转换为double并使用boost::factorial函数吗？计算是否在编译时执行？

- gnzlbg

---

模板的递归深度有限，因此实际上，在编译时计算阶乘所获得的加速并不是很大（特别是如果您使用动态编程）。 - Luchian Grigore

请查看此问题下“R..”的回答：http://stackoverflow.com/questions/3786207/howto-compute-the-factorial-of-x。溢出很可能是为什么 Boost 不希望您使用 int 进行计算的原因。 - mwigdahl

@mwigdahl 我可以将20！装入一个unsigned long int中，这已经超出了我的需求（然而，检查溢出是我更喜欢使用库函数的原因之一，我的实现没有对其进行检查）。 - gnzlbg

尝试使用增加的模板深度编译您的程序。 - pyCthon

在 g++ 上添加 --ftemplate-depth-200 - pyCthon

@pyCthon 问题在于20！约为2^63，因此21！会产生一个无符号长整型的溢出。这与gcc的递归深度无关。 - gnzlbg

Answer 1

如果您使用的是C++11，那么您不需要Boost，只需一个1行代码即可：

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

即使您的参数不是编译时常量，它也可以工作。对于n < 21，uint64_t将起作用。

如果您在编译时进行操作并与浮点值相乘，则不会有转换开销（转换也将在编译时进行）。

- Leonid Volnitsky

Answer 2

由于整数中只能容纳有限的阶乘值，您可以手动预先计算前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 的参数，那么在启用优化时，编译器应该简单地将函数调用替换为结果。我在 Mac 上使用 XCode 4.4 尝试了上述示例，并在汇编中看到它使用常数 24 初始化 fourFactorial：

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

这种方法可能比使用递归编译时技巧更快地进行编译。

- Emile Cormier