On: Nearly Divisionless Random Integer Generation on Various Systems

[raymondh]

If I'm reading this correctly, it is very close to what Python has been doing for over a decade, so I am not sure that using a "rejection method" counts as "new tech". Here are the relevant snippets.

Code for shuffle(x):

    for i in reversed(range(1, len(x))):
        j = randbelow(i+1)
        x[i], x[j] = x[j], x[i]

Code for randbelow(n):

    k = n.bit_length()
    r = getrandbits(k)
    while r >= n:
        r = getrandbits(k)
    return r

Code for getrandbits(k):

    bytes = ((k - 1) / 32 + 1) * 4;
    for (i=0 ; i<bytes ; i+=4, k-=32) {
        r = genrand_int32(self);
        if (k < 32)
            r >>= (32 - k);
        bytearray[i+0] = (unsigned char)r;
        bytearray[i+1] = (unsigned char)(r >> 8);
        bytearray[i+2] = (unsigned char)(r >> 16);
        bytearray[i+3] = (unsigned char)(r >> 24);
    }

[dgacmu → raymondh]

Rejection isn't new - what's new is using a variation of his "use the high order bits of the 64x64 multiply by a range to get a random number efficiently" trick (which he published two or three years ago) to substantially improve the efficiency of a rejection sampling method.

The efficient random number in a range trick is really cool. I've used it in a couple of data structures that we've designed - it's substantially faster than using modulus, or even using pre-computed division by reciprocal multiplication.

[nullwasamistake → raymondh]

Lemire has some great stuff. It looks like mostly self dicovery so some of his efforts have historical precendent.

[AlexCoventry → raymondh]

It's not presented very clearly in the blog post, but it's a novel use of rejection sampling.