Pseudo Random Number Generator for Low Quantities

I use the following code for a seeded pseudo random number generator, and it has worked well for many years.

It is called millions of times per batch in an optimisation algorithm and because of its simplicity it is very fast and of course repeatable.

However, for very low batch quantities i.e under 10 its deficiences are highlighted.

Can anyone suggest a better solution with small code for low batch quantities.

Code:

---

int randomgen( int start, int count )
{
/*
This generates a pseudo random number generator which can be reproduced at
will.
*/

SEED = ( ( 0XA3ED * SEED ) + 0X1D31 ) & 0X7FFF;

return ( abs( ( SEED % ( count - start + 1 ) + start ) ) );
}

---

What type is SEED?

What's the initial value of SEED.

For our amusement, what are the actual "deficiencies" you're worried about?

Is it just the first 10 which are an issue, or any consecutive run of 10 numbers anywhere in the repeating sequence?

PRNG's based on Linear Congruency are less random if you take the lower bits only (see "The Art of Computer Programming", from Knuth). So, one way to do it is to take the upper bits, but to do this you need to know the range of rand() result. I think this should do it (using GCC):

Code:

---

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

int main(void)
{
  int bits;
  int i, n;

  // Some implementations use RAND_MAX with less then 31 bits
  // but all I've seen uses all trailling bits as 1. This will calculate
  // the number of bits of RAND_MAX.
  bits = ( 8 * sizeof bits ) - __builtin_clz( RAND_MAX );

  // An attempt to "randomize" the seed.
  srand( time(NULL) );

  n = 8;  // used to format the output.

  // Generates 100 rolls of a dice (D6).
  for ( i = 0; i < 100; i++ )
  {
    if ( ! n )
    {
      putchar('\n');
      n = 8;
    }

    // Roll the D6 dice...
    //
    // Use the trailling 3 valid superior bits (inferior bits
    // are 'less' random - see "The Art of Computer Programming", Knuth, vol 2).
    printf( "%d\t", ( ( (unsigned int)rand() >> (bits - 3) ) % 6 ) + 1 );

    --n;
  }

  putchar('\n');
}

---

This hack isn't perfect! 6 and 7 will, calculated after the shift (but before adding 1), be translated to 0 and 1, so this 2 values can appear more frequently than they should (bad distribution)... In this case, perhaps, a simple ((rand() % 6)+1) will do.

SEED is a global.

It is externally set by a routine that is itself repeatable, and is used in this way to offset any bias that the initial SEED value might have.

However, when I am constantly sampling within a small range, the sampling results are not as uniform as I would like and my optimisation may have a unique best result which I could miss. Normally, I am sampling with a range measured in hundreds or thousands, and there are no problems, as there are multiple optimal solutions.

I have always understood that this was not a perfect routine, but it tested better than rand() and rands() at the time, which is why I used it.

Hopes this makes it clearer.

Then do as flp1969 suggests, and sample the most significant bits.

@johnggold, Your routine is the same as srand()/rand() - it is LCG as well. You are just using different parameters than the C standard library (which varies from compiler to compiler). If you are compiling for Intel/AMD processors, you can use RDRAND instruction to get more "random" values without the need for a 'seed'. But this instruction is slower than the average LCG implementation.

There are other PRNGs available: xorshift128+, mersene twister, ... But I think you should use rand() [or the "intrinsic" function _rdrandNN_step() function, in immintrin.h - but first, check your processor features via CPUID]. Of course, if your code is generic and must be compiled in various architectures, using RDRAND is problematic...

The problem with tweaking the LCG as you did is that it can have a narrower range, can wrap around faster and so on... Some analysis (and they are not easy!) are required to make sure your custum LCG really works.

I do have to work on different platforms and always generate the same results.

Use an array of numbers.

Its very easy to analyse. I simply run my optimisation routine and store the start, count and SEED values in CSV format, then good old Excel does the analysis for me.

That's how I got to to see the problem in the first place.

I can't use seedless, as there is no guarantee of repeatable results, which I depend on as the same run may be repeated weeks apart and has to generate the identical result.