NRK <nrk_AT_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
Received on Sun Mar 03 2024 - 15:05:47 CET