Welche gemeinsamen Algorithmen werden für Cs rand() verwendet?

Question

Ich verstehe, dass die C-Spezifikation keine Spezifikation über die spezifische Implementierung von rand() gibt. Welche verschiedenen Algorithmen werden üblicherweise auf verschiedenen Hauptplattformen verwendet? Wie unterscheiden sie sich?

Answer 1

diesen Artikel: http://en.wikipedia.org/wiki/List_of_random_number_generators

Dies ist der Quellcode des 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; 
} 

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

Wie Sie sehen können, ist es einfach mit einem Zusatz multiplizieren und einer Verschiebung . Die Werte werden sorgfältig ausgewählt, um sicherzustellen, dass Sie die Ausgabe für RAND_MAX-Iterationen nicht wiederholen.

Beachten Sie, dass dies eine alte Implementierung ist, die durch einen komplexeren Algorithmus ersetzt wurde: https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/random_r.c;hb=HEAD

Wenn die Verbindung, wenn gebrochen, Google für „glibc rand_r“

Answer 2

Sie könnten Zufalls Bibliothek für verschiedene boost Zufallszahlengeneratoren, wenn Sie etwas Bestimmtes oder Fortgeschrittenes benötigen.

Die Dokumentation von Boost Random ist here.

Answer 3

Der Bereich der PRNGs (Pseudo Random Number Generators) ist ziemlich groß.

Zunächst müssen Sie verstehen müssen, dass ohne einen externen Eingang (in der Regel physisch) Sie keine wirkliche Quelle von Zufallszahlen bekommen .. Deshalb ist diese Algorithmen genannt werden Pseudozufall: sie in der Regel einen Samen verwenden um eine Position in einer sehr langen Sequenz zu initialisieren, die scheint zufällig, aber es ist überhaupt nicht zufällig.

Eine der einfachsten Algorithmen ist die Kongruenzgenerator (LCG), die einige costraints hat eine lange Sequenz zu garantieren, und es ist überhaupt nicht sicher. Ein weiterer lustiger (zumindest für den Namen) ist der Blum Blum Shub Generator (BBS), der für normale PRNGs ungewöhnlich ist, da er auf Potenzierung in Modulo-Arithmetik beruht und eine Sicherheit bietet, die mit anderen Algorithmen wie RSA und El Gamal vergleichbar ist Brechen der Sequenz (auch wenn ich mich nicht sicher bin)

Answer 4

Ich habe einmal einen Bericht über CRNGs für einen Kurs in Diskrete Mathematik geschrieben. Denn es ist, zerlegt ich 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 

So ist es ein LCG so etwas wie (nicht getestet) ...

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