目前我使用的是非常快的 XorShift 算法:

inline uint r() {
  static uint y = 2463534242u; // seed
  y ^= (y<<13);
  y ^= (y>>17);
  y ^= (y<<5);
  return y;
}

现在我想从区间 [0, n) 生成一个整数。我当然可以这样做:

r() % n

但这很慢。有没有更快的方法？

附言 区间内不同数字概率的小幅不等式是可以接受的。

最佳答案

如果您的n 低于模板的编译器递归深度，您可以尝试来自The fastest way to generate a random permutation 的方法。并让编译器使用更轻量级的操作优化模数。

对于较大的n，您可以使用https://arxiv.org/pdf/1805.10941.pdf 中的方法，其中大部分时间除法运算被乘法(加上小的按位运算)代替。

uint32_t NextInt(const uint32_t modulo) {
    const uint32_t mask = uint32_t(-1);
    uint32_t x = r();
    uint64_t m = x * uint64_t(modulo);
    if(m < modulo) {
        final uint32_t t = uint32_t(-modulo) % modulo;
        while(m < t) {
            x = r();
            m = x * uint64_t(modulo);
        }
    }
    return uint32_t(m >> 32);
}

https://stackoverflow.com/questions/4669039/