64位范围之间的随机数 [英] 64bit random number between a range
问题描述
所以，我一直在寻找一个功能，这需要两个参数低值和高值（这两个64位整数），比生成这些范围之间的随机数了两天。我把遇到的问题是，数量只是没有一个64位的int值。或在边缘处的数目比在中间的那些更为常见。
下面是一些code：它只是不断要么返回-1或0 ...
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆inttypes.h GT;范围1的int64_t = 0，范围2 = 18446744073709551614;getRandomInRange的int64_t（低的int64_t和int64_t高）
{
base_random的int64_t = RAND（）;
如果（RAND_MAX == base_random）返回getRandomInRange（低，高）;
INT范围=高一低，
余数= RAND_MAX％的范围内，
斗= RAND_MAX /范围;
如果（base_random＆LT; RAND_MAX余）{
返回低+ base_random /桶;
}其他{
返回getRandomInRange（低，高）;
}
}诠释主（）{
INT I;
对于（i = 0; I＆LT; 100;我++）{
的printf（随机数：％LLD \\ n，getRandomInRange（范围1，范围2））;
}
}
拍摄模N不会导致均匀分布，除非正好ñ划分范围R：
RND = 0..15，范围= 9。 0 1 2 3 4 5 6 7 8示 - 0..8％9
0 1 2 3 4 5 6≤ - 9-15％9
----------------------------------
2 2 2 2 2 2 2 1 1所述; - 总和= 16
同样地，如果一个人试图避免该事实由与例如乘以9月16日
RND = 0..15，范围= 9，减少功能= RND * -9;＆GT; 4，一个具有
0 1 2 3 4 5 6 7 8 RND = 0，2，4，6，8，9，13，15和
0 1 2 3 5 6 7 RND = 1，3，5，7，10，12，14
------------------------
2 2 2 2 1 2 2 2 1所述; - 总和= 16
这就是所谓的鸽子洞的原则在行动。
创建的随机数的均匀分布的一种适当的方式是生成CEIL（LOG2（N））的随机数的位，直到由位psented数重新$ P $小于范围：
INT rand_orig（）; //原始的随机函数从0..2 ^ n-1个返回值
//假设N = CEIL（LOG2（N））;
INT兰特（INT N）
{
诠释Ÿ;
做{
Y = rand_orig（）;
}而（Y＆GT; = N）;
返回是;
}
这可能是当然的，如果rand_orig改善（）;将返回的多的较大值N >>日志（N）的均匀分布;然后就足够了放弃rand_orig的（）是比N的最大倍数，降低与模数范围较大的只有这些值。
另一种方法是，以均匀地创建平衡值的方法（N>范围）的所有桶，例如
的#define CO_PRIME 1 //最好有一些大素2 ^（N-1） - ; CO_PRIME＆LT; 2 ^ n-1个
INT rand_orig（）; //一些函数返回范围内的随机数0..2 ^ n-1个
INT兰特（INT N）// N是范围
{
静态INT X;
INT Y = rand_orig（）;
INT new_rand =（X + Y）％N;
X =（X + CO_PRIME）％N;
返回new_rand;
}
现在这个平衡任期期间 X 是N，导致至少均匀分布。
So I have been searching for a couple of days for a functions which takes 2 arguments a low value and a high value(both of which 64bits ints) than generates a random number between these ranges. The problem I keep encountering is that the number just isn't a 64 bit int. or the number at the edges are more common than the ones in the middle.
Here is some code: it just keeps returning either -1 or 0...
#include<stdio.h>
#include<stdlib.h>
#include<inttypes.h>
int64_t range1=0,range2=18446744073709551614;
int64_t getRandomInRange(int64_t low, int64_t high )
{
int64_t base_random = rand();
if (RAND_MAX==base_random) return getRandomInRange(low, high);
int range = high-low,
remainder = RAND_MAX%range,
bucket = RAND_MAX/range;
if (base_random < RAND_MAX-remainder) {
return low+base_random/bucket;
} else {
return getRandomInRange(low, high);
}
}
int main () {
int i;
for (i=0;i<100;i++) {
printf("random number: %lld\n",getRandomInRange(range1, range2));
}
}
Taking a modulo N doesn't lead to uniform distribution, unless N divides the range R exactly:
rnd = 0..15, range = 9.
0 1 2 3 4 5 6 7 8 <-- 0..8 % 9
0 1 2 3 4 5 6 <-- 9-15 % 9
----------------------------------
2 2 2 2 2 2 2 1 1 <-- sum = 16
Likewise, if one tries to avoid that fact by multiplying with e.g. 9 / 16
rnd = 0..15, range = 9, reducing function = rnd * 9 >> 4, one has
0 1 2 3 4 5 6 7 8 for rnd = 0, 2, 4, 6, 8, 9, 13, 15 and
0 1 2 3 5 6 7 for rnd = 1, 3, 5, 7, 10, 12, 14
------------------------
2 2 2 2 1 2 2 2 1 <-- sum = 16
This is so called 'pigeon-hole principle' in action.
One proper way to create uniform distribution of random number is to generate ceil(log2(N)) bits of random number, until the number represented by the bits is less than the range:
int rand_orig(); // the "original" random function returning values from 0..2^n-1
// We assume that n = ceil(log2(N));
int rand(int N)
{
int y;
do {
y = rand_orig();
} while (y >= N);
return y;
}
This can be of course improved if the rand_orig(); would return much larger values n >> log(N) in uniform distribution; then it suffices to discard only those values of rand_orig() that are larger than the largest multiple of N and reducing the range with modulo.
Another way would be to create a method that balances the values (N > range) uniformly to all buckets, e.g.
#define CO_PRIME 1 // Better to have some large prime 2^(n-1) < CO_PRIME < 2^n-1
int rand_orig(); // some function returning random numbers in range 0..2^n-1
int rand(int N) // N is the range
{
static int x;
int y = rand_orig();
int new_rand = (x + y) % N;
x = (x + CO_PRIME) % N;
return new_rand;
}
Now the period of this balancing term x is N, leading to at least uniform distribution.
这篇关于64位范围之间的随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
