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