c++ - Tiempo de compilación
templates c++11 (6)
Necesito verificar si hay algún número primo entero en el tiempo de compilación (para poner el valor booleano como argumento de plantilla).
He escrito código que lo hacen bien:
#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 {
};
Funciona para números hasta ~ 1000000 y falla con error para 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
No puedo aumentar el límite de profundidad. ¿Es posible de alguna manera disminuir la profundidad que uso?
Cosa que quiero lograr : necesito verificar si el primado es constante en el tiempo de compilación sin cambiar la cadena de compilación con el límite de profundidad de plantilla 900 y el límite de profundidad de constexpr 512. (predeterminado para mi g ++). Debería funcionar para todos los int32 positivos o al menos para números hasta 10 9 +9
Aquí está mi intento de esto. Usando constexpr y la variante determinista de la prueba de primalidad de Miller-Rabin para números hasta 4,759,123,141 (que debería cubrir todos los uint32s, pero puede cambiar fácilmente el conjunto del comprobador de cebado para cubrir un rango mayor)
#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;
}
C ++ sin constexpr, IsPrime :: Value da el resultado en tiempo de compilación. El truco es tratar iterativamente de dividir por i = 3,5,7, ... hasta que i * i> n
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 };
};
Desde el punto de vista del lenguaje, la solución es aumentar el límite de profundidad. El programa es correcto, excepto que requiere "demasiadas" iteraciones. Pero usted ha declarado que no quiere aumentarla. (Parece que la profundidad de plantilla requerida es (sqrt (N) + C) donde C es una constante pequeña, por lo que para una profundidad máxima de 900 en su sistema, su implementación actual funcionará hasta 810000).
Puedo pensar en dos estrategias para aumentar el límite del rango superior:
Mejorar el algoritmo. Si solo marca los factores impares, puede reducir el número de iteraciones a la mitad. El límite superior sube por un factor de cuatro. Esto todavía no es cerca de mil millones, pero ciertamente se puede llegar acercándose más al tamiz ideal.
Use una declaración
typedefpara preevaluar parte de la metafunción y confíe en la política de memorización de su compilador para evitar que esa parte se vuelva a evaluar a profundidad.Esta estrategia no funcionará para las metafunciones que dependen en gran medida de los resultados de las iteraciones anteriores, pero en su caso, puede verificar los últimos 900 factores, y luego una verificación de los últimos 1800 factores utilizará automáticamente una copia en caché del resultado del último 900. Esto no está especificado por el estándar C ++, y no es estrictamente portátil, pero por otro lado tampoco lo es nada relacionado con estos límites de recursión.
Puede cambiar el requisito de espacio de lineal a logarítmico dividiendo el rango a la mitad utilizando un algoritmo de dividir y conquistar. Este método usa dividir y conquistar, y solo prueba factores impares ( 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))));
}
EDITAR: Use sqrt de tiempo de compilación para enlazar el espacio de búsqueda al techo (sqrt (n)), en lugar de n / 2. Ahora puede calcular is_prime(100000007) como desee (e is_prime(1000000000039ULL) para ese asunto) en Coliru sin explotar.
Disculpas por el horrible formato, todavía no he encontrado un estilo cómodo para el sub-lenguaje constexpr torturado de C ++ 11.
EDITAR: Código de limpieza: reemplazar macro con otra función, mover detalles de implementación a un espacio de nombres de detalle, robar estilo de sangría de la respuesta de Pablo.
Puedes echar un vistazo a constexpr. Tiene una sintaxis mucho más amigable que la meta programación de plantillas (al menos si no está familiarizado con las plantillas como yo). No puede usar ifs, ni ningún otro bucle. Pero con la recursión y el tenedor teniente, puede hacer casi todo lo que pueda con la meta programación de la plantilla, y generalmente también se ejecuta más rápido.
cpptruths.blogspot.no/2011/07/…
Este es un ejemplo práctico que utiliza un compilador en línea: http://coliru.stacked-crooked.com/view?id=6bc10e71b8606dd2980c0c5dd982a3c0-6fbdb8a7476ab90c2bd2503cd4005881
Dado que se ejecuta en tiempo de compilación, puede hacer una aserción estática para probarlo.
static_assert(is_prime_func(x), "...");
La afirmación fallará si x no es primo, lo que significa que la compilación fallará. Si x es primo, la compilación tendrá éxito pero no se generará ningún resultado.
Si desea verificar números realmente grandes, puede aumentar la profundidad de constexpr
-fconstexpr-depth=930000
No he probado cómo soporta los números grandes, pero asumo que varía de compilador a compilador.
Si quieres probarlo por ti mismo:
#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
}
Compilando
g++ -std=c++11 -O2 -Wall -pedantic -pthread main.cpp -std=c++11 -fconstexpr-depth=9300 && ./a.out
constexpr probable que constexpr sea más fácil de manejar, pero no hay ningún problema real al hacer esto con la creación de instancias de plantilla.
ACTUALIZACIÓN: Fija la raíz cuadrada entera de Newton-Raphson
Este código es subóptimo: eliminar todas las divisiones de prueba en números pares (y tal vez incluso en múltiplos de tres) obviamente aceleraría los tiempos de compilación, pero funciona e incluso con un número primo de 10 10 gcc utiliza menos de 1 GB de 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 { };