Linux에서 rand()가 Mac보다 훨씬 더 자주 숫자를 반복하는 이유는 무엇입니까?

Linux에서 rand()가 Mac보다 훨씬 더 자주 숫자를 반복하는 이유는 무엇입니까?

현재 진행 중인 프로젝트의 일부로 C에 해시맵을 구현하고 랜덤 삽입을 사용하여 테스트하고 있었습니다.에 띄었다.rand() Mac의보다 훨씬 더것. Linux의 경우 Mac의 경우 Mac의 경우보다 훨씬 더 자주 반복됩니다.RAND_MAX2147483647/0x7FFFFFFF두 플랫폼 모두에서요. 배열을 RAND_MAX+1- - long, 성성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는 지속적으로 약 7억 9천만 개의 중복을 생성합니다.Mac은 항상 1개만 생성하므로 거의 반복하지 않고 생성할 수 있는 모든 랜덤 번호를 통해 루프합니다.이게 어떻게 작동하는지 누가 좀 설명해 주시겠어요?다른 건 하나도 모르겠어요.man각 페이지가 어떤 RNG를 사용하고 있는지 알 수 없고 온라인에서 아무것도 찾을 수 없습니다.★★★★★★★★★★★★★★★★★★!

수 MacOS처럼 들릴 수 있습니다.rand()는 숫자를 반복하지 않는 것이 좋습니다.이 정도의 수의 숫자가 생성되면 많은 중복이 발생할 것으로 예상됩니다(실제로 약 7억 9000만, (2-1³¹)/e).마찬가지로 순서대로 숫자를 반복하면 중복이 발생하지 않지만 매우 랜덤하게 간주되지는 않습니다.그래서 Linux는 Linux입니다.rand()구현은 이 테스트에서 진정한 랜덤 소스와 구별할 수 없는 반면 macOS는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));

는 1에서 1까지의 .RAND_MAX한 번 꼭 한 번을 다시 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번, 한 번.다음 상태는 곱셈에 기반하므로 상태는 0일 수 없습니다(또는 미래의 모든 상태도 0일 수 있습니다).따라서 표시되는 반복된 번호가 첫 번째 번호이며 0은 반환되지 않습니다.

OS 하는 한 및에서 보다 macOS(또는 OS X)의 과 같습니다. 따라서 품질은rand()아아중 、 (장단 (asas 、 asasasasasasasasasasasasasasasasasasasasasasasasas. (와 같이 그들의 ( )는rand()사용 권장 사항과 함께 코멘트도 작성되어 있습니다.arc4random()대신).

이와 관련하여 이 (및 많은 다른) 랜덤성 테스트에서 적절한 결과를 얻을 수 있는 가장 단순한 의사 난수 발생기는 xorshift*입니다.

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

이 실장에서는, 테스트에서 거의 정확하게 7억 9000만개의 중복이 발생합니다.

MacOS는 stdlib에서 문서화되어 있지 않은 rand() 함수를 제공합니다.시드되지 않은 상태로 두면 첫 번째로 출력되는 값은 16807, 282475249, 1622650073, 984943658 및 1144108930입니다.빠른 검색에서는 이 시퀀스가 다음 공식을 반복하는 매우 기본적인 LCG 난수 생성기에 대응하고 있음을 알 수 있습니다.

x_n+1 = 7⁵ · x_n (mod³¹ 2 - 1)

이 RNG의 상태는 32비트 정수의 값에 의해 모두 설명되기 때문에 그 기간은 그리 길지 않습니다.정확하게는 2 - 2회 반복할 때마다³¹ 반복되며 1 ~ 2³¹ - 2의 모든 값을 출력합니다.

Linux의 모든 버전에 대해 rand()의 표준 구현이 있다고는 생각하지 않지만 자주 사용되는 glibc rand() 함수가 있습니다.단일 32비트 상태 변수 대신 1000비트가 넘는 풀을 사용합니다.이 풀은 완전히 반복되는 시퀀스를 생성하지 않습니다.이 RNG에서 처음 몇 개의 출력을 시드하지 않고 인쇄하면 버전을 알 수 있습니다(glibc rand() 함수는 1804289383, 846930886, 1681692777, 1714636915 및 1957747793).

따라서 Linux(MacOS에서는 거의 없음)에서 더 많은 충돌이 발생하는 이유는 기본적으로 Linux 버전의 rand()가 더 랜덤하기 때문입니다.

rand()는 C 표준으로 정의되며 C 표준에서는 사용할 알고리즘이 지정되어 있지 않습니다.분명히 애플은 GNU/Linux 구현보다 낮은 알고리즘을 사용하고 있습니다.Linux는 테스트에서 진정한 랜덤 소스와 구별할 수 없는 반면 Apple의 구현은 숫자를 섞기만 합니다.

임의의 품질의 난수를 원할 경우 반환되는 숫자의 품질을 최소한 어느 정도 보증하는 보다 나은 PRNG를 사용하거나 단순히 읽기만 하면 됩니다./dev/urandom또는 이와 유사합니다.후자는 암호화 품질 수치를 제공하지만 속도가 느립니다.그 자체로는 너무 느리더라도/dev/urandom보다 빠른 다른 PRNG에게 훌륭한 씨앗을 제공할 수 있습니다.

일반적으로 랜드/스랜드 쌍은 결과에서 상위 비트보다 랜덤성이 낮은 하위 비트로 인해 오랫동안 사용되지 않는 것으로 간주되어 왔습니다.이것은 결과와 무관할 수도 있고 그렇지 않을 수도 있지만, 일부 랜드/시랜드 구현이 현재 더 최신이지만 오래된 구현이 지속되고 랜덤(3)을 사용하는 것이 더 낫다는 것을 기억할 수 있는 좋은 기회라고 생각합니다.Arch Linux 박스에서 rand(3)의 man 페이지에 다음 주의사항이 아직 남아 있습니다.

  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.)

그 바로 아래 man 페이지에는 지금까지 본 것 중 가장 단순한 LC RNG와 작은 RAND_MAX를 가진 랜드와 스랜드의 매우 짧은 구현 예가 나와 있습니다.C 스탠다드 도서관에 있는 것과 일치하지 않는 것 같아요.아니길 바래야죠.

일반적으로 표준 라이브러리에서 어떤 것을 사용하는 경우, 가능하면 랜덤을 사용합니다(man 페이지에는 POSIX.1-2001로 돌아가 POSIX 표준으로 표시됩니다만, rand는 C가 표준화되기 훨씬 전의 표준입니다).또는 숫자 레시피(또는 온라인으로 검색) 또는 Knuth를 열어 실행하는 것이 좋습니다.이러한 기능은 매우 간단합니다.또한 가장 자주 필요한 특성 및 이미 알려진 품질을 가진 범용 RNG를 실현하기 위해서는 한 번만 수행하면 됩니다.

언급URL : https://stackoverflow.com/questions/61411498/why-does-rand-repeat-numbers-far-more-often-on-linux-than-mac