LSB位随机性更低吗？原理是什么？C语言最优LCG随机数实现是啥？

对于*线性同余生成器（LCG）*这类工程中最常用的伪随机数生成器，该现象本质是模数取值带来的固有缺陷：

• 绝大多数普通LCG会取2的整数次幂作为模数m（通常是2^31或232），方便计算机计算取模操作
• 这种参数下，低位的周期会远短于高位：*最低有效位（LSB）*的周期最长仅为2（即0和1交替出现），第1位的周期最长为4，以此类推，越往高位周期越长，*最高有效位（MSB）*的周期等于LCG的完整周期
• 短周期意味着低位的重复频率极高，几乎没有随机性可言，而高位的序列重复概率低，随机表现更好

注意：该缺陷仅存在于LCG、多重同余生成器这类非密码学安全的伪随机数生成器，密码学安全的PRNG不存在高低位随机性差异的问题。

以下资料不需要高深的数论或统计学知识，适合入门理解：

• 《计算机程序设计艺术 第2卷：半数值算法》的伪随机数章节入门部分：只需要高中数学基础就能理解常见PRNG的缺陷、参数选择逻辑，还给出了大量工程上可直接复用的验证结果
• 国内高校通用《数值分析》教材的随机数模块：面向工科生编写，重点讲工程场景下的随机数使用技巧，几乎没有复杂推导
• NIST SP800-22 随机性测试标准的概述部分：官方公开的通用随机数质量判断标准，只需阅读前两章就能掌握日常判断随机数是否可用的核心逻辑，不需要看懂具体的测试计算公式

C语言标准没有规定rand函数的具体实现，业界通用的最优LCG参数来自Knuth的验证，满足绝大多数非密码学场景的需求，实现代码如下：

#include <stdint.h>

// 静态种子变量，线程不安全，多线程场景需加锁或使用线程局部存储
static uint32_t lcg_seed = 1;

void srand(unsigned int seed) {
    lcg_seed = (uint32_t)seed;
}

int rand(void) {
    // LCG核心公式：Xn+1 = (a * Xn + c) mod m，此处m=2^32，a=1103515245，c=12345
    lcg_seed = 1103515245U * lcg_seed + 12345U;
    // 取高15位返回，符合C标准默认RAND_MAX=32767的要求，避免低位随机性差的问题
    return (int)(lcg_seed >> 16) & 0x7FFF;
}

该实现的完整周期为2^{32，高位随机性通过了基础的随机性测试，适合普通游戏、数值模拟、随机采样等场景。如果需要更大的输出范围，可以调整移位位数，例如返回高31位即可将RAND_MAX提升到2}31-1。

注意：该LCG实现不具备密码学安全性，不可用于密钥生成、加密通信等安全敏感场景。

内容的提问来源于stack exchange，提问作者Yuri Bittencourt