3 난수

Question

가정 당신은 일부 균일 destribution RND (x)는 기능 어떤 0 또는 당신이 어떤 RND을 만들려면이 기능을 사용할 수있는 방법 1. (X, N)를 반환해야 0에서 n까지의 균일 한 분산 수를 반환하는 함수는 무엇입니까?

나는 그것을 사용하는 모든 사람을 의미하지만 나에게는 너무 영리하지 않습니다. 예를 들어 오른쪽 테두리가 2^n-1 ([0-1], [0-3], [0-7] 등) 인 분포를 만들 수 있지만 범위에 대해이를 수행하는 방법을 찾을 수는 없습니다 합리적인 정밀도를 위해 매우 큰 숫자를 사용하지 않고 [0-2] 또는 [0-5]

Answer 1

0 또는 1

1. 찾기 반환 다른 함수 rnd1()를 사용하여 균일 범위의 난수 분포 반환 기능 rnd(n) 만들어야 [0, N]한다고 가정 같은 작은 k2^k >= n+1
그
2. k 비트로 구성된 번호를 만들고 rnd1()을 사용하여 비트를 모두 채 웁니다. 결과는 [0, 2^k-1] 범위의 균일하게 분산 된 숫자입니다.
3. n과 생성 된 숫자를 비교하십시오. n보다 작거나 같으면 리턴하십시오. 상기 코드

   unsigned int rnd(n) { 
       while (true) { 
       unsigned int x = rnd_full_unsigned_int(); 
       if (x < MAX_UNSIGNED_INT/(n+1) * (n+1)) { 
        return x % (n+1); 
       } 
       } 
   } 
   

   설명 : 그렇지 2. 일반적

단계로 이동이 넓은 범위의 숫자를 생성 라이브러리 함수를 사용하여 작은 범위에서 균일 한 숫자를 생성하는 방법의 변형은 . 단순히 rnd_full_unsigned_int() % (n+1)을 반환하면 작은 값으로 바이어스가 생성됩니다. 검은 나선형은 0에서 MAX_UNSIGNED_INT까지 가능한 모든 값을 내부에서부터 계산합니다. 단일 회전 경로의 길이는 (n + 1)입니다. 적색 선은 편향이 발생하는 이유를 보여줍니다. 따라서이 편향을 없애기 위해 먼저 [0, MAX_UNSIGNED_INT] 범위의 난수 x를 만듭니다 (비트 채우기가 쉽습니다). 그런 다음 x가 바이어스 생성 영역으로 떨어지면 다시 생성합니다. 바이어스 생성 영역에 빠지지 않을 때까지 계속해서 다시 만듭니다. 이 순간의 x는 형태가 a*(n+1)-1이므로, x % (n+1)은 균등하게 분산 된 수 [0, n]입니다.