C语言rand函数源码如何实现随机数生成？

C 语言标准只规定了 rand() 函数的接口和行为，并没有规定其具体的实现算法。 这意味着，不同的 C 标准库实现（在 Linux 上使用的 GNU C Library (glibc)，在 Windows 上使用的 MSVCRT）可能会使用不同的算法来生成随机数。

几乎所有现代实现都遵循一个事实标准：线性同余生成器。

下面,我将分两部分来解释：

1. LCG 算法原理：这是 rand() 函数背后最核心、最普遍的算法。
2. 真实世界的源码示例：展示 glibc 和 MSVCRT 中 rand() 的具体实现。

LCG (Linear Congruential Generator) 算法原理

LCG 是一种能产生伪随机数序列的算法，它非常简单、快速，并且只需要很少的内存（通常只需要一个状态变量）。

其核心公式如下：

X_{n+1} = (a * X_n + c) mod m

• X_{n+1} 是序列中的下一个随机数。
• X_n 是序列中的当前随机数（也称为“种子”或“状态”）。
• a 是乘数。
• c 是增量。
• m 是模数。

参数的选择

a, c, 和 m 的选择对随机数序列的质量至关重要，为了生成一个长周期（即在序列重复前产生尽可能多的不同数）的“好”的伪随机数，这些参数需要满足特定的数学条件。

最经典、最广为人知的 LCG 参数集是 Numerical Recipes 推荐的参数，以及被许多 C 库（包括早期的 BSD 和一些现代实现）采用的参数：

• m = 2^32 (模数)
• a = 1664525 (乘数)
• c = 1013904223 (增量)

rand() 和 srand() 的工作流程

1. 状态变量：在 C 库内部，有一个全局的、静态的 unsigned int 变量，我们称之为 state，它用来存储当前的 X_n。
2. srand(seed) 函数：
   • 这个函数的作用是初始化 state。
   • 当你调用 srand(seed) 时，库会将你提供的 seed 值赋给 state。
   • 如果你没有调用 srand()，state 会被初始化为一个固定的默认值（通常是 1），这会导致每次程序运行时产生的随机数序列都是一样的。
3. rand() 函数：
   • 每次调用 rand()，它都会执行一次 LCG 公式： state = (a * state + c) % m
   • 它返回这个计算出的新 state 值（或者对 state 进行一些处理后的值）。
   • 因为 state 是全局变量，所以下一次调用 rand() 时，它会使用上一次计算出的 state 作为新的 X_n，从而产生序列中的下一个数。

为什么返回的值范围是 0 到 RAND_MAX？

rand() 函数返回一个 int 类型的值，其范围在 0 到 RAND_MAX 之间（RAND_MAX 是一个宏，定义在 <stdlib.h> 中，通常值为 32767，即 2^15 - 1）。

这是因为 LCG 算法直接生成的数可能非常大（m=2^32 时，生成的数在 0 到 2^32-1 之间），为了得到一个范围更小、更符合传统需求的随机数，实现者通常会进行缩放。

最常见的缩放方法是：

1. 使用 LCG 算法生成一个在 [0, m-1] 范围内的数。
2. 将这个数除以 m，得到一个 [0.0, 1.0) 范围内的浮点数（但这不是 rand() 做的）。
3. 对于 rand()，更常见的做法是取 LCG 生成的数的低 16 位（或 15 位）。
   • 如果 m = 2^32，(state >> 16) & 0x7FFF 就可以得到一个 15 位的无符号数，其范围是 [0, 32767]，正好对应 RAND_MAX。

真实世界的源码示例

示例 1: GNU C Library (glibc) - Linux/macOS

在 glibc 中，rand() 的实现比简单的 LCG 稍微复杂一点，它使用了一个更高质量的 LCG 变体，并且为了与历史遗留代码兼容，其 RAND_MAX 是 2147483647 (即 2^31 - 1)。

文件路径通常是：stdlib/rand.c

/* Copyright (C) 1991-2025 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   ... (版权信息) */
#include <stdlib.h>
#include <stdint.h>
/* We use a multiplicative congruential generator with a = 1103515245
   and c = 12345. The period is 2^32. */
#define TYPE int32_t
#define A 1103515245
#define C 12345
#define M 0x7fffffff /* 2^31 - 1 */
/* 内部状态变量 */
static TYPE state = 1; // 默认种子为 1
int
rand (void)
{
  state = (A * state + C) % M;
  return state;
}
// srand() 函数的实现
void
srand (unsigned int seed)
{
  state = seed;
}

代码解读：

• 参数：这里使用的 LCG 参数是 a = 1103515245, c = 12345, m = 0x7fffffff (即 2^31 - 1)，这是一个经典的参数集，周期为 2^31。
• state：static TYPE state = 1; 是全局状态变量，默认初始化为 1。
• rand()：直接套用 LCG 公式 state = (A * state + C) % M;，因为 M 本身就是 RAND_MAX，state 的值直接在 [0, RAND_MAX] 范围内，无需额外缩放。
• srand()：直接将 state 设置为用户提供的 seed。

示例 2: Microsoft C Runtime Library (MSVCRT) - Windows

Windows 的 C 运行时库（例如在 Visual Studio 中）也使用 LCG，但其参数和实现细节与 glibc 不同。

其 RAND_MAX 通常是 32767 (即 2^15 - 1)。

// 这是一个简化的、基于公开信息的 MSVCRT rand() 实现示例
// 实际源码在 Microsoft 的内部仓库中，但逻辑基本一致
#include <stdlib.h>
// MSVCRT 使用的 LCG 参数
#define A 214013
#define C 2531011
#define M 2147483647 // 2^31 - 1
// 内部状态变量
static unsigned long int next = 1; // 默认种子为 1
int
rand (void)
{
  // 使用 LCG 公式更新状态
  next = next * A + C;
  // 将结果缩放到 [0, 32767] 的范围
  // (next >> 16) 会得到一个 0 到 65535 之间的数
  // 再与 0x7FFF (32767) 进行与操作，确保范围在 [0, 32767]
  return (int)((next >> 16) & 0x7FFF);
}
// srand() 函数的实现
void
srand (unsigned int seed)
{
  next = seed;
}

代码解读：

• 参数：a = 214013, c = 2531011, m = 2^31 - 1，这是一个不同的参数集。
• state：static unsigned long int next = 1; 是状态变量，默认值为 1。
• rand()：
  1. next = next * A + C;：执行 LCG 计算，next 的值在 [0, 2^31-1] 之间。
  2. return (int)((next >> 16) & 0x7FFF);：这是关键的一步，它将 32 位的 next 右移 16 位，取其高 16 位，然后与 0x7FFF（二进制 0111111111111111）进行与运算，只保留低 15 位，这样，最终返回的值就在 [0, 32767] 之间，正好是 RAND_MAX 的值。
• srand()：同样，直接用 seed 初始化 next。

总结与重要提示

为什么 rand() 不适合用于需要高安全性的场景？

1. 可预测性：LCG 算法是完全确定的，如果你知道 a, c, m 和当前的 state，你就能预测出下一个随机数，即使你不知道 state，只要观察到几个连续的输出，就很容易反向工程出整个序列。
2. 周期性：无论周期多长，序列最终都会重复。
3. 模式性：LCG 生成的数在多维空间中会形成明显的平面或超平面，不适合用于模拟或科学计算。

对于密码学、安全令牌、游戏服务器密钥等场景，绝对不要使用 rand()，你应该使用专门的密码学安全伪随机数生成器，例如在 C 中通过 <stdlib.h> 的 rand_s (Windows) 或第三方库如 OpenSSL 的 RAND_bytes，或者 C++11 的 <random> 库中的 std::random_device 和 std::mt19937 (Mersenne Twister)。