生成指定范围内的随机整数

我需要一个函数,将生成一个给定范围内的随机整数(包括边界值)。我没有不合理的质量/随机性要求; 我有四个要求:

  • 我需要速战速决。我的项目需要生成数百万(有时甚至数千万)的随机数,而我当前的生成器函数已被证明是一个瓶颈。
  • 我需要它是合理的统一(使用兰特()是完全罚款)。
  • 最小-最大范围可以是从 < 0,1 > 到 <-32727,32727 > 的任何值。
  • 必须是可播种的。

我目前有以下 C + + 代码:

output = min + (rand() * (int)(max - min) / RAND_MAX)

问题是它并不是真正统一的——只有当 RAND () = RAND _ MAX 时才返回 Max(对于 Visual C + + ,它是1/32727)。对于 <-1,1 > 这样的小范围来说,这是一个主要问题,因为最后一个值几乎从不返回。

所以我抓起笔和纸,想出了下面的公式(建立在(int)(n + 0.5)整数四舍五入技巧的基础上) :

Enter image description here

但它仍然不能给我一个统一的分布。对10000个样本进行重复运行,得到值为 -1,0的比例为37:50:13。1.

还有更好的公式吗? (或者甚至是整个伪随机数生成函数?)

317779 次浏览

下面是一个无偏见的版本,在 [low, high]中生成数字:

int r;
do {
r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

如果范围相当小,就没有理由在 do循环中缓存比较的右侧。

使用 梅森旋转算法加油实现相当容易使用,并且在许多实际应用程序中得到了良好的测试。我自己在几个学术项目中使用过它,比如 人工智能进化算法

下面是他们的例子,他们做了一个简单的函数来滚动一个六面骰子:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>


boost::mt19937 gen;


int roll_die() {
boost::uniform_int<> dist(1, 6);
boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
return die();
}

哦,这里还有一些这个发电机的改装,以防万一你不相信你应该使用它超过极差的 rand():

梅森旋转算法是随机的 诚发明的“数字”发电机 松本和西村拓治 网站内容包括 算法的实现。

本质上,梅森旋转算法是一个 非常大的线性反馈移位 该算法在一个 19,937位种子,存储在 624个元素的32位无符号数组 值2 ^ 19937-1是一个 梅森素数; 用于 操作种子是基于 古老的“扭曲”算法,所以 “梅森旋转算法”这个名字。

梅森的一个吸引人的方面 扭扭乐是二进制的运用 行动,而不是 费时的乘法 生成数字。算法也 有一个非常长的时期,和良好的 粒度。它既快又 对非加密应用程序有效。

我推荐 推进,随机图书馆。它非常详细,并且有很好的文档说明,允许您显式地指定您想要的发行版,并且在非加密场景中,实际上可以 表现突出一个典型的 C 库 Rand实现。

一个快速的,比你的稍微好一点的,但是仍然不完全统一的分布式解决方案是

output = min + (rand() % static_cast<int>(max - min + 1))

除了范围的大小为2的幂时,这种方法产生有偏差的非均匀分布 数字rand()的质量无关。对于这种方法的质量的综合测试,请 看看这个

让我们把问题分成两部分:

  • 生成0到(max-min)范围内的随机数 n
  • 把 min 加到那个数字上

第一部分显然是最难的。让我们假设 rand ()的返回值是完全一致的。使用模会增加偏差 到第一个 (RAND_MAX + 1) % (max-min+1)号码。因此,如果我们能够神奇地将 RAND_MAX改为 RAND_MAX - (RAND_MAX + 1) % (max-min+1),就不会再有任何偏见。

事实证明,如果我们愿意允许伪非确定性进入算法的运行时间,我们可以使用这种直觉。每当 rand ()返回一个太大的数时,我们只需要求取另一个随机数,直到得到一个足够小的数。

运行时间现在是 几何分布,期望值为 1/p,其中 p是在第一次尝试时获得足够小的数字的概率。由于 RAND_MAX - (RAND_MAX + 1) % (max-min+1)总是小于 (RAND_MAX + 1) / 2, 我们知道 p > 1/2,所以预期的迭代次数总是小于两次 任何范围。使用这种技术,应该可以在一个标准 CPU 上在不到一秒钟的时间内生成数千万个随机数。

虽然上述技术上是正确的,但 西蒙的回答在实践中可能更有用。你不应该自己实现这些东西。我见过很多拒绝抽样的实现,通常很难判断它是否正确。

int RandU(int nMin, int nMax)
{
return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

这是32768个整数到(nMax-nMin + 1)整数的映射。如果(nMax-nMin + 1)很小(如您所需) ,那么映射将非常好。但是请注意,如果(nMax-nMin + 1)很大,那么映射将不起作用(例如,您不能以等概率将32768个值映射到30000个值)。如果需要这样的范围-您应该使用32位或64位随机源,而不是15位 rand () ,或者忽略超出范围的 rand ()结果。

如果您的编译器支持 C + + 0x,并且您可以选择使用它,那么新的标准 <random>头文件可能会满足您的需要。它有一个高质量的 uniform_int_distribution,它将接受最小和最大的界限(包括你需要的) ,你可以选择各种随机数生成器插入该分布。

下面的代码生成一百万个随机 int,均匀分布在[ -57,365]中。我已经使用新的标准 <chrono>设施来计时,因为你提到的性能是一个主要问题。

#include <iostream>
#include <random>
#include <chrono>


int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double> sec;
Clock::time_point t0 = Clock::now();
const int N = 10000000;
typedef std::minstd_rand G;                // Select the engine
G g;                                       // Construct the engine
typedef std::uniform_int_distribution<> D; // Select the distribution
D d(-57, 365);                             // Construct the distribution
int c = 0;
for (int i = 0; i < N; ++i)
c += d(g);                             // Generate a random number
Clock::time_point t1 = Clock::now();
std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
return c;
}

对我来说(2.8 GHz Intel 核心 I5)这个输出:

2.10268 e + 07每秒随机数。

您可以通过向生成器的构造函数传递一个 Int来为生成器播种:

    G g(seed);

如果您后来发现 int不能覆盖您的发行版所需的范围,这可以通过像下面这样改变 uniform_int_distribution(例如,改为 long long)来补救:

    typedef std::uniform_int_distribution<long long> D;

如果您后来发现 minstd_rand不是一个足够高的质量发电机,这也可以很容易地交换出来。例如:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

对随机数发生器有独立的控制,随机分布可以相当自由。

我还计算了(未显示)这个发行版的前四个“ 瞬间”(使用 minstd_rand) ,并将它们与 理论价值进行比较,试图量化这个发行版的质量:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

(x_前缀表示“预期”。)

如果我没有记错的话,下面的表达应该是没有偏见的:

std::floor( ( max - min + 1.0 ) * rand() ) + min;

我在这里假设 rand ()给出了一个随机值,范围在0.0和1.0 之间,包括1.0,而且 Max是整数,条件是 < Max

最简单(因此也是最好的)的 C + + (使用2011年的标准)答案是:

#include <random>


std::random_device rd;     // Only used once to initialise (seed) engine
std::mt19937 rng(rd());    // Random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // Guaranteed unbiased


auto random_integer = uni(rng);

没有任何必要重新发明轮子,担心偏见,或担心使用时间作为随机种子。

这个公式很简单,试试这个表达式,

 int num = (int) rand() % (max - min) + min;
//Where rand() returns a random number between 0.0 and 1.0

假设 Max是整数值,

  • [ and ]表示包含这个值,
  • 方法不包括此值,

使用 C + + 的 Rand ()来获得正确的值。

参考文献:

有关()[]的定义,请访问 一个 href = “ https://en.wikipedia.org/wiki/Interval _ (數学)”rel = “ nofollow noReferrer”> Interval (数学)

对于 Rand沙子函数或 RAND _ MAX 定义, 访问 Rand”rel = “ nofollow noReferrer”> std: : rand

[最小,最大]

int randNum = rand() % (max - min + 1) + min

(最小,最大]

int randNum = rand() % (max - min) + min + 1

[最小,最大]

int randNum = rand() % (max - min) + min

(最少,最多)

int randNum = rand() % (max - min - 1) + min + 1

在这个问题的答案,拒绝抽样已经解决,但我想建议一个优化的基础上,rand() % 2^something没有引入任何偏见,如上所述。

算法很简单:

  • 计算比区间长度大2的最小幂
  • 在那个“新”区间内随机选择一个数字
  • 如果该数值小于原始间隔的长度,返回该数值
    • 否则拒绝

下面是我的示例代码:

int randInInterval(int min, int max) {
int intervalLen = max - min + 1;
//now calculate the smallest power of 2 that is >= than `intervalLen`
int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));


int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()"


if (randomNumber < intervalLen)
return min + randomNumber;      //ok!
return randInInterval(min, max);    //reject sample and try again
}

这种方法特别适用于小间隔,因为2的幂将“更接近”实际的间隔长度,因此错过的次数将更少。

PS: 显然避免递归会更有效率(没有必要一遍又一遍地计算日志上限... ...) ,但我认为这个例子更具可读性。

请注意,在大多数建议中,您从 RAND ()函数获得的初始随机值(通常从0到 RAND _ MAX)只是被浪费了。您只是创建了一个随机数出来,而有一个健全的程序,可以给你更多。

假设需要整数随机数的[ min,max ]区域,我们从[0,max-min ]开始

以 b = max-min + 1为基数

从表示从基数 b 中的 rand ()得到的数字开始。

这样就得到了 floor (log (b,RAND _ MAX)) ,因为基数 b 中的每个数字(可能最后一个除外)表示范围[0,max-min ]内的一个随机数。

当然,对于每个随机数 r + min,最后移动到[ min,max ]是很简单的。

int n = NUM_DIGIT-1;
while(n >= 0)
{
r[n] = res % b;
res -= r[n];
res /= b;
n--;
}

如果 NUM _ DIGIT 是基数 b 中可以提取的数字数,则为

NUM_DIGIT = floor(log(b,RAND_MAX))

那么上面是一个简单的实现,从一个 RAND _ MAX 随机数中提取从0到 b-1的 NUM _ DIGIT 随机数,提供 b < RAND _ MAX。

以下是 由沃尔特提供的思想。我编写了一个自包含的 C + + 类,它将在封闭的区间 [low, high]中生成一个随机整数。它需要 C + + 11

#include <random>


// Returns random integer in closed range [low, high].
class UniformRandomInt {


std::random_device _rd{};
std::mt19937 _gen{_rd()};
std::uniform_int_distribution<int> _dist;


public:


UniformRandomInt() {
set(1, 10);
}
UniformRandomInt(int low, int high) {
set(low, high);
}


// Set the distribution parameters low and high.
void set(int low, int high) {
std::uniform_int_distribution<int>::param_type param(low, high);
_dist.param(param);
}


// Get random integer.
int get() {
return _dist(_gen);
}


};

示例用法:

UniformRandomInt ur;
ur.set(0, 9); // Get random int in closed range [0, 9].


int value = ur.get()