Entender el algoritmo de la función rand() de Visual C++

En C/C++, normalmente usamos rand() y srand() cuando queremos obtener un entero aleatorio. Pero cuando intenté reescribirlo, me resultó difícil entender el algoritmo. La función se escribe muy fácilmente en solo unas pocas líneas, pero la fórmula es errónea.Entender el algoritmo de la función rand() de Visual C++

La fórmula principal:

ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L;

El código original involucrados:

void __cdecl srand (unsigned int seed) 
{ 
    _getptd()->_holdrand = (unsigned long)seed; 
} 

int __cdecl rand (void) 
{ 
    _ptiddata ptd = _getptd(); 
    return (((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff); 
}

Fuente

2011-07-22 moonkey

hmm, no sé, la función ya está ahí ... ¿Por qué intentar volver a implementarla? –

+10

@Rocky, no hay nada de malo en tratar de entender los fundamentos del código que damos por sentado. De hecho, debe ser alentado. –

@Rocky: ¡De hecho! Nunca dé algo por hecho si al menos no tiene la posibilidad de tener la esperanza de poder explicar el principio. Qi Guo: si estás cansado del LCG, echa un vistazo al Mersenne Twister, un PRNG popular, rápido y de alta calidad. –

Es sólo la aritmética modular. Está multiplicando y sumando un número tomado de módulo 2^32 (por ejemplo) y devolviendo los 16 bits superiores como su número "aleatorio". Debido a que está multiplicando y sumando números que son coprimos al módulo, esto crea una especie de números distribuidos uniformemente.

La elección cuidadosa de los dos números es muy importante. Por ejemplo, si hubiera usado "* 4" y "+ 8", probablemente no experimentaría una gran cantidad de aleatoriedad.

Este esquema se llama linear congruential.

Fuente

2011-07-22 16:31:26

Ese generador de números pseudoaleatorios es un Linear Congruential Generator.

Fuente

2011-07-22 16:33:14

puede encontrar una explicación de la congruencia generador lineal (LCG) y otras familias similares o generadores pseudo-aleatorios, y acerca de la selección de estas constantes específicas en un excelente artículo publicado este mes (7-2011) en el Dr. Dobb Diario (DDJ): Fast, High-Quality, Parallel Random-Number Generators: Comparing Implementations.

creo que tendrá que registrarse en el sitio web del DDJ (gratis) para leer la primera parte de este artículo (link), pero si usted está en C++ y las matemáticas las que debe hacerlo de todos modos ...

Fuente

2011-07-22 16:35:23

Gracias:) He entrado en el enlace que se da, pero es bastante difícil de leer, ya que el inglés no es mi lengua materna. Haré todo lo posible. – moonkey

Antes de llamar a rand, ya que la página man para srand indica que "Si no se proporciona ningún valor inicial, la función rand() se inicializa automáticamente con un valor de 1", entonces un mejor enfoque para invocar rand es invocar primero a srand, "establecerá su argumento como la semilla para que una nueva secuencia de enteros pseudoaleatorios sea devuelta por rand()".

Como ejemplo, considere la siguiente awk, nawk, gawk código que se utiliza en una secuencia de comandos shell bash para crear un nuevo (al azar) Dirección MAC - es decir .genmacaddr referencia en fragmento de código:

enter code here 
BEGIN { 
    n0 = "00" 
    srand() 
    n1 = sprintf("%02x", int(255 * rand())) 
    n2 = sprintf("%02x", int(255 * rand())) 
    n3 = sprintf("%02x", int(255 * rand())) 
    n4 = sprintf("%02x", int(255 * rand())) 
    n5 = sprintf("%02x", int(255 * rand())) 
    print n0":"n1":"n2":"n3":"n4":"n5 
}

donde el fragmento de código en la secuencia de comandos shell bash es:

enter code here 
ifconfig eth0 down 
newmacaddr=`nawk -f .genmacaddr -` 
ifconfig eth0 hw ether $newmacaddr 
ifconfig eth0 up

Si no estoy equivocado, el valor de inicialización para srand se deriva de reloj del sistema.

Espero que esto lo ayude a comprender un enfoque de su solución de codificación que funcionará.

Fuente

2011-07-22 17:15:01 Tom

Como se ha dicho que es una congruencia lineal, (se puede ver que si quieres en el comentario de fondo sobre cómo éstas generan pseudo-aleatorios valores)

la semilla se almacena en _getptd() -> _ holdrand (de aquí en adelante llamado holdrand)

Este código "funciona" al hacer la multiplicación normal y agregar el paso pero luego desbordamiento holdrand a obtener el "módulo" implícito 0x100000000.

Menciono esto porque no es inmediatamente obvio, y generalmente no se considera un buen estilo.

Desbordamiento técnico de una variable entera provoca el comportamiento indefinido, pero en la mayoría de las plataformas es bastante predecible por lo que los ingenieros de Microsoft están ignorando ese problema.

Fuente

2013-02-09 12:44:32 Jasen

Entender el algoritmo de la función rand() de Visual C++

Respuesta

Cuestiones relacionadas