Compile time primality test

The powerful template mechanism of C++ allows us to write pretty complex Meta Functions, which are executed by the compiler during compilation. There are two basic types of meta-functions: one whose result is a type (mainly dealt with by Boost.MPL), and the other is a compile-time computation (which can result in any compile time constant). In this post we will review an example of the latter.

We would like to achieve a compile time boolean constant of the form is_prime::res. The problem with such meta programming task, in my opinion, is that it requires a functional programming mindset. Something that we, as C++ programmers, aren’t necessarily used to. But I am sure we will be able to tackle it anyway.

The algorithm we are going to implement is something along the lines of the following imperative code snippet:

#include <cmath>

bool is_prime (unsigned n) {
    if (n<2) return false;
    for (unsigned i=2;i<=std::sqrt(n);++i)
        if (!(n%i)) return false;
    return true;
}

As always when programming is involved, we shall start from the bottom and go up; Create all of our needed basic building blocks first, so we will be able to utilize them later to build the whole application. Let us start with computing the square root of a given number:

// our numeric type, to allow easy modification later
typedef unsigned number;

// square root computation, using binary search
template <number num, number begin = 0, number end = num>
class sqrt {
        const static number mid = (begin+end) / 2;
        const static number midsqr = mid * mid;
    public:
        const static number res = sqrt<num,
                        (midsqr<num)?mid+1:begin,
                        (midsqr<num)?end:mid>::res;
};

// specialization to stop recursion
template <number num, number lim>
struct sqrt<num, lim, lim> {
    const static number res = lim;
};

The proposed implementation uses a binary search to look for the square root (or the closest integer) of the given number. Note that if we didn’t employ a binary search approach, the depth of the recursive template instantiation would have been too much for the compiler to handle (even for the example presented here). Since we are using a binary search, the complexity is O(logn) instead of O(n) – which makes a great difference.

Now we shall approach the problem of going over all the possible dividers of the given number (up to its square root), to see if any of them can successfully divide our (prime) candidate:

// check if a certain number has any dividers within the range
template <number num, number begin = 2, number end = sqrt<num>::res>
struct has_any_divs {
    const static bool res = !(num%begin) ||
                    has_any_divs<num, begin+1, end>::res;
};

// specialization to stop recursion
template <number num, number lim>
struct has_any_divs<num, lim, lim> {
    const static bool res = !(num%lim);
};

Now we pretty much have all the basic building blocks we are going to need. It is time to use them to create the desired is_prime functionality:

// is the given number a prime?
template <number num>
struct is_prime {
    const static bool res = !has_any_divs<num>::res;
};

// these require specializations
template <> struct is_prime<2> { const static bool res = true;  };
template <> struct is_prime<1> { const static bool res = false; };
template <> struct is_prime<0> { const static bool res = false; };

A small test case would be in order:

#include <iostream>

// an example
int main () {
    std::cout << std::boolalpha;
    std::cout << "is 65537 prime? " << is_prime<65537>::res <<
        std::endl;
    std::cout << "is 65549 prime? " << is_prime<65549>::res <<
        std::endl;
}

Such a compile time primality check can be useful, for example, when implementing a generic (templated) Prime Double Hash Table, using some kind of a Compile Time Assert:

template <bool> struct CTAssert; // an incomplete type
template <>     struct CTAssert<true> {}; // no error IFF true

template <typename T, unsigned Size> struct PrimeDoubleHashTable {
    CTAssert<is_prime<Size>::res> HASH_TABLE_SIZE_MUST_BE_PRIME;
    // ....
};

One thought on “Compile time primality test

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>