PRNG生成范围下限的高效实现方法咨询

嘿，这个问题我之前也碰到过，朴素的“重复生成直到符合最小值”确实效率不高，尤其是当目标范围和PRNG原生范围不匹配的时候。下面给你几个更高效的实现思路，分场景适用：

1. 改进型拒绝采样（无偏差，推荐用于严格均匀需求） #

这是工业界常用的方法，核心是避免无限制循环同时保证输出的均匀性。原理是先计算出原生PRNG范围内，能被目标范围整除的最大上限，只保留这个上限内的生成值，这样模运算后不会有偏差。

具体步骤：

• 假设你的PRNG输出范围是 [0, M)（比如LCG的模m就是M）
• 目标范围是 [min, max]，计算目标长度 range = max - min + 1
• 计算余数 rem = M % range，如果rem不为0，就拒绝所有小于rem的生成值（因为这些值会导致模range后某些数出现概率更高）
• 把接受的数值模range后加上min，就是目标范围内的数

C#代码示例（以LCG为例）：

// 假设你的LCG生成方法返回0到lcgMaxValue-1的整数
private int YourLCGGenerate()
{
    // 你的LCG实现，比如：
    _current = (int)((_a * _current + _c) % _m);
    return _current;
}

public int GenerateInRange(int min, int max)
{
    int lcgMaxValue = _m; // 你的LCG的模值
    int range = max - min + 1;
    
    // 计算需要拒绝的阈值
    int rejectThreshold = lcgMaxValue % range;
    
    int result;
    do
    {
        result = YourLCGGenerate();
    } while (result < rejectThreshold); // 拒绝会导致偏差的小数值
    
    return (result % range) + min;
}

这个方法的循环次数期望值非常接近1，只有当range接近M时才会偶尔循环，效率比朴素方法高太多，而且完全没有偏差。

2. 线性缩放（简单高效，适合对均匀性要求不高的场景） #

如果你的场景（比如游戏、UI随机）可以接受极其微小的偏差，直接用线性缩放会更简单，不需要循环：

public int GenerateInRangeFast(int min, int max)
{
    int lcgMaxValue = _m;
    double normalized = (double)YourLCGGenerate() / lcgMaxValue;
    int range = max - min + 1;
    return (int)(normalized * range) + min;
}

注意：这个方法因为浮点数精度的问题，少数值出现的概率会略高，不适合模拟、统计计算等需要严格均匀的场景。

3. 利用PRNG的数学特性直接生成（针对LCG等线性生成器） #

对于LCG这类线性同余生成器，你可以直接调整生成参数来输出目标范围的数，而不需要先生成大范围再转换。比如如果目标范围是[L, R]，可以把LCG的结果直接映射为：

// 当range是LCG模m的约数时，直接映射无偏差
int result = (YourLCGGenerate() % range) + min;

但这个方法仅当range是m的约数时才完全无偏差，否则还是需要配合前面的拒绝采样来修正。

额外提醒 #

• 滞后斐波那契生成器的处理逻辑和LCG一致，因为它们都是输出一个连续范围内的整数，改进型拒绝采样同样适用。
• 如果是密码学级别的PRNG（比如RNGCryptoServiceProvider），官方推荐的也是改进型拒绝采样来保证无偏差。

内容的提问来源于stack exchange，提问作者MDM-P