17

コンパイル時にいくつかの整数素数をチェックする必要があります (ブール値をテンプレート引数として入れるため)。

私はそれをうまくやるコードを書きました：

#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 9のエラーで失敗します

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と深さ制限512でコンパイル文字列を変更せずに、コンパイル時に定数素数であることを確認する必要がありconstexprます（私のg ++​​のデフォルト）。すべての正の int32 に対して、または少なくとも 10 9 +9までの数値に対して機能するはずです。

4

6 に答える 6

4

constexprおそらく扱いやすいですが、純粋なテンプレートのインスタンス化でこれを行うのに実際の問題はありません。

更新: Newton-Raphson 整数の平方根を修正

このコードは最適ではありません -- すべてのテスト区分を偶数 (場合によっては 3 の倍数) で削除すると、明らかにコンパイル時間が短縮されます -- しかし、素数が約 10 10 gcc の場合でも、1GB 未満の RAM を使用して動作します。

#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 { };
于 2013-08-19T07:24:14.607 に答える
3

constexpr を見ることができます。テンプレート メタ プログラミングよりもはるかに使いやすい構文です (少なくとも、私のようなテンプレートに慣れていない場合)。if やループは使用できません。しかし、再帰と 10 項演算子を使用すると、テンプレート メタ プログラミングでできることのほとんどすべてを行うことができ、通常は実行速度も速くなります。

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

オンライン コンパイラを使用した実際の例を次に示し ます。

コンパイル時に実行されるため、静的アサートを実行してテストできます。

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
于 2013-08-18T21:10:29.020 に答える