Thread: Seeded/Seedless random number

Originally Posted by christop

I just noticed this part of your dieharder output (from 10 hours ago):

Code:

   rng_name    |rands/second|   Seed   |
        mt19937|  7.47e+07  |2183355501|

It looks like dieharder is using the "mt19937" RNG by default (the man page for dieharder confirms this). That is the "Mersenne Twister" using 19937 bits of state. This is a pretty good RNG, as you can see from dieharder's analysis.

Edit to add: you need to call dieharder with the "-g 200" option to make it read your "random" data on standard input.

Oh okay thx, might as well stick with file for now since it is currently running

Originally Posted by laserlight

So the utility just discarded what was fed to it via standard input?

It appears so.

In any case, the manual gives a clear example of the simplest way to test a random-number generator:

The simplest way to use dieharder with an external generator that produces raw binary (presumed random) bits is to pipe the raw binary output from this generator (presumed to be a binary stream of 32 bit unsigned integers) directly into dieharder, e.g.:

cat /dev/urandom | ./dieharder -a -g 200

(Just replace "cat /dev/urandom" with "./mcc_rnd_die.elf", and make sure the program produces binary output.)

Here's the code I'm testing. I modified flp1969's code just slightly to produce binary output.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

// using size_t instead of ptrdiff_t (same thing)
typedef size_t mcc_rnd_t;

static unsigned long mcc__rnd( mcc_rnd_t *seed );

int main( void )
{
  long seed = 1;

  for (;;)
    {
      unsigned long x = mcc__rnd( &seed );
      fwrite( &x, 4, 1, stdout );
    }
}

unsigned long mcc__rnd( mcc_rnd_t *seed )
{
  /* Initial random value */
  unsigned long val = ( unsigned long )( &seed ) * ( unsigned long )clock() * ( unsigned long )clock();

  if ( seed )
  {
    if ( *seed == 0 )
      *seed = 1;

    val %= *seed;
    *seed <<= 1;
  }

  return val;
}

And here's dieharder's output so far (called with ./178596 | dieharder -a -g 200):

Code:

#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
stdin_input_raw|  1.47e+06  |2985300269|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.00000000|  FAILED
      diehard_operm5|   0|   1000000|     100|0.00000000|  FAILED
  diehard_rank_32x32|   0|     40000|     100|0.00000000|  FAILED
    diehard_rank_6x8|   0|    100000|     100|0.00000000|  FAILED
   diehard_bitstream|   0|   2097152|     100|0.00000000|  FAILED

It's not looking very promising.

Originally Posted by laserlight

... that produces binary output, or we could say a (pseudo-) random bit generator. Using text input instead may invalidate the results, so more changes to awsdert's program would be needed

EDIT:

If we're interpreting the output correctly, then the test output still states that your RNG output isn't being used. Yet the input filenane is listed, so maybe your RNG output is being used, but somehow in combination with the default PRNG, so the test results still don't show how statistically random your RNG is by itself.

Hmm then I'll do a bit of reading and come back to this after and try the binary output method

Originally Posted by christop

It appears so.

In any case, the manual gives a clear example of the simplest way to test a random-number generator:



(Just replace "cat /dev/urandom" with "./mcc_rnd_die.elf", and make sure the program produces binary output.)

Okay tried that, got this:

Code:

make --no-print-directory dieharder_rnd
gcc -ggdb -Wall -lpthread -DBUILD_FOR_DIEHARDER -o ./mcc_rnd_die.elf mcc_rnd.c
./mcc_rnd_die.elf | dieharder -a -g 200
# stdin_input_raw(): Error: EOF
Compilation finished successfully.

on this code:

Code:

#ifdef BUILD_FOR_DIEHARDER
#define PER_LOOP 200
int main() {
	ulong val;
	for ( int i = 0 ; i < PER_LOOP; i++ ) {
		val = mcc___rnd( NULL );
		fwrite( &val, 4, 1, stdout );
	}
	return 0;
}
#elif

Can you tell me waht I'm doing wrong?

Make it an infinite loop. Dieharder will read as much data as it wants (which is A LOT, or so I've read).

Originally Posted by christop

Make it an infinite loop. Dieharder will read as much data as it wants (which is A LOT, or so I've read).

Okay that seems to be working but its going abysmally slow

Edit: Gonna hop in bath then go to bed and try again 2mw since I'll have some time then

Originally Posted by awsdert

Try without the seed set, ie NULL, also how did you get your terminal to do that? I've tried but it doesn't do that

Better, but worse then LCG (rand()) - you can see "continuous" small blocks at the same color in the final picture...

Code:

$ gcc -O2 -o random random.c
$ ./random > pic.ppm
$ eog pic.ppm

Here I converted the pic.ppm file to png with ImageMagick and reduced the resolution:

Code:

$ convert pic.ppm -resize 256x256 pic.png

This forum don't accept 1024x1024 pictures (file too long) or ppm format.

Why are you trying to create a PRNG from scratch? Usually it is difficult to do it right.
Here's a code I use in a project because I don't like LCG (due to the less random nature of lower bits):

Code:

#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdint.h>

#define _INIT __atrubute__((constructor))

// defined elsewhere...
extern void fatal_error( char *, ... );

/* The Random SEED will be created by SRANDOM */
// FIXME: Ok, this code isn't thread safe!
static uint64_t _seed[2];

/* xorshift128+

   We don't have to worry about the lower bits
   been less random than the upper, in theory. 

   I only need 32 bits random values...
*/
static uint32_t random_xorshift128plus ( void )
{
  uint64_t s0 = _seed[1];
  uint64_t s1 = _seed[0];
  _seed[0] = s0;

  s1 ^= s1 << 23;
  _seed[1] = s1 ^ s0 ^ ( s1 >> 18 ) ^ ( s0 >> 5 );

  return ( _seed[1] + s0 );
}

// NOTE: Intel specific!
#if defined(__i386) || defined(__x86_64)
static uint32_t random_rdrand ( void )
{
  uint32_t r;

  // FIXME: Should try 10 times and call fatal_error() in case of failure,
  //     but this way is faster and I never knwe of RDRAND to fail.
  __asm__ __volatile__ (
    "1: rdrand %0\n"
    "   jnc 1b"
    : "=a" ( r )
  );

  return r;
}
#endif

static void empty_srandom ( void ) {}

static void get_random_seed ( void )
{
  // NOTE: Could use gettimeofday() and use it as seed,
  //       but, this way I'll make sure the seed is random.

  int _fd, r;
  void *p, *endp;

  if ( ( _fd = open ( "/dev/urandom", O_RDONLY ) ) == -1 )
    fatal_error ( "Cannot open /dev/urandom to get initial random seed." );

  /* NOTE: initializes this code "global" _seed var. */
  p = &_seed;
  endp = p + sizeof _seed;

  while ( p < endp )
  {
    if ( ( r = read ( _fd, p, endp - p ) ) == -1 )
      break;

    p += r;
  }

  close ( _fd );

  if ( r == -1 )
    fatal_error ( "Cannot read initial seed from /dev/urandom." );
}

/* The "constructor" below will overide this IF the platform is Intel/AMD and
   if RDRAND is supported. */
void ( *SRANDOM ) ( void ) = get_random_seed;
uint32_t ( *RANDOM ) ( void ) = random_xorshift128plus;

// Intel architecture dependend constructor.
#if defined(__i386) || defined(__x86_64)
#define RDRAND_BIT (1U << 30)

//--- Make sure to use RDRAND instruction if the processor has it.
static void _INIT check_rdrand ( void )
{
  int c;

  __asm__ __volatile__ ( "cpuid" : "=c" ( c ) : "a" ( 1 ) :
#ifdef __i386
                         "ebx", "edx"
#else /* x86_64 */
                         "rbx", "rdx"
#endif
                       );

  if ( c & RDRAND_BIT )
  {
    RANDOM = random_rdrand;
    SRANDOM = empty_srandom;  // RDRAND doesn't need a seed.
  }
}
#endif

Now, SRANDOM() and RANDOM() are used. SRANDOM() to initialize the seed and RANDOM() to get the random values.

Originally Posted by flp1969

Why are you trying to create a PRNG from scratch? Usually it is difficult to do it right.
Here's a code I use in a project because I don't like LCG (due to the less random nature of lower bits):

Code:

#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdint.h>

#define _INIT __atrubute__((constructor))

// defined elsewhere...
extern void fatal_error( char *, ... );

/* The Random SEED will be created by SRANDOM */
// FIXME: Ok, this code isn't thread safe!
static uint64_t _seed[2];

/* xorshift128+

   We don't have to worry about the lower bits
   been less random than the upper, in theory. 

   I only need 32 bits random values...
*/
static uint32_t random_xorshift128plus ( void )
{
  uint64_t s0 = _seed[1];
  uint64_t s1 = _seed[0];
  _seed[0] = s0;

  s1 ^= s1 << 23;
  _seed[1] = s1 ^ s0 ^ ( s1 >> 18 ) ^ ( s0 >> 5 );

  return ( _seed[1] + s0 );
}

// NOTE: Intel specific!
#if defined(__i386) || defined(__x86_64)
static uint32_t random_rdrand ( void )
{
  uint32_t r;

  // FIXME: Should try 10 times and call fatal_error() in case of failure,
  //     but this way is faster and I never knwe of RDRAND to fail.
  __asm__ __volatile__ (
    "1: rdrand %0\n"
    "   jnc 1b"
    : "=a" ( r )
  );

  return r;
}
#endif

static void empty_srandom ( void ) {}

static void get_random_seed ( void )
{
  // NOTE: Could use gettimeofday() and use it as seed,
  //       but, this way I'll make sure the seed is random.

  int _fd, r;
  void *p, *endp;

  if ( ( _fd = open ( "/dev/urandom", O_RDONLY ) ) == -1 )
    fatal_error ( "Cannot open /dev/urandom to get initial random seed." );

  /* NOTE: initializes this code "global" _seed var. */
  p = &_seed;
  endp = p + sizeof _seed;

  while ( p < endp )
  {
    if ( ( r = read ( _fd, p, endp - p ) ) == -1 )
      break;

    p += r;
  }

  close ( _fd );

  if ( r == -1 )
    fatal_error ( "Cannot read initial seed from /dev/urandom." );
}

/* The "constructor" below will overide this IF the platform is Intel/AMD and
   if RDRAND is supported. */
void ( *SRANDOM ) ( void ) = get_random_seed;
uint32_t ( *RANDOM ) ( void ) = random_xorshift128plus;

// Intel architecture dependend constructor.
#if defined(__i386) || defined(__x86_64)
#define RDRAND_BIT (1U << 30)

//--- Make sure to use RDRAND instruction if the processor has it.
static void _INIT check_rdrand ( void )
{
  int c;

  __asm__ __volatile__ ( "cpuid" : "=c" ( c ) : "a" ( 1 ) :
#ifdef __i386
                         "ebx", "edx"
#else /* x86_64 */
                         "rbx", "rdx"
#endif
                       );

  if ( c & RDRAND_BIT )
  {
    RANDOM = random_rdrand;
    SRANDOM = empty_srandom;  // RDRAND doesn't need a seed.
  }
}
#endif

Now, SRANDOM() and RANDOM() are used. SRANDOM() to initialize the seed and RANDOM() to get the random values.

I'm trying to do so because my hobby project mitsy (for the unaware it is my attempt at creating a compiler, end goal is to be portable) is under MIT License and I do not want any code that uses a different license there, I also want it to be thread safe to
avoid issues that I've read about in musl (which now that I think about it could have an implementation I could use, I'll look into that in a minute), also it is going to provide fallback functions for every standard function defined by the relative standards not just in user land but also kernel land, I've so far managed something for the limits file which was something I had been struggling with in a lot of previous hobby projects. Btw any of my code you see with mcc prepended to the front is code that I plan to utilize in mitsy

Er this is giving me errors, gonna copy past a bit from musl and make more back end compatible while I wait on a response:

Code:

/* Credit to flp1969 for this,
https://cboard.cprogramming.com/c-programming/178596-seeded-seedless-random-number.html
*/
ulong mcc_x86_rnd() {
#if defined(__i386) || defined(__x86_64)
	ulong val;
	__asm__ __volatile__ (
		"1: rdrand %0\n"
		"   jnc 1b"
		: "=a" ( val )
	);
	return val;
#endif
}

Well now I'm trying this:

Code:

unsigned musl_temper(unsigned x)
{
	x ^= x>>11;
	x ^= x<<7 & 0x9D2C5680;
	x ^= x<<15 & 0xEFC60000;
	x ^= x>>18;
	return x;
}

#define musl_rand_r(seed) \
	(musl_temper((seed) = (seed) * 1103515245 + 12345)/2)

#define musl_srand(seed,s) ((seed) = (s) - 1)
#define musl_rand(seed) \
	(((seed) = 6364136223846793005ULL*(seed) + 1) \
	>> (((sizeof(seed) / 2) * CHAR_BIT)+1))

/* Credit to flp1969 for this,
https://cboard.cprogramming.com/c-programming/178596-seeded-seedless-random-number.html
*/
uint_least64_t mcc_x86_rnd() {
	uint_least64_t val;
#if 1
	struct timeval was;
	gettimeofday(&was,NULL);
	val = was.tv_usec * (clock() * clock());
#elif defined(__i386) || defined(__x86_64)
	__asm__ __volatile__ (
		"1: rdrand %0\n"
		"   jnc 1b"
		: "=a" ( val )
	);
#endif
	return val;
}
ulong mcc___rnd( mcc_rnd_t *seed ) {
	/* Initial random value */
	ulong _seed = mcc_x86_rnd(), val;
	val = musl_rand_r(_seed);
	return musl_rand(val);
}

1st 2 have passed, still waiting on rest

Originally Posted by flp1969

Better, but worse then LCG (rand()) - you can see "continuous" small blocks at the same color in the final picture...

Code:

$ gcc -O2 -o random random.c
$ ./random > pic.ppm
$ eog pic.ppm

Here I converted the pic.ppm file to png with ImageMagick and reduced the resolution:

Code:

$ convert pic.ppm -resize 256x256 pic.png

This forum don't accept 1024x1024 pictures (file too long) or ppm format.

Thanks, finally got round to trying it as I was tired of trying to pass the failed/weak results of some of the tests, was taking too long so I tried this which is faster but eog reports an incorrect byte initial byte:

Code:

gcc -ggdb -Wall -lpthread -DDRAW_NOISE -o ./mcc_rnd_noisy.elf mcc_rnd.c
./mcc_rnd_noisy.elf > pic.ppm
eog pic.ppm
Compilation finished successfully.

Did I do something wrong here?

Code:

#elif defined( DRAW_NOISE )
#define PER_LOOP 1024
#define rand2rgb(n) \
  ( ( int ) ( ( (n) * 16777215.0L ) / ULONG_MAX ) )
int main() {
	int x, y;
	uint val;
	for ( x = 0; x < PER_LOOP; ++x ) {
		for ( y = 0; y < PER_LOOP; ++y ) {
			val = rand2rgb(mcc___rnd( NULL ));
			fwrite( &val, 3, 1, stdout );
		}
	}
	return 0;
}
#else

Post #43: You need to verify if your processor supports RDRAND. That's why I did use that "constructor" attribute extension to GCC to check through CPUID.