Thread: Seeded/Seedless random number

  1. #61
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    Well just finished running the version that was using NULL on the seed under dieharder (results attached), while not perfect it does seem to pass roughly 50% of the tests which is good enough for now, especially as it is a seedless run. As stated before security software should be able to use this just fine, although I wouldn't trust it if it uses just this.

    Incidentally I found a way to not bother remembering macros:
    Code:
    #define MCC___DEF(NAME) (NAME)
    #define MCC__DEF(NAME) MCC___DEF(NAME)
    #define MCC_DEF(NAME) \
    	(MCC__DEF(__##NAME##__) | MCC__DEF(__##NAME)\
    	| MCC__DEF(_##NAME##_) | MCC__DEF(_##NAME)\
    	| MCC__DEF(NAME))
    #define MCC____RND(V) (V ^ (V * (V << (V & 0xF))))
    uint mcc____rnd() {
    #if MCC_DEF(X86) | MCC_DEF(X86_64) | MCC_DEF(x86) | MCC_DEF(x86_64)
    	uint a, b;
    	asm volatile("rdtsc":"=a"(a),"=b"(b));
    	return MCC____RND(a);
    #else
    	struct timespec ts;
    	clock_gettime(CLOCK_REALTIME,&ts);
    	return MCC____RND(ts.tv_nsec);
    #endif
    }
    Edit: Because some peops will be curios...
    Code:
    gcc -ggdb -Wall -lpthread -DQUICKY_RND -o ./mcc_rnd_quicky.elf mcc_rnd.c
    ./mcc_rnd_quicky.elf
    mcc___rnd() took 0 seconds and 198353 nanoseconds
    rand_r() took 0 seconds and 116349 nanoseconds
    Compilation finished successfully.
    Code:
    #define PER_LOOP 10000
    int main() {
    	struct timespec init, stop;
    	uint seed = time(NULL), i;
    	clock_gettime(CLOCK_REALTIME,&init);
    	for ( i = 0; i < PER_LOOP; ++i ) {
    		(void)mcc____rnd();
    	}
    	clock_gettime(CLOCK_REALTIME,&stop);
    	printf( "mcc___rnd() took %lld seconds and %lld nanoseconds\n",
    		(long long)(stop.tv_sec - init.tv_sec),
    		(long long)(stop.tv_nsec - init.tv_nsec) );
    	clock_gettime(CLOCK_REALTIME,&init);
    	for ( i = 0; i < PER_LOOP; ++i ) {
    		(void)rand_r(&seed);
    	}
    	clock_gettime(CLOCK_REALTIME,&stop);
    	printf( "rand_r() took %lld seconds and %lld nanoseconds\n",
    		(long long)(stop.tv_sec - init.tv_sec),
    		(long long)(stop.tv_nsec - init.tv_nsec) );
    	return 0;
    }
    Edit 2: I tried removing the loop out of curiosity, was surprised to get consistent results looking like this:
    Code:
    gcc -ggdb -Wall -lpthread -DQUICKY_RND -o ./mcc_rnd_quicky.elf mcc_rnd.c
    mcc_rnd.c: In function ‘main’:
    mcc_rnd.c:101:26: warning: unused variable ‘i’ [-Wunused-variable]
      101 |  uint seed = time(NULL), i;
          |                          ^
    ./mcc_rnd_quicky.elf
    mcc___rnd() took 0 seconds and 182 nanoseconds
    rand_r() took 0 seconds and 550 nanoseconds
    Compilation finished successfully.
    Attached Files Attached Files
    Last edited by awsdert; 01-12-2020 at 06:33 PM.

  2. #62
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    Why not use Mersenne Twister? Its behaviour is known, and mathematically proven, and it's easy to implement. The paper and reference implementation can be found here: Mersenne Twister: A random number generator (since 1997/10)

    An advantage (shared with other PRNGs) is that you can give it a fixed seed so you know the sequence will be the same for the given seed; useful for debugging.

  3. #63
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    Quote Originally Posted by Hodor View Post
    Why not use Mersenne Twister? Its behaviour is known, and mathematically proven, and it's easy to implement. The paper and reference implementation can be found here: Mersenne Twister: A random number generator (since 1997/10)

    An advantage (shared with other PRNGs) is that you can give it a fixed seed so you know the sequence will be the same for the given seed; useful for debugging.
    Isn't the point of a random number generator supposed to be ooh I dunno not fixed?

  4. #64
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,926
    Quote Originally Posted by awsdert
    Isn't the point of a random number generator supposed to be ooh I dunno not fixed?
    No, that's not necessarily the point: while "true randomness" typically cannot have sequences reproduced on demand other than by saving the sequences to replay them, there's statistical randomness and randomness that is unpredictable, and these don't require that the sequence cannot be repeated on demand given only a seed. If you're running a simulation, or as Hodor said, debugging, being able to repeat the pseudorandom sequence on demand is useful.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #65
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    Quote Originally Posted by laserlight View Post
    No, that's not necessarily the point: while "true randomness" typically cannot have sequences reproduced on demand other than by saving the sequences to replay them, there's statistical randomness and randomness that is unpredictable, and these don't require that the sequence cannot be repeated on demand given only a seed. If you're running a simulation, or as Hodor said, debugging, being able to repeat the pseudorandom sequence on demand is useful.
    Well as you'll note I used a macro on this last version so I can always maintain only slightly different functions and the developer using them can simply use a macro to decide if they want the seeded version, something like this:
    Code:
    #ifdef _DEBUG
    #define MCC_RND( VAL ) mcc_rnd_r( &VAL )
    #else
    #define MCC_RND( VAL ) VAL = mcc_rnd()
    #endif

  6. #66
    Registered User
    Join Date
    Feb 2019
    Posts
    722
    Quote Originally Posted by awsdert View Post
    Thanks, I tried reading through the 1st one but used so many math symbols that it would take too long for me to understand it, I do wish they had thought to include simple pseudo code as well,
    What suprises me is that you are dealing with mathematical problems (floating point, random numbers), but refuse to learn the proper mathematics...

  7. #67
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    Quote Originally Posted by flp1969 View Post
    What suprises me is that you are dealing with mathematical problems (floating point, random numbers), but refuse to learn the proper mathematics...
    Nah its not that, I can read scripts easily enough since they're in nice simple lines but math symbols go all over the place and there are some I'm not even familiar with, I only got a B in my GCSEs and wasn't really interested in studying it in the last 14 odd years, but on that note do you have a good reference to look through for studying each symbol? (preferably list format with the name of each symbol next to them and a basic description, I can google from there once I know the name and find the description insufficient for learning about it)

  8. #68
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    Quote Originally Posted by awsdert View Post
    Nah its not that, I can read scripts easily enough since they're in nice simple lines but math symbols go all over the place and there are some I'm not even familiar with, I only got a B in my GCSEs and wasn't really interested in studying it in the last 14 odd years, but on that note do you have a good reference to look through for studying each symbol? (preferably list format with the name of each symbol next to them and a basic description, I can google from there once I know the name and find the description insufficient for learning about it)
    Knuth gives pseudocode or code in the MIX or MMIX language (which both have assemblers... MIX or MMIX depends on what revision of his books you look at) or both. So volume 2 and the stuff about random numbers has lots of mathematics but lots of pseudocode as well (all the volumes do). The Mersenne twister algorithm, linked to above, even uses a LCG random number generator to set its initial state from a given seed and references Knuth. There's not really even much, if any, mathematics to understand (unless you want to). If I see code that uses some kind of weird unpublished random (or pseudo-random) number generator all sorts of alarm bells go off and I'd steer clear of it. I can understand the mathematics for most PRNGs but even if I can't (there are some that are just beyond my ability) I'd rather see code using algorithms written in peer-reviewed journals; especially if I need something that approaches anything useful for secure cryptography because I either don't have the ability to prove these things myself or I don't have the time.

    Mersenne twister is fast but not as fast as your code or a LCG PRNG. Pretty close though and it has better randomness than rand() (side note: does the C standard specify what algorithm rand() must use?)

    Edit: there was a PRNG algorithm published in Doctor Dobb's Journal in about 1995 based on the Fibonacci sequence that was good for CPUs at the time that didn't have FPUs. Its period was terrible but it was easy to implement in ASM and good enough for games. I can't find a reference to it but I don't think it was a "classical" LCG, although it might have been (can't say for sure because I cannot find the article)
    Last edited by Hodor; 01-13-2020 at 06:03 AM.

  9. #69
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,926
    Quote Originally Posted by Hodor
    does the C standard specify what algorithm rand() must use?
    No, except that it does require a PRNG and imposes some minimum requirements on the PRNG like a minimum RAND_MAX.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #70
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    Quote Originally Posted by laserlight View Post
    No, except that it does require a PRNG and imposes some minimum requirements on the PRNG like a minimum RAND_MAX.
    Thanks. That's what I thought but wasn't sure

  11. #71
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    I, erm, think I fixed the time based generator to be shall we say WAY more secure than before, I was experimenting hoping to get a few more passed and on my current attempt (dieharder is still running, at lagged sum tests right now) a LOT more were passing than I expected with the simple change I made (also change a few names because I found this method only works for counter based values, got a different one for seeds).
    My current experimental code
    Code:
    #define MCC_RND(TICK) (((TICK) ^ ((TICK) * ((TICK) << ((TICK) & 0xF)))) + ((TICK) % 123))
    #define MCC_RNG_SEED(SEED) (((SEED) * ((SEED) % 4321)) + ((SEED) % 12345))
    #define MCC_RNG_(SEED) ((MCC_RNG_SEED(SEED) ^ (SEED)))
    #define MCC_RNG(SEED) MCC_RND(MCC_RNG_(SEED))
    
    #if 0//MCC_DEF(X86) | MCC_DEF(X86_64) | MCC_DEF(x86) | MCC_DEF(x86_64)
    #define mcc_get_ticks(TS) \
    	do { asm volatile("rdtsc":\
    		"=" #TS ".tv_sec" (TS.tv_sec),\
    		"=" #TS ".tv_nsec" (TS.tv_nsec));\
    	} while (0)
    #else
    #define mcc_get_ticks(TS) clock_gettime(CLOCK_REALTIME,&TS);
    #endif
    
    #define mcc_random(V,TS) \
    	do { mcc_init_seed(TS); \
    	V = MCC_RND(TS.tv_nsec ^ V); } while (0)
    
    uint mcc_rng() {
    	struct timespec ts;
    	mcc_get_ticks(ts);
    	return MCC_RNG(ts.tv_nsec + (ulong)&ts);
    }
    uint mcc_rng_r( uint *seed ) {
    	return (*seed = MCC_RNG(*seed));
    }
    long mcc_random_between( uint *seed, long min, long max ) {
    	/* Initial random value */
    	long val = (*seed = MCC_RNG( *seed ));
    	if ( val < min ) return (min != 0) ? val % min : -(val & 1);
    	if ( val > max ) return (max != 0) ? val % max : (val & 1);
    	return val;
    }
    Edit: Gonna go out for breakfast, dieharder should be done by the time I come back and I can then upload the results
    Last edited by awsdert; 01-14-2020 at 04:21 AM.

  12. #72
    Registered User
    Join Date
    Feb 2019
    Posts
    722
    Why not keep this simple. You are not, obviously, interested in a cryptographically secure RNG, so LCG, Mersene Twister, Xorshift128 or any other PRNG is suitable. A thread safe LCG is easy enough to be implemented. For example:
    Code:
    unsigned int myrand( unsigned int *state )
    {
      unsigned int r;
    
      /* LCG: Stolen from glibc (changed to unsigned int). */
      r = ( *state * 1103515245 ) + 12345;
      *state = r;
    
      return r;
    }
    This "state" is your initial seed and the values 1103515245 and 12345 are good enough for an LCG...

    If you want to use RDRAND for Intel/AMD processors, you can do something like this:
    Code:
    /* rand.c */
    #include <cpuid.h>
    
    /* Interface pointers to proper functions. */
    void (*SRAND)( unsigned int *, unsigned int );
    unsigned int (*RAND)( unsigned int * );
    
    /* Because RDRAND don't need a seed! */
    static void empty( unsigned int *state, unsigned int seed ) {}
    
    /* mysrand() & myrand() are thread safe. You need only to provide
       A pointer to the initial seed */
    static void mysrand( unsigned int *state, unsigned int seed )
    {
      *state = seed;
    }
    
    static unsigned int myrand( unsigned int *state )
    {
      unsigned int r;
    
      /* LCG: Stolen from glibc (changed to unsigned int). */
      r = ( *state * 1103515245 ) + 12345;
      *state = r;
    
      return r;
    }
    
    #if defined(__i386) || defined(__x86_64)
    static unsigned int rdrand( unsigned int *state )
    /* state pointer is ignored! */
    {
      unsigned int r;
    
      /* Need to save EBX/RBX because of SysV calling convention. */
      __asm__ __volatile__(
        "1:\n\t"
        "  rdrand %0\n\t"
        "  jnc 1b" : "=c" (r) ::
      #ifdef __i386
        "ebx"
      #else
        "rbx"
      #endif
      );
    
      // NOTE: There is an intrinsic called _rdrand32_step(), but it created worse code
      // than this one...
    
      return r;
    }
    #endif
    
    /* The default behavior is to use LCG, unless we are dealing with
       Intel/AMD processors which have RDRAND instruction. */
    void (*SRAND)( unsigned int *, unsigned int ) = mysrand;
    unsigned int (*RAND)( unsigned int * ) = myrand;
    
    #if defined(__i386) || defined(__x86_64)
    /* You can change this to a simple RAND_init() function which must be called before any
       use of SRAND() or RAND(). I prefer to use the GCC extension. */
    static void __attribute__((constructor)) RAND_ctor( void )
    {
      int a, b, c, d;
    
      __cpuid( 1, a, b, c, d ); // Yep, this is an intrinsic @ cpuid.h.
                                // You can do this in asm, if you wish...
    
      if ( c & bit_RDRND )      // bit_RDRND also defined in cpuid.h
      {
        SRAND = empty;
        RAND = rdrand;
      }  
    }
    #endif
    A small test code:
    Code:
    /* test.c */
    #include <stdio.h>
    #include <time.h>
    #include <limits.h>
    
    #define scale2rgb(n) \
      ( unsigned int ) ( ( (n) * 16777215.0 ) / UINT_MAX )
    
    extern void (*SRAND)( unsigned int *, unsigned int );
    extern unsigned int (*RAND)( unsigned int * );
    
    int main ( void )
    {
      int i;
      unsigned int rnd_state, r;
    
      SRAND( &rnd_state, time(NULL) );
    
      puts("P6\n1024 1024\n255");
      for ( i = 0; i < 1024*1024; i++ )
      {
        r = scale2rgb(RAND(&rnd_state));
        fwrite( &r, 3, 1, stdout );
      }
    }
    Compiling and linking:
    Code:
    $ cc -O2 -c rand.c test.c
    $ cc -O2 -s -o test test.o rand.o
    $ ./test > pic.ppm
    Last edited by flp1969; 01-14-2020 at 05:41 AM.

  13. #73
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,048
    Well here's the results, just 2 failures out of the lot, I can live with that for now, I'll switch back to my other project for a while and fix an allocation issue I just thought of in it (related to the custom allocator and it's realloc part)
    Attached Files Attached Files

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 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
  2. Replies: 5
    Last Post: 10-05-2009, 10:21 AM
  3. Replies: 2
    Last Post: 12-25-2003, 01:31 AM
  4. random number between negative and positive number
    By anomaly in forum C++ Programming
    Replies: 6
    Last Post: 12-06-2003, 08:40 AM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM

Tags for this Thread