Quali algoritmi comuni sono usati per C's rand()?

Question

Comprendo che la specifica C non fornisce alcuna specifica sull'implementazione specifica di rand(). Quali diversi algoritmi sono comunemente usati su diverse piattaforme principali? Come si differenziano?

Answer 1

veda questo articolo: http://en.wikipedia.org/wiki/List_of_random_number_generators

Questo è il codice sorgente di di 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; 
} 

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

Come si può vedere, è semplicemente moltiplicare con l'aggiunta e uno spostamento . I valori sono scelti con cura per assicurarsi di non avere ripetizioni dell'output per le iterazioni RAND_MAX.

Si noti che questo è un vecchio di attuazione che è stato sostituito da un algoritmo più complesso: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=HEAD

Se il collegamento in caso di rottura, Google per "glibc rand_r"

Answer 2

Si potrebbe utilizzare Boost biblioteca casuale per diverso generatori di numeri casuali, se hai bisogno di qualcosa di specifico, o più avanzato.

La documentazione di Boost Random è here.

Answer 3

Il campo dei PRNG (Pseudo Random Number Generators) è piuttosto vasto.

Prima di tutto devi capire che senza avere un input esterno (di solito fisico) non puoi ottenere una vera fonte di numeri casuali .. Ecco perché questi algoritmi si chiamano pseudo random: di solito usano un seme per inizializzare una posizione in una sequenza molto lunga che sembra casuale ma non è affatto casuale.

uno degli algoritmi più semplici è la lineare congruenziale Generator (LCG), che ha alcuni costraints per garantire una lunga sequenza e non è custodito tutto.

Un altro divertente (almeno per il nome) è il generatore Blum Blum Blum (BBS) che è insolito per i normali PRNG perché si basa sull'esponenziazione in modulo aritmetico dando una sicurezza paragonabile ad altri algoritmi come RSA e El Gamal in rompere la sequenza (anche se non sono sicuro della prova)

Answer 4

Una volta ho scritto un rapporto sui CRNG per un corso di Matematica Discreta. Per esso, ho smontato rand() in 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 

quindi è un qualcosa di simile LCG (non testato) ...

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