C++ Template Metaprogramming Part 2 of n

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)