C++ template factorial computation

Question

Say I have this code:

template <int n>
class Factorial
{
    public:
        static const int f = Factorial<n-1>::f*n;
};
template<>
class Factorial<0>
{
    public:
        static const int f =1;
};

It's a template that's meant to compute a factorial. It should be computed at compile time. Is it generally reasonable (specifically: quicker) to perform computations via templates at compile time? P.S. Sorry if this has been asked and answered before, I searched for this particualr question and only found similar ones.

What sorts of things do you want to compute at compile-time? Many worthwhile ones are too complicated to do with templates in the first place. — Ry-, Aug 10 '14 at 15:57
Simple ones, probably. Let's not go further than arithmetic-based things; finding a factorial is just a lot of multiplying. — Chiffa, Aug 10 '14 at 16:00
quicker than what? If you compare to run time, well they are faster to run and slower to compile. — dornhege, Aug 10 '14 at 16:00
Compile time computation isn't quicker from most perspective: It's harder/slower to write the code, and the same computation takes more time (because template evaluation is not as fast as compiled and optimized code). You also lose on executable size which is also important and can affect performance too. The only thing you gain is that you don't have to do the computation at run time. Plus, most interesting computations *can't* be done at compile time. — , Aug 10 '14 at 16:00
@NicholasM, how so? To delnan: thanks, that's about the extent of what I wished to know. — Chiffa, Aug 10 '14 at 16:03
@delnan: You won't lose anything on executable size or performance: const stuff is compiled into constants, and not instantiated classes are not added to the binary. — Maxim Razin, Aug 10 '14 at 16:05
Assuming a current compiler, computations like this can be done much more easily with a `constexpr` function. As a rule, these also avoid the horrendously slow compile times you frequently get from deeply recursive TMP. — Jerry Coffin, Aug 10 '14 at 16:06
Yes, constexpr is much more readable: `constexpr int factorial(int i) { return i<=1 ? 1 : i * factorial(i-1); }` — Maxim Razin, Aug 10 '14 at 16:08
@JerryCoffin, so the bottom-line should be "re-write the whole thing as a `constexpr`"? — Chiffa, Aug 10 '14 at 16:09
With a 64-bit unsigned integral type you can compute 20! and not one bit more. Not worth the effort. Just precompute a small table once (or pirate it off teh interwebs). — n. m. could be an AI, Aug 10 '14 at 16:13
@Chiffa: Assuming your compiler supports it, yes, a `constexpr` is almost always preferable to TMP (for things that both can do--TMP can still do type-oriented "stuff" that `constexpr` simply can't). — Jerry Coffin, Aug 10 '14 at 16:14
@Chiffa: still hardly worth the effort for n!. In any case, I think it's worth to remember that the moment you need *any* kind of run-time input, the template solution will quickly lose its attractiveness. Just how would you implement a function like `int GetFactorial() { int input; std::cin >> input; /* ??? */ return result; }` You'd end up creating a huge switch statement along the lines of `case 8: return Factorial<8>::f;`. — Christian Hackl, Aug 10 '14 at 16:20
Indeed. But the aim was to get all my numbers at compile time; this application shouldn't read `int` inputs and return factorials, it's more of a PoC. — Chiffa, Aug 10 '14 at 16:26

score 4 · Accepted Answer · edited May 23 '17 at 12:05

If you can compute something at compile time, you should do that, unless this complicates your code a lot. Generally, the compiler will compute constant sub-expressions at compile time for you. The computation that you show, however, is different, because it uses templates as a Turing-complete programming system.

This particular template is meant to provide a trivial demo of how to compute something at compile time. The program looks very much like a Prolog program: it consists of a trivial base case and a recursive reduction step. The problem with programs of this kind is that they are remarkably hard to understand. Although there are situations when compile-time computations help you build reliable software, the applicability of these methods is limited because of significant maintenance liabilities that they create.

At the moment I'm writing code that in all probability will be both heavily commented and also read by me and me alone, which empowers me to use all kinds of esoteric techniques. Having said that, thanks for the general coding style/maintainability advice. — Chiffa, Aug 10 '14 at 16:12

C++ template factorial computation

1 Answers1