임의의 범위를 1–5에서 1–7로 확장
1 ~ 5 범위의 임의의 정수를 생성하는 함수가 주어지면 1 ~ 7 범위의 임의의 정수를 생성하는 함수를 작성하십시오.
- 간단한 해결책은 무엇입니까?
- 메모리 사용량을 줄이거 나 느린 CPU에서 실행하는 효과적인 솔루션은 무엇입니까?
이것은 Adam Rosenfield의 솔루션과 동일하지만 일부 독자에게는 좀 더 명확 할 수 있습니다. rand5 ()가 1에서 5까지의 범위에서 통계적으로 임의의 정수를 반환하는 함수라고 가정합니다.
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
어떻게 작동합니까? 다음과 같이 생각해보십시오.이 2 차원 배열을 종이에 인쇄하고 다트 보드에 붙이고 무작위로 다트를 던진다 고 상상해보십시오. 0이 아닌 값에 도달하면 선택할 수있는 0이 아닌 값의 수가 같으므로 1에서 7 사이의 통계적으로 임의의 값입니다. 0을 쳤다면 0이 아닐 때까지 계속해서 다트를 던지십시오. 이것이 바로이 코드가하는 일입니다. i와 j 인덱스는 다트 보드에서 무작위로 위치를 선택하고 좋은 결과를 얻지 못하면 계속 다트를 던집니다.
Adam이 말했듯이 이것은 최악의 경우 영원히 실행될 수 있지만 통계적으로 최악의 경우는 발생하지 않습니다. :)
1/7은 기본 5에서 무한 십진수이기 때문에 일정한 시간에 실행되는 (정확히 정확한) 솔루션은 없습니다. 하나의 간단한 솔루션은 거부 샘플링을 사용하는 것입니다. 예 :
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
예상되는 런타임은 25/21 = 1.19 반복 반복이지만 무한 반복 할 확률은 무한합니다.
첫 번째 답변 외에 다른 답변을 추가하고 싶습니다 . 이 답변 은 임의성 사용을 최대화 하기 위해에 대한 호출 rand5()당 호출 수를 최소화하려고 rand7()합니다. 즉, 임의성을 귀중한 자원으로 생각한다면 임의의 비트를 버리지 않고 가능한 한 많이 사용하고 싶습니다. 이 답변은 Ivan의 답변에 제시된 논리와 약간 유사합니다 .
랜덤 변수 의 엔트로피는 잘 정의 된 수량입니다. 동일한 확률 (균일 분포)을 가진 N 상태를 취하는 랜덤 변수의 경우 엔트로피는 log 2 N입니다. 따라서 rand5()약 2.32193 비트의 엔트로피를 rand7()가지며 약 2.80735 비트의 엔트로피를가집니다. 임의성 사용을 극대화하려면에 대한 각 호출에서 2.32193 비트의 엔트로피를 모두 사용 rand5()하고를 호출 할 때마다 필요한 2.80735 비트의 엔트로피를 생성하는 데 적용해야합니다 rand7(). 따라서 근본적인 한계는 log (7) / log (5) = 1.20906 호출 rand5()당 rand7().
참고 사항 :이 답변의 모든 로그는 달리 지정하지 않는 한 밑이 2입니다. rand5()[0, 4] rand7()범위의 숫자를 반환하는 것으로 가정하고 [0, 6] 범위의 숫자를 반환하는 것으로 가정합니다. 범위를 각각 [1, 5] 및 [1, 7]로 조정하는 것은 간단합니다.
그럼 어떻게할까요? 우리는 0과 1 사이 의 무한 정확한 임의의 실수를 생성합니다 (이런 무한 정확한 숫자를 실제로 계산하고 저장할 수있는 순간을 가장합니다-나중에 수정하겠습니다). 5 진법으로 숫자를 생성하여 이러한 숫자를 생성 할 수 있습니다. 임의의 숫자 0. a1 a2 a3 ...을 i선택합니다 rand5(). 여기서 각 숫자 a 는를 호출하여 선택됩니다 . 예를 들어 RNG가 iall i에 대해 a = 1을 선택한 경우 , 그것이 매우 무작위가 아니라는 사실을 무시하면 실수 1/5 + 1/5 2 + 1/5 3 + ... = 1/4 (기하 급수의 합).
좋아요, 그래서 우리는 0과 1 사이의 임의의 실수를 선택했습니다. 이제 저는 그러한 난수가 균일하게 분포되어 있다고 주장합니다. 직관적으로 이것은 각 숫자가 균일하게 선택되었고 숫자가 무한히 정확하기 때문에 이해하기 쉽습니다. 그러나 이것에 대한 공식적인 증명은 다소 더 관련이 있습니다. 지금 우리는 이산 분포 대신 연속 분포를 다루고 있기 때문에 우리의 숫자가 구간 [ a, b] 에있을 확률 이 다음의 길이와 같다는 것을 증명해야합니다. 그 간격, b - a. 증거는 독자 =)를위한 연습으로 남겨집니다.
이제 [0, 1] 범위에서 균일하게 선택된 임의의 실수를 가지므로, [0, 6] 범위의 균일 한 난수로 변환하여의 출력을 생성해야합니다 rand7(). 어떻게할까요? 방금 한 것과 반대로-7 진법의 무한 정확한 10 진수로 변환 한 다음 각 7 진법 숫자는 rand7().
이전의 예를 들어 rand5()1의 무한 스트림을 생성하면 임의의 실수는 1/4이됩니다. 1/4을 밑수 7로 변환하면 무한 십진수 0.15151515 ...를 얻으므로 출력 1, 5, 1, 5, 1, 5 등으로 생성합니다.
좋아, 그래서 우리는 주요 아이디어를 가지고 있지만 두 가지 문제가 남아 있습니다. 우리는 실제로 무한히 정확한 실수를 계산하거나 저장할 수 없습니다. 그래서 우리는 한정된 부분만을 어떻게 다룰까요? 두 번째로, 우리는 실제로 이것을 7 진법으로 어떻게 변환할까요?
0과 1 사이의 숫자를 7 진법으로 변환하는 한 가지 방법은 다음과 같습니다.
- 7 곱하기
- 결과의 정수 부분은 다음 밑수 7 자리입니다.
- 정수 부분을 빼고 소수 부분 만 남깁니다.
- 1 단계로 이동
무한 정밀도 문제를 처리하기 위해 부분 결과를 계산하고 결과가 될 수있는 상한도 저장합니다. 즉, rand5()두 번 호출 했고 두 번 모두 1을 반환 했다고 가정 합니다. 지금까지 생성 한 숫자는 0.11 (기본 5)입니다. 생성 할 나머지 무한 일련의 호출이 무엇이든, rand5()우리가 생성하는 임의의 실수는 0.12보다 크지 않을 것입니다. 0.11 ≤ 0.11xyz ... <0.12 인 것은 항상 사실입니다.
따라서 지금까지의 현재 숫자와 최대 값을 추적하여 두 숫자를 모두 7 진법으로 변환 합니다 . 첫 번째 k숫자가 일치 하면 다음 k숫자를 안전하게 출력 할 수 있습니다 . 기본 5 자리의 무한 스트림은 k기본 7 표현 의 다음 자리에 영향을 미치지 않습니다 !
이것이 바로 알고리즘입니다.의 다음 출력을 rand7()생성 rand5()하기 위해 무작위 실수를 7 진수로 변환 할 때 다음 숫자의 값을 확실하게 알 수 있도록 필요한만큼의 숫자 만 생성합니다 . 테스트 도구가있는 Python 구현 :
import random
rand5_calls = 0
def rand5():
global rand5_calls
rand5_calls += 1
return random.randint(0, 4)
def rand7_gen():
state = 0
pow5 = 1
pow7 = 7
while True:
if state / pow5 == (state + pow7) / pow5:
result = state / pow5
state = (state - result * pow5) * 7
pow7 *= 7
yield result
else:
state = 5 * state + pow7 * rand5()
pow5 *= 5
if __name__ == '__main__':
r7 = rand7_gen()
N = 10000
x = list(next(r7) for i in range(N))
distr = [x.count(i) for i in range(7)]
expmean = N / 7.0
expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))
print '%d TRIALS' % N
print 'Expected mean: %.1f' % expmean
print 'Expected standard deviation: %.1f' % expstddev
print
print 'DISTRIBUTION:'
for i in range(7):
print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
print
print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)
rand7_gen()생성기 를 반환합니다. 내부 상태는 숫자를 7 진수로 변환하는 것과 관련된 내부 상태입니다. 테스트 도구는 next(r7)10000 번 호출 하여 10000 개의 난수를 생성 한 다음 그 분포를 측정합니다. 정수 수학 만 사용되므로 결과가 정확합니다.
또한 여기의 숫자는 매우 커지고 매우 빠릅니다. 5와 7의 거듭 제곱은 빠르게 증가합니다. 따라서, 큰 산술로 인해 많은 난수를 생성 한 후 성능이 눈에 띄게 저하되기 시작합니다. 그러나 여기에서 내 목표는 성능을 최대화하는 것이 아니라 임의 비트의 사용을 최대화하는 것이 었습니다 (두 번째 목표 임에도 불구하고).
이것의 한 번 실행에서 나는 rand5()10000 호출에 대해 12091 호출을 수행 rand7()하여 평균 4 개의 유효 숫자에 대한 최소 log (7) / log (5) 호출을 달성했으며 결과 출력은 균일했습니다.
포트 위해서 임의의 큰 정수가 내장되어 있지 않은 언어 코드, 당신은의 값을 모자해야 pow5하고 pow7네이티브 통합 유형의 최대 값 - 그들은 너무 커질 경우, 다음 재설정 모든 것을 다시 시작하십시오. 이렇게하면 호출 rand5()당 평균 호출 수가 rand7()약간 증가하지만 32 비트 또는 64 비트 정수의 경우에도 너무 많이 증가해서는 안됩니다.
(나는 Adam Rosenfeld의 답변 을 훔쳐서 약 7 % 더 빠르게 실행했습니다.)
rand5 ()가 균등 분포로 {0,1,2,3,4} 중 하나를 반환하고 목표가 균등 분포로 {0,1,2,3,4,5,6}을 반환한다고 가정합니다.
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
루프가 변수에서 만들 수있는 가장 큰 값을 추적하고 있습니다 max. 지금까지의 결과가 max % 7과 max-1 사이이면 결과는 해당 범위에서 균일하게 분산됩니다. 그렇지 않은 경우 0과 max % 7-1 사이의 임의의 나머지를 사용하고 rand ()를 다시 호출하여 새 숫자와 새 최대 값을 만듭니다. 그런 다음 다시 시작합니다.
편집 :이 방정식에서 rand5 ()를 호출하는 횟수는 x입니다.
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
연산:
7은 3 비트 시퀀스로 표현 될 수 있습니다.
rand (5)를 사용하여 각 비트를 0 또는 1로 무작위로 채 웁니다.
예 : rand (5)를 호출하고
결과가 1 또는 2
이면 결과가 4 또는 5이면 비트를 0으로 채우고
결과가 3이면 비트를 1로 채운 다음 무시하고 다시 수행합니다 (거부).
이렇게하면 0/1로 3 비트를 무작위로 채울 수 있으므로 1-7에서 숫자를 얻을 수 있습니다.
편집 : 이것은 가장 간단하고 효율적인 대답처럼 보이므로 여기에 대한 몇 가지 코드가 있습니다.
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
편집 : 그것은 잘 작동하지 않습니다. 1000 분의 2 정도 차이가납니다 (완벽한 rand5라고 가정). 버킷은 다음을 얻습니다.
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
합계로 전환하여
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
2가 추가 될 때마다 크기가 증가하는 것 같습니다.
BTW : 위의 오류 표는 샘플링을 통해 생성 된 것이 아니라 다음과 같은 반복 관계에 의해 생성되었습니다.
p[x,n]에 대한 호출에서output=x발생할 수 있는 여러 가지 방법 입니다.nrand5
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
다음은 {1, 2, 3, 4, 5}에 균일 분포를 생성하는 난수 생성기를 사용하여 {1, 2, 3, 4, 5, 6, 7}에 균일 분포를 생성합니다. 코드는 지저분하지만 논리는 명확합니다.
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
가장 효율적인 대답을 제공하려는 추가 제약을 고려한다면, 즉 입력 스트림이 주어진 경우, 1-5 I길이 의 균일하게 분포 된 정수는 가장 긴 상대 길이의 1-7에서 균일하게 분포 된 정수 m스트림을 출력합니다. O에 m, 말하십시오 L(m).
이를 분석하는 가장 간단한 방법은 스트림 I와 O5 진 및 7 진을 각각 처리하는 것입니다. 이것은 스트림을 가져가는 주 답변의 아이디어 a1, a2, a3,... -> a1+5*a2+5^2*a3+..와 마찬가지로 stream에 대해 달성됩니다 O.
그럼 길이의 입력 스트림의 섹션 가지고 있으면 m choose n s.t. 5^m-7^n=c어디에 c>0가능한 한 작게한다. 그런 다음 길이가 m 인 입력 스트림에서 1to to 정수로의 5^m균일 한 맵이 있고 1에서 정수 7^n길이 n의 출력 스트림으로의 또 다른 균일 한 맵이 있습니다. 여기서 매핑 된 정수일 때 입력 스트림에서 몇 가지 경우를 잃어야 할 수도 있습니다. 을 초과 7^n합니다.
그래서이 값주는 L(m)주위의 m (log5/log7)약이다 .82m.
위 분석의 어려움은 5^m-7^n=c정확히 풀기 어려운 방정식 과 획일 값 1이 5^m초과 7^n하여 효율성을 잃는 경우 입니다.
문제는 m (log5 / log7)의 가능한 최상의 값에 얼마나 근접 할 수 있는지입니다. 예를 들어이 숫자가 정수에 가까워지면 정확한 정수 출력 값을 얻을 수있는 방법을 찾을 수 있습니까?
경우 5^m-7^n=c다음 입력 스트림에서 우리는 효과적으로에서 균일 난수 생성 0에를 (5^m)-1하고보다 높은 어떤 값을 사용하지 않습니다 7^n. 그러나 이러한 값은 구출되어 다시 사용할 수 있습니다. 1에서 5^m-7^n. 그래서 우리는 더 많은 출력 값을 만들 수 있도록 이것을 사용하고 7 진 숫자로 변환 할 수 있습니다.
우리가 할 수있는 경우 T7(X)의 출력 순서의 평균 길이로 random(1-7)균일 한 크기의 입력에서 유도 된 정수 X, 그 가정 5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.
그렇다면 T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)우리는 길이를 길이 잔차 확률 7 ^ N0 / m ^ 5와 서열이 전혀 없기 때문에, 5^m-7^n0확률을 (5^m-7^n0)/5^m).
계속 대체하면 다음을 얻습니다.
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
그 후
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
이것을 넣는 또 다른 방법은 다음과 같습니다.
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
가능한 가장 좋은 경우는 where 5^m=7^n+s, where 위의 내 원본 s<7입니다.
그럼 T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)전처럼.
최악의 경우는 k와 st 5 ^ m = kx7 + s 만 찾을 수있는 경우입니다.
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
다른 경우는 중간에 있습니다. 매우 큰 m에 대해 얼마나 잘 할 수 있는지, 즉 오류 항을 얼마나 잘 얻을 수 있는지 보는 것은 흥미로울 것입니다.
T7(5^m) = m (Log5/Log7)+e(m)
e(m) = o(1)일반적 으로 달성하는 것은 불가능 해 보이지만 우리가 증명할 수 있기를 바랍니다 e(m)=o(m).
그런 다음 모든 것은의 5^m다양한 값에 대한 의 7 자리 숫자 분포 에 m있습니다.
나는 이것을 다루는 많은 이론이 있다고 확신합니다. 나는 언젠가 다시보고보고 할 수 있습니다.
여기서 숙제 문제가 허용됩니까?
이 함수는 0과 6 사이의 숫자를 생성하기 위해 조잡한 "기본 5"수학을 수행합니다.
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
다음은 Adam의 대답을 Python으로 구현 한 것 입니다.
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
저는 제가 살펴보고있는 알고리즘을 파이썬에 던지는 것을 좋아합니다. 그래서 저는 그것들을 가지고 놀 수 있도록 여기에 게시하고 싶습니다. 함께 던지는 데 오랜 시간이 걸리지 않고 누군가에게 유용하다는 희망으로 여기에 게시 할 것이라고 생각했습니다.
왜 간단하지 않습니까?
int random7() {
return random5() + (random5() % 3);
}
이 솔루션에서 1과 7을 얻을 확률은 모듈로 때문에 낮지 만 빠르고 읽기 쉬운 솔루션을 원한다면 이것이 갈 길입니다.
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
선택한 솔루션과 달리 알고리즘은 일정한 시간에 실행됩니다. 그러나 선택한 솔루션의 평균 실행 시간보다 rand5를 2 번 더 호출합니다.
이 생성기는 완벽하지 않지만 (숫자 0은 다른 어떤 숫자보다 0.0064 % 더 많은 확률을 가짐), 대부분의 실제적인 목적을 위해 일정 시간 보장이이 부정확성을 능가합니다.
설명
이 솔루션은 숫자 15,624를 7로 나눌 수 있다는 사실에서 파생되므로 0에서 15,624까지의 숫자를 무작위로 균일하게 생성 한 다음 mod 7을 취하면 거의 균일 한 rand7 생성기를 얻을 수 있습니다. 0에서 15,624 사이의 숫자는 rand5를 6 번 굴려서 다음과 같이 기본 5 숫자의 자릿수를 형성하는 데 사용하여 균일하게 생성 할 수 있습니다.
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
그러나 mod 7의 속성을 사용하면 방정식을 약간 단순화 할 수 있습니다.
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
그래서
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
된다
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
이론
숫자 15,624는 무작위로 선택되지 않았지만 fermat의 작은 정리를 사용하여 발견 할 수 있습니다. p가 소수이면
a^(p-1) = 1 mod p
그래서 이것은 우리에게
(5^6)-1 = 0 mod 7
(5 ^ 6) -1은 다음과 같습니다.
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
이것은 기본 5 형식의 숫자이므로이 방법을 사용하여 임의의 숫자 생성기에서 다른 임의의 숫자 생성기로 이동할 수 있음을 알 수 있습니다. 지수 p-1을 사용할 때 항상 0에 대한 작은 편향이 도입됩니다.
여기서 rand (n)이 " 0 에서 n-1 까지의 균일 분포에서 임의의 정수"를 의미 한다고 가정하면 여기에 그 효과가있는 Python의 randint를 사용하는 코드 샘플이 있습니다. randint (5) 및 상수 만 사용 하여 randint (7) 의 효과를 생성합니다 . 사실 좀 어리석은
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
Adam Rosenfield의 정답 뒤에있는 전제는 다음과 같습니다.
- x = 5 ^ n (그의 경우 : n = 2)
- n rand5 호출을 조작하여 [1, x] 범위 내 에서 숫자 y 를 얻습니다 .
- z = ((int) (x / 7)) * 7
- y> z이면 다시 시도하십시오. 그렇지 않으면 y % 7 + 1을 반환합니다.
n이 2와 같을 때 4 개의 일회용 가능성이 있습니다 : y = {22, 23, 24, 25}. n = 6을 사용하는 경우, 1 개의 스로 어웨이 (y = {15625}) 만 있습니다.
5 ^ 6 = 15625
7 * 2232 = 15624
rand5에 더 많이 전화합니다. 그러나 버리는 값 (또는 무한 루프)을 얻을 가능성이 훨씬 낮습니다. y에 대해 가능한 폐기 값을 얻을 수없는 방법이 있다면 아직 찾지 못했습니다.
내 대답은 다음과 같습니다.
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
다른 것보다 조금 더 복잡하지만 rand5에 대한 호출을 최소화한다고 생각합니다. 다른 솔루션과 마찬가지로 오랜 시간 동안 반복 될 가능성이 적습니다.
간단하고 효율적 :
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
( 당신이 가장 좋아하는 "프로그래머"만화는 무엇입니까? ) 에서 영감을 얻었습니다 .
선택할 수있는 가능성이 7 개가 아닌 한, 가능성의 수에 5를 곱하는 또 다른 난수를 그립니다. Perl에서 :
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
1부터 시작하는 범위가 마음에 들지 않으므로 0부터 시작하겠습니다. :-)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
균등 분배와 rand5 호출이 없습니다.
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
미리 시드를 설정해야합니다.
나는 그것이 대답되었다는 것을 알고 있지만 이것은 잘 작동하는 것 같지만 편견이 있는지 말할 수 없습니다. 내 '테스트'는 그것이 적어도 합리적이라고 제안합니다.
아마도 Adam Rosenfield가 친절하게 언급 할 수 있을까요?
내 (순진한?) 아이디어는 다음과 같습니다.
rand7을 만들기에 충분한 임의의 비트가있을 때까지 rand5를 누적합니다. 최대 2 개의 rand5가 필요합니다. rand7 번호를 얻으려면 누적 값 mod 7을 사용합니다.
누산기 오버플로를 방지하고 누산기가 mod 7이므로 누산기의 mod 7을 사용합니다.
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
rand7 () 함수는 다음과 같습니다.
(rand5의 범위는 0-4이고 rand7은 0-6입니다.)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
편집 : 1 억 번의 시도에 대한 결과를 추가했습니다.
'실제'랜드 함수 모드 5 또는 7
rand5 : avg = 1.999802 0 : 20003944 1 : 19999889 2 : 20003690 3 : 19996938 4 : 19995539 rand7 : avg = 3.000111 0 : 14282851 1 : 14282879 2 : 14284554 3 : 14288546 4 : 14292388 5 : 14288736 6 : 14280046
내 rand7
평균은 괜찮아 보이고 숫자 분포도 괜찮아 보입니다.
randt : avg = 3.000080 0 : 14288793 1 : 14280135 2 : 14287848 3 : 14285277 4 : 14286341 5 : 14278663 6 : 14292943
위에서 언급 한 우아한 알고리즘이 있지만 여기에 접근하는 한 가지 방법이 있습니다. 0에서 생성 된 값을 가정합니다.
R2 = 2보다 작은 값을 제공하는 난수 생성기 (샘플 공간 = {0, 1})
R8 = 8보다 작은 값을 제공하는 난수 생성기 (샘플 공간 = {0, 1, 2, 3, 4, 5, 6, 7 })
R2에서 R8을 생성하려면 R2를 세 번 실행하고 3 개 실행의 결합 결과를 3 자리 숫자로 된 이진수로 사용합니다. 다음은 R2가 세 번 실행될 때의 값 범위입니다.
0 0 0-> 0
.
.
11 1-> 7
이제 R8에서 R7을 생성하려면 7이 반환되면 R7을 다시 실행하면됩니다.
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
로터리 솔루션은 R5에서 R2를 생성하고 (R8에서 R7을 생성 한 것처럼), R2에서 R8을 생성 한 다음 R8에서 R7을 생성하는 것입니다.
다음은 정수 내에 완전히 들어가고 최적의 약 4 % 내에있는 솔루션입니다 (예 : {0..6}의 모든 항목에 대해 {0..4}의 1.26 임의의 숫자 사용). 코드는 Scala에 있지만 수학은 모든 언어에서 합리적으로 명확해야합니다. 7 ^ 9 + 7 ^ 8이 5 ^ 11에 매우 가깝다는 사실을 활용합니다. 따라서 5 진법에서 11 자리 숫자를 선택한 다음 범위 내에있는 경우 (9 진법 7 자리 숫자 제공) 7 진법의 9 자리 숫자로 해석하고 9 자리 숫자를 초과하는 경우 8 자리 숫자로 해석합니다. . :
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
인터프리터에 테스트를 붙여 넣으면 (실제로 REPL) 다음을 얻습니다.
scala> val five = new Random5
five: Random5 = Random5@e9c592
scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
분포는 훌륭하고 평평합니다 (대략 가우시안 분포에서 예상 한대로 각 빈에서 10 ^ 8의 1/7 중 약 10k 이내).
사용하여 압연 총 , 당신은 둘 다 할 수
- 균등 분배를 유지하십시오. 과
- 무작위 시퀀스의 요소를 희생 할 필요가 없습니다.
이 두 가지 문제는 단순한 rand(5)+rand(5)...유형 솔루션 의 문제입니다 . 다음 Python 코드는이를 구현하는 방법을 보여줍니다 (대부분이 배포를 증명하고 있음).
import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
##### qq.py #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
##### qq_notsogood.py #####
#r = 20
#while r > 6:
#r = int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)
그리고이 출력은 결과를 보여줍니다.
pax$ python qq.py
0: 99908 14.27257
1: 100029 14.28986
2: 100327 14.33243
3: 100395 14.34214
4: 99104 14.15771
5: 99829 14.26129
6: 100408 14.34400
Variation = 1304 (0.18629%)
pax$ python qq.py
0: 99547 14.22100
1: 100229 14.31843
2: 100078 14.29686
3: 99451 14.20729
4: 100284 14.32629
5: 100038 14.29114
6: 100373 14.33900
Variation = 922 (0.13171%)
pax$ python qq.py
0: 100481 14.35443
1: 99188 14.16971
2: 100284 14.32629
3: 100222 14.31743
4: 99960 14.28000
5: 99426 14.20371
6: 100439 14.34843
Variation = 1293 (0.18471%)
rand(5)+rand(5)6 개 이상을 반환하는 경우를 무시하는 단순한 은 위에 표시된 방법의 100 배인 18 %의 일반적인 변형을 갖습니다 .
pax$ python qq_notsogood.py
0: 31756 4.53657
1: 63304 9.04343
2: 95507 13.64386
3: 127825 18.26071
4: 158851 22.69300
5: 127567 18.22386
6: 95190 13.59857
Variation = 127095 (18.15643%)
pax$ python qq_notsogood.py
0: 31792 4.54171
1: 63637 9.09100
2: 95641 13.66300
3: 127627 18.23243
4: 158751 22.67871
5: 126782 18.11171
6: 95770 13.68143
Variation = 126959 (18.13700%)
pax$ python qq_notsogood.py
0: 31955 4.56500
1: 63485 9.06929
2: 94849 13.54986
3: 127737 18.24814
4: 159687 22.81243
5: 127391 18.19871
6: 94896 13.55657
Variation = 127732 (18.24743%)
그리고 Nixuz의 조언에 따라 스크립트를 정리하여 항목을 추출하고 사용할 수 있습니다 rand7....
import random
# rand5() returns 0 through 4 inclusive.
def rand5():
return int (random.random () * 5)
# rand7() generator returns 0 through 6 inclusive (using rand5()).
def rand7():
rand7ret = 0
while True:
rand7ret = (rand7ret + rand5()) % 7
yield rand7ret
# Number of test runs.
count = 700000
# Work out distribution.
distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
r = rgen.next()
distrib[r] = distrib[r] + 1
# Print distributions and calculate variation.
high = distrib[0]
low = distrib[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
if distrib[i] < low:
low = distrib[i]
if distrib[i] > high:
high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
이 대답은 Rand5 함수에서 가능한 가장 많은 엔트로피를 얻는 실험에 가깝습니다. 따라서 t는 다른 구현보다 다소 불분명하고 거의 확실히 훨씬 느립니다.
0-4에서 균일 분포를 가정하고 0-6에서 결과 균일 분포를 가정합니다.
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
Rand5 호출 당 버퍼에 추가되는 비트 수는 현재 4/5 * 2이므로 1.6입니다. 0.05만큼 증가하는 1/5 확률 값이 포함되어 있으면 1.65이지만 코드에서 이것을 비활성화해야했던 주석을 참조하십시오.
Rand7에 대한 호출에 사용되는 비트 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
이것은 3 + 3/8 + 3/64 + 3/512 ... 약 3.42
세븐에서 정보를 추출하여 호출 당 1 / 8 * 1 / 7 비트를 회수하므로 약 0.018
이렇게하면 호출 당 3.4 비트의 순 소비가 제공됩니다. 즉, Rand7마다 Rand5에 대한 호출 비율은 2.125입니다. 최적은 2.1이어야합니다.
Rand5에 대한 호출 비용이 극도로 비싸지 않는 한 (외부 엔트로피 소스를 호출하는 경우) 이 방법이 여기에있는 다른 많은 방법 보다 훨씬 느리다고 생각합니다 .
PHP에서
function rand1to7() {
do {
$output_value = 0;
for ($i = 0; $i < 28; $i++) {
$output_value += rand1to5();
}
while ($output_value != 140);
$output_value -= 12;
return floor($output_value / 16);
}
루프를 사용하여 16과 127 사이의 난수를 생성하고 16으로 나누어 1과 7.9375 사이의 부동 소수점을 만든 다음 반올림하여 1과 7 사이의 정수를 얻습니다. 착각하지 않으면 16/112의 기회가 있습니다. 7 가지 결과 중 하나.
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
필요한 함수는 rand1_7 () 이며 테스트하고 플롯 할 수 있도록 rand1_5 ()를 작성했습니다.
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
첫 번째 함수의 출력을 조정하십시오.
0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
참고 URL : https://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7
'programing' 카테고리의 다른 글
| JPA와 Hibernate의 차이점은 무엇입니까? (0) | 2020.09.30 |
|---|---|
| LINQ Aggregate 알고리즘 설명 (0) | 2020.09.30 |
| 동적으로 명명 된 속성을 JavaScript 개체에 추가 할 수 있습니까? (0) | 2020.09.30 |
| 숫자가 실수인지 정수인지 어떻게 확인합니까? (0) | 2020.09.30 |
| Mac OS X에서 Java는 어디에 설치됩니까? (0) | 2020.09.30 |