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 runtime-recursive 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 20-23.
Finally for consistency with recursive implementation, there is a complie-time 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 non-sensical 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 -ftemplate-depth-4096 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.