从范围生成随机整数
我需要一个在给定范围内（包括边界值）生成一个随机整数的函数。 我没有不合理的质量/随机性要求，我有四个要求：
- 我需要它快速。 我的项目需要生成数百万（甚至有时甚至数千万）的随机数，而我目前的生成器function已经被certificate是一个瓶颈。
- 我需要它是相当统一的（使用rand（）是完美的）。
- 最小 – 最大范围可以是从<0，1>到<-32727，32727>之间的任何值。
- 它必须是可以种植的。
我目前有以下C ++代码：
output = min + (rand() * (int)(max - min) / RAND_MAX) 问题是，它不是一致的 – 只有当rand（）= RAND_MAX（对于Visual C ++，它是1/32727），才返回max。 对于像<-1,1>这样的小范围来说，这是最后一个值几乎从不返回的主要问题。
于是我抓起笔和纸，拿出下面的公式（它是build立在（int）（n + 0.5）整数舍入技巧上的）：
但它仍然没有给我统一的分配。 用10000个样品重复运行，给出比值为37:50:13，值为-1,0.1。
你能否build议更好的配方？ （甚至是整个伪随机数发生器的function）
快一点，比你的好一点，但是分布式解决scheme还不够好
output = min + (rand() % static_cast<int>(max - min + 1))
除了范围的大小是2的幂， 这种方法不piperand()的质量如何都会产生有偏差的不均匀分布的数字 。 对于这种方法的质量的全面testing，请阅读 。
最简单的（因此是最好的）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);
不需要重新发明轮子。 没有必要担心偏见。 无需担心使用时间作为随机种子。
如果你的编译器支持C ++ 0x，并且使用它是你的一个选项，那么新的标准<random>头可能会满足你的需要。 它具有高质量的uniform_int_distribution ，它将接受最小和最大边界（包括你所需要的），并且你可以select各种随机数发生器来插入这个分布。
这里是生成一百万个随机int的代码，均匀分布在[-57,365]。 我已经使用了新的std <chrono>设施来logging时间，因为你提到的是性能是你最关心的一个问题。
#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; G g; typedef std::uniform_int_distribution<> D; D d(-57, 365); int c = 0; for (int i = 0; i < N; ++i) c += d(g); Clock::time_point t1 = Clock::now(); std::cout << N/sec(t1-t0).count() << " random numbers per second.\n"; return c; }
对于我（2.8 GHz的英特尔酷睿i5）打印出来：
2.10268e + 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
对随机数发生器进行单独控制，随机分布可以相当自由。
我还计算了（未显示）这个分布的前4个“时刻”（使用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_前缀是指“预期的”）
我们将问题分成两部分：
- 在0到（max-min）范围内生成一个随机数
n。 - 添加分钟到该号码
第一部分显然是最难的。 假设rand（）的返回值是完全一致的。 使用模数会给第一个(RAND_MAX + 1) % (max-min+1)数字增加偏差。 所以如果我们可以奇迹般地把RAND_MAX变成RAND_MAX - (RAND_MAX + 1) % (max-min+1) ，就不会有任何偏差。
事实certificate，如果我们愿意让伪非确定性进入我们algorithm的运行时间，我们可以使用这种直觉。 每当rand（）返回一个太大的数字，我们只要求另一个随机数，直到得到一个足够小的数。
运行时间现在是几何分布的 ，预期值为1/p ，其中p是在第一次尝试中获得足够小数目的概率。 由于RAND_MAX - (RAND_MAX + 1) % (max-min+1)总是小于(RAND_MAX + 1) / 2 ，所以我们知道p > 1/2 ，所以预期的迭代次数总是小于2任何范围。 采用这种技术，在标准CPU上，应该有可能在不到一秒的时间内生成数以千万计的随机数。
编辑：
虽然以上在技术上是正确的，但DSimon的答案在实践中可能更有用。 你不应该自己实现这个东西。 我已经看到很多拒收采样的实现，通常很难判断它是否正确。
怎么样梅森扭转者 ？ boost实现相当容易使用，并且在许多真实世界的应用程序中都经过了很好的testing。 我自己在几个学术项目中使用它，例如人工智能和演化algorithm。
这里是他们的例子，他们做一个简单的function，滚动一个六面骰子：
#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(); }
哦，这里是更多的这个发生器的pimping，以防万一你不相信你应该使用它在极其低劣的rand() ：
Mersenne Twister是由松本诚和西村拓二发明的“随机数”发生器; 他们的网站包含了该algorithm的许多实现。
实质上，Mersenne Twister是一个非常大的线性反馈移位寄存器。 该algorithm在一个19,937位的种子上运行，存储在一个由32位无符号整数组成的624个元素的数组中。 价值2 ^ 19937-1是一个梅森素数; 操纵种子的技术是基于一个较老的“扭曲”algorithm – 因此被称为“梅森扭转者”。
Mersenne Twister的一个吸引人的方面是使用二进制运算 – 而不是耗时的乘法 – 来产生数字。 该algorithm还具有很长的周期，且粒度较好。 对于非encryption应用程序来说，它既快速又有效。
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（）结果。
这是一个无偏的版本，可以生成[low, high] ：
int r; do { r = rand(); } while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low)); return r % (high + 1 - low) + low;
如果你的范围相当小，没有理由在do循环中caching比较的右边。
我推荐Boost.Random库 ，它是超级详细和有据可查的，可以让你明确地指定你想要的发行版本，而在非encryption场景中，实际上可以超越典型的C库rand实现。
如果我没有弄错，下面的expression应该是没有偏见的：
std::floor( ( max - min + 1.0 ) * rand() ) + min;
我在这里假定rand（）给出了一个在0.0到1.0之间的随机值，不包括1.0，max和min是满足条件min <max的整数。
这个公式很简单，所以试试这个expression式，
int num = (int) rand() * (max - min) + min; //Where rand() returns a random number between 0.0 and 1.0
