Computing the factorial of a small integer at compile time

Question

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?

There's a limited depth at which a template can recurse to, so IRL the speedup from computing the factorial at compile-time isn't that great (esp. if you use dynamic programming). — Luchian Grigore, Jul 31 '12 at 17:59
See "R.."'s response under this question: http://stackoverflow.com/questions/3786207/howto-compute-the-factorial-of-x. Overflow is very likely why Boost doesn't want you to use an int for this. — mwigdahl, Jul 31 '12 at 18:02
@mwigdahl I can fit up to 20! into an unsigned long int which is more than what I need (however, checking for overflow would be one of the reasons that push me to prefer using a library function, my implementation does not check for it). — gnzlbg, Jul 31 '12 at 18:23
@pyCthon the problem is that 20! is approx 2^63 so 21! produces an overflow of unsigned long it. It has nothing to do with the recursion depth of gcc. — gnzlbg, Aug 01 '12 at 21:42

Leonid Volnitsky · Accepted Answer · 2014-10-10T21:49:59.697

9

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).

edited Oct 10 '14 at 21:49

answered Jul 31 '12 at 18:20

Leonid Volnitsky

8,854
5
38
53

score 3 · Answer 2 · answered Jul 31 '12 at 20:43

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.

Computing the factorial of a small integer at compile time

2 Answers2

Linked