Quels sont les algorithmes courants utilisés pour rand() de C?

Question

Je comprends que la spécification C ne donne aucune spécification sur l'implémentation spécifique de rand(). Quels algorithmes différents sont couramment utilisés sur différentes plateformes majeures? En quoi diffèrent-ils?

Answer 1

Voir cet article: http://en.wikipedia.org/wiki/List_of_random_number_generators

Voici le code source de rand() de glibc:

/* 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; 
} 

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

Comme vous pouvez le voir, il est multiplier simplement avec un ajout et un changement . Les valeurs sont soigneusement choisies pour s'assurer que vous n'obtenez pas de répétition de la sortie pour les itérations RAND_MAX.

Notez que c'est une ancienne mise en œuvre qui a été remplacé par un algorithme plus complexe: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=HEAD

Si le lien si elle est brisée, Google pour « glibc rand_r »

Answer 2

Vous pouvez utiliser Boost bibliothèque aléatoire pour différents générateurs de nombres aléatoires, si vous avez besoin de quelque chose de spécifique, ou plus avancé.

La documentation de Boost Random est here.

Answer 3

Le domaine des PRNG (Pseudo Random Number Generators) est assez vaste. Tout d'abord, vous devez comprendre que sans avoir une entrée externe (généralement physique) vous ne pouvez pas obtenir une vraie source de nombres aléatoires .. C'est pourquoi ces algorithmes sont appelés pseudo aléatoire: ils utilisent généralement une graine pour initialiser une position dans une très longue séquence que semble aléatoire mais ce n'est pas aléatoire du tout.

L'un des plus simples algorithmes est le linéaire Congruential Générateur (LCG), qui a des costraints pour garantir une longue séquence et il est sûr pas du tout. Le Blum Blum Shub Generator (BBS) est également amusant (du moins pour le nom), ce qui est inhabituel pour les PRNG normales car il repose sur l'exponentiation en modulo arithmétique, offrant une sécurité comparable à celle d'autres algorithmes comme RSA et El Gamal. briser la séquence (même si je ne suis pas sûr de la preuve)

Answer 4

J'ai déjà écrit un rapport sur les CRNG pour un cours en mathématiques discrètes. Pour cela, je démonte rand() dans 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 

Il est donc quelque chose comme LCG (non testé) ...

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