hay una cosa tal como un generador de números pseudo-aleatoria accesible aleatoriamente? (Preferiblemente de código abierto)

Question

En primer lugar, ¿existe tal cosa como un generador de números aleatorios de acceso aleatorio, en el que no sólo podría generar secuencialmente números aleatorios que todos estamos acostumbrados, asumiendo rand100 () siempre genera un valor de 0-100:

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

sino también el acceso al azar cualquier valor aleatorio como:

rand100 (0) salida sería 14, siempre y cuando usted no cambió la semilla

rand100 (3) haría siempre salida 22

rand100 (4) haría siempre de salida 67

y así sucesivamente ...

he encontrado realmente un algoritmo generador de código abierto que hace esto, pero no se puede cambiar la semilla. Sé que pseudoaleatoriedad es un campo complejo; No sabría cómo alterar para añadir esa funcionalidad.

¿Hay un acceso aleatorio generador de números aleatorios seedable, preferentemente fuente abierta? o hay un mejor término para esto puedo Google para obtener más información?

Si no es así, la parte 2 de mi pregunta sería, ¿hay algún generador de números fiable aleatoria de código abierto convencional pseudoaleatoria seedable por lo que pude portarlo a múltiples plataformas / lenguajes, manteniendo una secuencia coherente de valores para cada plataforma para cualquier semilla dada ?

Answer 1

El PCG de generadores de números pseudo-aleatorios familia puede saltar hacia adelante y hacia atrás en el tiempo logarítmica (es decir, saltar hacia adelante 1.000 números requiere O (log (1000)) operaciones), que es probablemente lo suficientemente bueno para ser considerado de acceso aleatorio. La referencia C y C ++ implementaciones tanto soporta esta característica.

La tabla de la página principal del sitio PCG indica que un número de otros generadores puede soportar salto adelante, pero no he visto en ningún implementaciones.

Answer 2

No he oído hablar de nada de eso, pero me parece que podría tomar utilizar un hash decente y escribir función de contenedor que toma un valor semilla y su 'índice', y los ejecuta a través de la función hash. No estoy seguro de la aleatoriedad de la salida de bits mediante distintas funciones hash criptográficas, pero me imagino que alguien ha tomado un vistazo a eso.

Answer 3

Blum Blum Shub es un generador de números pseudoaleatorios con una semilla y de acceso aleatorio a cualquier valor que genera.

Answer 4

Gracias por todas las respuestas, y también, para cualquier persona que pueda suceder en esta pidiendo una pregunta similar, he encontrado una solución que no es exactamente lo que pedí, pero reune los requisitos para mis propósitos.

Es un perlin clase de ruido que se puede encontrar aquí . No estoy seguro de cómo computacionalmente complejo esto es relativo a un generador de números aleatorios convencional, que es una preocupación, ya que una de las plataformas previstas es Android. Además, el ruido Perlin no es lo mismo que pseudoaleatoriedad, pero por lo que puedo decir, una octava más alta y / o valor de frecuencia debe proporcionar aleatoriedad adecuada para fines no criptográficos, en los que el nivel estadístico de aleatoriedad real no es tan importante como la mera apariencia de aleatoriedad.

Esta solución permite la siembra, y también permite el muestreo de un conjunto aleatorio desde cualquier punto, en otras palabras, la aleatoriedad de acceso aleatorio.

aquí está un conjunto ejemplo de c regulares ++ aleatoriedad (rand% 200) en la columna de la izquierda para la comparación, y perlin ruido (con el equivalente de 200%) a la derecha:

91 , 100
48 , 97
5 , 90
93 , 76
197 , 100
97 , 114
132 , 46
190 , 67
118 , 103
78 , 96
143 , 110
187 , 108
139 , 79
69 , 58
156 , 81
123 , 128
84 , 98
15 , 105
178 , 117
10 , 82
13 , 110
182 , 56
10 , 96
144 , 64
133 , 105

tanto se sembraron a 0

los parámetros para el ruido Perlin fueron

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

el orden de muestreo secuencial para el ruido Perlin era simplemente

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200

Answer 5

Una vez leí una muy buena entrada en el blog de un tipo que solía trabajar en Google, que respondió a una pregunta muy similar a la suya.

En resumen, la respuesta fue utilizar un cifrado de bloques con un número aleatorio como la clave de cifrado, y el índice del número que desea en la secuencia que los datos a ser cifrados. Se menciona una cifra que puede trabajar en bloques de cualquier tamaño (en bits), que es conveniente - que tendría que buscar el blog para encontrar el nombre del cifrado

.

Por ejemplo: dice que quiere un barajar al azar de números enteros de 0 a (2 ^ 32) -1. Se puede lograr que el uso de un cifrado de bloques que toma la entrada 4 bytes, y vuelve 4 bytes codificados. Para repetir la serie, primero "cifrar" un bloque de valor 0, 1, luego 2, etc. Si sólo quiere el artículo 1 millones, en la secuencia de la barajadas, que acaba de cifrar el número 1.000.000.

Las "secuencias aleatorias" obtendrá utilizando un sistema de cifrado son diferentes de lo que se obtendría utilizando una función hash (como se sugiere @MichaelBurr). El uso de un sistema de cifrado, se puede obtener un permutación al azar de un rango de números enteros, y probar cualquier elemento de permutación que en un tiempo constante. En otras palabras, los "números aleatorios" no se repetirán. Si utiliza una función hash, los números en la secuencia pueden repetir.

Una vez dicho todo esto, @ solución de MichaelBurr es más apropiado para su situación, y recomiendo que lo utilice.

Answer 6

Una forma de lograr esto es para sintetizar una mayor cantidad de datos al azar de un conjunto más pequeño. Una forma de hacer esto es tener tres conjuntos de datos aleatorios pre-generados. Cada matriz debe tener número primo de entires.

Para producir nuestros números aleatorios nos imaginamos cada una de estas pastillas de una sola vez a ser bucle inifintely y muestra de forma incremental; combinamos los datos en cada uno de ellos utilizando XOR.

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

El ejemplo de código de arriba muestra un ejemplo sencillo que los rendimientos 344618953247 entires accesibles al azar. Para asegurar resultados reproducibles entre las corridas, se debe proporcionar un generador de números aleatorios con una semilla. Un sistema más complejo construido en el mismo principio con la variación de semillas basado en recoger diferentes números primos se puede encontrar en http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Answer 7

Todos los generadores yo sepa son iterativos. Por lo tanto, cualquier 'acceso aleatorio' implicaría el cálculo de todos los valores de la primera a la que usted solicita.

Lo más cerca que podría llegar es tomar una semilla fija, hachís, y luego cifrar el valor de índice, el uso de algo que realmente mezclas con entusiasmo.

O generar una larga lista de ellos y la almacena.

Answer 8

echar un vistazo a esta patente: De acceso aleatorio pseudo generador de números aleatorios https://patents.google.com/patent/US4791594

Se utiliza un esquema de codificación de bits de múltiples etapas para generar una secuencia de números pseudo que es capaz de ser visitada al azar.

La idea es utilizar la dirección de entrada como bits de control a varios números de scramble de semillas, y luego XOR los resultados para producir una salida, a continuación, una segunda pasada de codificación utilizando el resultado generado a partir de la pasada anterior.