1103515245가 란드에서 사용되는 이유는 무엇입니까?

1103515245가 란드에서 사용되는 이유는 무엇입니까?

이 놀랍도록 간단한 구현을 말씀드리는 겁니다.rand() C준:

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

이 위키피디아 기사를 통해 우리는 승수가a(위 코드에서)a = 1103515245)는 다음 두 가지 조건만 충족해야 합니다.

1. a - 1의 모든 주요 인자에 의해 나뉠 수 있습니다.m.
   (저희의 경우는m = 2^32 int 의, .m단 하나의 소인수 = 2)를 갖습니다.
2. a - 1만약에 4의 배수입니다.m4의 배수입니다.
   (32768은 4이며, 1103515244당)

왜 그들은 1103515245 같은 이상하고 기억하기 어려운 숫자를 선택했을까요?

어쩌면 이 숫자가 다른 숫자보다 낫다는 현명한 이유가 있을지도 모릅니다.

예를 들어, 설정하지 않는 이유는 무엇입니까?a = 20000000001크고,, 하기 쉽죠 더 크고, 멋있어 보이고, 기억하기 쉽죠.

LCG를 사용하여 d차원 공간에 점을 그리면 최대 d!m의 ^1/_d초평면에 놓이게 됩니다.이것은 알려진 LCG의 결함입니다.

(완전한 주기 조건을 벗어난) a와 m을 신중하게 선택하지 않으면 그보다 훨씬 적은 수의 평면에 놓여 있을 수 있습니다.이 숫자들은 스펙트럼 테스트라고 불리는 것에 의해 선택됩니다.

스펙트럼 테스트(spectral test)는 d차원 관절 분포가 놓이는 연속 초평면 사이의 최대 거리입니다.검정할 수 있는 d개에 대해 가능한 한 작기를 원하는 것입니다.

이 주제에 대한 역사적 고찰은 이 문서를 참조하십시오.인용한 발전기는 (ANSIC로) 문서에 언급되어 있으며, 그다지 좋지 않은 것으로 판단되었습니다.그러나 높은 차수의 16비트는 허용할 수 있지만 많은 응용 프로그램들은 32768개 이상의 별개의 값이 필요할 것입니다. (댓글에서 지적한 바와 같이, 주기는 실제로 2^31입니다. 위키백과 링크의 완전한 주기성의 조건은 아마도 필요한 것일 뿐입니다.)

ANSI 문서의 원본 소스 코드는 높은 순서의 16비트를 취하지 않아 오용하기 쉬운 매우 불량한 생성기를 생성했습니다(rand() % n사람들이 처음으로 생각하는 것은 그들 사이에 숫자를 그리는 것입니다.0그리고.n, 이 경우 매우 random하지 않은 결과를 얻을 수 있습니다.)

수치 레시피의 LCG에 대한 논의도 참조하십시오.인용:

더 나쁜 것은, 많은 초기 개발자들이 m과 a에 대해 특히 나쁜 선택을 했다는 것입니다.= 65539 및 m = 231과 같은 악명 높은 루틴 중 하나인 RANDU는 수년 동안 IBM 메인프레임 컴퓨터에서 널리 사용되었으며 다른 시스템에도 널리 복사되었습니다.우리 중 한 명은 한 대학원생이 단지 11대의 비행기로 "난수" 플롯을 만들다가 컴퓨터 센터의 프로그래밍 컨설턴트로부터 "난수 생성기를 잘못 사용했다"는 말을 들었던 것을 떠올립니다. "우리는 각 숫자가 개별적으로 난수라는 것은 보장하지만, 그 중 하나 이상이 난수라는 것은 보장하지 않습니다."그것은 우리의 대학원 교육을 최소한 1년 뒤로 미뤘습니다.

그 것을 기억하라.rand()는 균일 분포의 근사치입니다.이러한 숫자는 더 균일하게 보이는 분포를 생성한다는 것을 보여주기 위해 테스트되었기 때문에 사용됩니다.

대표적인 범위의 부호 없는 정수 쌍의 수를 고려할 때, 유효한 모든 씨앗과 함께 모두 시험해 본 사람은 없을 것입니다.매개변수를 더 잘 선택할 수 있다고 생각되면 시도해 보십시오!코드가 있으면 LCG의 파라미터를 계산하고 테스트를 실행합니다.여러 개의 숫자(예: 천만 개)를 생성하고, 생성된 숫자의 히스토그램을 계산한 후 분포를 표시합니다.

편집 실제 응용 프로그램에서 사용할 의사 난수 생성기 개발에 관심이 있다면 해당 주제에 대한 상당한 문헌을 읽어보는 것이 좋습니다.위에 제시된 "조언"은 임의의 "더 크고, 멋져 보이고, 기억하기 쉬운" LCG 매개변수를 선택하는 것이 매우 좋지 않은 분포를 제공한다는 것을 보여주는 데 도움이 될 뿐입니다./편집

게다가 그것은 라이브러리 기능이고 나는 표준 라이브러리 버전을 사용하는 프로그램을 본 적이 없습니다.rand()LCG의 파라미터를 기억해야 합니다.

초기 계산은 비트와 바이트에 관심을 가지는 경향이 있었고 코드의 바이트를 최소화하기 위해 레지스터를 가지고 장난을 쳤습니다(줄이 바이트가 있기 전에).

아래에서 합리적인 단서를 하나 발견했을 뿐입니다.

이 발전기의 출력은 그다지 무작위적이지 않습니다.위에 나열된 샘플 생성기를 사용하면 16개 키 바이트의 시퀀스가 매우 비랜덤하게 됩니다.예를 들어, rand()의 각 연속적인 출력의 낮은 비트가 교대로(예를 들어, 0,1,0,1,0,1,1,...) 된다는 것이 밝혀졌습니다. 그 이유를 알 수 있습니까?x * 1103515245의 로우 비트는 x의 로우 비트와 동일한 다음 12345를 더하면 로우 비트가 뒤집힙니다.따라서 로우 비트가 교대로 바뀝니다.이것은 가능한 키의 집합을 원하는 값인 2128보다 훨씬 적은 2113개의 가능성으로만 좁힙니다.

http://inst.eecs.berkeley.edu/ ~cs161/fa08/Notes/random.pdf

그리고 두 가지 합리적인 답변:

Bays, Durham Bays, Carter, SD Durham에 의한 불량 난수 발생기 개선(1976)

http://en.wikipedia.org/wiki/TRNG

그 숫자는 특별한 것 같아요, 두 소수 사이에요: P.

이제 진지하게 이야기를 나누면서 좋은 선택인지 알아보기 위해 결과물을 살펴보십시오.한 번 뒤집어도 매우 다른 결과를 볼 수 있을 것입니다.

또한 예측 가능성을 얼마나 기대하는지 고려해 보십시오.그 구현은 끔찍합니다. FNV-1a와 같이 더 강력하면서도 간단한 대안을 고려할 수 있습니다.

언급URL : https://stackoverflow.com/questions/8569113/why-1103515245-is-used-in-rand