가

Question

당신이 반환하는 int randBit() 기능을 제공하고 가정 임의 INT 주어진 임의의 비트 기능을 생성, 균일하게 0 또는

randNumber (INT 최대) 함수를 작성 1. 분산.

내 구현이지만 이것이 옳다는 것을 증명하거나 증명할 수는 없습니다.

// max number of bits 
    int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

    int ret = randBit(); 
    while (i-- > 0) { 
     ret = ret << 1 | randBit(); 
    } 

    return ret; 

내가 가진 기본적인 아이디어는

• 이 수 후
• 지속적으로 연결하여 수를 생성에 존재하는 비트 수를 찾을 수 있다는 것입니다 LSB 비트 수는

을 충족 될 때까지

Answer 1

int를 임의의 비트로 채우기위한 접근 방식은 제 생각에는 올바른 방법입니다.

// max number of bits 
int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

int rnd = 0; 
int mask = 1; 

while (i-- > 0) { 
    rnd = rnd << 1 | randBit(); 
    mask <<= 1; // or: mask *= 2 
} 
double q = (double)rnd/mask; // range is [0, 1) 
return (int)((max + 1) * q); 

하는의이 살펴 보겠습니다 : 최대 2의 전원이며 루프에서 떨어져 하나 일 때 알고리즘에만 작동하기 때문에, 나는이 수정을 건의 할 것

i 항상 것입니다 max이 차지하는 비트 수와 같아야합니다. 루프가 끝나면 rnd에는 0 또는 1로 임의로 채워진 해당 비트 수가 포함되고 mask-1에는 1로 채워진 해당 비트 수가 포함됩니다. 따라서 rnd과 mask-1의 지수가 0과 1 사이에 균등하게 분포되어 있다고 가정하는 것이 안전합니다.이 값을 max으로 곱하면 부동 소수점/실수 값으로 균등하게 분산 된 0에서 max 사이의 결과가 나타납니다.

이제이 결과는 정수로 매핑되어야하며 물론 균일하게 분포되기를 원할 것입니다. 여기에서 유일한 캐치는 1입니다. rnd과 mask-1의 지수가 정확히 1 일 경우 원하는 결과 범위로 스케일링 할 때 문제가되는 가장자리 경우가 있습니다. 균등하게 분포 된 0 .. max-1 값이 있지만 max이됩니다. 희소 한 예외.

이 조건을 처리하려면 0에서 1까지의 범위를 가지지 만 1 은 인 몫을 만들어야합니다. 이것은 rnd/mask에 의해 달성됩니다. 이 범위는 max+1을 곱하고 int로 캐스팅함으로써 균등하게 확산 된 정수 0 .. max에 쉽게 매핑 될 수 있습니다.