A simple PRNG using /dev/urandom

[sje]

Here's some C++ source code for a PRNG (pseudorandom number generator) which uses guarded access to the kernel's /dev/urandom device. It is not very fast, even if the spinlocks are removed and the PRNG is run only by a single thread. But the output is of very high quality.

First, the header file class definition:

Code: Select all

class PRNG
{
public:
  PRNG(void);
  ~PRNG(void);

  ui32 NextDwrd(void);
  ui64 NextQwrd(void);
  
  ui Pick(const ui bound);
  
private:
  std::ifstream *ifsptr;
  SpinLockPtr    spinlockptr;
};

And the implementation:

Code: Select all

PRNG::PRNG(void)
{
  ifsptr = new std::ifstream("/dev/urandom", std::ios::binary);
  spinlockptr = new SpinLock();
}

PRNG::~PRNG(void)
{
  delete spinlockptr;
  delete ifsptr;
}

ui32 PRNG::NextDwrd(void)
{
  ui32 nextdwrd;
  
  spinlockptr->Lock();
  ifsptr->read((char *) &nextdwrd, sizeof(nextdwrd));
  spinlockptr->Unlock();
  return nextdwrd;
}

ui64 PRNG::NextQwrd(void)
{
  ui64 nextqwrd;
  
  spinlockptr->Lock();
  ifsptr->read((char *) &nextqwrd, sizeof(nextqwrd));
  spinlockptr->Unlock();
  return nextqwrd;
}

ui PRNG::Pick(const ui bound)
{
  ui pick = 0;
  
  if (bound == 0)
    Die("PRNG::Pick", "zero bound");
  else
  {
    if (bound > 1)
    {
      const ui range = -bound % bound;
      ui next = NextDwrd();
      
      while &#40;next < range&#41;
        next = NextDwrd&#40;);
      pick = next % bound;
    &#125;;
  &#125;;
  return pick;
&#125;

[matthewlai]

Have you seen the new PRNG support in C++11 by any chance? The standard library now contains quite a few PRNGs, and many helper functions to use them to draw from many different types of distributions. And everything is portable.

http://en.cppreference.com/w/cpp/numeric/random

std::random_device is an interface to OS-specific random number generators (probably /dev/urandom on Linux).

[sje]

Have you seen the new PRNG support in C++11 by any chance?

Alas, I must code using a dialect supported on all my machines, and C++11 is too much for some of them.

[matthewlai]

Have you seen the new PRNG support in C++11 by any chance?

Alas, I must code using a dialect supported on all my machines, and C++11 is too much for some of them.

That's unfortunate . Cannot upgrade GCC on those machines? Or are they Windows?

[sje]

That's unfortunate . Cannot upgrade GCC on those machines? Or are they Windows?

They include older Macs dating back to the year 2000.

Mostly only Macs made since 2009 are able to include C++11 in the tool chain.

[Look]

Have you seen the new PRNG support in C++11 by any chance?

Alas, I must code using a dialect supported on all my machines, and C++11 is too much for some of them.

That's unfortunate . Cannot upgrade GCC on those machines? Or are they Windows?

Support For C++11 Features in Visual Studio:

https://msdn.microsoft.com/en-us/library/hh567368.aspx

[mar]

Code: Select all

      const ui range = -bound % bound;
      ui next = NextDwrd();
      
      while &#40;next < range&#41;
        next = NextDwrd&#40;);
      pick = next % bound;
&#125;

Very nice solution for uniform distribution. Your own?
I prefer modulo-free but I find this very elegant because you can change range on the fly.

[matthewlai]

Have you seen the new PRNG support in C++11 by any chance?

Alas, I must code using a dialect supported on all my machines, and C++11 is too much for some of them.

That's unfortunate . Cannot upgrade GCC on those machines? Or are they Windows?

Support For C++11 Features in Visual Studio:

https://msdn.microsoft.com/en-us/library/hh567368.aspx

Yes, modern VS supports C++11 very well. I mentioned Windows because I know modern VS doesn't run on older Windows versions, and modern Windows also doesn't run on older hardware.

As you can see from that table, even VS 2012 is missing many commonly used features, so 2013 is the first version that has more or less complete support.

That's not true for the most part for Linux for example, where even very old machines can run recent distributions.

[matthewlai]

That's unfortunate . Cannot upgrade GCC on those machines? Or are they Windows?

They include older Macs dating back to the year 2000.

Mostly only Macs made since 2009 are able to include C++11 in the tool chain.

Ah I see.

For Macs that old, would it be a good idea to convert them to Linux instead? That way they can still get all the new stuff.

Ubuntu no longer officially supports PowerPC, but it's still community-supported, and has all the latest software.

Latest Debian still officially supports PPC.

[sje]

Sample timings

I programmed Symbolic to have its random game generator use the new PRNG.

A random game generation calls the PRNG an average of about 334 times. So a million random games needs about 3.4e+8 such calls. Here's the output of a million game request on a old 2.66GHz quad core machine (four threads):

Code: Select all

[] rg 1000000
   checkmate   153133 0.153133
  fiftymoves   193492 0.193492
insufficient   566914 0.566914
  repetition    25053 0.025053
   stalemate    61408 0.061408
Average ply length: 334.411
Maximum ply length: 865
PT: 21:38.407 (Processor time)
WT: 5:29.544 (Wall time)

The above example indicates a throughput rate of just over 3,000 games per second and just over one million PRNG calls per second.

As you may have guessed, most of the time is spent in the PRNG spinlock and the kernel's /dev/urandom mutex.

It might be possible to save some time by having the PRNG contain a big fat buffer filled by a single call to /dev/urandom.