¿Es 1.0 un resultado válido desde std :: generate_canonical?

Siempre pensé que los números aleatorios estarían entre cero y uno, sin 1 , es decir, son números del intervalo medio abierto [0,1]. La documentación en cppreference.com de std::generate_canonical confirma esto.

Sin embargo, cuando ejecuto el siguiente progtwig:

 #include  #include  #include  int main() { std::mt19937 rng; std::seed_seq sequence{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; rng.seed(sequence); rng.discard(12 * 629143 + 6); float random = std::generate_canonical<float, std::numeric_limits::digits>(rng); if (random == 1.0f) { std::cout << "Bug!\n"; } return 0; } 

Me da el siguiente resultado:

 Bug! 

es decir, me genera un perfecto 1 , lo que causa problemas en mi integración de MC. ¿Es ese comportamiento válido o hay un error de mi parte? Esto da el mismo resultado con G ++ 4.7.3

 g++ -std=c++11 test.c && ./a.out 

y clang 3.3

 clang++ -stdlib=libc++ -std=c++11 test.c && ./a.out 

Si este es el comportamiento correcto, ¿cómo puedo evitar 1 ?

Edición 1 : G ++ de git parece sufrir el mismo problema. Estoy en

 commit baf369d7a57fb4d0d5897b02549c3517bb8800fd Date: Mon Sep 1 08:26:51 2014 +0000 

y comstackr con ~/temp/prefix/bin/c++ -std=c++11 -Wl,-rpath,/home/cschwan/temp/prefix/lib64 test.c && ./a.out da el mismo resultado, ldd rendimientos

 linux-vdso.so.1 (0x00007fff39d0d000) libstdc++.so.6 => /home/cschwan/temp/prefix/lib64/libstdc++.so.6 (0x00007f123d785000) libm.so.6 => /lib64/libm.so.6 (0x000000317ea00000) libgcc_s.so.1 => /home/cschwan/temp/prefix/lib64/libgcc_s.so.1 (0x00007f123d54e000) libc.so.6 => /lib64/libc.so.6 (0x000000317e600000) /lib64/ld-linux-x86-64.so.2 (0x000000317e200000) 

Editar 2 : informé sobre el comportamiento aquí: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63176

Editar 3 : El equipo clang parece estar al tanto del problema: http://llvm.org/bugs/show_bug.cgi?id=18767

El problema está en mapear desde el std::mt19937 de std::mt19937 ( std::uint_fast32_t ) para float ; el algoritmo descrito por el estándar proporciona resultados incorrectos (inconsistentes con su descripción de la salida del algoritmo) cuando se produce una pérdida de precisión si el modo de redondeo IEEE754 actual no es redondeado a negativo-infinito (tenga en cuenta que el valor predeterminado es redondo) -to-más cercano).

La salida 7549723 de mt19937 con su semilla es 4294967257 ( 0xffffffd9u ), que cuando se redondea a flotante de 32 bits da 0x1p+32 , que es igual al valor máximo de mt19937, 4294967295 ( 0xffffffffu ) cuando también se redondea a 32 bits flotador.

El estándar podría garantizar un comportamiento correcto si fuera a especificar que al convertir desde la salida de la URNG al RealType de generate_canonical , el redondeo debe realizarse hacia el infinito negativo; esto daría un resultado correcto en este caso. Como QOI, sería bueno para libstdc ++ hacer este cambio.

Con este cambio, ya no se generará 1.0 ; en su lugar, los valores límite 0x1.fffffep-N para 0 < N <= 8 se generarán más a menudo (aproximadamente 2^(8 - N - 32) por N , dependiendo de la distribución real de MT19937).

Yo recomendaría no usar float con std::generate_canonical directamente; en lugar de generar el número en double y luego redondo hacia el infinito negativo:

  double rd = std::generate_canonical::digits>(rng); float rf = rd; if (rf > rd) { rf = std::nextafter(rf, -std::numeric_limits::infinity()); } 

Este problema también puede ocurrir con std::uniform_real_distribution ; la solución es la misma, especializar la distribución en double y redondear el resultado hacia el infinito negativo en float .

De acuerdo con el estándar, 1.0 no es válido.

C ++ 11 §26.5.7.2 Plantilla de función generate_canonical

Cada función instanciada a partir de la plantilla descrita en esta sección 26.5.7.2 mapea el resultado de una o más invocaciones de un generador de números aleatorios uniforme suministrado g a un miembro del RealType especificado de modo que, si los valores g i producidos por g se distribuyen uniformemente , los resultados de la ejemplificación tj , 0 ≤ t j <1 , se distribuyen de la manera más uniforme posible, como se especifica a continuación.

Acabo de encontrarme con una pregunta similar con uniform_real_distribution , y así es como interpreto la redacción parsimoniosa del Standard sobre el tema:

El Estándar siempre define las funciones matemáticas en términos matemáticos , nunca en términos de coma flotante IEEE (porque el Estándar aún pretende que el punto flotante podría no significar el punto flotante IEEE). Entonces, cada vez que vea una redacción matemática en el Estándar, se trata de matemática real , no de IEEE.

El Estándar dice que tanto uniform_real_distribution(0,1)(g) como generate_canonical(g) deben devolver valores en el rango semiabierto [0,1). Pero estos son valores matemáticos . Cuando tomas un número real en el rango medio abierto [0,1) y lo representas como coma flotante IEEE, bueno, una fracción significativa del tiempo redondeará hasta T(1.0) .

Cuando T es float (24 bits de mantisa), esperamos ver uniform_real_distribution(0,1)(g) == 1.0f aproximadamente 1 en 2 ^ 25 veces. Mi experimentación de fuerza bruta con libc ++ confirma esta expectativa.

 template void test(long long N, const F& get_a_float) { int count = 0; for (long long i = 0; i < N; ++i) { float f = get_a_float(); if (f == 1.0f) { ++count; } } printf("Expected %d '1.0' results; got %d in practice\n", (int)(N >> 25), count); } int main() { std::mt19937 g(std::random_device{}()); auto N = (1uLL < < 29); test(N, [&g]() { return std::uniform_real_distribution(0,1)(g); }); test(N, [&g]() { return std::generate_canonical(g); }); } 

Ejemplo de salida:

 Expected 16 '1.0' results; got 19 in practice Expected 16 '1.0' results; got 11 in practice 

Cuando T es double (53 bits de mantisa), esperamos ver uniform_real_distribution(0,1)(g) == 1.0 aproximadamente 1 en 2 ^ 54 veces. No tengo la paciencia para probar esta expectativa. 🙂

Mi entendimiento es que este comportamiento está bien. Puede ofender nuestro sentido de “medio abierto” que una distribución que dice devolver números “menores que 1.0” puede de hecho devolver números que son igual a 1.0 ; pero esos son dos significados diferentes de “1.0”, ¿ves? El primero es el matemático 1.0; el segundo es el número de coma flotante de precisión simple IEEE 1.0 . Y nos han enseñado durante décadas a no comparar los números de punto flotante para obtener la igualdad exacta.

Cualquiera que sea el algoritmo al que alimente los números aleatorios, no le importará si a veces obtiene exactamente 1.0 . No hay nada que puedas hacer con un número de punto flotante, excepto operaciones matemáticas, y tan pronto como hagas una operación matemática, tu código tendrá que lidiar con el redondeo. Incluso si pudieras legítimamente asumir que generate_canonical(g) != 1.0f , aún no podrías asumir que generate_canonical(g) + 1.0f != 2.0f – debido a redondeando Usted simplemente no puede alejarse de eso; Entonces, ¿por qué pretendemos en esta única instancia que puedes?