What is the fast modulo replacement for random number generation?

Question

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.

That xorshift `r` function looks quite like http://xkcd.com/221/ . — user562374, Jan 12 '11 at 13:28
How do you define slow? The DIV instruction can be used for this and it runs in 26 clock cycles on a modern x86 (i7) and in 40 on Core2. — Jonas Elfström, Jan 12 '11 at 13:35
This is still much compared to the clock cycles needed for r(). — Łukasz Lew, Jan 12 '11 at 13:50
@user562374 - I thought the same until I saw y is declared static. — hookenz, Nov 30 '11 at 03:12
@ŁukaszLew, have you solved this problem? I need roughly the same, or even to optimize a larger task: get the index vector for a random permutation between `0` and `n!-1` inclusively — Serge Rogatch, Oct 03 '22 at 17:44

score 0 · Answer 1 · answered Oct 04 '22 at 08:46

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

What is the fast modulo replacement for random number generation?

1 Answers1