得到比RAND_MAX大的随机数

Question

Andrew关于加速C++的问题7-9问道：

7-9.(困难)第7.4.4/135号编中的nrand的实现不会适用于大于RAND_MAX的参数。通常，这个限制是没有问题的，因为RAND_MAX通常是最大的可能整数。然而，在一些实现中，RAND_MAX比最大的可能整数要小得多。例如，RAND_MAX为32767 (2^15 -1)，最大可能的整数为2147483647 (2^31 -1)，这并不少见。重新实现nrand，以便它对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);

然而，由于浮点数的离散性质，这可能意味着有些值将永远不会出现在您的输出流中。

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只保留rand()返回的任何数字中最不重要的8位；也就是说，它只保留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的位置。