compile time primes

compile-time-primes-2.cpp

// compiled on Ubuntu 13.04 with:
// clang++ -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes-2.cpp -o compile-time-primes-2

// assembly output with:
// clang++ -S -mllvm --x86-asm-syntax=intel -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes-2.cpp -o compile-time-primes-2.asm

#include <array>
#include <iostream>

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return counter >= limit
        ? number % limit != 0
        : number % counter
            ? is_prime(number, number / counter, counter + 2)
            : false;
}

template<typename T>
constexpr bool is_prime(T n)
{
    return n == 2 || n == 3 || n == 5
        ? true
        : n <= 1 || n % 2 == 0
            ? false
            : is_prime(n, n / 3, T{3});
}

template<size_t n>
struct print_below;

template<> struct print_below<2> { inline static void primes() { std::cout << 2; } };
template<size_t n>
struct print_below
{
    inline static void primes()
    {
        print_below<n - 1>::primes();
        constexpr bool is_n_prime = is_prime(n);
        if(is_n_prime)
            std::cout << ", " << n;
    }
};
 
template <typename T, T... N>
struct primes { static const std::array<bool, sizeof...(N)> cache; };

template <typename T, typename L, T R>
struct append_param;

template <typename T, T... L, T R>
struct append_param<T, primes<T, L...>, R> { using primes = primes<T, L..., R>; };

template <size_t N>
struct indexer : append_param<size_t, typename indexer<N - 1>::primes, N - 1> {};

template <>
struct indexer<0> { using primes = primes<size_t>; };

template <typename T, T... N>
const std::array<bool, sizeof...(N)> primes<T, N...>::cache = {{ is_prime(N)... }};

int main()
{
    const auto &primes_cache = indexer<1000>::primes::cache;

    for(size_t i = 1; i < primes_cache.size(); ++i)
        std::cout << i << (primes_cache[i] ? " is " : " is not ") << "prime" << std::endl;
}

compile-time-primes.cpp

// compiled on Ubuntu 13.04 with:
// clang++ -O3 -ftemplate-depth-10240 -fconstexpr-depth=1024 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-time-primes.cpp -o compile-time-primes

#include <iostream>
#include <cinttypes>

template<typename T>
constexpr bool is_prime(T number, T limit, T counter)
{
    return counter >= limit
        ? number % limit != 0
        : number % counter
            ? is_prime(number, number / counter, counter + 2)
            : false;
}

template<typename T>
constexpr bool is_prime(T n)
{
    return n == 2 || n == 3 || n == 5
        ? true
        : n <= 1 || n % 2 == 0
            ? false
            : is_prime(n, n / 3, T{3});
}

template<std::uint64_t n>
struct print_below;

template<> struct print_below<2> { inline static void primes() { std::cout << 2; } };
template<std::uint64_t n>
struct print_below
{
    inline static void primes()
    {
        print_below<n - 1>::primes();
        constexpr bool is_n_prime = is_prime(n);
        if(is_n_prime)
            std::cout << ", " << n;
    }
};

int main()
{
    std::cout << "Some primes: \n";
    print_below<8000>::primes();
    std::cout << std::endl;

    // constexpr std::uint64_t large_number = 18446744073709551557ull;
    //
    // The following gets executed in runtime even with -O3.
    // Exceeding constexpr compile-time recursion limit makes is_prime to be evaluated at runtime
    //
    // std::cout << large_number << " is prime" << std::boolalpha << is_prime(large_number) << std::endl;
    
    // constexpr std::uint64_t large_number = 18446744073709551557ull;
    //
    // The following will not compile, since assigning to a constexpr variable
    // force compile-time evaluation, but is_prime can't be evaluated at compile-time
    // since its evaluation exceeds the constexpr compile-time recursion limit.
    // So assigning to a constexpr variable or using the expressing in constexpr contexts (like array bounds)
    // is the only safe way to assure things are evaluated at compile-time.
    //
    // constexpr bool is_large_number_prime = is_prime(large_number);
    //
    // if(is_large_number_prime)
    //     std::cout << large_number << " is prime" << std::endl;
    // else
    //     std::cout << large_number << " is not prime" << std::endl;

    // This is the largest prime that can be calcutated with is_prime at compile-time on
    // clang version 3.4 (trunk 183073) with the default -fconstexpr-depth=512
    // constexpr std::uint32_t large_number = 1045493;

    // This one won't compile anymore, increase with -fconstexpr-depth option.
    constexpr std::uint32_t large_number = 1045507;
    
    constexpr bool is_large_number_prime = is_prime(large_number);
    if(is_large_number_prime)
        std::cout << large_number << " is prime" << std::endl;
    else
        std::cout << large_number << " is not prime" << std::endl;
}