c++ - 获取大于 RAND_MAX 的随机数

Question

Accelerated C++ Andrew Koenig 的第 7-9 题问:

7-9. (difficult) The implementation of nrand in §7.4.4/135 will not work for arguments greater than RAND_MAX. Usually, this restriction is no problem, because RAND_MAX is often the largest possible integer anyway. Nevertheless, there are implementations under which RAND_MAX is much smaller than the largest possible integer. For example, it is not uncommon for RAND_MAX to be 32767 (2^15 -1) and the largest possible integer to be 2147483647 (2^31 -1). Reimplement nrand so that it works well for all values of n.

如果n > RAN_MAX我的想法是采取

double temp = n/RAN_MAX + .5;
int mult = temp;
int randomNum = 0;

for (int i = 0; i != mult; mult++)
    randomNum += rand();

然后测试 randomNum < n。这会生成一个随机数 > RAND_MAX 吗？我不知道如何使用比我的计算机可以处理的更大的整数，所以我认为没有任何真正的方法可以告诉。

Answer 1

如果您真的在处理大于计算机处理能力的整数，那就太复杂了。

但对于大于 int 的整数，您确实有多种选择，这些包括:unsigned int , long , unsigned long , long long , unsigned long long按大小递增的顺序排列。数字有多大取决于您的架构。

例如，在我的机器上有以下内容:

Data Type:   Bytes  Minimum               Maximum
Short SInt:  2      -32768                32767
Short UInt:  2      0                     65535
UInt:        4      0                     4294967295
SInt:        4      -2147483648           2147483647
ULong:       8      0                     18446744073709551615
SLong:       8      -9223372036854775808  9223372036854775807
ULong Long:  8      0                     18446744073709551615
SLong Long:  8      -9223372036854775808  9223372036854775807

因此，如您所见，您可以使数字比 int 大得多和 32767。

一种方法如下:

double a=rand()/(double)RAND_MAX;
unsigned long long random_n=(unsigned long long)(BIG_MAXIMUM_NUMBER*a);

但是，由于 float 的离散性，这可能意味着某些值永远不会出现在您的输出流中。

C++11 有一个 解决这个问题和你提到的问题的库。其用法示例如下:

const int min = 100000;
const int max = 1000000;
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(min,max);
int random_int = distribution(generator);

只需更改数据类型以满足您的大需求。

另一种看待这个问题的方式是我们可以解释 rand()作为返回一个位域，而且，由于它是一个统一的 PRNG，所有位域都是同样可能的。然后我们可以多次调用 rand()获得多个同样可能的位字段并将它们合并以产生大数字。以下是我们如何从两个 8 位随机数生成一个 16 位随机数:

uint16 a=(uint16)(rand()&255);
uint16 b=(uint16)(rand()&255);
uint16 random_int=b<<8 | a;

rand()&255只保留任何数字的 8 个最低有效位 rand()返回；也就是说，它只保留 rand() 的最后一个字节。 .

(uint16)将此字节转换为无符号的 16 位数字。

a<<8移动 a 的位左边 8 位，这为安全添加 b 腾出了空间.

但是如果 rand() 怎么办？返回一个有符号值，使最高有效位始终为 0 或 1？然后我们可以执行以下操作:

uint16 a=(uint16)(rand()&255);
uint16 b=(uint16)(rand()&255);
uint16 c=(uint16)(rand()&1);
uint16 random_int=c<<14 | b<<7 | a;

我们左移 b只有 7 位，因此第 8 个最低有效位是随机的。这意味着第 14 位和第 15 位最低有效位将是非随机的。因为我们想模仿 rand() 的行为，我们将第 15 个最低有效位保留为非随机位，并捕获一个随机位左移到第 14 个 LSB 的位置。