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

Question

He leído que tiene algo que ver con el tiempo, también se obtiene al incluir el tiempo.h, así que lo asumí demasiado, 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?

Answer 1

rand devuelve los números generados por pseudo-random number generator (PRNG). La secuencia de números que devuelve es determinista, en función del valor con el que se inicializó el PRNG (llamando al srand).

Los números se deben distribuir de forma tal 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 que debe 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).

Answer 2

¿Cómo funciona rand()?

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

He leído que tiene algo que ver con el tiempo , también que se obtiene de incluyendo time.h

rand() tiene nada que ver con el hora. Sin embargo, es muy común usar time() para obtener la "semilla" para el PRNG para que pueda obtener diferentes números "aleatorios" cada vez que se ejecuta su programa.

Además, ¿tiene alguna tendencia hacia números pares o impares o algo por el estilo?

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

Answer 3

Brevemente:

• Se utilizan 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 números 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 Mersenne Twister es probablemente la opción más popular.

Ahora, si usted está interesado en las razones por qué lo anterior es cierto, aquí están los detalles morbosos sobre cómo rand() obras:

rand() es lo que se llama un "linear congruential generator." Esto significa que se emplea una ecuación de la forma:

x _{n + 1} = (* a **** x _n + *** b *) mod m

donde x _n es el número aleatorio n^º, y un y b son algunos enteros predeterminados. La aritmética se realiza modulo m, con m generalmente 2 dependiendo de la máquina, de manera que sólo los 32 bits más bajos se mantienen en el cálculo de x _{n + 1}.

En inglés, 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 evidente:

• En primer lugar, se necesita un número aleatorio de partida. Esta es la "semilla" de su generador de números aleatorios, y aquí es donde ha escuchado que se está usando time.h. 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 será siempre dar exactamente la misma secuencia de números aleatorios. Esto suena mal, pero es realmente útil, ya que la depuración es mucho más fácil cuando usted controla las entradas a su programa

• En segundo lugar, un y b han de elegir con sumo cuidado 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 la elección de un un que satisface * *** una Mod8 = 5 junto con *** * b = 1 asegurará que todos los m enteros son igualmente probables, independiente de la elección de las semillas.También desea un valor de a que es realmente grande, de modo que cada vez que lo multiplique por x _n activará el módulo y cortará una gran cantidad de dígitos, o de lo contrario muchos números seguidos simplemente ser múltiplos el uno del otro. Como resultado, dos valores comunes de a (por ejemplo) son 1566083941 y 1812433253 según Knuth. La biblioteca GNU C pasa a utilizar un = 1103515245 y b = 12.345. Una lista de valores para muchas implementaciones está disponible en el wikipedia page for 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. En la mayoría de los casos, esto significa que su generador de números aleatorios se repetirá cada 2 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 al azar. Tienen una especie de correlación graciosa. Si se toma tres números enteros consecutivos, (x, Y, z), a partir de un LCG con algún valor de un y m, esos tres puntos se siempre caída de la red de puntos generados por todas las combinaciones lineales de los tres puntos (1, a, a), (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.

La parte buena es que GLCs como rand() son muy, muy baja huella. 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 es siempre 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.