OSX의 rand()가 스펙트럼 테스트에 실패하게하려면 어떻게해야합니까?

Question

프로그래밍 클래스의 목적을 위해 보통 표준 C 라이브러리와 함께 제공되는 난수 생성기의 약점, 구체적으로 OSX (quoth the manpage)와 함께 제공되는 "잘못된 임의 생성기"rand()을 설명하려고합니다.

나는 스펙트럼 테스트에 대한 이해를 테스트하는 간단한 프로그램을 작성 :

#include <stdio.h> 
#include <stdlib.h> 

int main() { 
    int i; 
    int prev = rand(); 
    int new; 

    for (i=0; i<100000; i++) { 
    new = rand(); 
    printf("%d %d\n", prev, new); 
    prev = new; 
    } 
    return 0; 
} 

을하지만 결과 산점도를 그릴 때, 여기에 내가 무엇을 얻을 수 있습니다 :

나는 것 사람이 찾은 것과 같은 더 많은 구조를 보여줄 것으로 기대했습니다. on Wikipedia. 내가 여기서 뭔가 잘못하고있는거야? 더 많은 차원에서 플롯해야합니까? 나는 숫자가 여기 1E7보다 작은, 그리고 플롯의 부분 확대 PJS의 제안에 따라

UPDATE

내가 볼 것입니다 :

나는 정확히 찾아 같은 줄이 pjs에 의해 보여 주었다. 그것들은 수직 인 것처럼 보이지만, 어떤 값들이 "놓친"것을 암시하기 때문에 불가능합니다. rand(). 내가 데이터를 sort -n 때 내가 무엇을보고 (샘플)입니다 :

571 9596797 
572 9613604 
575 9664025 
578 9714446 
580 9748060 
581 9764867 
584 9815288 
586 9848902 
587 9865709 
590 9916130 
592 9949744 
127774 13971 
127775 30778 
127780 114813 
127781 131620 
127782 148427 
127783 165234 
127785 198848 
127787 232462 
127788 249269 

즉, 포인트 거의이다 라인에 누워 있지만, 매우, 수직 없습니다. 당신은 몇 가지 측면을 가지고 a 및 b의 방정식을 해결할 수

next = a * prev + b (mod RAND_MAX+1) 

: 나쁜 rand 가정

는

Answer 1

선형 합동 생성기는 모두 George Marsaglia가 확인한 문제점을 겪고 있습니다. "Marsaglia 's Theorem"은 k- 튜플 (길이가 k 인 벡터)이 제한된 수의 초평면에 떨어질 것이라고 말합니다. 바운드는 m**(1/k)이며, 여기서 k는 튜플의 크기이고 m은 생성자의 모듈러스에 사용되는 숫자입니다. 따라서 계수가 (2**31 - 1)이고 3을 보면 3-d 플롯은 올바른 방향에서 보았을 때 (2**31 - 1) 또는 약 1290 평면의 입방체 루트를 넘지 않는 지점을 표시합니다.

모든 LCG는 Marsaglia 's Theorem의 적용을받습니다. "좋은"사람이 상한 또는 그 근처에서 행동 할 때, 나쁜 사람은 상 한계에 잘 못 미친다. 이것이 스펙트럼 테스트가 효과적으로 측정 한 것입니다. Wikipedia 링크에서 보았던 것과 같습니다. 지옥의 LCG 인 RANDU는 단순한 15 개의 평면에 속하는 삼중 항을 만듭니다.

Apple의 탄소 라이브러리 생성기는 16807을 승수로 사용하고 (2**31 - 1)을 모듈러스로 사용합니다. LCG가 진행되면서 그렇게 나쁘지는 않습니다. 그러므로 당신의 음모는 RANDU와 같은 극단을 보여주지 못했습니다. 그러나, 괜찮은 품질의 난수를 원하면 LCG를 사용하지 마십시오.

부록은

나는 앞서 갔다와 애플 랜드() 함수에서 억 번호를 크랭크,하지만 쌍의 두 값 미만 200 만, 즉, 아래 있던 사람을 인쇄했습니다 당신의 음모의 왼쪽 구석. 물론, 그들은 라인에 빠지다. 선의 밀도 때문에 실제로 확대해야합니다.

올드 조지는 영리한 친구였습니다! 각 입력 임의의 경우

Answer 2

는 형태의 선형 합동 생성기, 즉이다. 그 후에, 당신은 구조가 쉽게 명백해질 수 있도록 출력 기능을 생성 할 수 있어야합니다.