Thread: Pseudo Random Number Generator for Low Quantities

  1. #1
    Registered User
    Join Date
    Aug 2010
    Location
    England
    Posts
    90

    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 ) ) );
    }
    Last edited by Salem; 07-30-2019 at 12:10 AM. Reason: Missed code tags!
    Never re-write code unless the user benefits

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    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.
    Last edited by flp1969; 07-30-2019 at 05:28 AM.

  4. #4
    Registered User
    Join Date
    Aug 2010
    Location
    England
    Posts
    90
    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.
    Never re-write code unless the user benefits

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Then do as flp1969 suggests, and sample the most significant bits.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    @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.

  7. #7
    Registered User
    Join Date
    Aug 2010
    Location
    England
    Posts
    90
    I do have to work on different platforms and always generate the same results.
    Never re-write code unless the user benefits

  8. #8
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Use an array of numbers.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  9. #9
    Registered User
    Join Date
    Aug 2010
    Location
    England
    Posts
    90
    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.
    Never re-write code unless the user benefits

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-08-2017, 06:48 AM
  2. pseudo-random number generator problem
    By clarkk in forum C++ Programming
    Replies: 2
    Last Post: 06-27-2011, 09:31 AM
  3. need a random number generator thats not compleatly random
    By thedodgeruk in forum C++ Programming
    Replies: 1
    Last Post: 06-05-2011, 06:48 AM
  4. Replies: 2
    Last Post: 08-13-2008, 08:02 AM
  5. Independent streams of pseudo random number generator
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-15-2001, 05:32 AM

Tags for this Thread