범위 내에서 임의의 정수를 생성하는 방법
이것은 이전에 게시 된 질문의 후속입니다.
주사위의 측면을 모방하기 위해 1 ~ 6과 같은 특정 범위 내에서 임의의 숫자를 생성 할 수 있기를 바랍니다.
어떻게하면 되나요?
지금까지의 모든 답은 수학적으로 잘못되었습니다. 반환 하는 구간의 길이를 나누지 않는 한 (즉, 2의 거듭 제곱) 반환 rand() % N은 범위 내의 숫자를 균일하게 제공하지 않습니다 . 또한의 모듈 리가 독립적 인지 여부를 알지 못합니다. 균일하지만 매우 무작위 적이 지 않은. 합리적으로 보이는 유일한 가정 은 푸 아송 분포를내는 것입니다. 같은 크기의 겹치지 않는 두 부분 구간은 똑같이 가능성이 있고 독립적입니다. 유한 한 값 집합의 경우 이는 균일 한 분포를 의미하며의 값 이 잘 분산되도록합니다.[0, N)Nrand()rand()0, 1, 2, ...rand()rand()
즉, 범위를 변경하는 유일한 올바른 방법은 rand()상자로 나누는 것입니다. 예를 들어 RAND_MAX == 11범위를 원하는 경우 1, 2 등으로 1..6할당해야합니다 . 이들은 분리되고 동일한 크기의 간격이므로 균일하고 독립적으로 분포됩니다.{0,1}{2,3}
부동 소수점 나누기를 사용하라는 제안은 수학적으로 타당하지만 원칙적으로 반올림 문제가 있습니다. 아마도 double그것을 작동시키기에 충분히 높은 정밀도 일 것입니다. 아마 아닐거야. 나는 모르고 그것을 알아 내고 싶지도 않다. 어쨌든 대답은 시스템에 따라 다릅니다.
올바른 방법은 정수 산술을 사용하는 것입니다. 즉, 다음과 같은 것을 원합니다.
#include <stdlib.h> // For random(), RAND_MAX
// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
unsigned long
// max <= RAND_MAX < ULONG_MAX, so this is okay.
num_bins = (unsigned long) max + 1,
num_rand = (unsigned long) RAND_MAX + 1,
bin_size = num_rand / num_bins,
defect = num_rand % num_bins;
long x;
do {
x = random();
}
// This is carefully written not to overflow
while (num_rand - defect <= (unsigned long)x);
// Truncated division is intentional
return x/bin_size;
}
루프는 완벽하게 균일 한 분포를 얻기 위해 필요합니다. 예를 들어, 0에서 2까지의 임의의 숫자가 주어지고 0에서 1까지의 숫자 만 원하면 2를 얻지 못할 때까지 계속 당기십시오. 이것이 동일한 확률로 0 또는 1을 제공하는지 확인하는 것은 어렵지 않습니다. 이 방법은 다르게 코딩되었지만 nos가 대답 한 링크에도 설명되어 있습니다. 나는 더 나은 배포판을 가지고 random()있기보다는 rand()(에 대한 man 페이지에서 언급했듯이 rand()) 사용하고 있습니다.
기본 범위를 벗어난 임의의 값을 얻으려면 [0, RAND_MAX]까다로운 작업을 수행해야합니다. 아마도 가장 편리한 함수를 정의하는 것입니다 random_extended()끌어 n비트 (사용 random_at_most()으로) 되돌아 [0, 2**n)한 다음 적용 random_at_most()과 random_extended()대신에 random()(그리고 2**n - 1대신에 RAND_MAX) 이하의 임의의 값을 뽑아 2**n당신이 그런를 보유 할 수있는 숫자 유형이 가정, 가치. 마지막으로, 물론 음수 값을 포함 [min, max]하여를 사용하여 값을 얻을 수 있습니다 min + random_at_most(max - min).
@Ryan Reich의 답변에 이어 정리 된 버전을 제공 할 것이라고 생각했습니다. 첫 번째 경계 검사는 두 번째 경계 검사를 고려할 때 필요하지 않으며 재귀 적이 아닌 반복적으로 만들었습니다. [최소, 최대] 범위의 값을 반환합니다 . 여기서 max >= min및 1+max-min < RAND_MAX.
unsigned int rand_interval(unsigned int min, unsigned int max)
{
int r;
const unsigned int range = 1 + max - min;
const unsigned int buckets = RAND_MAX / range;
const unsigned int limit = buckets * range;
/* Create equal size buckets all in a row, then fire randomly towards
* the buckets until you land in one of them. All buckets are equally
* likely. If you land off the end of the line of buckets, try again. */
do
{
r = rand();
} while (r >= limit);
return min + (r / buckets);
}
다음은 범위의 최대 값과 최소값을 알고 있고 범위 사이에 포함 된 숫자를 생성하려는 경우 공식입니다.
r = (rand() % (max + 1 - min)) + min
unsigned int
randr(unsigned int min, unsigned int max)
{
double scaled = (double)rand()/RAND_MAX;
return (max - min +1)*scaled + min;
}
그냥하지 않겠습니까?
srand(time(NULL));
int r = ( rand() % 6 ) + 1;
%모듈러스 연산자입니다. 기본적으로 6으로 나누고 나머지를 반환합니다 ... from 0-5
편향 문제를 이해하지만 거부 기반 방법의 예측할 수없는 실행 시간을 견딜 수없는 사람들을 위해이 시리즈는 [0, n-1]간격 에서 점차적으로 편향되지 않은 임의의 정수를 생성 합니다.
r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...
고정 소수점 임의의 i * log_2(RAND_MAX + 1)비트 수 ( i반복 횟수) 를 합성하고에 의해 긴 곱셈을 수행하여이를 수행합니다 n.
에 비해 비트 수가 충분히 크면 n바이어스가 헤아릴 수 없을 정도로 작아집니다.
이 질문 에서와 같이 RAND_MAX + 1이보다 작은 지 n( 이 질문 에서와 같이 ) 또는 2의 거듭 제곱 이 아닌지 여부 는 중요하지 않지만 RAND_MAX * n큰 경우 정수 오버플로를 방지하려면주의해야합니다 .
모듈로 편향을 피하기 위해 (다른 답변에서 제 안됨) 항상 다음을 사용할 수 있습니다.
arc4random_uniform(MAX-MIN)+MIN
여기서 "MAX"는 상한이고 "MIN"은 하한입니다. 예를 들어 10에서 20 사이의 숫자의 경우 :
arc4random_uniform(20-10)+10
arc4random_uniform(10)+10
간단한 솔루션이며 "rand () % N"을 사용하는 것보다 낫습니다.
다음은 Ryan Reich의 솔루션보다 약간 더 간단한 알고리즘입니다.
/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
uint32_t range = (end - begin) + 1;
uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);
/* Imagine range-sized buckets all in a row, then fire randomly towards
* the buckets until you land in one of them. All buckets are equally
* likely. If you land off the end of the line of buckets, try again. */
uint32_t randVal = rand();
while (randVal >= limit) randVal = rand();
/// Return the position you hit in the bucket + begin as random number
return (randVal % range) + begin;
}
Example (RAND_MAX := 16, begin := 2, end := 7)
=> range := 6 (1 + end - begin)
=> limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)
The limit is always a multiple of the range,
so we can split it into range-sized buckets:
Possible-rand-output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Buckets: [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
Buckets + begin: [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]
1st call to rand() => 13
→ 13 is not in the bucket-range anymore (>= limit), while-condition is true
→ retry...
2nd call to rand() => 7
→ 7 is in the bucket-range (< limit), while-condition is false
→ Get the corresponding bucket-value 1 (randVal % range) and add begin
=> 3
Ryan이 맞지만 무작위성의 원인에 대해 알려진 것을 기반으로 솔루션은 훨씬 더 간단 할 수 있습니다. 문제를 다시 설명하려면 :
[0, MAX)균등 분포 로 범위 내에서 정수를 출력하는 임의성의 근원이 있습니다 .- 목표는 범위
[rmin, rmax]에서 균일하게 분포 된 임의의 정수를 생성하는 것입니다0 <= rmin < rmax < MAX.
In my experience, if the number of bins (or "boxes") is significantly smaller than the range of the original numbers, and the original source is cryptographically strong - there is no need to go through all that rigamarole, and simple modulo division would suffice (like output = rnd.next() % (rmax+1), if rmin == 0), and produce random numbers that are distributed uniformly "enough", and without any loss of speed. The key factor is the randomness source (i.e., kids, don't try this at home with rand()).
Here's an example/proof of how it works in practice. I wanted to generate random numbers from 1 to 22, having a cryptographically strong source that produced random bytes (based on Intel RDRAND). The results are:
Rnd distribution test (22 boxes, numbers of entries in each box): 1: 409443 4.55% 2: 408736 4.54% 3: 408557 4.54% 4: 409125 4.55% 5: 408812 4.54% 6: 409418 4.55% 7: 408365 4.54% 8: 407992 4.53% 9: 409262 4.55% 10: 408112 4.53% 11: 409995 4.56% 12: 409810 4.55% 13: 409638 4.55% 14: 408905 4.54% 15: 408484 4.54% 16: 408211 4.54% 17: 409773 4.55% 18: 409597 4.55% 19: 409727 4.55% 20: 409062 4.55% 21: 409634 4.55% 22: 409342 4.55% total: 100.00%
This is as close to uniform as I need for my purpose (fair dice throw, generating cryptographically strong codebooks for WWII cipher machines such as http://users.telenet.be/d.rijmenants/en/kl-7sim.htm, etc). The output does not show any appreciable bias.
Here's the source of cryptographically strong (true) random number generator: Intel Digital Random Number Generator and a sample code that produces 64-bit (unsigned) random numbers.
int rdrand64_step(unsigned long long int *therand)
{
unsigned long long int foo;
int cf_error_status;
asm("rdrand %%rax; \
mov $1,%%edx; \
cmovae %%rax,%%rdx; \
mov %%edx,%1; \
mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
*therand = foo;
return cf_error_status;
}
I compiled it on Mac OS X with clang-6.0.1 (straight), and with gcc-4.8.3 using "-Wa,q" flag (because GAS does not support these new instructions).
As said before modulo isn't sufficient because it skews the distribution. Heres my code which masks off bits and uses them to ensure the distribution isn't skewed.
static uint32_t randomInRange(uint32_t a,uint32_t b) {
uint32_t v;
uint32_t range;
uint32_t upper;
uint32_t lower;
uint32_t mask;
if(a == b) {
return a;
}
if(a > b) {
upper = a;
lower = b;
} else {
upper = b;
lower = a;
}
range = upper - lower;
mask = 0;
//XXX calculate range with log and mask? nah, too lazy :).
while(1) {
if(mask >= range) {
break;
}
mask = (mask << 1) | 1;
}
while(1) {
v = rand() & mask;
if(v <= range) {
return lower + v;
}
}
}
The following simple code lets you look at the distribution:
int main() {
unsigned long long int i;
unsigned int n = 10;
unsigned int numbers[n];
for (i = 0; i < n; i++) {
numbers[i] = 0;
}
for (i = 0 ; i < 10000000 ; i++){
uint32_t rand = random_in_range(0,n - 1);
if(rand >= n){
printf("bug: rand out of range %u\n",(unsigned int)rand);
return 1;
}
numbers[rand] += 1;
}
for(i = 0; i < n; i++) {
printf("%u: %u\n",i,numbers[i]);
}
}
Will return a floating point number in the range [0,1]:
#define rand01() (((double)random())/((double)(RAND_MAX)))
'IT story' 카테고리의 다른 글
| 정적 메소드와 정적 변수는 Java에서 어디에 저장됩니까? (0) | 2020.08.17 |
|---|---|
| 문자열에서 첫 x 문자를 제거 하시겠습니까? (0) | 2020.08.17 |
| jquery $ (window) .height ()는 문서 높이를 반환합니다. (0) | 2020.08.15 |
| GC.Collect ()를 사용하는 것이 왜 그렇게 잘못 되었나요? (0) | 2020.08.15 |
| Vim : 줄을 이전에 잡아 당긴 다른 줄로 바꾸기 (0) | 2020.08.15 |