¿Hay valores "buenos" de generación de PRNG sin estado oculto?

Necesito un buen generador de números pseudoaleatorios que pueda computarse como una función pura de su salida anterior sin ningún estado oculto. En "bueno" que quiero decir:¿Hay valores "buenos" de generación de PRNG sin estado oculto?

debo ser capaz de parametrizar generador de tal manera que ejecutarlo para 2^n iteraciones con ningún parámetro (o con algún gran subconjunto de ellos) debe cubrir todos o casi todos los valores entre 0 y 2^n - 1, donde n es el número de bits en el valor de salida.
salida del generador combinado de n + p bits deben cubrir todos o casi todos los valores entre 0 y 2^(n + p) - 1 si ejecutarlo para 2^n iteraciones para cada combinación posible de sus parámetros, donde p es el número de bits en los parámetros.

Por ejemplo, LCG se puede calcular como una función pura y que puede satisfacer primera condición, pero que no puede cumplir segundo. Digamos que tenemos LCG de 32 bits, m = 2^32 y es constante, nuestro p = 64 (dos parámetros de 32 bits a y c), n + p = 96, por lo que debemos ver los datos en tres partes desde la salida para cumplir con la segunda condición. Desafortunadamente, la condición no se puede cumplir debido a la secuencia estrictamente alternante de entradas impares y pares en la salida. Para superar esto, se debe introducir el estado oculto, pero eso hace que la función no sea pura y rompa la primera condición (largo período oculto).

EDIT: Estrictamente hablando, quiero familia de funciones parametrizada por p trozos y con pleno estado de n trozos, cada uno generando todas las posibles cadenas binarias de p + n bits de "randomish" única manera, no sólo de forma continua incrementando (p + n) - bit int. Se requiere una parametrización para seleccionar esa forma única.

¿Estoy deseando demasiado?

Fuente

2010-05-20 actual

¿Desea un generador de números aleatorios para generar una secuencia casi distinta? –

@Moron, sí. El generador debe ser capaz de generar todas o casi todas las posibles secuencias de bits distintas de longitud predefinida L en múltiples ejecuciones con diferentes parámetros que realizan no más de 2^n iteraciones para cada ejecución, donde n actual

Si espera k números distintos en k llamadas, no es aleatorio. Por ej. ¡Siempre puedo predecir el último! ¿O lo entendí mal? –

Probar LFSR
Todo lo que necesita es una lista de polinomios primitivos.
Período de generación de campo finito de esta manera, genera un campo de tamaño 2^n-1. Pero puede generalizar este procedimiento para generar cualquier cosa con un período de k^n-1.

no he visto esto en práctica, pero todo lo que tiene que poner en práctica está cambiando los números por número pequeño s> n donde mcd (s, 2^n-1) == 1. mcd es sinónimo de máximo común divisor

Fuente

2010-05-20 19:53:53

Según tengo entendido, hay un subconjunto de valores combinados que contienen ceros que no se pueden generar. – actual

Eso es verdad. Debería agregar manualmente soporte para ceros si lo necesita y simplemente saltar desde un valor predefinido por ejemplo 0x001 a 0x000 y luego volver al siguiente valor de 0x001. –

Puede usar cualquier cifra de bloque, con una clave fija. Para generar el siguiente número, descifrar el actual, incrementarlo y volver a cifrarlo. Debido a que las cifras de bloque son 1: 1, necesariamente iterarán a través de cada número en el dominio de salida antes de repetir.

Fuente

2010-05-20 20:55:47

Una idea interesante, pero demasiado lenta para mi aplicación. Gracias de todos modos. – actual

Hmm ... tal vez no tan lento. ¿Cómo crees que funcionará si genero una clave de ancho p, no n + p, y comienzo a XORing con datos de n + p ancho? ¿Generará todas las combinaciones de ancho n + p? – actual

Depende de dónde obtienes los datos. En términos generales, eso probablemente no generará una permutación. –

¿Hay valores "buenos" de generación de PRNG sin estado oculto?

Respuesta

Cuestiones relacionadas