从范围内生成随机整数

Question

我需要一个可以在给定范围内（包括边界值）生成随机整数的函数。我对质量和随机性没有过分要求，但有四个需求：

1. 函数需要快速。我的项目需要生成数百万甚至数千万个随机数，而我的当前生成函数已经成为瓶颈。 2. 它需要相当均匀（使用rand()是完全可以接受的）。 3. 最小-最大范围可以是从<0，1>到<-32727, 32727>的任何值。 4. 它必须是可种子的。

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

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

问题在于它并不真正是均匀分布的 - max 仅在 rand() = RAND_MAX 时返回（对于 Visual C++ ，这个值为 1/32727）。这是小范围内（如 <-1, 1>）的一个重大问题，最后一个值几乎永远不会被返回。 所以我拿起笔和纸，想出了以下公式（基于 (int)(n + 0.5) 整数舍入技巧）： 但它仍然不能给我一个均匀的分布。重复运行 10000 个样本，得到的值为 -1、0、1 的比例为 37:50:13。 是否有更好的公式？（或者整个伪随机数生成器函数？）

- Matěj Zábský

---

请参见：https://dev59.com/d0vSa4cB1Zd3GeqPifKd#2254535 - Jerry Coffin

@Bill MaGriff: 是的，它有相同的问题。一个简化版本是：如何平均地将10块糖果分给3个孩子（不打破任何一颗糖果）？答案是，你不能——你必须给每个孩子三颗，并且不给第十颗糖果给任何人。 - Jerry Coffin

你看过Boost.Random了吗？ - Fred Nurk

请查看Andrew Koenig的文章《几乎永远不会正确解决的一个简单问题》：http://www.drdobbs.com/blog/archives/2010/11/a_simple_proble.html - Gene Bushuyev

@Gene Bushuyev：Andrew和我已经在这个问题上强调了相当长的时间。请参见：http://groups.google.com/group/comp.lang.c++/browse_frm/thread/0cf416326d3da971/3372fa37f69caa2e?hl=en#3372fa37f69caa2e，以及：http://groups.google.com/group/comp.os.ms-windows.programmer.tools.mfc/msg/f04063c31a1a6e67?hl=en - Jerry Coffin

Answer 1

最简单（因此也是最好的）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);

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

- Walter

---

现在这应该是答案。请参考伪随机数生成参考文献了解更多功能。 - alextoind

我同意“simplest”（也是最惯用的），但不同意“best”。不幸的是，标准并未保证random_device在某些情况下可能会完全失效（参见此处）。此外，虽然mt19937是一种非常好的通用选择，但它并不是质量优秀生成器中速度最快的（请参考此处比较），因此可能不是 OP 的理想选择。 - Alberto M

@AlbertoM 很不幸，你提到的比较没有提供足够的细节，并且无法重现，这使得它变得可疑（此外，它是从2015年开始的，而我的答案可以追溯到2013年）。可能确实存在更好的方法（希望在未来，minstd将成为这样的方法），但这就是进步。至于random_device的差劲实现——那真是太糟糕了，应该被视为一个错误（如果C++标准允许的话，可能也是C++标准的错误）。 - Walter

我完全同意你的观点；实际上我并不想批评你的解决方案，只是想警告那些随意读者，尽管C++11有所承诺，但这个问题的最终答案还没有被写出来。我将在相关问题的回答中发布2015年该主题的概述。 - Alberto M

我会尽力进行翻译，以下是需要翻译的内容： @AndreyPortnoy 如果可能的话，我总是使用 auto 来声明自动变量，因为这样可以更方便地进行维护。即使我以后将 uniform_int_distribution<> 的模板参数更改为其他类型，比如 int64_t，它也会自动选择正确的类型。 - Walter

Answer 2

一个快速的、略微优于你的，但仍然没有正确均匀分布的解决方案是

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

除非范围的大小是2的幂，否则此方法会产生偏差的非均匀分布数字，无论rand()的质量如何。要全面测试此方法的质量，请阅读此内容。

- Mark B

---

谢谢，从快速测试来看，这似乎已经足够好了——其分布为-1、0、1，几乎是33:33:33。 - Matěj Zábský

它始终返回最大值。这里有什么我错过了吗？:| - rohan-patel

在C++中应该将rand()视为有害的，因为有更好的方法可以获得均匀分布且真正随机的数。 - Mgetz

它是否真的能够100%的时间内返回正确范围内的数字？我在这里找到了一些其他的stackoverflow答案，它使用递归来“正确地”完成：https://dev59.com/VHE85IYBdhLWcg3w_I78#6852396 - Czarek Tomczak

由于这是一个高度投票（比预期的更高）的答案，对于许多新读者来说似乎是可靠的信息来源，因此我认为提到这个解决方案的质量和潜在危险非常重要，所以我进行了编辑。 - plasmacel

Answer 3

如果您的编译器支持C++0x，并且使用它是一个选项，那么新的标准<random>头文件可能会满足您的需求。它具有高质量的uniform_int_distribution，该分布将接受最小和最大边界（根据您的需要包括在内），并且您可以在各种随机数生成器中选择插入到该分布中。

这里是生成一百万个[-57, 365]均匀分布的随机整数的代码。我已经使用新的std <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 英特尔Core i5），这将打印出：

每秒生成 2,10268e+07 个随机数。

你可以通过将一个整数传递给它的构造函数来设置生成器的种子：

    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_前缀表示“期望”的意思。）

- Howard Hinnant

---

这个答案可以用一个简短的代码片段来概括，该代码片段仅显示生成指定范围内随机整数所需的实际代码。 - arekolek

问题变得更容易解决是因为分布的最小值和最大值从未改变。如果您必须在每次迭代中使用不同的边界创建 d，那会有多慢？ - quant_dev

<random> 的设计使您无需创建新分布即可使用其他参数。只需在需要另一个随机值的调用站点插入新参数即可：d(g, D::param_type{m, M})。这不会对性能产生任何影响，因为通常没有显式 param_type 参数的重载会调用具有 param_type 的重载：https://github.com/llvm/llvm-project/blob/main/libcxx/include/__random/uniform_int_distribution.h#L231-L232 - Howard Hinnant

Answer 4

让我们将问题分为两部分：

• 在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上可以在不到一秒钟的时间内生成数千万个随机数。

虽然以上内容在技术上是正确的，但DSimon's answer在实践中可能更有用。您不应该自己实现这些东西。我见过很多拒绝抽样的实现，它们通常很难判断是否正确。

- Jørgen Fogh

---

为了完整起见：这是拒绝抽样。 - etarion

有趣的事实：Joel Spolsky曾经提到过这个问题的一个版本，作为StackOverflow擅长回答的例子。当时我查看了网站上关于拒绝抽样的答案，但是每一个答案都是错误的。 - Jørgen Fogh

其中一个棘手的方面是RAND_MAX通常等于INT_MAX，因此RAND_MAX + 1会溢出导致未定义的行为。 - Nate Eldredge

Answer 5

使用Mersenne Twister。Boost的实现相当易于使用，并在许多真实世界的应用中经过了良好的测试。我自己在几个学术项目中使用它，例如人工智能和进化算法。

以下是他们的示例，其中他们制作了一个简单的函数来掷一个六面骰子：

#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()函数打败，那么这里有更多的理由让你使用这个生成器：

Mersenne Twister是由松本真和西村拓士发明的"随机数"生成器；他们的网站包含了算法的众多实现。

本质上，Mersenne Twister是一个非常大的线性反馈移位寄存器。该算法基于一个19,937位的种子，在一个由32位无符号整数组成的624元素数组中存储。值2^19937-1是一个梅森素数；操纵种子的技术基于一种旧的“扭曲”算法——因此得名“Mersenne Twister”。

Mersenne Twister的一个吸引人的方面是它使用二进制运算——而不是耗时的乘法——来生成数字。该算法也具有非常长的周期和良好的粒度。对于非加密应用程序，它既快速又有效。

- Aphex

---

Mersenne Twister是一个很好的生成器，但它所处理的问题仍然存在，无论底层生成器本身如何。 - Jerry Coffin

我不想仅仅为了随机生成器就使用Boost库，因为（由于我的项目是一个库），这意味着将另一个依赖项引入到项目中。未来我可能会被迫使用它，那时我可以切换到这个生成器。 - Matěj Zábský

@Jerry Coffin 是哪个问题？我提供它是因为它满足了他的所有要求：它快速，均匀（使用 boost::uniform_int 分布），您可以将最小和最大范围转换为任何您喜欢的内容，并且它是可种植的。 - Aphex

@mzabsky 我可能不会因此而放弃。当我需要将我的项目提交给教授时，我只需包含我正在使用的相关boost头文件；你不应该将整个40mb的boost库与你的代码一起打包。当然，在你的情况下，由于版权等其他原因，这可能不可行... - Aphex

@Aphex 我的项目 不是一个真正需要非常均匀分布的科学模拟器或者其他什么。我使用旧的生成器已经1.5年了，没有任何问题。只有当我第一次需要从非常小的范围（比如这个例子中的3）生成数字时，我才注意到有偏差的分布。然而，速度仍然是考虑使用boost解决方案的一个争议点。我将查看它的许可证，以确定是否可以将这几个所需的文件添加到我的项目中 - 我喜欢现在的“Checkout -> F5 -> ready to use”。 - Matěj Zábský

Answer 6

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()结果。

- Lior Kogan

---

尽管它不太受欢迎，但这也是我用于非科学项目的工具。易于理解（您不需要数学学位），并且表现良好（从未使用过任何代码分析工具）。 :) 对于大范围的情况，我猜我们可以将两个rand()值串联在一起，并获得一个30位的值来使用（假设RAND_MAX = 0x7fff，即15个随机位）。 - efotinis

将 RAND_MAX 更改为 (double) RAND_MAX，以避免整数溢出警告。 - alex

Answer 7

假设min和max是整数值，

• [和]表示包括这个值，
• (和)表示不包括这个值，

使用上述方法来使用C++的rand()函数获取正确的值。

参考资料：

有关()[]定义，请访问区间(数学)。

有关rand和srand函数或RAND_MAX定义，请访问std::rand。

[min，max]

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

- Huang Kun

Answer 8

这里有一个不带偏见的版本，它可以在[low, high]范围内生成数字。

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

如果您的范围相对较小，则没有理由在do循环中缓存比较的右侧。

- Jeremiah Willcock

---

依我看，那里提出的解决方案都没有多大改进。他基于循环的解决方案可以工作，但对于像原帖中讨论的小范围来说可能相当低效。他的均匀分布解决方案实际上并不能产生真正的“均匀”变量。最多只能掩盖其不均匀性。 - Jerry Coffin

@Jerry：请检查新版本。 - Jeremiah Willcock

我对它的正确性有一点不确定。它有可能会正常工作，但正确性对我来说并不明显。 - Jerry Coffin

@Jerry：这是我的推理过程：为简单起见，假设范围为[0，h)。调用rand()有RAND_MAX+1个可能的返回值；取rand()％h会将其中 (RAND_MAX+1)/h 个值映射到每个 h 个输出值中，但是要注意，由于最后一次部分循环到 h 输出，(RAND_MAX+1)/h+1 个值将被映射到小于 (RAND_MAX+1)%h 的值上。因此，我们需要移除 (RAND_MAX+1)%h 个可能的输出以获得一个无偏分布。 - Jeremiah Willcock

Answer 9

我推荐使用Boost.Random库。它非常详细和文档完备，让你可以明确指定需要的分布情况，在非加密场景下，可以实际上性能优于典型的C库rand实现。请参考Boost.Random库和性能测试结果。

- DSimon

Answer 10

以下是 Walter 提出的想法。我编写了一个自包含的 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()

- stackoverflowuser2010