Series:
1. C++ Template Metaprogramming
2. C++ Template Metaprogramming Part 2 of n
This is second in series and I would like to expand on thinking recursively in this part, before than introducing other concepts. For this post lets create a template metaprogram to check if given number is prime or not.
This a standard iterative implementation of checking whether the number is prime:


All highlighted lines have one or more terminating conditions for computation. Line 4 checks for valid input, 7 filters out all even numbers. Line 9 ensures we terminate if have tried a lot of divisors (number/2 is the last thing we want to try) and 11 checks whether number is a multiple of divisor.
Given this it is implement a recursive equivalent with said terminating conditions:


The terminating conditions are similar, in here one is less optimal I am not checking for divisor being half of number, but all the way to the number. This does not has any impact on the result. Will compute a bit more.
Now that we have a working recursive implementation, coming up with template metaprogram is trivial. First of all the impl portion is very specific to evaluation so this is moved inside the template isPrime_c


Checking for even number is an optimization – isEven_c. At line 15 we check that whether the number is multiple of divisor or not. There is a subtle difference here as compared to recursive implementation: in runtimerecursive impl we checked for number being equal to divisor, else number % divisor would be 0. But in templates we have a partial specialization for this case – line 2023.
Finally for consistency with recursive implementation, there is a complietime error if the number is less than 3 – Line 26.
One thing to note is if you put in large number like 991 (yes it’s a prime number), then your code may fail to compile due to compiler crashing or some other nonsensical error message. Typically what this means is your compiler has exceeded template instantiation depth (we are doing recursion here..). The way around this is to compile using ftemplatedepth4096 option to gcc or clang. I haven’t checked this on Visual Studio, but I am sure there would be some way to extend template instantiation depth there as well.
On parting thought I would throw in a Template MetaProgram to evaluate fibnoacci sequence:


This is pretty much all I have for this post.
Related Reading