Computing the factorial of a small integer at comp

问题:

I just implemented (once again) a recursive template for computing the factorial of an integer at compile time (who would had thought that some day I'll actually need it!). Still, instead of rolling my own, I went to Boost looking for an answer. However, the factorial function in special math specifically forbids its use with integer types, so I just wrote my own.

Still, is there another function in Boost that I should use? Should I cast my integer to double and use the boost::factorial function? Is the computation performed at compile time?

回答1:

You don't need Boost, this is just 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 arg is not compile time constant too. uint64_t will work with n < 21.

If you are doing it in compile time and multiply with floating point value - there will be no conversion overhead (conversion will be at compile time too).

回答2:

Since there are a limited number of factorials that can fit inside an integer, you can simply pre-compute the first 20 values by hand and store them in a global or static array. Then use a global or static function to lookup 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 to factorial, then the compiler should simply substitute the function call with the result (when optimization is enabled). I have tried the above example in XCode 4.4 (on a Mac) and I see in the assembly that it initializes fourFactorial with the constant 24:

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

This method may result in faster compilation than by using recursive compile-time tricks.