rand()
Linux에서 Mac보다 숫자가 훨씬 자주 반복되는 것으로 보았을 때 작업중 인 프로젝트의 일부로 C에서 해시 맵을 구현하고 무작위 삽입을 사용하여 테스트했습니다 . RAND_MAX
두 플랫폼 모두에서 2147483647 / 0x7FFFFFFF입니다. 바이트 배열을 RAND_MAX+1
길게하고, RAND_MAX
난수를 생성하고 , 각각이 중복인지 메모하고, 표시된대로 목록에서 확인하는 이 테스트 프로그램으로 축소했습니다 .
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int main() {
size_t size = ((size_t)RAND_MAX) + 1;
char *randoms = calloc(size, sizeof(char));
int dups = 0;
srand(time(0));
for (int i = 0; i < RAND_MAX; i++) {
int r = rand();
if (randoms[r]) {
// printf("duplicate at %d\n", r);
dups++;
}
randoms[r] = 1;
}
printf("duplicates: %d\n", dups);
}
Linux는 일관 적으로 약 790 백만 개의 복제본을 생성합니다. Mac은 일관되게 하나만 생성하므로 거의 반복하지 않고 생성 할 수있는 모든 난수 를 반복합니다. 누구든지 이것이 어떻게 작동하는지 설명해 주시겠습니까? 매뉴얼 페이지와 다른 것을 말할 수 없으며, 각각의 RNG를 사용하고 있는지, 온라인에서 찾을 수없는 것을 알 수 없습니다. 감사!
답변
처음에는 macOS rand()
가 어떤 식 으로든 숫자를 반복하지 않는 것이 더 좋은 것처럼 들릴지 모르지만 , 생성 된 숫자의 양으로 많은 양의 사본 (실제 약 790 백만 또는 (2 31 -1) 이 보일 것으로 예상 됩니다 ) / e ). 마찬가지로 순서대로 숫자를 반복하면 중복이 생성되지 않지만 매우 무작위로 간주되지는 않습니다. 따라서 Linux 구현은 이 테스트 에서 실제 임의 소스와 구별 할 수 없지만 macOS 는 그렇지 않습니다.rand()
rand()
언뜻보기에 놀랍게 보이는 또 다른 것은 macOS rand()
가 중복을 피할 수있는 방법 입니다. 소스 코드를 살펴보면 구현은 다음과 같습니다.
/*
* Compute x = (7^5 * x) mod (2^31 - 1)
* without overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/
long hi, lo, x;
/* Can't be initialized with 0, so use another value. */
if (*ctx == 0)
*ctx = 123459876;
hi = *ctx / 127773;
lo = *ctx % 127773;
x = 16807 * lo - 2836 * hi;
if (x < 0)
x += 0x7fffffff;
return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));
이로 RAND_MAX
인해 시퀀스가 다시 반복되기 전에 정확히 1과 1 사이의 모든 숫자가 정확히 한 번만 나타납니다. 다음 상태는 곱셈을 기반으로하기 때문에 상태는 절대 0이 될 수 없습니다 (또는 모든 미래 상태도 0이됩니다). 따라서 반복되는 숫자는 첫 번째 숫자이고 0은 반환되지 않는 숫자입니다.
Apple은 적어도 macOS (또는 OS X)가 존재하는 한 문서 및 예제에서 더 나은 난수 생성기의 사용을 장려 해 왔기 때문에 품질이 rand()
중요하지 않은 것으로 간주되어 가장 간단한 의사 난수 발생기. (당신이 언급했듯이, 대신 rand()
에 사용하는 것이 좋습니다 arc4random()
.)
관련 메모에서, 무작위성에 대한이 (그리고 다른 많은) 테스트에서 괜찮은 결과를 생성하는 가장 간단한 의사 난수 생성기는 xorshift *입니다 .
uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;
이 구현은 테스트에서 거의 정확히 790 백만 개의 복제본을 생성합니다.
답변
MacOS는 stdlib에서 문서화되지 않은 rand () 함수를 제공합니다. 시드하지 않은 경우 출력되는 첫 번째 값은 16807, 282475249, 1622650073, 984943658 및 1144108930입니다. 빠른 검색 은이 시퀀스가 다음 공식을 반복하는 매우 기본적인 LCG 난수 생성기에 해당함을 보여줍니다.
x n +1 = 7 5 · x n (모드 2 31-1 )
이 RNG의 상태는 전적으로 단일 32 비트 정수 값으로 설명되므로주기가 그리 길지 않습니다. 정확히 말하면, 2마다 반복됩니다. (31) 1 내지 2의 모든 값을 출력하는 2 반복 – 31 – 2.
나는 생각하지 않습니다 모든 Linux 버전에 대해 표준 rand () 구현 하지만 자주 사용되는 glibc rand () 함수 가 있습니다. 단일 32 비트 상태 변수 대신 1000 비트가 넘는 풀을 사용하므로 모든 의도와 목적에 따라 완전히 반복되는 시퀀스가 생성되지 않습니다. 다시 말하지만,이 RNG에서 처음 몇 개의 출력을 먼저 시드하지 않고 인쇄하여 사용중인 버전을 찾을 수 있습니다. glibc rand () 함수는 숫자 1804289383, 846930886, 1681692777, 1714636915 및 1957747793을 생성합니다.
따라서 Linux에서 (그리고 MacOS에서는 거의 발생하지 않음) 더 많은 충돌을 일으키는 이유는 rand ()의 Linux 버전이 기본적으로 더 무작위이기 때문입니다.
답변
rand()
는 C 표준으로 정의되며 C 표준은 사용할 알고리즘을 지정하지 않습니다. 분명히, 애플은 GNU / 리눅스 구현에 열등한 알고리즘을 사용하고있다 : 리눅스는 테스트에서 실제 무작위 소스와 구별 할 수 없지만, 애플 구현은 단지 숫자를 뒤 섞는다.
임의의 품질의 난수를 원하는 경우 반환되는 숫자의 품질을 최소한 보장하는 더 나은 PRNG를 사용하거나 단순히 읽 /dev/urandom
거나 유사한 것을 사용하십시오. 후자는 암호화 품질 수치를 제공하지만 속도가 느립니다. 너무 느리더라도 /dev/urandom
더 빠른 다른 PRNG에 우수한 씨앗을 제공 할 수 있습니다.
답변
일반적으로, 랜드 / 랜드 쌍은 결과에서 상위 비트보다 랜덤 성이 적은 하위 비트로 인해 오랫동안 사용되지 않는 것으로 간주되었습니다. 이것은 결과와 관련이있을 수도 있고 아닐 수도 있지만, 일부 랜드 / 랜드 구현이 최신 버전이지만 이전 구현이 계속 유지되고 무작위를 사용하는 것이 좋습니다. ). 내 아치 리눅스 상자에서 다음 노트는 여전히 rand (3) 매뉴얼 페이지에 있습니다.
The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-or- der bits. Do not use this function in applications intended to be por- table when good randomness is needed. (Use random(3) instead.)
바로 아래 매뉴얼 페이지는 실제로 가장 간단한 LC RNG에 관한 rand 및 srand의 아주 짧고 간단한 예제 구현을 제공하며 작은 RAND_MAX를 갖습니다. C 표준 라이브러리의 내용과 일치한다고 생각하지 않습니다. 또는 적어도 나는 희망하지 않습니다.
일반적으로 표준 라이브러리에서 무언가를 사용하려는 경우 가능한 경우 무작위를 사용하십시오 (man 페이지는 POSIX 표준으로 다시 POSIX.1-2001로 나열하지만 rand는 C가 표준화되기 전에 표준 방식입니다) . 또는 더 나은 방법으로, 열린 Numerical Recipes (또는 온라인에서 찾음) 또는 Knuth를 크랙하여 구현하십시오. 그것들은 정말 쉬우 며 가장 자주 필요한 속성과 알려진 품질을 가진 범용 RNG를 갖기 위해 한 번만하면됩니다.