断尾法生成指定范围随机数的进阶思考

顾毅
再创世纪·代码厨房
2025-07-26
257热度
0评论

最近接触了一些随机数的使用场景，对于生成指定范围随机数有了一些新的体会。那么借此机会，直接写成系列文章好了。本文涉及大量数学公式推演，正好学习一下LaTex。后续考虑在使用场景、算法方面再做一些深入研究。

0. “断尾法”之重生

前序文章提到，“断尾法”生成指定范围随机数，其随机性是可靠的，但存在一定概率需要重新生成。极端情况下，重新生成的概率接近 $\dfrac{1}{2}$ ，由此造成其性能可能不佳，转而讨论了“走马灯法”。“走马灯法”可以视为“断尾法”的一种改良，通过“数据循环”的方式利用了本应被舍弃的“尾部”，降低了理论最大性能开销，却也引入了对随机性的一些不利影响。那么换种思路，如果能将“断尾法”中，原始随机数落入“尾部”而导致舍弃需要重新生成的概率降低到可接受的范围内，也是一种权衡的策略。

设伪随机数生成器的宽度为 $R$ ，则其随机值域为 $[0, R-1]$ 。“断尾法”中，设尾长度为 $T$ ，舍弃概率为 $p$ ，则：

(1) $\begin{align*} p=\frac{T}{R} \end{align*}$

希望 $p$ 尽可能小，只有两种办法， $T$ 尽可能小，或者 $R$ 尽可能大。“走马灯法”可以视为使 $T$ 尽可能小的一种特殊方法。那么，有什么办法使 $R$ 显著变大，而不影响整体随机性能？

常见的映射过程是直接将伪随机数发生器的生成值作为输入，使用伪随机数发生器的值域作为随机值域。如果在映射之前，可以将随机值域进行适当拓宽，那么落入尾而被舍弃的概率有可能减小。比如说，对于一个宽度小于 $2^{32}$ 的目标值域，使用64位随机数来映射。这当然可以，只是每次都需要额外增加一倍的资源来生成随机数，资源占用情况与原始“断尾法”的极端情况相当，得不偿失。因此，需要选择一个合适的拓展尺度，以获取尽可能好的“性价比”（性能资源比）。

0. 定义与术语

定义1：本文采用包含0的自然数集定义，即 $\mathbb{N} = \{0, 1, 2, ...\}$

定义2：自然数的求模运算（mod）：如果 $\exists k, t, r \in \mathbb{N}$ ， $n \in \mathbb{Z^+}$ 且 $t < n$ ，使 $r = kn + t$ 成立，则 $t = r \bmod n$ 。

1. 预备定理及证明

定理1：对于 $\boldsymbol{\forall n \in \mathbb{Z^+}}$ ， $\boldsymbol{0 \bmod n = 0}$

证明：根据定义，必然 $\exists k, t, r \in \mathbb{N}$ 且 $t < n$ ，使 $r = kn + t$ 成立，则 $t = r \bmod n$ 。

$\left. \begin{matrix} k \geq 0, n > 0 &\Rightarrow kn \geq 0\\ r = 0 &\Rightarrow kn + t = 0 \\ &t \geq 0 \end{matrix} \right\}\Rightarrow kn = t = 0 \Rightarrow 0 = 0 \bmod n$

证毕。

定理2：对于 $\boldsymbol{\forall r, n \in \mathbb{Z^+}}$ ，如果 $\boldsymbol{r < n}$ ，则 $\boldsymbol{r \bmod n = r}$

证明：根据定义，必然 $\exists k, t \in \mathbb{N}$ 且 $t < n$ ，使 $r = kn + t$ 成立，则 $t = r \bmod n$ 。

$\left. \begin{matrix} \left. \begin{matrix} r = kn + t < n \Rightarrow (1 - k)n > t \geq 0 \Rightarrow &(1 - k)n > 0\\ &n > 0 \end{matrix} \right\} \Rightarrow &k < 1 \\ &k \geq 0 \end{matrix} \right\} \Rightarrow k = 0 \Rightarrow r = t \Rightarrow r = r \bmod n$

证毕。

定理3：对于 $\boldsymbol{\forall k \in \mathbb{N}}$ ， $\boldsymbol{n \in \mathbb{Z^+}}$ ， $\boldsymbol{(kn) \bmod n = 0}$

证明：根据定义，设 $R = kn$ ，则 $R \in \mathbb{N}$ ，且必然 $\exists K, T \in \mathbb{N}$ 且 $T < n$ ，使 $R = Kn + T$ 成立，则 $T = R \bmod n$ 。

$\left. \begin{matrix} \left. \begin{matrix} R = kn = Kn + T \Rightarrow &0 \leq T = (k - K)n < n\\ &n > 0 \end{matrix} \right\} \Rightarrow &0 \leq k - K < 1 \\ &k, K \in \mathbb{N} \end{matrix} \right\} \Rightarrow \begin{cases}k = K \\ T = 0 \end{cases} \Rightarrow (kn) \bmod n = 0$

证毕。

定理4：对于 $\boldsymbol{\forall k, T \in \mathbb{N}}$ ， $\boldsymbol{n \in \mathbb{Z^+}}$ ， $\boldsymbol{(kn + T) \bmod n = T \bmod n}$

证明：根据定义，必然 $\exists k_T, t_T \in \mathbb{N}$ 且 $t_T < n$ ，使 $T = k_Tn + t_T$ 成立。不妨设 $R = kn + T$ ， $K = k + k_T$ ，则 $R, K \in \mathbb{N}$ 。

(2) $\begin{align*} R &= kn + T= kn + k_Tn + t_T= (k + k_T)n + t_T\\ &= Kn + t_T \end{align*}$

于是 $\exists K, t_T, R \in \mathbb{N}$ ， $n \in \mathbb{Z^+}$ 且 $t_T < n$ ，使 $R = Kn + t_T$ 成立，满足mod运算定义

则 $t_T = R \bmod n = T \bmod n$

证毕。

定理5：对于 $\boldsymbol{\forall R_x, R_y \in \mathbb{N}}$ ， $\boldsymbol{n \in \mathbb{Z^+}}$ ， $\boldsymbol{(R_x + R_y ) \bmod n = (R_x \bmod n + R_y \bmod n) \bmod n}$

证明：设 $T_n = R_n \bmod n$ （其中 $T_n, R_n \in \mathbb{N}$ 且 $T_n < n$ ），必然 $\exists k_n \in \mathbb{N}$ ，使 $R_n = k_nn + T_n$ 。则

$R_x + R_y = k_xn + T_x + k_yn + T_y = (k_x + k_y)n + T_x + T_y$

根据定理3、4可知，

(3) $\begin{align*} (R_x + R_y) \bmod n &= ((k_x + k_y)n + T_x + T_y) \bmod n= (T_x + T_y) \bmod n \\ &= (R_x \bmod n + R_y \bmod n) \bmod n \end{align*}$

证毕。

定理6：对于 $\boldsymbol{\forall R_x, R_y \in \mathbb{N}}$ ， $\boldsymbol{n \in \mathbb{Z^+}}$ ， $\boldsymbol{(R_xR_y ) \bmod n = ((R_x \bmod n)(R_y \bmod n)) \bmod n}$

证明：设 $T_n = R_n \bmod n$ （其中 $T_n, R_n \in \mathbb{N}$ ， $n \in \mathbb{Z^+}$ ，且 $T_n < n$ ），必然 $\exists k_n \in \mathbb{N}$ ，使 $R_n = k_nn + T_n$ 。则

$R_xR_y= (k_xn + T_x)(k_yn + T_y) = k_xk_yn^{2} + (k_x + k_y)n + T_xT_y$

根据定理3、4可知，

(4) $\begin{align*} (R_xR_y) \bmod n &= (k_xk_yn^{2} + (k_x + k_y)n + T_xT_y) \bmod n= (T_xT_y) \bmod n \\ &= ((R_x \bmod n)(R_y \bmod n)) \bmod n \end{align*}$

证毕。

2. 拓宽随机值域与舍弃概率的定量关系

设伪随机数生成器的宽度为 $R$ ，目标值域宽度为 $n$ ，尾长为 $T (T < n)$ ，且 $\exists k \in \mathbb{N}$ 使 $R = kn + T$ 成立。

当 $k = 0$ 时， $R = T < n$ ，在随机数映射的场景无实际意义；

当 $k > 0$ 时，

(5) $\begin{align*} R = kn + T > (k + 1)T \Rightarrow T < \frac{R}{k + 1} \le \frac{R}{2} \end{align*}$

当且仅当 $k = 1$ 时，

(6) $\begin{align*} T_{\text{MAX}} = \left \lfloor \frac{R - 1}{2} \right \rfloor \end{align*}$

加下标0表示 $n$ 取给定值时对应的各个参数，则

(7) $\begin{align*} R = k_0n_0 + T_0, p_0 = \frac{T_0}{R} \leq \frac{T_{\text{MAX}}}{R} < \frac{1}{2} \end{align*}$

将随机值域拓宽为 $m$ 倍 ( $m > 1$ )，加下标m表示将 $R$ 拓宽之后的各个参数（此时保持 $n$ 不变），则

(8) $\begin{align*} R_{\text{m}} &= mR = m(k_0n_0 + T_0)= mk_0n_0 + mp_0R \end{align*}$

当 $mp_0R < n_0$ 时，

$T_m = mp_0R, p_m = \frac{mp_0R}{mR} = p_0, \frac{p_m}{p_0} = 1$

此种情况下，随机宽度增大，舍弃概率 $p$ 却没有减小，徒增资源投入，应避免出现。

当 $mp_0R = n_0$ 时，

$T_m = 0, p_m = 0, \frac{p_m}{p_0} = 0$

此种情况下，舍弃概率 $p$ 减小至0，是理论上的最佳。

当 $mp_0R > n_0$ 时，可对(8)式继续展开

(9) $\begin{align*} R_{\text{m}} &= mk_0n_0 + mp_0R = mk_0n_0 + mp_0(k_0n_0 + p_0R) \\ &= (mk_0 + mp_0k_0)n_0 + mp_0^2R = ... \\ &= (1 + p_0 + p_0^2 + ... + p_0^{i-1})mk_0n_0 + mp_0^iR\\ &= \frac{1-p_0^i}{1 - p_0}mk_0n_0 + mp_0^iR \end{align*}$

由于 $p_0 < \dfrac{1}{2}$ ，则必然 $\exists i \in \mathbb{Z}^{+}$ 使 $mp_0^iR \leq n_0 < mp_0^{i - 1}R$ ，此时

(10) $\begin{align*} T_m = mp_0^iR, p_m = \frac{mp_0^iR}{mR} = p_0^i, \frac{p_m}{p_0} = p_0^{i - 1} \end{align*}$

可见，当 $i$ 增大时，舍弃概率 $p$ 以指数速率减小。综上所述，当 $mp_0R \geq n_0$ ，即 $m\geq \dfrac{n_0}{p_0R} = \dfrac{n_0}{T_0}$ 时，舍弃概率 $p$ 必然减小。

对 $m$ 与 $i$ 的定量关系继续推理，

$mp_0^iR \leq n_0 < mp_0^{i - 1}R \Rightarrow p_0^i \leq \frac{n_0}{mR} < p_0^{i - 1}$

不等式两边同取 $A(A > 1)$ 为底的对数，

$i\log_{A}{p_0}=\log_{A}{p_0^i}\leq \log_{A}{\dfrac{n_0}{mR}} < \log_{A}{p_0^{i-1}} = (i-1)\log_{A}{p_0}$

又 $p_0 < 1$ ， $\log_{A}{p_0} < 0$ ，则

$i - 1 < \frac{\log_{A}{\dfrac{n_0}{mR}}}{\log_{A}{p_0}} \leq i$

考虑到 $i \in \mathbb{Z}^{+}$ ，则

(11) $\begin{align*} i = \left\lceil \dfrac{\log_{A}{\dfrac{n_0}{mR}}}{\log_{A}{p_0}} \right\rceil \end{align*}$

3. 拓宽随机值域与资源开销的定量关系

设某伪随机数生成流程的舍弃概率为 $p$ ， $j$ 表示生成符合要求随机数（首次不被舍弃）所需要的次数，数列 $\{a_j\}$ 表示与次数 $j$ 对应的概率，则

(12) $\begin{align*} a_1 &= 1-p \\ a_2 &= p(1-p)\\ a_3 &= p^2(1-p)\\ ...\\ a_j &= p^{j - 1}(1-p) \end{align*}$

一个稳定的伪随机数发生器，其每一次生成随机数所需的资源开销（比如时间复杂度、空间复杂度）应当是一致的，多次生成所需的总开销与生成次数成正比。设该伪随机数发生器每一次生成随机数需要的资源为常数 $C(C > 0)$ ，生成一次符合要求的随机数（首次不被舍弃）的期望资源开销为 $S$ ，则

(13) $\begin{align*} S &= \sum_{j = 1}^{\infty} Cip ^ {j - 1}(1-p) = C (1-p) \sum_{j = 1}^{\infty} j p ^ {j - 1}\\ &= C (1-p) \sum_{j = 1}^{\infty} \dfrac{dp^j}{dp} = C (1-p) \dfrac{d(\sum_{j = 0}^{\infty} p ^ j)}{dp}\\ &= C (1-p) \dfrac{d(\dfrac 1{1-p})}{dp} = C (1-p) \dfrac{1}{(1-p)^2}\\ &= \dfrac{C}{1-p} \end{align*}$

如果使用多次生成/裁切的方法来拓宽随机值域，则生成所需的总开销与总位数成正比。此处需要特别注意，随机数的总位数并非其最大值（例如32位伪随机数发生器产生的每一个随机数在二进制下位数皆为32，而其最大值为 $2^{32} - 1$ ）。有一宽度为 $R(R > 0)$ 的伪随机数发生器，在 $A(A \in \mathbb{Z^+})$ 进制下的位数为 $x(x \geq 0)$ ，则 $R = A ^ x$ ；另有一变量 $m(m>1)$ ，在 $A$ 进制下位数为 $y$ ，则 $m = A ^ y$ 。此处不限制 $x, y \in \mathbb{Z}$ 。将该伪随机数发生器值域扩展至 $m$ 倍，此时随机值域的位数为 $z$ ，则

(14) $\begin{align*} mR = A ^ x A ^ y = A ^ {x + y} = A ^ z \Rightarrow z = log_{A}{mR} \end{align*}$

对其值域拓展至 $m$ 倍，对应所需资源为 $C_\text{m}$ ，则

$\dfrac{C_\text{m}}{C} = \dfrac{log_{A}{mR}}{log_{A}{R}}$

由此可得

(15) $\begin{align*} C_\text{m} = C\dfrac{log_{A}{mR}}{log_{A}{R}} \end{align*}$

加下标0表示未拓宽随机值域的各个参数，则

$S_0 = \dfrac{C_0}{1-p_0}$

加下标m表示拓宽随机值域后的各个参数，则

$S_\text{m} = \dfrac{C_\text{m}}{1-p_\text{m}} = \dfrac{C_0}{1-p_0^i}\dfrac{log_{A}{mR}}{log_{A}{R}}$

当 $S_\text{m} < S_0$ ，所需资源开销减少，则

(16) $\begin{align*} &\dfrac{C_0}{1-p_0^i}\dfrac{log_{A}{mR}}{log_{A}{R}} < \dfrac{C_0}{1-p_0} \\ &\Rightarrow \dfrac{log_{A}{m} + log_{A}{R}}{log_{A}{R}} = \dfrac{log_{A}{m}}{log_{A}{R}} + 1< \dfrac{1-p_0^i}{1-p_0} \\ &\Rightarrow \dfrac{log_{A}{m}}{log_{A}{R}} < \dfrac{p_0 - p_0^i}{1 - p_0} \\ &\Rightarrow log_{A}{m} < {log_{A}{R}}\dfrac{p_0 - p_0^i}{1 - p_0} \end{align*}$

对不等式两边取 $A$ 的指数，则

(17) $\begin{align*} m < R ^ {\dfrac {p_0 - p_0^i}{1 - p_0}} \end{align*}$

综上所述，当 $m < R ^ {\dfrac {p_0 - p_0^i}{1 - p_0}}$ 时，所需资源开销必然减小。

4. 拓宽因子

如果一个随机数发生器是符合均匀分布的，这就表明该发生器生成的任一随机数的出现概率均等。对于32位伪随机数发生器，均匀分布又等价于：该发生器生成的任一32 位随机数，其每一位取0或者1的概率皆为 $\dfrac{1}{2}$ 。一个 32 位无符号整形数R可以表示为：

(18) $\begin{align*} R=\sum_{i=0}^{31}{b_i2^i} \end{align*}$

其中， $b_i$ 是第 $i$ 位的比特值（0 或 1）。从此32位随机数中任取 $l$ 位，其每一位取0或者1的概率仍为 $\dfrac{1}{2}$ ，则该 $l$ 位组成 $[0, 2^l - 1]$ 中任一值的概率皆为 $\dfrac{1}{2^l}$ ，符合均匀分布。特别的，当 $l = 8$ 时，即取出了一个字节，该字节的值在 $[0, 2^8 - 1]$ 也是均匀分布的。

由前述推理可知，当 $m\geq \dfrac{n_0}{p_0R} = \dfrac{n_0}{T_0}$ 时，舍弃概率必然减小；当 $m < R ^ {\dfrac {p_0 - p_0^i}{1 - p_0}}$ 时，所需资源开销必然减少。考虑到常见的伪随机数发生器的宽度一般为 $2^i(i \in \mathbb{Z^+})$ ，再考虑现代计算机常见的内存结构是以字节为单位的（长度小于字节的内存结构需要通过位操作完成），则在必要的时候拓宽8位（即取一个完整字节）是合理的最小值。以下取 $m = 256$ 试算32位伪随机数发生器的极端情况下，舍弃概率与所需资源开销的实际变化。由于 $R$ 与 $m$ 都用二进制表示，此处取 $A = 2$ 。

对于32位伪随机数发生器，

(19) $\begin{align*} &R = 2 ^{32}\\ &T_0 = T_\text{MAX} = \left \lfloor \dfrac{R - 1}{2} \right \rfloor = 2 ^{31} - 1\\ &n_0 = 2 ^{31} + 1\\ &k_0 = 1\\ &p_0 = \dfrac{T_0}{R} = \dfrac{2 ^{31} - 1}{2 ^{32}} = \dfrac{1}{2} - \dfrac{1}{2 ^{32}}\approx \dfrac{1}{2}\\ &S_0 = \dfrac{C_0}{1-p_0} = \dfrac{C_0}{\dfrac{1}{2} + \dfrac{1}{2 ^{32}}}\approx 2C_0 \end{align*}$

当 $m = 2^8$ 时，

(20) $\begin{align*} &R_\text{m} = mR = 2^8 2 ^{32} = 2 ^ {40} = (2 ^ {31} + 1)(2 ^ 9 - 1) + 2^{31} + 1 - 2^9\\ &T_\text{m} = 2^{31} + 1 - 2^9\\ &k_\text{m} = 2 ^ 9 - 1\\ &p_\text{m} = \dfrac{T_\text{m}}{R_\text{m}} < \dfrac{T_\text{MAX}}{mR} < \dfrac{1}{2m} = \dfrac{1}{2^9}\\ &S_\text{m} = \dfrac{C_\text{m}}{1-p_\text{m}} = \dfrac{\dfrac{log_{2}{2^{8}2^{32}}}{log_{2}{2^{32}}}C_0}{1-p_\text{m}} \approx \dfrac{5}{4}C_0 \end{align*}$

由此可知，当 $m = 2^8$ 时，对于极端情况，舍弃概率由约 $\dfrac{1}{2}$ 显著减小至约 $\dfrac{1}{2^9}$ ，所需资源开销由约 $2C_0$ 减小至约 $\dfrac{5}{4}C_0$ ，优化的效果非常可观，且当 $m = 2^8$ 时，期望资源开销收敛在 $\dfrac{5}{4}C_0$ 附近，其它变量的影响可以忽略不计。因此，对于一个给定的 $n$ 值，不妨加下标1表示各个变量，则当 $S_1 > S_\text{m}$ 时，拓宽操作才有意义，即

(21) $\begin{align*} &S_1 > S_\text{m}\\ &\Rightarrow \dfrac{C_0}{1-p_1} > \dfrac{5}{4}C_0\\ &\Rightarrow p_1 > \dfrac{1}{5} \end{align*}$

即当原始舍弃概率大于 $\dfrac{1}{5}$ 时，使用 $m = 2^8$ 对随机值域进行拓宽，期望资源开销必然减小。由此定义一个符合均匀分布的8位随机数为随机数发生器宽度的拓宽因子。根据前述的分析，使用符合均匀分布的伪随机数发生器生成的32位无符号随机数的每一个字节，可以作为拓宽因子，而不影响随机性能。

5. 代码实现

uint32_t GetRandomUInt32(uint32_t a, uint32_t b)
{
    if(a > b)
    {
        return GetRandomUInt32(b, a);
    }
    if(a == b)
    {
        return a;
    }
    if(0 == a && UINT32_MAX == b)
    {
        return GetRandomUInt32();
    }

    uint32_t iRangeSize = b - a + 1;
    // 防止溢出，等价于uint32_t iTailSize = (UINT32_MAX + 1) % iRangeSize;
    uint32_t iTailSize = (UINT32_MAX - iRangeSize + 1) % iRangeSize; 
    // 防止溢出，等价于if(iTailSize > (UINT32_MAX + 1) / 5)
    bool bExpand = false;
    if(iTailSize > (UINT32_MAX - 4) / 5 + 1) 
    {
        iTailSize = (iTailSize << 8) % iRangeSize; // 定理4
        bExpand = true;
    }
    // 拓宽后，舍弃仅发生在0xff == iExpand时，因此仍然记录32位的体长即可
    uint32_t iMaxBodyValue = UINT32_MAX - iTailSize; 

    if(bExpand)
    {
        while(true)
        {
            uint8_t iExpand = GetRandomUInt8();
            uint32_t iRand = GetRandomUInt32();
            if(0xff == iExpand && iRand > iMaxBodyValue)
            {
                continue;
            }
            
            // 防止溢出，等价于a + (iExpand << 32 + iRand) % iRangeSize; 
            return a + (iExpand * ((UINT32_MAX - iRangeSize + 1) % iRangeSize) + iRand) % iRangeSize; 
        }
    }
    else
    {
        while(true)
        {
            uint32_t iRand = GetRandomUInt32();
            if(iRand > iMaxBodyValue)
            {
                continue;
            }
            
            return a + iRand % iRangeSize;
        }
    }
}

其中，GetRandomUInt32()是一个均匀分布的32位伪随机数发生器；GetRandomUInt8()是一个8位伪随机数发生函数，该函数截取32位发生器生成的一个32位无符号数的一个字节作为输出。整体代码实现并不复杂。

二零二五年七月二十六日

顾毅写于厦门