6 ms·
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
by raymondh 7y ago
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);
}
- nullwasamistake 7y agoLemire has some great stuff. It looks like mostly self dicovery so some of his efforts have historical precendent.
- dgacmu 7y agoRejection 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.
- AlexCoventry 7y agoIt's not presented very clearly in the blog post, but it's a novel use of rejection sampling.