Thread: Seeded/Seedless random number

  1. #46
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    PPM (binary) Graphics format:

    P6
    width height
    max-value-per-component
    <binary data> (RR GG BB RR GG BB ...)

    The first 3 lines are strings

    Example:

    P6
    1024 1024
    255
    FF FF FF 80 23 4D ... (binary)

    You must have 1024*1024 bytes in binary to match the width and height.

    You can change P6 to P3 and write RR GG BB in decimal string:

    P3
    1024 1024
    255
    255 255 255
    128 34 77
    ... (strings)

    See netpbm format

  2. #47
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    PPM (binary) Graphics format:

    P6
    width height
    max-value-per-component
    <binary data> (RR GG BB RR GG BB ...)

    The first 3 lines are strings

    Example:

    P6
    1024 1024
    255
    FF FF FF 80 23 4D ... (binary)

    You must have 1024*1024 bytes in binary to match the width and height.

    You can change P6 to P3 and write RR GG BB in decimal string:

    P3
    1024 1024
    255
    255 255 255
    128 34 77
    ... (strings)

    See [utl=https://en.wikipedia.org/wiki/Netpbm_format]netpbm format[/url]
    thank you that worked
    Used this:
    Code:
    uint mcc___rnd( uint *seed ) {
    	/* Initial random value */
    	uint _seed;
    	char tseed[10] = "946853721";
    	struct timespec ts;
    	clock_gettime(CLOCK_REALTIME,&ts);
    	_seed = ((ulong)&_seed + ts.tv_nsec + (ts.tv_nsec << 1)) *
    		tseed[ts.tv_nsec%10];
    	if ( !seed ) seed = &_seed;
    	return _seed + (tseed[*seed%10] * tseed[_seed%10] * _seed);
    }
    Gave me noisy result (with some slight tears) despite it failing the dieharder tests
    Code:
    #ifdef HARDY_RND
    int main() {
    	uint val;
    	while ( 1 ) {
    		val = mcc___rnd( NULL );
    		fwrite( &val, 4, 1, stdout );
    	}
    	return 0;
    }
    #elif defined( NOISY_RND )
    #define PER_LOOP 1024
    long double rand2rgb( uint n ) {
    	long double f = n;
    	return (f * 16777215.0L);
    }
    int main() {
    	int x, y;
    	uint val;
    	char *header = "P6\n1024 1024\n255\n";
    	fwrite(header,strlen(header),1,stdout);
    	for ( x = 0; x < PER_LOOP; ++x ) {
    		for ( y = 0; y < PER_LOOP; ++y ) {
    			val = mcc___rnd( NULL );
    			fwrite( &val, 4, 1, stdout );
    		}
    	}
    	return 0;
    }
    #else
    Gotts leave for work now so don't have time to look through posts for how to downsize image for uploading

  3. #48
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Quote Originally Posted by awsdert View Post
    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
    The rand() function is ISO 9989 standard, not subject to any licensing (maybe ISO/IEC)... And, as far as I know, xorshift128+ isn't subject to licensing as well...

    Quote Originally Posted by awsdert View Post
    , 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)
    If you want to avoid licensing, using MUSL it's not going to help you... For thread safety, there is rand_r(), where you pass the seed to the function:

    Code:
    int rand_r( unsigned int *seedp);
    Quote Originally Posted by awsdert View Post
    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
    Ahhhh... then you have a freestading (not hosted) project (kernel).... ok, it is a good idea to provide low level functions yourself. But, seems to me, yours are too much complex for a kernel... I would stick to LCG/xorshift128+ and/or RDRAND because they are fast and small.

    []s
    Fred

  4. #49
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Ahhh... BTW... if your processor uses Big Endian, I think it must be wise to do something like this. PPM format expects RR GG BB in that order:

    Code:
    ...
    int t;
    val = t = rand2rgb( func() );
    
    #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    t = __builtin_bswap32( t );
    #endif
    
    fwrite( &t, 3, 1, stdout );
    ...

  5. #50
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    Ahhh... BTW... if your processor uses Big Endian, I think it must be wise to do something like this. PPM format expects RR GG BB in that order:

    Code:
    ...
    int t;
    val = t = rand2rgb( func() );
    
    #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    t = __builtin_bswap32( t );
    #endif
    
    fwrite( &t, 3, 1, stdout );
    ...
    nah my cpu is little endian, I think it was an AMD FX Quad Core, old but still doing the job, thinking about investing in an AMD Zen bundle after replacing my washing machine which is surely on its way out

  6. #51
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Quote Originally Posted by awsdert View Post
    nah my cpu is little endian, I think it was an AMD FX Quad Core, old but still doing the job, thinking about investing in an AMD Zen bundle after replacing my washing machine which is surely on its way out
    One more reason to check if your processor supports RDRAND (AMD FX, maybe not!)... I recomend you do the same I did before: Declare 2 pointers to functions and initialize them after calling an "init" funcion (don't need to have the 'constructor' attribute)...

  7. #52
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    One more reason to check if your processor supports RDRAND (AMD FX, maybe not!)... I recomend you do the same I did before: Declare 2 pointers to functions and initialize them after calling an "init" funcion (don't need to have the 'constructor' attribute)...
    Yeah I removed that for now, better a slow but working version than a fast but hit and miss version, I'll try that when I can look at the macros and instructions properly on monday

  8. #53
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Quote Originally Posted by awsdert View Post
    Yeah I removed that for now, better a slow but working version than a fast but hit and miss version, I'll try that when I can look at the macros and instructions properly on monday
    Why "miss"? Example code to use RDRAND if available and to make sure will always return a random valid value:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    
    /* Test if RDRAND is available via CPUID[EAX=1]:ECX:30 */
    int rdrand_avail( void )
    {
    #if defined(__i386) || defined(__x86_64)
      int avail;
    
      __asm__ __volatile__ (
        "cpuid" : "=c" ( avail ) : "a" (1) :
    #ifdef __i386
        "ebx", "edx"
    #else
        "rbx", "rdx"
    #endif
      );
    
      return !!( avail & ( 1U << 30 ) );
    #else
      return 0;
    #endif  
    }
    
    /* Stolen from Intel intrinsics (immintrin.h). Updates *step with CF.
       *step = 1 means we have a random value, otherwise,
       we need to try again. */
    static uint32_t rdrand_step( int *step )
    {
      uint32_t r;
    
      __asm__ __volatile__ (
        "xorl %%ecx,%%ecx\n\t"
        "rdrand %0\n\t"
        "setc %%cl"
        : "=a" (r), "=c" (*step)
      );
    
      return r;
    }
    
    uint32_t rdrand( void )
    {
      uint32_t r;
      int count, step;
    
      /* To avoid the possibility to get 0,
         Intel recomends to try to read 10 times.
         Accordingly to the documentation the odds to
         NOT get another 0 after this is "astronomical". */
      count = 10;
      while ( count-- )
      {
        r = rdrand_step( &step );
        if ( step )
          break;
      }
    
      // We tried 10 times and all failed (unlikely),
      // show an error and abort!
      if ( ! count )
      {
        fputs( "ERROR: cannot get random value from RDRAND instruction.\n", stderr );
        abort();
      }
    
      return r;
    }
    
    int main( void )
    {
      if ( ! rdrand_avail() )
      {
        // Here we could inicialize pointers to funtions to
        // use PRNGs in case RDRAND isn't available. For example:
        //
        //  /* external identifiers: */
        //  void (*SRAND)( uint32_t );
        //  uint32_t (*RAND)( void );
        //
        //  static void do_norhing( uint32_t s ) { }
        //
        //  if ( rdrand_avail() ) { SRAND = do_nothing; RAND = rdrand; }
        //  else                  { SRAND = srand; RAND = rand; }
        //
        // Now we can use SRAND() and RAND() as srand() and rand(),
        // being sure the correct vesion will be called.
    
        fputs( "ERROR: RDRAND not available for this processor.\n", stderr );
        return EXIT_FAILURE;
      }
    
      printf( "%u\n", rdrand() );
    
      return EXIT_SUCCESS;
    }

  9. #54
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    Why "miss"? Example code to use RDRAND if available and to make sure will always return a random valid value:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    
    /* Test if RDRAND is available via CPUID[EAX=1]:ECX:30 */
    int rdrand_avail( void )
    {
    #if defined(__i386) || defined(__x86_64)
      int avail;
    
      __asm__ __volatile__ (
        "cpuid" : "=c" ( avail ) : "a" (1) :
    #ifdef __i386
        "ebx", "edx"
    #else
        "rbx", "rdx"
    #endif
      );
    
      return !!( avail & ( 1U << 30 ) );
    #else
      return 0;
    #endif  
    }
    
    /* Stolen from Intel intrinsics (immintrin.h). Updates *step with CF.
       *step = 1 means we have a random value, otherwise,
       we need to try again. */
    static uint32_t rdrand_step( int *step )
    {
      uint32_t r;
    
      __asm__ __volatile__ (
        "xorl %%ecx,%%ecx\n\t"
        "rdrand %0\n\t"
        "setc %%cl"
        : "=a" (r), "=c" (*step)
      );
    
      return r;
    }
    
    uint32_t rdrand( void )
    {
      uint32_t r;
      int count, step;
    
      /* To avoid the possibility to get 0,
         Intel recomends to try to read 10 times.
         Accordingly to the documentation the odds to
         NOT get another 0 after this is "astronomical". */
      count = 10;
      while ( count-- )
      {
        r = rdrand_step( &step );
        if ( step )
          break;
      }
    
      // We tried 10 times and all failed (unlikely),
      // show an error and abort!
      if ( ! count )
      {
        fputs( "ERROR: cannot get random value from RDRAND instruction.\n", stderr );
        abort();
      }
    
      return r;
    }
    
    int main( void )
    {
      if ( ! rdrand_avail() )
      {
        // Here we could inicialize pointers to funtions to
        // use PRNGs in case RDRAND isn't available. For example:
        //
        //  /* external identifiers: */
        //  void (*SRAND)( uint32_t );
        //  uint32_t (*RAND)( void );
        //
        //  static void do_norhing( uint32_t s ) { }
        //
        //  if ( rdrand_avail() ) { SRAND = do_nothing; RAND = rdrand; }
        //  else                  { SRAND = srand; RAND = rand; }
        //
        // Now we can use SRAND() and RAND() as srand() and rand(),
        // being sure the correct vesion will be called.
    
        fputs( "ERROR: RDRAND not available for this processor.\n", stderr );
        return EXIT_FAILURE;
      }
    
      printf( "%u\n", rdrand() );
    
      return EXIT_SUCCESS;
    }
    Miss as in if incorrectly detected causes the process to crash

  10. #55
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Not sticking around tonight but here's the 256x256 version of what I get without a seed plus the original 1024x1024 pic
    pic.ppm - Google Drive
    Attached Images Attached Images Seeded/Seedless random number-pic-png 

  11. #56
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Quote Originally Posted by awsdert View Post
    Not sticking around tonight but here's the 256x256 version of what I get without a seed plus the original 1024x1024 pic
    pic.ppm - Google Drive
    Compare this to the "noise" you get with the LCG (rand)... You'll notice yours has some "regular" spots (not as random as it should be)...

    As I said... this is better than before, but rand() is better.

  12. #57
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    Compare this to the "noise" you get with the LCG (rand)... You'll notice yours has some "regular" spots (not as random as it should be)...

    As I said... this is better than before, but rand() is better.
    Quote Originally Posted by awsdert View Post
    Gave me noisy result (with some slight tears) despite it failing the dieharder tests
    Yeah I noticed , incidentally before that I had accidentally tried with a hard-coded value that I just randomly hit some keys on my numpad for and I didn't notice any tears on that so I think for now that will do and later I'll work on making it faster since for time being this won't be operating in kernel land anyways

  13. #58
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    The rand() function is ISO 9989 standard, not subject to any licensing (maybe ISO/IEC)... And, as far as I know, xorshift128+ isn't subject to licensing as well...
    Noted, I will keep that in mind for future reference
    Quote Originally Posted by flp1969 View Post
    If you want to avoid licensing, using MUSL it's not going to help you...
    Comparison of C/POSIX standard library implementations for Linux
    Since musl is under MIT License also it is not an issue to include it's code so long as I reference the source
    Quote Originally Posted by flp1969 View Post
    For thread safety, there is rand_r(), where you pass the seed to the function:

    Code:
    int rand_r( unsigned int *seedp);
    Thank you, used it to compare results when improving the function
    Quote Originally Posted by flp1969 View Post
    Ahhhh... then you have a freestanding (not hosted) project (kernel)
    Almost, it simply plugs in what is missing before it passes on the main part of the project, so if for example the standard headers were to include the mitsy headers (which is what it's own implementation would do if mitsy fell back to it) then fallback functions are need for code assuming those functions exist to work properly, there are defines to tell it to not include the standard headers and just define the library by itself (which would then clash with actual headers if they were included along side)

    Been meaning to reply to those before but phone was not suitable and forgot by the time I had a chance, on another note I managed to fix the code to be faster and more random after taking a leaf out of musl's book and using xor combined with a shift, at first I used musl_temper (what I renamed temper to when using in this closed environment test project) and sure enough that work and now I use a smaller faster variation of that, now it looks like this:
    Code:
    uint mcc___rnd( uint *seed ) {
    	/* Initial random value */
    	uint _seed;
    	char tseed[10] = "9462537";
    	struct timespec ts;
    	clock_gettime(CLOCK_REALTIME,&ts);
    	_seed = ((ulong)&ts * ts.tv_nsec);
    	_seed ^= _seed >> _seed & 0xF;
    	if ( !seed ) seed = &_seed;
    	return _seed + (tseed[*seed&7u] * tseed[_seed&7u] * _seed);
    }
    noisy.ppm - Google Drive
    Gotta go to work now so won't respond often or at all until after gospel later tonight
    Attached Images Attached Images Seeded/Seedless random number-noisy-png 

  14. #59
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Good books about random number generators:

    Luc Devroye - Non Uniform Random Variates

    and, of course, volume 2 of the art of computer programming by Donald E. Knuth

    Donald E. Knuth - The Art of Computer Programming (all)

  15. #60
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,032
    Quote Originally Posted by flp1969 View Post
    Good books about random number generators:

    Luc Devroye - Non Uniform Random Variates

    and, of course, volume 2 of the art of computer programming by Donald E. Knuth

    Donald E. Knuth - The Art of Computer Programming (all)
    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, anyways I'll put that on back burner for now, in mean time I'll ask this instead, how many cpu instructions do you know of that supposed to return different values often, also do you know of how to read IRQ0 in assembly? I want to default to that when no other architecture is detected which would provide the speedup needed without sacrificing the seedless state, at the moment I am seriously considering a version of the function that takes no parameters to remove all the push/pop stuff that slows a seeded function down, I managed to get the speed down to an average of 200000 nanoseconds by utilizing the rdtsc call directly (although I forgot the macro to detect it so currently have an #if 1 there instead)

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