Random

Xorshift 是什么 Xorshift 是 George Marsaglia 在 2003 年发表的一类伪随机数生成算法（PRNG，Pseudo-Random Number Generator），核心思路是反复对一个整数状态做"自己和自己移位后的版本"做异或（XOR），只用异或和移位两种运算就能生成看起来随机的数字序列。 它属于线性反馈移位寄存器（LFSR，Linear Feedback Shift Register）的一种变体，相比传统的线性同余法（LCG，Linear Congruential Generator，也就是很多语言标准库 rand() 背后的算法）不需要乘法和取模，只用位运算，速度快很多；相比更复杂的 Mersenne Twister（java.util.Random 用的不是这个，但 Python、PHP 等语言的默认随机数用的是它），实现更简单、状态更小。 代价是随机质量不如 Mersenne Twister，不能用于密码学场景（不是 CSPRNG，Cryptographically Secure PRNG），但对哈希表、游戏、模拟、需要"看起来随机就行"的场景完全够用，且速度优势明显。 基本算法 最经典的 32 位 xorshift 只需要一个非零的整数状态 x 和三次移位异或： uint32_t xorshift32(uint32_t x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } 每次调用把上一次的输出作为下一次的输入（状态），就能生成一串伪随机序列。三个移位量 (13, 17, 5) 不是随便选的——Marsaglia 在论文里给出了一批能保证生成的序列覆盖 2^32 - 1 个非零状态（即最大周期）的移位量组合，(13, 17, 5) 是其中常用的一组。如果移位量选得不好，会导致序列过早循环或者分布不均匀。 64 位状态的版本同理，只是移位量不同： uint64_t xorshift64(uint64_t x) { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } 为什么异或和移位比乘除法快 xorshift 只用异或和移位，LCG 需要乘法，还常常需要取模——这两类操作在 CPU 上的实际开销差距很大，不只是"位运算听起来更底层"这种直觉。 ...

LCG 是什么 线性同余生成器（LCG，Linear Congruential Generator）是历史最悠久、实现最简单的一类伪随机数算法（PRNG，Pseudo-Random Number Generator）。1949 年由 D. H. Lehmer 提出雏形，此后几十年里几乎所有编程语言标准库的 rand() 都是它的某个变体。 它的核心是一条递推公式：给定当前状态 seed，用一次乘法、一次加法、一次取模算出下一个状态，同时把这个状态作为输出。相比 Mersenne Twister 随机数算法 和 Xorshift 伪随机数算法，LCG 实现最简单、状态最小，但随机质量也最差，且不是密码学安全的随机数生成器（不是 CSPRNG，Cryptographically Secure PRNG），不能用在密钥生成、令牌生成等安全场景。 递推公式 X(n+1) = (a * X(n) + c) mod m 四个参数决定了一个具体的 LCG： X(0)：种子（seed），初始状态 a：乘数（multiplier） c：增量（increment） m：模数（modulus） c = 0 的特例叫乘同余生成器（multiplicative congruential generator，也叫 Lehmer RNG）；c != 0 时才是完整的（mixed）LCG。取模运算保证了状态永远落在 [0, m) 区间内，序列迟早会回到某个之前出现过的状态并开始循环——这个循环长度就是"周期"，LCG 的周期上限是 m。 参数怎么选：Hull–Dobell 定理 不是随便选四个数字就能得到一个"好"的 LCG。如果参数选得不好，序列可能远没跑到 m 就开始循环，或者呈现明显的规律。Hull–Dobell 定理给出了 c != 0 时序列能达到最大周期 m（即遍历 [0, m) 里所有整数才循环）的充要条件： ...

Mersenne Twister 是什么 Mersenne Twister（简称 MT，梅森旋转算法）是松本真（Makoto Matsumoto）和西村拓士（Takuji Nishimura）在 1997 年发表的伪随机数生成算法（PRNG），名字来自它的周期长度——最常用的变体 MT19937 的周期是 2^19937 - 1，这是一个梅森素数（Mersenne prime，形如 2^p - 1 的素数）。 它是目前应用最广泛的通用 PRNG 之一：Python、PHP、R、Ruby、Excel 的默认随机数生成器用的都是 MT19937；C++11 标准库 <random> 里的 std::mt19937 也是它。相比 Xorshift 伪随机数算法 和 Java Random 随机数 里的线性同余法（LCG），MT 的随机质量（统计意义上的均匀性、独立性）好得多，周期也长得多，代价是内部状态更大、实现更复杂。 和 xorshift、LCG 一样，MT 不是密码学安全的随机数生成器（不是 CSPRNG）：观察连续 624 个输出就能反推出完整的内部状态，从而预测后续所有输出，所以不能用在密钥生成、令牌生成等安全场景，这些场景要用专门的 CSPRNG（比如 Java 的 java.security.SecureRandom）。 核心设计 状态：624 个 32 位整数 MT19937 的内部状态是一个长度 624 的 32 位整数数组，一共 624 * 32 = 19968 位，比 xorshift（几十到几百位状态）或 LCG（48 位状态）大得多——这也是"随机质量更好"的代价之一：状态越大，能表达的不同序列就越多，越不容易在短序列内暴露周期性规律。 生成流程分两步 状态推进（twist）：每消耗完 624 个输出后，对整个状态数组做一次"扭转"变换，生成下一批 624 个新状态。扭转的核心是对相邻状态做位组合，再乘上一个固定的常数矩阵（用移位和异或实现，不是真正的矩阵乘法，效果类似线性反馈移位寄存器）。 输出提炼（tempering）：每次取值时，不直接返回状态数组里的原始整数，而是先对它做一轮固定的移位、掩码、异或组合（tempering），目的是消除原始状态里明显的统计规律，让直接输出的比特看起来更均匀。 这种"大状态 + 定期批量刷新 + 每次输出前额外处理"的设计，是 MT 和 xorshift/LCG 这类"每次输出就是一次状态更新"的算法的主要区别。 ...

Java 里获取随机数的几种方式 在 Java 中，获取随机数广义上有三种途径： 用 System.currentTimeMillis() 拿到当前时间的毫秒数，当作一个"看起来随机"的数字。 用 Math.random()，返回一个 [0, 1) 之间均匀分布的 double 值。 用 java.util.Random 类，功能更完整的专业随机数工具类。 Math.random() 内部其实也是委托给一个 java.util.Random 实例（每个类第一次调用时惰性初始化一个内部单例），所以第 2、3 种本质上是同一套实现。 java.util.Random 的用法 Random 有两种构造方法： Random()：用当前时间 System.currentTimeMillis() 作为种子（seed）。 Random(long seed)：用指定的 seed 初始化。 产生 Random 对象后，调用 nextInt()、nextLong()、nextFloat()、nextDouble()、nextBoolean()、nextGaussian()（返回符合高斯/正态分布的 double）等方法获得不同类型的随机数。 如果两个 Random 对象用相同的种子、并且以相同的顺序调用相同的方法，它们返回的值会完全相同——因为随机数序列完全由种子和内部算法决定： import java.util.Random; public class TestRandom { public static void main(String[] args) { Random random1 = new Random(100); System.out.println(random1.nextInt()); System.out.println(random1.nextFloat()); System.out.println(random1.nextBoolean()); Random random2 = new Random(100); System.out.println(random2.nextInt()); // 和 random1 完全一样 System.out.println(random2.nextFloat()); System.out.println(random2.nextBoolean()); } } 指定范围内的随机数，可以用取模运算符 %（配合 Math.abs 避免负数）： ...