如何用加法和移位实现模t余r的n位随机数生成？

核心思路 #

要避开效率低下的长除法，我们可以通过预计算移位近似逆元替代x//t的计算，再结合移位、加法完成后续操作，最终得到满足结果 ≡ r mod t的均匀分布n位随机数。

1. 预计算关键参数 #

针对给定的t，先确定两个参数：

• k：取n位整数的总位数（比如uint64_t对应64）
• m：预计算一个近似等于2^k / t的值，可通过移位+加法的牛顿迭代法得到，全程不用除法
  同时预计算阈值threshold = (2^k) % t，用于后续拒绝采样保证计算精确性。

2. 拒绝采样过滤无效值 #

拿到随机数x后，先判断：如果x >= 2^k - threshold，直接丢弃这个x，重新生成新的随机数。这一步是为了确保剩下的x用移位+加法算出的商是精确的，避免近似误差。

3. 用移位+加法计算商q #

原本的q = x//t，可以通过q = (x * m) >> k计算。如果要彻底禁用乘法（仅用加法+移位），可以把m拆成2的幂次之和（比如m = 2^a + 2^b + ...），将x*m转化为(x<<a) + (x<<b) + ...，再右移k位得到q。

4. 生成最终结果 #

计算q*t时，同样把t拆成2的幂次之和（比如t=10=2^3+2^1），将q*t转化为(q<<3) + (q<<1)，最后加上r就得到符合要求的结果。

特殊情况优化：t是2的幂 #

如果t是2的幂（比如t=2^s），直接简化操作：

• q = x >> s（移位直接替代除法）
• result = (q << s) + r
  此时效率最高，无额外计算开销。

示例代码（uint64_t） #

假设t为已知常量，预计算好m和threshold：

#include <stdint.h>

// 你的n位随机数生成器
uint64_t get_random_uint64();

// 预计算参数：替换为对应t的实际值
#define PRECOMPUTED_M 0x...
#define PRECOMPUTED_THRESHOLD 0x...

uint64_t gen_mod_r(uint64_t r) {
    uint64_t x;
    // 拒绝采样，保证计算精确
    do {
        x = get_random_uint64();
    } while (x >= (1ULL << 64) - PRECOMPUTED_THRESHOLD);

    // 用移位加法计算q = x//t（示例：m=2^60 + 2^58）
    uint64_t q = ((x << 60) + (x << 58)) >> 64;

    // 用移位加法计算q*t（示例：t=2^3 + 2^1=10）
    uint64_t qt = (q << 3) + (q << 1);
    return qt + r;
}

均匀性说明 #

拒绝采样过滤了会导致计算误差的x区间，避免了直接模运算带来的分布偏斜；精确计算的q保证每个符合≡r mod t的n位整数被选中的概率完全一致。

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