A simple PRNG using /dev/urandom

[sje]

Disconnecting the spinlock and requiring each thread to have its own PRNG instance more than doubles the speed. I think this is about as fast as it will get using /dev/urandom.

Code: Select all

[] rg 1000000
   checkmate   153137 0.153137
  fiftymoves   192654 0.192654
insufficient   567287 0.567287
  repetition    25390 0.02539
   stalemate    61532 0.061532
Average ply length: 334.338
Maximum ply length: 895
PT: 7:09.070
WT: 2:28.816

[sje]

Revised code with buffering and selectable thread safety:

Code: Select all

#define PRNGBufferLen BX(20)

class PRNG
{
public:
  PRNG(const bool issafe);
  ~PRNG(void);

  ui32 NextDwrd(void);
  ui64 NextQwrd(void);
  
  ui Pick(const ui bound);
  
private:
  void LoadBuffer(void);
  void ReadFromBuffer(ui8Ptr const targetptr, const ui count);
  
  bool           isthreadsafe;
  std::ifstream *ifsptr;
  SpinLockPtr    spinlockptr;
  ui8Ptr         bufferptr;
  ui             offset;
};

Code: Select all

PRNG::PRNG(const bool issafe)
{
  isthreadsafe = issafe;
  ifsptr = new std::ifstream("/dev/urandom", std::ios::binary);
  spinlockptr = new SpinLock();
  bufferptr = new ui8[PRNGBufferLen];
  LoadBuffer();
}

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

void PRNG::LoadBuffer(void)
{
  ifsptr->read((char *) bufferptr, PRNGBufferLen);
  offset = 0;
}

void PRNG::ReadFromBuffer(ui8Ptr const targetptr, const ui count)
{
  ui8Ptr tptr = targetptr;
  
  if (isthreadsafe)
    spinlockptr->Lock();

  ZOL(index, count)
  {
    if (offset == PRNGBufferLen)
      LoadBuffer();
    *tptr++ = bufferptr[offset++];
  };

  if (isthreadsafe)
    spinlockptr->Unlock();
}

ui32 PRNG::NextDwrd(void)
{
  ui32 nextdwrd;

  ReadFromBuffer((ui8Ptr) &nextdwrd, sizeof(nextdwrd));
  return nextdwrd;
}

ui64 PRNG::NextQwrd(void)
{
  ui64 nextqwrd;
  
  ReadFromBuffer((ui8Ptr) &nextqwrd, sizeof(nextqwrd));
  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 (next < range)
        next = NextDwrd();
      pick = next % bound;
    };
  };
  return pick;
}

[hMx]

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.

I don't understand. Transforming a RNG stream will yield another RNG stream (with maybe another distribution), but not any pseudorandom stream. Please also see wikipedia about the pseudo, https://en.wikipedia.org/wiki/Pseudorandomness :

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuinely random one, and has the benefit that it can be used again and again to produce exactly the same numbers - useful for testing and fixing software.

Sorry for being nitpicking. I like the RNG, but I think the name PRNG is misleading, here.

[sje]

Real RNGs

https://en.wikipedia.org/wiki/Hardware_ ... _generator

[kbhearn]

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.

I don't understand. Transforming a RNG stream will yield another RNG stream (with maybe another distribution), but not any pseudorandom stream. Please also see wikipedia about the pseudo, https://en.wikipedia.org/wiki/Pseudorandomness :

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuinely random one, and has the benefit that it can be used again and again to produce exactly the same numbers - useful for testing and fixing software.

Sorry for being nitpicking. I like the RNG, but I think the name PRNG is misleading, here.

precisely because of that definition you just quoted, the kernel RNG has been called a PRNG in recent times. The interrupts and network traffic and what not that feed timestamps into the entropy pool while very hard to predict are not truly random. About the only thing that seems to be allowed to call itself truly random these days has to be based off quantum effects.

[hMx]

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.

I don't understand. Transforming a RNG stream will yield another RNG stream (with maybe another distribution), but not any pseudorandom stream. Please also see wikipedia about the pseudo, https://en.wikipedia.org/wiki/Pseudorandomness :

A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuinely random one, and has the benefit that it can be used again and again to produce exactly the same numbers - useful for testing and fixing software.

Sorry for being nitpicking. I like the RNG, but I think the name PRNG is misleading, here.

precisely because of that definition you just quoted, the kernel RNG has been called a PRNG in recent times. The interrupts and network traffic and what not that feed timestamps into the entropy pool while very hard to predict are not truly random. About the only thing that seems to be allowed to call itself truly random these days has to be based off quantum effects.

I do understand that the kernel RNG is not the best possible RNG. But it is also not an entirely deterministic causal process. For me, pseudo-random implies that it can be repeated, and that is not the case here. One may call the kernel RNG a weak one, or a not truely one, but not a pseudo one, I find that misleading.[/i]

[sje]

1e+8 random games in three hours which needed about 124 GiB read from /dev/urandom (ca. 12 MiB/second). The /dev/urandom throughput is the limiting factor with on average 4.5 of the 8 hyperthreads being blocked waiting.

Code: Select all

[] rg 100000000
   checkmate 15308505 0.153085
  fiftymoves 19340471 0.193405
insufficient 56714899 0.567149
  repetition  2517152 0.0251715
   stalemate  6118973 0.0611897
Average ply length: 334.34
Maximum ply length: 1037
PT: 10:34:46.844
WT: 3:03:38.892

[sje]

1e+8 random games, again, but this time using two bytes from /dev/urandom instead of four for each random move pick.

Code: Select all

[] rg 100000000
   checkmate 15301890 0.153019
  fiftymoves 19341065 0.193411
insufficient 56717240 0.567172
  repetition  2518543 0.0251854
   stalemate  6121262 0.0612126
Average ply length: 334.36
Maximum ply length: 1055
PT: 9:24:54.925
WT: 1:54:15.471

[sje]

The above were generated on Mac OS/X machines. The following was made on a quad core 3.1 GHz AMD Athlon II X4 box:

Code: Select all

[] rg 100000000
   checkmate 15313187 0.153132
  fiftymoves 19338722 0.193387
insufficient 56709782 0.567098
  repetition  2518753 0.0251875
   stalemate  6119556 0.0611956
Average ply length: 334.331
Maximum ply length: 1067
PT: 8:02:30.765
WT: 2:01:12.606

Note that the /dev/urandom draw here is able to match the need of the game generation.

----
From:

https://en.wikipedia.org/wiki/Compariso ... generators

See:

http://www.seeedstudio.com/depot/FST01- ... -1279.html

http://ubld.it/products/truerng-hardwar ... generator/

https://www.tindie.com/products/Wayward ... ite-noise/

http://www.moonbaseotago.com/onerng/

Buy one of each and XOR the streams.

[matthewlai]

Revised code with buffering and selectable thread safety:

Code: Select all

#define PRNGBufferLen BX(20)

class PRNG
{
public:
  PRNG(const bool issafe);
  ~PRNG(void);

  ui32 NextDwrd(void);
  ui64 NextQwrd(void);
  
  ui Pick(const ui bound);
  
private:
  void LoadBuffer(void);
  void ReadFromBuffer(ui8Ptr const targetptr, const ui count);
  
  bool           isthreadsafe;
  std::ifstream *ifsptr;
  SpinLockPtr    spinlockptr;
  ui8Ptr         bufferptr;
  ui             offset;
};

Code: Select all

PRNG::PRNG(const bool issafe)
{
  isthreadsafe = issafe;
  ifsptr = new std::ifstream("/dev/urandom", std::ios::binary);
  spinlockptr = new SpinLock();
  bufferptr = new ui8[PRNGBufferLen];
  LoadBuffer();
}

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

void PRNG::LoadBuffer(void)
{
  ifsptr->read((char *) bufferptr, PRNGBufferLen);
  offset = 0;
}

void PRNG::ReadFromBuffer(ui8Ptr const targetptr, const ui count)
{
  ui8Ptr tptr = targetptr;
  
  if (isthreadsafe)
    spinlockptr->Lock();

  ZOL(index, count)
  {
    if (offset == PRNGBufferLen)
      LoadBuffer();
    *tptr++ = bufferptr[offset++];
  };

  if (isthreadsafe)
    spinlockptr->Unlock();
}

ui32 PRNG::NextDwrd(void)
{
  ui32 nextdwrd;

  ReadFromBuffer((ui8Ptr) &nextdwrd, sizeof(nextdwrd));
  return nextdwrd;
}

ui64 PRNG::NextQwrd(void)
{
  ui64 nextqwrd;
  
  ReadFromBuffer((ui8Ptr) &nextqwrd, sizeof(nextqwrd));
  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 (next < range)
        next = NextDwrd();
      pick = next % bound;
    };
  };
  return pick;
}

A little off topic here, but is there a reason for all those things to be pointers? It seems like they can just be regular members and there would be no need for heap allocation/deallocation (of course, in C++11 or Boost, smart pointers would be another safe option).

Also for "isthreadsafe", it may be faster to make it a template parameter instead, so compiler can optimize it out completely if you don't need it.