NRK <n...@disroot.org> wrote: > I'd recommend using the bitmask approach described in here: > https://www.pcg-random.org/posts/bounded-rands.html#bitmask-with-rejection-unbiased-apples-method
I thought the approach used by OpenBSD was simpler, and performed better, becaused it avoided the loop, which might cause the algorithm to repeat itself, overall slowing the algorithm. It seems not to be the case according to this link. However, the 2 last approaches described (Debiased Int Mult, (t-opt) and (t-opt, m-opt)) seem to perform better, for small-constant benchmarks, small-shuffle and all-ranges-shuffle, with non-negligible performance gains. Where Bitmask performs better, the difference seems negligible. I see that the implementation I sent doesn't have good performance, but should we not rather implement "Debiased Int Mult (t-opt)"? > And if you want a portable clz without depending on __builtin_clz() then see: > https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 I'll work on that, thanks. > I'm not sure why you think arc4random() is better. I doubt you need any > cryptograhic guarantees here. rand(3) could not be used because RAND_MAX causes some problems. random(3) needs a seed, and a good random seed is tricky to get. We can't read from /dev/urandom because it might be that we're in a chroot ; the timestamp can be quite random on its lower bits, but it changes too slowly. Nanoseconds seem okay, but I'm not sure whether or not it's sufficiently random. arc4random(3) doesn't uses seeds, which means that I cannot initialize it wrong (ie., use a PRNG in a way that its results aren't random). > Personally I'd just go with a simple PCG construction. It takes about > ~6 lines of code [0], is fast and has good statistical properties. > Would also avoid spending time locking/unlocking mutex inside libc for > no reason. I think it's a good idea to have our own fast PRNG, but I originally thought it was better to trust the implementers of libc for making a _random_ PRNG. I will play with the PRNG you've sent me though. Thank you -- Elie Le Vaillant