编译时间检查 [英] Compile time prime checking

问题描述

我需要检查编译时是否有一些整数素数(将布尔值作为模板参数).

I need to check is some integer prime in compile time (to put the boolean value as template argument).

我编写的代码很不错:

#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 ⁹

It works for numbers to ~1000000 and fails with error for 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

我不能增加深度限制.可以降低我使用的深度吗?

I can't increase the depth limit. Is it somehow possible to decrease depth I use?

我要实现的目标:我需要检查编译时间是否为常数素，而无需更改模板深度限制为900和 constexpr 的编译字符串>深度限制512.(我的g ++的默认设置).它应该适用于所有正整数int32或至少适用于10 ⁹ +9

Thing I want to achive: I need to check is constant prime in compile time without changing compilation string with template depth limit 900 and constexpr depth limit 512. (default for my g++). It should work for all positive int32's or at least for numbers up to 10⁹+9

推荐答案

您可以使用分治法将范围分为两半，从而将空间要求从线性更改为对数.此方法使用分治法，仅测试奇数因子(在Coliru居住/a>):

You can change the space requirement from linear to logarithmic by splitting the range by halves using a divide-and-conquer algorithm. This method uses divide-and-conquer, and only tests odd factors (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))));
}

使用编译时sqrt将搜索空间绑定到ceiling(sqrt(n))，而不是n/2.现在可以根据需要计算 is_prime(100000007)(和is_prime(1000000000039ULL)在科利鲁(Coliru)上没有爆炸.

Use compile-time sqrt to bound search space to ceiling(sqrt(n)), instead of n / 2. Now can compute is_prime(100000007) as desired (and is_prime(1000000000039ULL) for that matter) on Coliru without exploding.

为糟糕的格式表示歉意，我仍然没有找到C ++ 11折磨过的 constexpr 子语言的舒适样式.

Apologies for the horrible formatting, I still haven't found a comfortable style for C++11's tortured constexpr sub-language.

清理代码:用另一个函数替换宏，将实现细节移入细节命名空间，从Pablo的答案中窃取缩进样式.

Cleanup code: replace macro with another function, move implementation detail into a detail namespace, steal indentation style from Pablo's answer.

这篇关于编译时间检查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！