产生任意范围的整数随机数

约 1353 字大约 5 分钟

.NET

2021-03-19

有一天，我突然想验证一下 .NET 产生任意范围的整数随机数是不是保证完全等概率的。

零

我们先讨论一下，如何用 0~(n-1) 的随机数生成器，生成 0~(m-1) 范围的随机数。

最朴素的想法

先考虑 n>m 的情形，最简单的做法是，先产生一个 0~(n-1) 的随机数，如果小于 m，就使用这个结果；如果大于等于 m，就重来。如果 n>2m，可以目标范围的一个数对应原生成器的两个或以上的数。

至于 n<m 的情况，可以多次生成来获得一个更大范围的生成器，比如生成两次就是 0~(n^2-1) 的随机数生成器。

由于上面的那种想法没有完全利用产生的随机数，我希望能够产生尽量少的随机数达到目的。我首先考虑的是，把 [0,1) 分成更小的区间，比如 [0,1/m), [1/m, 2/m), ...。这些区间作为目标，同时划分出 [0,1/n), [1/n, 2/n), ... 这些区间。每生成一个随机数，就从后者当中选取一个区间。如果选中的区间是前面区间的子集，就取该区间对应的数字；如果不是，就继续划分为 n 个区间并且随机取一个。

这种想法在产生无限个随机数时，效率是最高的，因为所有信息都被用到了。但是只生成一个随机数时，却不如上面的。或者说，需要使用 0~(n-1) 的生成器的次数的期望更高。

举个例子，用 n=8 的生成器，生成 m=7 的随机数。按朴素的想法，每次有 1/8 的概率需要再生成一次。但是按第二种想法，只有第一次产生 0 或 7 时，才只需要生成一次。从第二次开始，依旧每次有 1/8 的概率需要再次生成。

一

.NET 的 `System.Random` 类

现在我们来看 .NET 中的随机数。

.NET 内置了两个与产生随机数有关的类。一个是 System.Random，通过算法产生伪随机数；另一个实际上有至少两个相关类，用来产生无法预测的，可以用作加密用途的生成器。

先看 System.Random。这个类是这么定义的：

public class Random
{
    public Random();
    public Random(int Seed);

    public virtual int Next();
    public virtual int Next(int maxValue);
    public virtual int Next(int minValue, int maxValue);
    public virtual void NextBytes(byte[] buffer);
    public virtual void NextBytes(Span<byte> buffer);
    public virtual double NextDouble();
    protected virtual double Sample();
}

其中 Next(int maxValue) 和 Next(int minValue, int maxValue) 包含 minValue，但均不包含 maxValue，前者默认 minValue 为 0。而 Next() 默认 minValue 为 0，maxValue 为 int.MaxValue（是的，范围比 Int32 可表示的范围的一半少 1）。

先看有趣的 NextDouble() 方法。这个方法产生一个大于等于 0 但小于 1 的随机浮点数。有些地方用这种方式产生一定范围内的整数

int Next(int maxValue)
{
    return (int)Math.Floor(maxValue * NextDouble());
}

很明显，这种方法只能近似等概率。这是因为，由于精度限制，能产生的不同的随机浮点数的个数是有限的，而每一个浮点数都会固定对应一个结果，这样就不能保证每个结果都对应同样个数的浮点数，因而概率不等。

生成指定范围的随机数

如果现在我告诉你，随机数生成器的底层是产生一堆随机比特，或者说，是第一位都等概率随机的 System.UInt32，让你去写产生指定范围随机数，即 int Next(int minValue, int maxValue)，你会怎么写？

最简单的办法，如果还是不考虑概率的微小差别，可以简单这么写

int Next(int minValue, int maxValue)
{
    Debug.Assert(minValue < maxValue);
    uint range = maxValue - minValue;
    if (range == 1) return minValue;
    uint rand = NextUInt32();
    return minValue + (int)(rand % range);
}

为了保证完全等概率，可以这么改写

int Next(int minValue, int maxValue)
{
    Debug.Assert(minValue < maxValue);
    uint range = (uint)(maxValue - minValue);
    uint max = (uint)(((ulong)uint.MaxValue + 1) / range * range - 1);
    while (true)
    {
        uint rand = NextUInt32();
        if (rand <= max)
            return minValue + (int)(rand % range);
    }
}

好了，我们看一下.NET 中是如何实现的

public override int Next(int minValue, int maxValue)
{
    ulong exclusiveRange = (ulong)(maxValue - minValue);

    if (exclusiveRange > 1)
    {
        // Narrow down to the smallest range [0, 2^bits] that contains maxValue.
        // Then repeatedly generate a value in that outer range until we get one within the inner range.
        int bits = BitOperations.Log2Ceiling(exclusiveRange);
        while (true)
        {
            ulong result = NextUInt64() >> (sizeof(ulong) * 8 - bits);
            if (result < exclusiveRange)
            {
                return (int)result + minValue;
            }
        }
    }

    Debug.Assert(minValue == maxValue || minValue + 1 == maxValue);
    return minValue;
}

.NET 并没有使用乘、除算出范围，再用模确定数字，而是计算出需要的比特，并直接抛弃掉多余的。这么做可能是考虑到性能。

二

在 .NET 中，还有一个类是与生成随机数有关的（确切地说，有多个类）。最主要的就是 System.Security.Cryptography.RandomNumberGenerator。从命名空间就可以看出来，这是用来产生可用于加密的随机数的。有趣的是，它用来生成给定范围随机数的方法是通过位运算得到一个 mask，然后用按位与去取需要的比特，而 System.Random 是计算出需要的比特数，用位移取得需要的比特。

产生任意范围的整数随机数

零

最朴素的想法

另外一种想法

一

.NET 的 System.Random 类

生成指定范围的随机数

二

.NET 的 `System.Random` 类