Computing factorial small integer at compile time

Question

I just implemented (once again) a recursive template for calculating the factorial of an integer at compile time (who would have thought that someday I would really need it!). Nevertheless, instead of riding on my own, I went to Boost in search of an answer. However, the factor function in special mathematics specifically prohibits its use with integer types, so I just wrote my own.

However, is there another function in Boost that I should use? Should I defer my integer to double and use boost::factorial ? Does compilation run at compile time?

Answer 1

You do not need Boost, this is just a 1-liner if you have C ++ 11:

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

And it will work even if your argument is not a compile-time constant. uint64_t will work with n <21.

If you do this at compile time and multiply by a floating point value, there will be no overhead for the conversion (conversion will also be at compile time).

Answer 2

Since there is a limited number of factorials that can fit into an integer, you can simply pre-calculate the first 20 values ​​manually and save them in a global or static array. Then use a global or static function to find the factorial in the array:

 #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"; } 

If you use a literal as an argument for factorial , then the compiler should simply replace the function call with the result (when optimization is turned on). I tried the above example in Xcode 4.4 (on Mac), and I see in the assembly that it initializes fourFactorial constant 24:

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

This method can lead to faster compilation than using recursive compilation tricks.