什么是随机数生成的快速模替换？

发布于 2024-10-11 23:02:42 字数 328 浏览 3 评论 0原文

目前我正在使用非常快的 XorShift 算法：

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

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

r() % n

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

聚苯乙烯区间内不同数字的概率存在微小的不平等是可以接受的。

原文

Currently I'm using a very fast XorShift algorithm:

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

Now I want to generate an integer from interval [0, n). Of course I can do this:

r() % n

But this is slow. Is there a faster way?

PS
A small inequalities in probabilities of different numbers in the interval are acceptable.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风月客 2024-10-18 23:02:42

如果您的 n 低于模板的编译器递归深度，您可以尝试生成随机排列的最快方法，并让编译器通过更轻量级的操作来优化模数。

对于较大的 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);
}

If your n is below the compiler recursion depth for templates, you can try the approach from The fastest way to generate a random permutation and let the compiler optimize the modulo with more lightweight operations.

For larger n you can use the approach from https://arxiv.org/pdf/1805.10941.pdf , where most of the time the division operation is replaced with multiplication (plus small bitwise ops).

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);
}

回复收藏 0 原文

~没有更多了~