나머지 연산 난수 편향 계산기

M이 n으로 나누어떨어지지 않으면 앞쪽 값들에 난수가 한 번씩 더 대응되기 때문입니다. M = n·q + r로 쓰면 0부터 r−1까지는 q+1개의 난수가, 나머지는 q개가 대응됩니다. 그래서 앞쪽 r개의 값이 (q+1)/q배 더 자주 나옵니다. r이 0이면, 즉 나누어떨어지면 편향이 전혀 없습니다.

q ≈ M/n이므로 편향의 크기는 1/q, 곧 n/M 규모입니다. 주사위(n=6)를 32비트 난수로 뽑으면 7억분의 1이라 평생 알아채지 못합니다. 하지만 n이 M에 가까워질수록 커지고, n이 M의 절반을 넘으면 q = 1이 되어 앞쪽 값이 정확히 두 배 나옵니다.

n이 클 때입니다. 랜덤 셔플, 추첨, 큰 범위에서의 표본 추출처럼 n이 난수 범위에 비해 크면 결과가 눈에 띄게 치우칩니다. 반대로 n이 작고 M이 크면 실용적으로는 무시할 수 있지만, 암호학적 용도라면 크기와 무관하게 없애야 합니다.

기각 표집을 씁니다. x < n·q일 때만 받아들이고 그보다 크면 버리고 다시 뽑으면, 남은 범위가 n으로 정확히 나누어떨어져 완전히 고르게 됩니다. 버리는 비율은 r/M이라 대개 무시할 만합니다.

최악이라도 평균 2번을 넘지 않습니다. n이 M보다 작으면 n·q가 M의 절반을 넘기 때문입니다. 대부분의 경우 버리는 비율이 백만분의 1 이하라 사실상 한 번에 끝납니다. 속도 걱정으로 편향을 그냥 두는 것은 값싼 선택이 아닙니다.

M도 2의 거듭제곱이라면 안전합니다. 그때는 나누어떨어져 나머지가 0이 됩니다. 다만 옛 rand()처럼 M이 2¹⁵나 RAND_MAX+1이 아닌 값인 경우가 있고, n이 실행 중에 정해지는 값이라면 2의 거듭제곱임을 보장할 수 없습니다.

실제 분포가 완전히 고른 분포와 얼마나 떨어져 있는지를 하나의 수로 나타낸 것이며, r(n−r)/(nM)입니다. 각 값의 확률 차이를 모두 더해 2로 나눈 값과 같습니다. 나머지가 0이면 0이고, r이 n의 절반 근처일 때 가장 큽니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.