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:

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:

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

template<int number> struct isPrime_c { private: template<int number1> struct isEven_c { static const bool value = number1 % 2 == 0; }; template<int number1, int divisor> struct isPrime_cimpl { static const bool value = number1 % divisor == 0 ? false : isPrime_cimpl<number1, divisor + 1>::value; }; template<int number1> struct isPrime_cimpl<number1, number1> { static const bool value = true; }; public: static_assert(number > 2, "numbers less than 3 cannot be primes"); static const bool value = isEven_c<number>::value ? false : isPrime_cimpl<number,2>::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:

template<int idx> struct fib_c { static const int value = fib_c<idx-1>::value + fib_c<idx-2>::value; }; template<> struct fib_c<0> { static const int value = 0; }; template<> struct fib_c<1> { static const int value = 1; }; #include <iostream> 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.

Related Reading

C++ Templates (nullptr.me)