为什么 rand() 在使用 1 和 UINT_MAX 作为种子时产生相同的值？

Question

这是一些代码：

#include <iostream>

int main() {
    srand(1);
    std::cout << rand() << "\n";
    srand(UINT_MAX);
    std::cout << rand() << "\n";
}

这会产生以下输出：

16807
16807

为什么这两个种子产生相同的结果？它们在连续 rand() 调用中产生的整个值序列也是相同的。可能值的范围太大，这不可能是纯巧合。是吗：

实施 rand() 的意外（如果是这样，我很好奇那可能是什么）
设计使然（如果是，为什么？）

（可能相关：种子10、100、1000、10000和100000分别产生168070、1680700、16807000、168070000和1680700000。）

Answer 1

如前所述here，如果将 seed 设置为 1，生成器将重新初始化为其初始值并生成与调用 rand 或 srand 之前相同的值.

另请注意，具有相同种子的两次不同初始化将在后续调用 rand 时生成相同的连续结果。

Answer 2

这取决于您的随机数生成器的实现。参见 What common algorithms are used for C's rand()? 对于常见的实现。

通常可能的种子值 space 比您的 UINT_MAX 短得多。可能是 1 和 UINT_MAX 映射到相同的内部种子。

通常Linear congruential generator用于rand()，那么第一个生成的随机数取决于

first_random_number  = (seed * const + another_const)  % third_constant

在种子上。这解释了您发现的依赖性。

Answer 3

我看不出为什么将您观察到的不幸相关性设计到您正在使用的 rand 的实现中。正如您所建议的，这很可能是 实施的意外 。也就是说，我也认为这是巧合，您可以准确地与这些输入产生相关性。另一个实现可能有其他组不幸的输入。

if so, I'm curious what that might be

如果您的实现是开源的，那么您可以通过阅读源代码找到答案。如果它是专有的，您仍然可以在某些文档中找到对算法的提及，或者如果您是客户，您可以询问实施者。

Answer 4

tl;dr: rand() 众所周知是那么糟糕。

实际值是实现定义的。我在我的平台上得到以下值：

seed:          1 : 41
seed: 4294967295 : 35
seed:         10 : 71
seed:        100 : 365
seed:       1000 : 3304
seed:      10000 : 32694

rand() 可以让匆忙的临时用户看起来有些随意。它不适用于其他任何东西。

实施通常使用低质量的生成器（最常见的是 Linear Congruential with bad constants）。

所需的数值范围是 0...32767，虽然实施可能通常不会超过该范围 - 因此您可以预期许多种子会产生相同的值。

对于现代 C++，请参阅 <random> 以获得可靠的选项。

Answer 5

一个非常简单可用的随机数生成器是Lehmer number generator。这个RNG可能是最简单的用软件实现的，它仍然可以使用，所以它可能是随机性问题最多的，也最容易分析。

数字 16807（又名 7 的五次方）与 Lehmer RNG 相关联，因为它在 1988 年用于最早的实现之一 - 显然今天仍在使用！

第N个随机数的公式为（用^求幂）：

R(n) = (seed * (16807 ^ n)) mod (2 ^ 31 - 1)

如果设置 seed = 1，n = 1：

R(1) = 16807 mod (2 ^ 31 - 1) = 16807

如果设置种子=2 ^ 32 - 1:

R(1) =
    (2 ^ 32 - 1) * 16807 ≡ (expressing 2^32 = 2^31 * 2)
    ((2 ^ 31 - 1) * 2 + 1) * 16807 ≡ (distributive law)
    (2 ^ 31 - 1) * 2 * 16807 + 1 * 16807 ≡ (modulo 2^31-1)
    16807

这里随机序列第一个数相等是因为Lehmer RNG中的模数几乎是2的幂(2^31-1)，而你的seed也差不多是2的幂(2^32-1).

seed = 2^31.

也会发生同样的情况

为什么 rand() 在使用 1 和 UINT_MAX 作为种子时产生相同的值？

Why does rand() produce the same value when seeded with 1 and UINT_MAX?

c++

random

srand