A simple PRNG using /dev/urandom

[mar]

I stole it.

Search the web for "modulus bias" and you'll see similar code in many places.

You know, I always enjoy vastly more 10 interesting lines than 100k lines of crap.
That being said, I very much enjoyed how Ronald decodes multiple bits of static Huffmann in Syzygy (without LUT), because obviously decoding bit by bit is slow.
I find it a pity that many fail to see such beauty...

[AlvaroBegue]

There is another problem. /dev/random and cousins are slow. All the hysteresis data takes time to gather, and once you exhaust what is there, you get ti wait while more is collected. Better might be a simple linear congruential PRNG where you use /dev/random to seed it, then call it 10K times, and re-seed. This prevents any short cycles from showing up and beats on the kernel much less...

I don't think "hyteresis" is the word you were looking for; probably "entropy".

Anyway, that's what /dev/urandom is for: It doesn't stop generating data even if its estimate of entropy is low.

[bob]

There is another problem. /dev/random and cousins are slow. All the hysteresis data takes time to gather, and once you exhaust what is there, you get ti wait while more is collected. Better might be a simple linear congruential PRNG where you use /dev/random to seed it, then call it 10K times, and re-seed. This prevents any short cycles from showing up and beats on the kernel much less...

I don't think "hyteresis" is the word you were looking for; probably "entropy".

Anyway, that's what /dev/urandom is for: It doesn't stop generating data even if its estimate of entropy is low.

yes. Not sure what I was thinking of there. Thanks.

And I had not looked at /dev/urandom specifically. But kernel calls to get random numbers seems like a VERY slow way of doing this, anyway.

[AlvaroBegue]

There is another problem. /dev/random and cousins are slow. All the hysteresis data takes time to gather, and once you exhaust what is there, you get ti wait while more is collected. Better might be a simple linear congruential PRNG where you use /dev/random to seed it, then call it 10K times, and re-seed. This prevents any short cycles from showing up and beats on the kernel much less...

I don't think "hyteresis" is the word you were looking for; probably "entropy".

Anyway, that's what /dev/urandom is for: It doesn't stop generating data even if its estimate of entropy is low.

yes. Not sure what I was thinking of there. Thanks.

And I had not looked at /dev/urandom specifically. But kernel calls to get random numbers seems like a VERY slow way of doing this, anyway.

It does seem pretty slow. On a i3-4350 I get about 2 million 64-bit numbers per second from /dev/urandom, but 400 million 64-bit numbers per second using C++11's std::mt19937_64.

[sje]

100 million random games in 9 hours 15 minutes

Code: Select all

[] rg 100000000
   checkmate 15300361 0.153004
  fiftymoves 19346686 0.193467
insufficient 56712907 0.567129
  repetition  2518894 0.0251889
   stalemate  6121152 0.0612115
Average ply length: 334.356
Maximum ply length: 1005
PT: 1:11:59:11.054
WT: 9:15:10.695

Game throughput rate: 3 KHz
Random call rate: 1 MHz

By the way, this is the OpenBSD /dev/urandom in play.

[sje]

Search the web for "modulus bias" and you'll see similar code in many places.

You know, I always enjoy vastly more 10 interesting lines than 100k lines of crap.

Sorry for any inconvenience; I stole the idea so long ago that I can't recall the source -- but I did recall the search terms.

[sje]

And I had not looked at /dev/urandom specifically. But kernel calls to get random numbers seems like a VERY slow way of doing this, anyway.

You're right, it is slow. There are two reasons for this. The first is that the kernel's demand of pseudorandom numbers is low. The second is that the driver code has seen many modifications over the past quarter century; nearly all for improving the quality of the output and few, if any, for increasing the speed.

[sje]

With buffering a megabyte of /dev/urandom per read, there is a slight speed improvement:

Code: Select all

[] rg 1000000
   checkmate   152751 0.152751
  fiftymoves   193819 0.193819
insufficient   567363 0.567363
  repetition    25021 0.025021
   stalemate    61046 0.061046
Average ply length: 334.44
Maximum ply length: 873
PT: 19:16.566
WT: 4:54.936

That's about a 10% speed increase.

[michiguel]

Here's some C++ source code for a PRNG (pseudorandom number generator) which uses guarded access to the kernel's /dev/urandom device.

This very much looks like a RNG, without any pseudo. What do I miss?

/dev/random and /dev/urandom are PRNG. They take environmental noise (or hardware RNG output), and do some math with it to make a pseudo-random stream with the desired distribution.

Well, we are down to definitions, but I generally expect to be able to reproduce what my program did if I am careful to seed the PRNG appropriately. This won't work with /dev/urandom. For that reason alone, I would much rather use a standard PRNG without any pesky entropy getting in the way.

I also almost always use pure PRNG. /dev/urandom is really only beneficial for cryptographic applications.

A chess engine does need a RNG. At least it needs an initial random number to seed the PRNG used for the book. This would be useful to seed that initial number.

Miguel

[sje]

A chess engine does need a RNG. At least it needs an initial random number to seed the PRNG used for the book. This would be useful to seed that initial number.

A repeatable PRNG is quite useful for generating Zobrist hash keys.