Первичная проверка времени компиляции

Question

Мне нужно проверить, является ли целое число простым во время компиляции (чтобы поставить логическое значение в качестве аргумента шаблона).

Я писать код, что делать это хорошо:

#include <type_traits> 
namespace impl { 
    template <int n, long long i> 
    struct PrimeChecker { 
     typedef typename std::conditional< 
        (i * i > n), 
        std::true_type, 
        typename std::conditional< 
         n % i == 0, 
         std::false_type, 
         typename PrimeChecker<n, (i * i > n) ? -1 : i + 1>::type 
        >::type 
       >::type type; 
    }; 
    template <int n> 
    struct PrimeChecker<n, -1> { 
     typedef void type; 
    }; 
} // namespace impl 
template<int n> 
struct IsPrime { 
    typedef typename impl::PrimeChecker<n, 2>::type type; 
}; 

template<> 
struct IsPrime<1> : public std::false_type { 
}; 

Он работает для чисел до ~ 1000000. и с ошибкой 10

prog.cpp:15:23: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct impl::PrimeChecker<1000000000, 901ll>’ 
       >::type type; 
        ^
prog.cpp:15:23: recursively required from ‘struct impl::PrimeChecker<1000000000, 3ll>’ 
prog.cpp:15:23: required from ‘struct impl::PrimeChecker<1000000000, 2ll>’ 
prog.cpp:24:54: required from ‘struct IsPrime<1000000000>’ 
prog.cpp:32:41: required from here 

Я не могу увеличить глубины. Как можно уменьшить глубину, которую я использую?

, что я хочу для того чтобы достигнуть: Мне нужно проверить, является постоянным премьером во время компиляции без изменения компиляции строки с ограничением глубины шаблона 900 и constexpr глубины пределом 512. (по умолчанию для моего г ++). Он должен работать для всех положительных int32 или, по крайней мере, для чисел до 10 +9

Answer 1

Вы можете изменить требования к пространству от линейного до логарифмического, разделив диапазон пополам, используя алгоритм разделения и покоя. Этот метод использует разделяй и захват, и только тесты нечетные факторы (Live at Coliru):

namespace detail { 
using std::size_t; 

constexpr size_t mid(size_t low, size_t high) { 
    return (low + high)/2; 
} 

// precondition: low*low <= n, high*high > n. 
constexpr size_t ceilsqrt(size_t n, size_t low, size_t high) { 
    return low + 1 >= high 
    ? high 
    : (mid(low, high) * mid(low, high) == n) 
     ? mid(low, high) 
     : (mid(low, high) * mid(low, high) < n) 
     ? ceilsqrt(n, mid(low, high), high) 
     : ceilsqrt(n, low, mid(low, high)); 
} 

// returns ceiling(sqrt(n)) 
constexpr size_t ceilsqrt(size_t n) { 
    return n < 3 
    ? n 
    : ceilsqrt(n, 1, size_t(1) << (std::numeric_limits<size_t>::digits/2)); 
} 


// returns true if n is divisible by an odd integer in 
// [2 * low + 1, 2 * high + 1). 
constexpr bool find_factor(size_t n, size_t low, size_t high) 
{ 
    return low + 1 >= high 
    ? (n % (2 * low + 1)) == 0 
    : (find_factor(n, low, mid(low, high)) 
     || find_factor(n, mid(low, high), high)); 
} 
} 

constexpr bool is_prime(std::size_t n) 
{ 
    using detail::find_factor; 
    using detail::ceilsqrt; 

    return n > 1 
    && (n == 2 
     || (n % 2 == 1 
      && (n == 3 
       || !find_factor(n, 1, (ceilsqrt(n) + 1)/2)))); 
} 

EDIT: Использование во время компиляции SQRT для связанного пространства поиска к потолку (SQRT (N)), а п/2 Теперь можно вычислить is_prime(100000007) по желанию (и is_prime(1000000000039ULL) в этом отношении) на Coliru без взрыва.

Извинения за ужасное форматирование, я до сих пор не нашел удобного стиля для C++ 11, подвергнутого пыткам constexpr.

EDIT: код очистки: заменить макрос другой функцией, переместить деталь реализации в пространство имен деталей, украсть стиль отступов из ответа Пабло.

Answer 2

Вы можете посмотреть на constexpr. Он имеет гораздо более дружелюбный синтаксис, чем мета-программирование шаблонов (по крайней мере, если вы не знакомы с такими шаблонами, как я). Вы не можете использовать if или любые циклы. Но с рекурсией и многопользовательским вы можете делать почти все, что вы можете, с помощью метапрограмм шаблонов, и обычно это работает быстрее.

http://cpptruths.blogspot.no/2011/07/want-speed-use-constexpr-meta.html

Вот рабочий пример с помощью онлайна-компилятора: http://coliru.stacked-crooked.com/view?id=6bc10e71b8606dd2980c0c5dd982a3c0-6fbdb8a7476ab90c2bd2503cd4005881

Поскольку он выполняется во время компиляции, вы можете сделать статические проверки, чтобы проверить его.

static_assert(is_prime_func(x), "..."); 

утверждают, потерпит неудачу, если x не является простым, то есть компиляция потерпит неудачу. Если x является простым, компиляция будет успешной, но не будет генерироваться вывод.

Если вы хотите проверить, действительно большое число можно увеличить глубину constexpr

-fconstexpr-depth=930000 

Я не проверял, как большое число он поддерживает, но я предполагаю, что это зависит от компилятора компилятора.

Если вы хотите, чтобы проверить это для себя:

#include <cstdio> 

constexpr bool is_prime_recursive(size_t number, size_t c) 
{ 
    return (c*c > number) ? true : 
      (number % c == 0) ? false : 
       is_prime_recursive(number, c+1); 
} 

constexpr bool is_prime_func(size_t number) 
{ 
    return (number <= 1) ? false : is_prime_recursive(number, 2); 
} 

int main(void) 
{ 
    static_assert(is_prime_func(7), "..."); // Computed at compile-time 
} 

Компиляция

g++ -std=c++11 -O2 -Wall -pedantic -pthread main.cpp -std=c++11 -fconstexpr-depth=9300 && ./a.out 

Answer 3

С точки зрения языка, решение увеличить предел глубины. Программа правильная, за исключением того, что она требует «слишком много» итераций. Но вы заявили, что не хотите его увеличивать. (Похоже, что требуемая глубина шаблона (sqrt (N) + C), где C - небольшая константа, поэтому для максимальной глубины 900 в вашей системе ваша текущая реализация будет работать до 810000.)

Я могу подумайте о двух стратегиях для увеличения верхнего предела диапазона:

1. Улучшить алгоритм.Если вы проверяете нечетные факторы, вы сокращаете количество итераций пополам. Верхний предел увеличивается в четыре раза. Это все еще не где-то около миллиарда, но вы, безусловно, можете добраться туда, ближе к идеальному ситу.

2. Используйте объявление typedef, чтобы предварительно оценить часть метафайла и полагаться на политику замещения вашего компилятора, чтобы остановить эту деталь от переоценки на полной глубине.

   Эта стратегия не будет работать для метафайлов, которые в значительной степени зависят от результатов предыдущих итераций, но в вашем случае вы можете проверить последние 900 факторов, а затем проверить последние 1800 факторов автоматически будет использовать кешированную копию результат от 900. Это не указано стандартом C++ и строго не переносимо, но, с другой стороны, ничто не связано с этими ограничениями на рекурсию.

Answer 4

Вот моя попытка. Использование constexpr и deterministic variant of the Miller-Rabin primality test для чисел до 4,759,123,141 (которые должны охватывать все uint32s, но вы можете легко изменить набор праймеров клетчатой, чтобы покрыть больший диапазон)

#include <cstdint> 

constexpr uint64_t ct_mod_sqr(uint64_t a, uint64_t m) 
{ 
    return (a * a) % m; 
} 

constexpr uint64_t ct_mod_pow(uint64_t a, uint64_t n, uint64_t m) 
{ 
    return (n == 0) 
    ? 1 
    : (ct_mod_sqr(ct_mod_pow(a, n/2, m), m) * ((n & 1) ? a : 1)) % m; 
} 

constexpr bool pass_prime_check_impl(uint64_t x, uint32_t n1, uint32_t s1) 
{ 
    return (s1 == 0) 
    ? false 
    : (x == 1) 
     ? false 
     : (x == n1) 
     ? true 
     : pass_prime_check_impl(ct_mod_sqr(x, n1 + 1), n1, s1 - 1) 
    ; 
} 

constexpr bool pass_prime_check_impl(uint32_t a, uint32_t n1, uint32_t s1, uint32_t d, uint64_t x) 
{ 
    return (x == 1) || (x == n1) 
    ? true 
    : pass_prime_check_impl(ct_mod_sqr(x, n1 + 1), n1, s1) 
    ; 
} 

constexpr bool pass_prime_check_impl(uint32_t a, uint32_t n1, uint32_t s1, uint32_t d) 
{ 
    return pass_prime_check_impl(a, n1, s1, d, 
           ct_mod_pow(a, d, n1 + 1)); 
} 

constexpr bool pass_prime_check_impl(uint32_t n, uint32_t a) 
{ 
    return pass_prime_check_impl(a, n - 1, 
           __builtin_ctz(n - 1) - 1, 
           (n - 1) >> __builtin_ctz(n - 1)); 
} 

constexpr bool pass_prime_check(uint32_t n, uint32_t p) 
{ 
    return (n == p) 
    ? true 
    : pass_prime_check_impl(n, p); 
} 

constexpr bool is_prime(uint32_t n) 
{ 
    return (n == 2) 
    ? true 
    : (n % 2 == 0) 
     ? false 
     : (pass_prime_check(n, 2) && 
     pass_prime_check(n, 7) && 
     pass_prime_check(n, 61)) 
    ; 
} 

int main() 
{ 
    static_assert(is_prime(100000007), "100000007 is a prime!"); 
    static_assert(is_prime(1000000007), "1000000007 is a prime!"); 
    static_assert(is_prime(1000000009), "1000000009 is a prime!"); 
    static_assert(!is_prime(1000000011), "1000000011 is not a prime!"); 
    return 0; 
} 

Answer 5

constexpr, вероятно, легче иметь дело, но есть нет реальной проблемы с этим с помощью создания уникального шаблона.

UPDATE: Фиксированный Ньютона-Рафсона целое квадратный корень

Этот код неоптимальным - сбросив все тестовые подразделения четными номерами (и, возможно, даже кратные трех), очевидно, ускорить время компиляции - но он работает и даже с размером около 10 gcc использует менее 1 ГБ ОЗУ.

#include <type_traits> 

template<typename a, typename b> struct both 
    : std::integral_constant<bool, a::value && b::value> { }; 

template<long long low, long long spread, long long n> 
struct HasNoFactor 
    : both<typename HasNoFactor<low, spread/2, n>::type, 
     typename HasNoFactor<low+spread/2, (spread + 1)/2, n>::type> { }; 

template<long long low, long long n> 
struct HasNoFactor<low, 0, n> : std::true_type { }; 

template<long long low, long long n> 
struct HasNoFactor<low, 1, n> 
    : std::integral_constant<bool, n % low != 0> { }; 

// Newton-Raphson computation of floor(sqrt(n)) 

template<bool done, long long n, long long g> 
struct ISqrtStep; 

template<long long n, long long g = n, long long h = (n + 1)/2, bool done = (g <= h)> 
struct ISqrt; 

template<long long n, long long g, long long h> 
struct ISqrt<n, g, h, true> : std::integral_constant<long long, g> { }; 

template<long long n, long long g, long long h> 
struct ISqrt<n, g, h, false> : ISqrt<n, h, (h + n/h)/2> { }; 

template<long long n> 
struct IsPrime : HasNoFactor<2, ISqrt<n>::value - 1, n> { }; 

template<> struct IsPrime<0> : std::false_type { }; 
template<> struct IsPrime<1> : std::false_type { }; 

Answer 6

C++ without constexpr, IsPrime :: Значение дает результат компиляции. Хитрость заключается в том, чтобы итеративно попытаться разделить на г = 3,5,7, ... до тех пор, пока я * я> п

template <int n, int i, int b> struct IsPrimeIter; 

template <int n, int i> 
struct IsPrimeIter<n, i, 0> { 
    enum _ { Value = 0 }; 
}; 

template <int n, int i> 
struct IsPrimeIter<n, i, 1> { 
    enum _ { Value = 1 }; 
}; 

template <int n, int i> 
struct IsPrimeIter<n, i, 2> { 
    enum _ { Value = IsPrimeIter<n, i+2, 
          (i * i > n) ? 1 : 
          n % i == 0 ? 0 : 2>::Value }; 
}; 

template <int n> 
struct IsPrime { 
    enum _ { Value = n <= 1 ? false: 
        (n == 2 || n == 3) ? true: 
        (n % 2 == 0) ? false : 
        IsPrimeIter<n, 3, 2>::Value }; 
};