¿Cómo funciona Rand ()? ¿Tiene ciertas tendencias? ¿Hay algo mejor para usar?

He leído que tiene algo que ver con el tiempo, también se obtiene al incluir el tiempo. Así que asumí eso, pero ¿cómo funciona exactamente? Además, ¿tiene alguna tendencia hacia números impares o pares o algo así? Y, finalmente, ¿hay algo con una mejor distribución en la biblioteca estándar de C o en el marco de la Fundación?

Brevemente:

  • time.h para obtener una semilla, que es un número aleatorio inicial. C luego hace un montón de operaciones en este número para obtener el siguiente número aleatorio, luego las operaciones en ese para obtener el siguiente, luego … usted obtiene la imagen.

  • rand() puede tocar todos los enteros posibles. No preferirá números pares o impares independientemente de la semilla de entrada, felizmente. Aún así, tiene límites: se repite relativamente rápido, y en casi todas las implementaciones solo da números hasta 32767.

  • C no tiene otro generador de números aleatorios incorporado. Si necesita uno realmente difícil, hay muchos paquetes disponibles en línea, pero el algoritmo de Mersenne Twister es probablemente la opción más popular.

Ahora, si le interesan los motivos por los cuales lo anterior es cierto, aquí están los detalles sangrientos sobre cómo funciona rand() :

rand() es lo que se llama un ” generador congruente lineal “. Esto significa que emplea una ecuación de la forma:

x n + 1 = ( * a **** x n + *** b * ) mod m

donde x n es el n ° número aleatorio, y a y b son algunos enteros predeterminados. La aritmética se realiza módulo m , con m usualmente 2 32 dependiendo de la máquina, de modo que solo se mantienen los 32 bits más bajos en el cálculo de x n + 1 .

En inglés, entonces, la idea es la siguiente: para obtener el siguiente número aleatorio, multiplique el último número aleatorio por algo, sume un número y luego tome los últimos dígitos.

Algunas limitaciones son rápidamente evidentes:

  • Primero, necesitas un número aleatorio inicial. Esta es la “semilla” de tu generador de números aleatorios, y aquí es donde has oído hablar del time.h está usando. Como queremos un número realmente aleatorio, es una práctica común preguntar al sistema qué hora es (en forma de número entero) y usar esto como el primer “número aleatorio”. Además, esto explica por qué usar la misma semilla dos veces siempre dará exactamente la misma secuencia de números aleatorios. Esto suena mal, pero en realidad es útil, ya que la depuración es mucho más fácil cuando controlas las entradas de tu progtwig

  • Segundo, a y b tienen que ser elegidos muy, muy cuidadosamente o obtendrás algunos resultados desastrosos. Afortunadamente, la ecuación para un generador congruente lineal es lo suficientemente simple como para que las matemáticas se hayan resuelto con cierto detalle. Resulta que elegir una a que satisfaga * a *** mod8 = 5 junto con *** b * = 1 asegurará que todos los m enteros sean igualmente probables, independientemente de la elección de la semilla. También quiere un valor de a que sea realmente grande, de modo que cada vez que lo multiplique por x n active el módulo y recorte muchos dígitos, o de lo contrario muchos números seguidos serán múltiplos uno del otro. Como resultado, dos valores comunes de a (por ejemplo) son 1566083941 y 1812433253 según Knuth. La biblioteca GNU C usa a = 1103515245 yb = 12345. Una lista de valores para muchas implementaciones está disponible en la página de wikipedia para LCGs .

  • En tercer lugar, el generador congruente lineal en realidad se repetirá a sí mismo debido a ese módulo. Esto llega a ser una matemática bastante embriagadora, pero el resultado de todo es felizmente muy simple: la secuencia se repetirá luego de que se hayan generado m números. En la mayoría de los casos, esto significa que su generador de números aleatorios se repetirá cada 2 32 ciclos. Eso suena mucho, pero realmente no es para muchas aplicaciones. Si está realizando un trabajo numérico serio con simulaciones de Monte Carlo, este número es irremediablemente inadecuado.

  • Un cuarto problema mucho menos obvio es que los números en realidad no son realmente aleatorios. Tienen una especie de correlación graciosa. Si toma tres enteros consecutivos, ( x , y , z ), de un LCG con algún valor de ay m , esos tres puntos siempre caerán en el enrejado de puntos generados por todas las combinaciones lineales de los tres puntos (1, a , a 2 ), (0, m, 0), (0, 0, m). Esto se conoce como el Teorema de Marsaglia, y si no lo entiendes, está bien. Todo lo que significa es esto: los trillizos de números aleatorios de un LCG mostrarán correlaciones en algún nivel profundo y profundo. Por lo general, es demasiado profundo para que usted o yo lo notemos, pero está ahí. ¡Es posible incluso reconstruir el primer número en una secuencia “aleatoria” de tres números si le dan el segundo y el tercero! Esto no es bueno para la criptografía en absoluto.

Lo bueno es que los LCG como rand() tienen una huella muy, muy baja. Por lo general, requiere solo 32 bits para retener el estado, lo que es realmente agradable. También es muy rápido y requiere muy pocas operaciones. Esto lo hace bueno para sistemas integrados no críticos, videojuegos, aplicaciones casuales, cosas así.

Los PRNG son un tema fascinante. Wikipedia siempre es un buen lugar para ir si tiene hambre de aprender más sobre la historia o las diversas implementaciones que existen hoy en día.

rand devuelve los números generados por un generador de números pseudoaleatorios (PRNG). La secuencia de números que devuelve es determinista, en función del valor con el que se inicializó el PRNG (llamando a srand ).

Los números se deben distribuir de modo que parezcan algo aleatorios, por lo que, por ejemplo, los números impares y pares se deben devolver aproximadamente en la misma frecuencia. La implementación real del generador de números aleatorios queda sin especificar, por lo que el comportamiento real es específico de la implementación.

Lo importante para recordar es que rand no devuelve números aleatorios; devuelve números pseudoaleatorios, y los valores que devuelve están determinados por el valor inicial y el número de veces que se ha llamado rand . Este comportamiento es correcto para muchos casos de uso, pero no es apropiado para otros (por ejemplo, rand no sería apropiado para su uso en muchas aplicaciones criptográficas).

¿Cómo funciona Rand ()?

http://en.wikipedia.org/wiki/Peudorandom_number_generator

He leído que tiene algo que ver con el tiempo, también se obtiene al incluir el tiempo.

rand() no tiene nada que ver con el tiempo. Sin embargo, es muy común utilizar el time() para obtener la “semilla” para el PRNG, de modo que obtenga diferentes números “aleatorios” cada vez que se ejecute su progtwig.

Además, ¿tiene alguna tendencia hacia números impares o pares o algo así?

Depende del método exacto utilizado. Hay una implementación popular de rand() que alterna entre números impares y pares. Así que evite escribir código como rand() % 2 que depende de que el bit más bajo sea aleatorio.