# 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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  bool isPrime(int number) { if(number < 3) throw std::invalid_argument("numbers less than 3 cannot be primes"); // any even number cannot be a prime bool result = number % 2 != 0; for(int divisor = 2; result && divisor < number/2; ++divisor) { result = number % divisor != 0; } return result; } 

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:

  1 2 3 4 5 6 7 8 9 10 11 12 13  bool isPrime_rimpl(int number, int divisor) { return number == divisor ? true : number % divisor == 0 ? false : isPrime_rimpl(number, ++divisor); } bool isPrime_r(int number) { if(number < 3) throw std::invalid_argument("numbers less than 3 cannot be primes"); return isPrime_rimpl(number, 2); } 

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

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30  template struct isPrime_c { private: template struct isEven_c { static const bool value = number1 % 2 == 0; }; template struct isPrime_cimpl { static const bool value = number1 % divisor == 0 ? false : isPrime_cimpl::value; }; template struct isPrime_cimpl { static const bool value = true; }; public: static_assert(number > 2, "numbers less than 3 cannot be primes"); static const bool value = isEven_c::value ? false : isPrime_cimpl::value; }; 

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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  template struct fib_c { static const int value = fib_c::value + fib_c::value; }; template<> struct fib_c<0> { static const int value = 0; }; template<> struct fib_c<1> { static const int value = 1; }; #include int main() { std::cout << fib_c<0>::value << std::endl; std::cout << fib_c<1>::value << std::endl; std::cout << fib_c<2>::value << std::endl; std::cout << fib_c<3>::value << std::endl; std::cout << fib_c<4>::value << std::endl; std::cout << fib_c<5>::value << std::endl; return 0; } 

This is pretty much all I have for this post.