Nearly Divisionless Random Integer Generation on Various Systems

It seems based on her testing that a very simple bit mask & rejection technique ("Apple's method", as Apple implemented it in their modification of arc4random_uniform) is the fastest among the unbiased techniques, particularly for large N, while for mixed N Lemire's technique seems competitive or better. She suggests a further optimisation, which now clearly "wins" except for large N.

Cool stuff - I find random number generation fascinating.

http://www.pcg-random.org/posts/bounded-rands.html

Code for shuffle(x):

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

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

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