¿Qué algoritmos comunes se usan para el rand de C()?

Question

Entiendo que la especificación C no proporciona ninguna especificación sobre la implementación específica de rand(). ¿Qué algoritmos diferentes se usan comúnmente en las diferentes plataformas principales? ¿Cómo difieren?

Answer 1

Ver este artículo: http://en.wikipedia.org/wiki/List_of_random_number_generators

Este es el código fuente de glibc rand():

/* Reentrant random function from POSIX.1c. 
    Copyright (C) 1996, 1999, 2009 Free Software Foundation, Inc. 
    This file is part of the GNU C Library. 
    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996. 

    The GNU C Library is free software; you can redistribute it and/or 
    modify it under the terms of the GNU Lesser General Public 
    License as published by the Free Software Foundation; either 
    version 2.1 of the License, or (at your option) any later version. 

    The GNU C Library is distributed in the hope that it will be useful, 
    but WITHOUT ANY WARRANTY; without even the implied warranty of 
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
    Lesser General Public License for more details. 

    You should have received a copy of the GNU Lesser General Public 
    License along with the GNU C Library; if not, write to the Free 
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 
    02111-1307 USA. */ 

#include <stdlib.h> 


/* This algorithm is mentioned in the ISO C standard, here extended 
    for 32 bits. */ 
int 
rand_r (unsigned int *seed) 
{ 
    unsigned int next = *seed; 
    int result; 

    next *= 1103515245; 
    next += 12345; 
    result = (unsigned int) (next/65536) % 2048; 

    next *= 1103515245; 
    next += 12345; 
    result <<= 10; 
    result ^= (unsigned int) (next/65536) % 1024; 

    next *= 1103515245; 
    next += 12345; 
    result <<= 10; 
    result ^= (unsigned int) (next/65536) % 1024; 

    *seed = next; 

    return result; 
} 

Fuente: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/rand_r.c;hb=HEAD

Como se puede ver, es simplemente multiplicar con una adición y un cambio . Los valores se eligen cuidadosamente para garantizar que no se repita la salida de las iteraciones RAND_MAX.

Tenga en cuenta que esta es una vieja aplicación que ha sido sustituido por un algoritmo más complejo: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=HEAD

Si el enlace en caso de rotura, en Google de "rand_r glibc"

Answer 2

Se podría impulsar el uso de la biblioteca aleatoria de diferente generadores de números aleatorios, si necesita algo específico o más avanzado.

La documentación de Boost Random es here.

Answer 3

El campo de los PRNG (generadores de números aleatorios) es bastante amplio.

En primer lugar hay que entender que sin tener una entrada externa (por lo general física) no se puede conseguir una verdadera fuente de números aleatorios .. Es por eso que estos algoritmos se llaman seudo aleatoria: por lo general utilizan una semilla para inicializar una posición en una secuencia muy larga que parece aleatorio pero no es aleatorio en absoluto.

Uno de los algoritmos más simples es la congruencia lineal Generador (LCG), que tiene algunas costraints para garantizar una secuencia larga y no es seguro en absoluto.

Otro gracioso (al menos para el nombre) es el Blum Blum Shub Generator (BBS) que es inusual para PRNG normales porque depende de la exponenciación en aritmética de módulo dando una seguridad comparable a otros algoritmos como RSA y El Gamal en rompiendo la secuencia (también si no estoy seguro acerca de la prueba)

Answer 4

Una vez escribí un informe sobre CRNG para un curso en Matemáticas Discretas. Para ello, desmonté rand() en msvcrt.dll:

msvcrt.dll:77C271D8 mov  ecx, [eax+14h] 
msvcrt.dll:77C271DB imul ecx, 343FDh 
msvcrt.dll:77C271E1 add  ecx, 269EC3h 
msvcrt.dll:77C271E7 mov  [eax+14h], ecx 
msvcrt.dll:77C271EA mov  eax, ecx 
msvcrt.dll:77C271EC shr  eax, 10h 
msvcrt.dll:77C271EF and  eax, 7FFFh 

así que es un algo como LCG (no probado) ...

int ms_rand(int& seed) 
{ 
    seed = seed*0x343fd+0x269EC3; // a=214013, b=2531011 
    return (seed >> 0x10) & 0x7FFF; 
}