如何无状态快速生成[a,b]区间内第n个均匀分布伪随机数？

核心思路 #

使用确定性伪随机函数，仅以输入参数n、区间[a,b]、可选seed为计算依据，直接生成对应位置的伪随机数，全程不保留任何内部状态。由于对随机性质量要求不高，优先选择计算效率高的实现方案。

方案一：线性同余生成器（LCG）无状态实现 #

LCG是一种轻量的伪随机数生成算法，可通过数学推导直接计算第n个值，无需维护递推状态。

实现原理

LCG的递推公式为：X_{k+1} = (A * X_k + C) mod M
通过数学推导，第n个值的计算公式可简化为：
X_n = (A^n * seed + C * (A^{n-1} + A^{n-2} + ... + 1)) mod M
其中等比数列和可通过模逆元快速计算，A^n mod M用快速幂实现，保证计算效率。

代码示例（Python）

def get_nth_random_lcg(n, a, b, seed=12345):
    # LCG参数（经典取值，满足低随机性需求）
    LCG_A = 1103515245
    LCG_C = 12345
    LCG_M = 2 ** 31

    # 快速幂计算base^exp mod mod_val
    def pow_mod(base, exp, mod_val):
        result = 1
        base = base % mod_val
        while exp > 0:
            if exp % 2 == 1:
                result = (result * base) % mod_val
            exp = exp >> 1
            base = (base * base) % mod_val
        return result

    a_pow_n = pow_mod(LCG_A, n, LCG_M)
    # 计算等比数列和的模运算结果
    sum_geometric = (a_pow_n - 1) * pow(LCG_A - 1, -1, LCG_M) % LCG_M
    # 计算第n个LCG值
    x_n = (a_pow_n * seed + LCG_C * sum_geometric) % LCG_M

    # 归一化到[0,1)，再映射到[a,b]区间
    uniform_01 = x_n / LCG_M
    return a + uniform_01 * (b - a)

方案二：哈希函数实现 #

利用哈希函数的确定性，将n与seed的组合作为输入，生成固定哈希值后映射到目标区间，实现简单且无需复杂数学推导。

代码示例（Python）

import hashlib

def get_nth_random_hash(n, a, b, seed=12345):
    # 将n和seed拼接为字节串作为哈希输入
    input_data = f"{n}_{seed}".encode("utf-8")
    # 生成MD5哈希，取前4字节转换为整数
    hash_result = hashlib.md5(input_data)
    hash_int = int.from_bytes(hash_result.digest()[:4], byteorder="big")
    # 归一化到[0,1)区间后映射到[a,b]
    uniform_01 = hash_int / 2 ** 32
    return a + uniform_01 * (b - a)

方案对比 #

• LCG方案：计算速度快，适合对性能敏感的场景，随机性满足低要求场景。
• 哈希方案：实现更简洁，随机性略优于LCG，计算开销稍高。

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