Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #139043 > unrolled thread

Multi-channel rand()

Back to article view | Back to comp.lang.c

Contents

  Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-24 19:54 -0500
    Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-24 19:38 -0800
    Re: Multi-channel rand() nobody@example.org (Scott) - 2018-12-25 04:05 +0000
      Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-24 23:57 -0500
        Re: Multi-channel rand() Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2018-12-25 09:22 +0000
          Professional coders??? (Was: Multi-channel rand()) gazelle@shell.xmission.com (Kenny McCormack) - 2018-12-25 10:09 +0000
          Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 07:59 -0500
            Re: Multi-channel rand() Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2018-12-25 21:59 +0000
              Re: Multi-channel rand() nobody@example.org (Scott) - 2018-12-26 02:43 +0000
        Re: Multi-channel rand() rbowman <bowman@montana.com> - 2018-12-25 10:15 -0700
          Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-25 10:14 -0800
    Re: Multi-channel rand() Anton Shepelev <anton.txt@g{oogle}mail.com> - 2018-12-25 13:35 +0300
      Re: Multi-channel rand() fir <profesor.fir@gmail.com> - 2018-12-25 02:56 -0800
      Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:02 -0500
    Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-25 11:52 +0000
      Re: Multi-channel rand() Anton Shepelev <anton.txt@g{oogle}mail.com> - 2018-12-25 14:58 +0300
      Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-25 06:59 -0500
        Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:05 -0500
      Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-25 08:04 -0500
    Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 15:48 +0000
      Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 07:58 -0800
        Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 12:06 -0500
          Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:45 -0500
            Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 13:20 -0500
              Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 10:30 -0800
                Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-26 11:35 -0800
                  Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 14:52 -0500
                Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:31 -0500
                  Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 22:28 -0500
                  Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 20:42 -0800
              Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 15:32 -0800
            Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 19:38 +0000
              Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 15:35 -0800
          Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:59 -0500
            Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:05 -0500
          Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 13:08 -0500
            Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 15:50 -0500
        Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 17:42 +0000
          Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 12:48 -0500
          Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 12:58 -0500
            Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 19:03 +0000
              Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 14:45 -0500
                Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 20:46 +0000
                  Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 16:25 -0500
                    Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 17:13 -0500
                      Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-26 22:23 -0500
                    Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-26 23:39 +0000
                  Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 17:36 -0500
              Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 16:27 -0500
      Re: Multi-channel rand() rbowman <bowman@montana.com> - 2018-12-26 19:19 -0700
        Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-26 22:17 -0500
        Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-26 19:32 -0800
        Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-26 19:34 -0800
          Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-27 11:29 +0000
            Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 05:27 -0800
              Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 09:41 -0500
                Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 09:42 -0500
                  Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 07:01 -0800
                    Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 10:28 -0500
                      Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 10:48 -0500
                        Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 11:08 -0500
                          Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-27 13:49 -0800
                            Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 17:18 -0500
                              Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-29 13:59 -0800
                                Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 14:01 -0800
                                  Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-30 22:07 +0000
                                  Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-30 17:20 -0500
                          Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 17:47 -0500
                            Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-30 20:45 -0800
                      Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 08:22 -0800
                        Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 11:40 -0500
                          Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 09:21 -0800
                            Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 12:45 -0500
                              Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 10:57 -0800
                                Re: Multi-channel rand() "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2018-12-27 14:35 -0500
                                Re: Multi-channel rand() Tim Rentsch <txr@alumni.caltech.edu> - 2018-12-28 09:25 -0800
                                  Re: Multi-channel rand() Tim Rentsch <txr@alumni.caltech.edu> - 2018-12-28 09:55 -0800
                                Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-28 12:36 -0800
                        Re: Multi-channel rand() Robert Wessel <robertwessel2@yahoo.com> - 2018-12-27 20:34 -0600
                Re: Multi-channel rand() Richard Damon <Richard@Damon-Family.org> - 2018-12-27 10:37 -0500
              Re: Multi-channel rand() Bart <bc@freeuk.com> - 2018-12-27 14:46 +0000
                Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 07:05 -0800
                  Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-27 11:28 -0800
                    Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 12:07 -0800
                      Re: Multi-channel rand() Keith Thompson <kst-u@mib.org> - 2018-12-27 12:47 -0800
                        Re: Multi-channel rand() James Kuyper <jameskuyper@alumni.caltech.edu> - 2018-12-27 14:47 -0800
    Re: Multi-channel rand() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-26 11:58 -0800

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#139082

On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:
> On 25/12/2018 00:54, Rick C. Hodgin wrote:
> > Is there an equivalent of a multi-channel rand() function that enables
> > multiple simultaneous separate pseudo-random number generators by some-
> > thing like a handle or instance of each in the standard library?
> 
> This doesn't seem too hard, but it's obviously not in the standard 
> library (which AFAIK only has rand()). Example:
> 
> -------------------
> #include <stdio.h>
> #include <stdlib.h>
> #include <stdint.h>
> 
> typedef uint64_t u64;
> typedef u64* Randgen;
> 
> Randgen new_randgen(u64 seed1, u64 seed2) {
> // needs two 64-bit non-zero seeds
>      Randgen s;
> 
>      s=malloc(sizeof(u64)*2);
>      if (s==NULL) {
>          return s;
>      }
>      s[0]=seed1;
>      s[1]=seed2;
>      return s;
> }
> 
> void free_randgen(Randgen s) {
>      free(s);
> }
> 
> u64 random(Randgen s) {
> // based on 'xorshift128+'
>      u64 x = s[0];
>      u64 const y = s[1];
>      s[0] = y;
>      x ^= x << 23; // a
>      s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
>      return s[1] + y;
> }
> 
> int main(void) {
>      u64 a;
>      Randgen r1,r2,r3;
> 
>      r1=new_randgen(374646464,84747774);
>      r2=new_randgen(374646464,84747774);
>      r3=new_randgen(374646464,84747774);
> 
>      for (int i=0; i<10; ++i) {
>          printf("%d %016llX %016llX %016llX\n",i,
>              random(r1), random(r2), random(r3));
>      }
> 
>      free_randgen(r1);
>      free_randgen(r2);
>      free_randgen(r3);
> 
> }
> -----------------------
> 
> All three streams show the same results because I've used the same seed 
> for each.
> 
> (To reset a stream R to a new seed, either free R and set R to a new 
> generator, or change the two u64s that R points to, or provide a 
> function for that.
> 
> However this depends entirely on the PRNG used. The point of my example 
> is to show how easy it is to superimpose a 'multi-channel' API on a 
> single-stream PRNG.)

I agree.  That's what I intended to do, but I didn't know where
there was good prng source code that was in the Public Domain.

I'm looking for a nicely distributed prng.  I'm using the built-
in one with Visual C++ presently and it has really odd patterns
which, when scaled into a lesser range (like 1-10), produce oft-
repeated values.  I'll have to add logic to prohibit too many of
any single integer appearing in a row, or over a short span, as
there are times it will return four mapped to the same integer
in the 1..10 range in a row.  That's not acceptable for this
type of game's needs.  It also sometimes has an affinity for a
certain set of values, like it will produce a lot of 3s, 5s, 8s,
and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
7s, and 10s, for example.  Weird.

I was able to get my random seeding working properly.  It uses
user interaction time coupled with computer system time, and
takes multiple samples during game setup, and uses those values.
It's seeding things nicely.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139084

On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:
>> On 25/12/2018 00:54, Rick C. Hodgin wrote:
>>> Is there an equivalent of a multi-channel rand() function that enables
>>> multiple simultaneous separate pseudo-random number generators by some-
>>> thing like a handle or instance of each in the standard library?
>>
>> This doesn't seem too hard, but it's obviously not in the standard 
>> library (which AFAIK only has rand()). Example:
>>
>> -------------------
>> #include <stdio.h>
>> #include <stdlib.h>
>> #include <stdint.h>
>>
>> typedef uint64_t u64;
>> typedef u64* Randgen;
>>
>> Randgen new_randgen(u64 seed1, u64 seed2) {
>> // needs two 64-bit non-zero seeds
>>      Randgen s;
>>
>>      s=malloc(sizeof(u64)*2);
>>      if (s==NULL) {
>>          return s;
>>      }
>>      s[0]=seed1;
>>      s[1]=seed2;
>>      return s;
>> }
>>
>> void free_randgen(Randgen s) {
>>      free(s);
>> }
>>
>> u64 random(Randgen s) {
>> // based on 'xorshift128+'
>>      u64 x = s[0];
>>      u64 const y = s[1];
>>      s[0] = y;
>>      x ^= x << 23; // a
>>      s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
>>      return s[1] + y;
>> }
>>
>> int main(void) {
>>      u64 a;
>>      Randgen r1,r2,r3;
>>
>>      r1=new_randgen(374646464,84747774);
>>      r2=new_randgen(374646464,84747774);
>>      r3=new_randgen(374646464,84747774);
>>
>>      for (int i=0; i<10; ++i) {
>>          printf("%d %016llX %016llX %016llX\n",i,
>>              random(r1), random(r2), random(r3));
>>      }
>>
>>      free_randgen(r1);
>>      free_randgen(r2);
>>      free_randgen(r3);
>>
>> }
>> -----------------------
>>
>> All three streams show the same results because I've used the same seed 
>> for each.
>>
>> (To reset a stream R to a new seed, either free R and set R to a new 
>> generator, or change the two u64s that R points to, or provide a 
>> function for that.
>>
>> However this depends entirely on the PRNG used. The point of my example 
>> is to show how easy it is to superimpose a 'multi-channel' API on a 
>> single-stream PRNG.)
> 
> I agree.  That's what I intended to do, but I didn't know where
> there was good prng source code that was in the Public Domain.
> 
> I'm looking for a nicely distributed prng.  I'm using the built-
> in one with Visual C++ presently and it has really odd patterns
> which, when scaled into a lesser range (like 1-10), produce oft-
> repeated values.  I'll have to add logic to prohibit too many of
> any single integer appearing in a row, or over a short span, as
> there are times it will return four mapped to the same integer
> in the 1..10 range in a row.  That's not acceptable for this
> type of game's needs.  It also sometimes has an affinity for a
> certain set of values, like it will produce a lot of 3s, 5s, 8s,
> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
> 7s, and 10s, for example.  Weird.
> 
> I was able to get my random seeding working properly.  It uses
> user interaction time coupled with computer system time, and
> takes multiple samples during game setup, and uses those values.
> It's seeding things nicely.
> 

Beware of trying to force randomization by removing 'obviously
non-random' sequences, because ALL specific pattern should be equally
likely, so 4 6s in a row (from a 1-10 draw) should happen once every
10,000 numbers, so removing it makes the results LESS random.

Also, given a given random number generator, there are better and worse
ways to extract a random subrange. For many generators, using something
like mod or anding the lower bits is very bad, as the lower bits are
less random than upper bits.

[toc] | [prev] | [next] | [standalone]

#139086

On 12/26/2018 12:06 PM, Richard Damon wrote:
> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
>> I'm looking for a nicely distributed prng.  I'm using the built-
>> in one with Visual C++ presently and it has really odd patterns
>> which, when scaled into a lesser range (like 1-10), produce oft-
>> repeated values.  I'll have to add logic to prohibit too many of
>> any single integer appearing in a row, or over a short span, as
>> there are times it will return four mapped to the same integer
>> in the 1..10 range in a row.  That's not acceptable for this
>> type of game's needs.  It also sometimes has an affinity for a
>> certain set of values, like it will produce a lot of 3s, 5s, 8s,
>> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
>> 7s, and 10s, for example.  Weird.
> 
> Beware of trying to force randomization by removing 'obviously
> non-random' sequences, because ALL specific pattern should be equally
> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
> 10,000 numbers, so removing it makes the results LESS random.

Agree.  If it were a game like Tetris, would you want or expect
to get four of a particular type of piece in a row?  Or to have
a predominance of a particular subset of the various pieces?

> Also, given a given random number generator, there are better and worse
> ways to extract a random subrange. For many generators, using something
> like mod or anding the lower bits is very bad, as the lower bits are
> less random than upper bits.

I scale the result into the range.  The rand() function in C returns
a value 0..32767 on my machine.  I use a formula like this:

     const float MAX_RANGE = 9.0f;

     // Get a random value in the range 1..10
     lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);

It works well, but the algorithm it uses doesn't seem to be a good
prng.  Everyone who's test-played the game to date comments on it.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139091

On 12/26/18 12:45 PM, Rick C. Hodgin wrote:
> On 12/26/2018 12:06 PM, Richard Damon wrote:
>> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
>>> I'm looking for a nicely distributed prng.  I'm using the built-
>>> in one with Visual C++ presently and it has really odd patterns
>>> which, when scaled into a lesser range (like 1-10), produce oft-
>>> repeated values.  I'll have to add logic to prohibit too many of
>>> any single integer appearing in a row, or over a short span, as
>>> there are times it will return four mapped to the same integer
>>> in the 1..10 range in a row.  That's not acceptable for this
>>> type of game's needs.  It also sometimes has an affinity for a
>>> certain set of values, like it will produce a lot of 3s, 5s, 8s,
>>> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
>>> 7s, and 10s, for example.  Weird.
>>
>> Beware of trying to force randomization by removing 'obviously
>> non-random' sequences, because ALL specific pattern should be equally
>> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
>> 10,000 numbers, so removing it makes the results LESS random.
> 
> Agree.  If it were a game like Tetris, would you want or expect
> to get four of a particular type of piece in a row?  Or to have
> a predominance of a particular subset of the various pieces?
> 
>> Also, given a given random number generator, there are better and worse
>> ways to extract a random subrange. For many generators, using something
>> like mod or anding the lower bits is very bad, as the lower bits are
>> less random than upper bits.
> 
> I scale the result into the range.  The rand() function in C returns
> a value 0..32767 on my machine.  I use a formula like this:
> 
>     const float MAX_RANGE = 9.0f;
> 
>     // Get a random value in the range 1..10
>     lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);
> 
> It works well, but the algorithm it uses doesn't seem to be a good
> prng.  Everyone who's test-played the game to date comments on it.
> 

In many implementations, rand() IS based on the sample code from K&R,
which is very old, very simple, and not very good. The fix isn't to add
ad hoc randomizer fixes like you were suggesting, but to use a better
random number generator, and a source of those algorithms was given earlier.

Typically, the basic rand() function in the library is a simple cheap
generator, which gives you results comparable to the cost of it (not
great). For many purposes, it is good enough, but for many others,
particularly if 'patterns' can be discerned, it isn't.

[toc] | [prev] | [next] | [standalone]

#139092

On Wednesday, December 26, 2018 at 1:20:23 PM UTC-5, Richard Damon wrote:
> On 12/26/18 12:45 PM, Rick C. Hodgin wrote:
> > On 12/26/2018 12:06 PM, Richard Damon wrote:
> >> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
> >>> I'm looking for a nicely distributed prng.  I'm using the built-
> >>> in one with Visual C++ presently and it has really odd patterns
> >>> which, when scaled into a lesser range (like 1-10), produce oft-
> >>> repeated values.  I'll have to add logic to prohibit too many of
> >>> any single integer appearing in a row, or over a short span, as
> >>> there are times it will return four mapped to the same integer
> >>> in the 1..10 range in a row.  That's not acceptable for this
> >>> type of game's needs.  It also sometimes has an affinity for a
> >>> certain set of values, like it will produce a lot of 3s, 5s, 8s,
> >>> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
> >>> 7s, and 10s, for example.  Weird.
> >>
> >> Beware of trying to force randomization by removing 'obviously
> >> non-random' sequences, because ALL specific pattern should be equally
> >> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
> >> 10,000 numbers, so removing it makes the results LESS random.
> > 
> > Agree.  If it were a game like Tetris, would you want or expect
> > to get four of a particular type of piece in a row?  Or to have
> > a predominance of a particular subset of the various pieces?
> > 
> >> Also, given a given random number generator, there are better and worse
> >> ways to extract a random subrange. For many generators, using something
> >> like mod or anding the lower bits is very bad, as the lower bits are
> >> less random than upper bits.
> > 
> > I scale the result into the range.  The rand() function in C returns
> > a value 0..32767 on my machine.  I use a formula like this:
> > 
> >     const float MAX_RANGE = 9.0f;
> > 
> >     // Get a random value in the range 1..10
> >     lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);
> > 
> > It works well, but the algorithm it uses doesn't seem to be a good
> > prng.  Everyone who's test-played the game to date comments on it.
> > 
> 
> In many implementations, rand() IS based on the sample code from K&R,
> which is very old, very simple, and not very good. The fix isn't to add
> ad hoc randomizer fixes like you were suggesting, but to use a better
> random number generator, and a source of those algorithms was given earlier.
> 
> Typically, the basic rand() function in the library is a simple cheap
> generator, which gives you results comparable to the cost of it (not
> great). For many purposes, it is good enough, but for many others,
> particularly if 'patterns' can be discerned, it isn't.

I need help implementing one.  I tried to use <random> but could
not get it to work properly.  I realize it was me doing it wrong,
but the online tutorials I found showed code examples which would
not compile in my instance of Visual Studio 2008.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139094

On 12/26/2018 10:30 AM, Rick C. Hodgin wrote:
> On Wednesday, December 26, 2018 at 1:20:23 PM UTC-5, Richard Damon wrote:
>> On 12/26/18 12:45 PM, Rick C. Hodgin wrote:
>>> On 12/26/2018 12:06 PM, Richard Damon wrote:
>>>> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
[...]
> I need help implementing one.  I tried to use <random> but could
> not get it to work properly.  I realize it was me doing it wrong,

Show some code, dang it! I hope you are not trying to compile it with a 
C compiler:

https://en.cppreference.com/w/cpp/header/random


> but the online tutorials I found showed code examples which would
> not compile in my instance of Visual Studio 2008.

Ummm... Why would they not compile? Why not upgrade your old compiler, 
you seem to really like MSVC:

https://visualstudio.microsoft.com/vs/express

or try another one. Like GCC?

[toc] | [prev] | [next] | [standalone]

#139097

On 12/26/2018 2:35 PM, Chris M. Thomasson wrote:
> On 12/26/2018 10:30 AM, Rick C. Hodgin wrote:
>> I need help implementing one.  I tried to use <random> but could
>> not get it to work properly.  I realize it was me doing it wrong,
> 
> Show some code, dang it! I hope you are not trying to compile it with a C 
> compiler:

I write mostly C code in a C++ compiler.  I use C++ about 1% of the
time, save some of the syntax relaxations I use often (single-line
comments, no "struct" keyboard, anonymous structs and unions), as
well as C++'s stricter typing.

> https://en.cppreference.com/w/cpp/header/random

The code I was using:

     http://www.cplusplus.com/reference/random/

     std::default_random_engine generator;
     std::uniform_int_distribution<int> distribution(1,6);
     int dice_roll = distribution(generator);
     // generates number in the range 1..6

I get an error on uniform_int_distribution.  I looked in the random
header file on my machine and found uniform_int and tried it, but it
also wouldn't compile.

I'm not a C++ guy, so I gave it about one minute of my time and then
went back to rand().

>> but the online tutorials I found showed code examples which would
>> not compile in my instance of Visual Studio 2008.
> 
> Ummm... Why would they not compile? Why not upgrade your old compiler, you 
> seem to really like MSVC:
> 
> https://visualstudio.microsoft.com/vs/express
> 
> or try another one. Like GCC?

VS2008 and VS2010 are the last Visual Studios that don't require a
stamp or branding to be setup when installed.  Microsoft used to
force you to be online to use VS2012.  People hated that, so they
moved to something sneakier.  When you use VS2015 or later, you
must login at least once, and then that login brands the work you
do with Microsoft in that instance.

I truly hate Microsoft and the way they're moving people to be
always online, always dependent upon other online systems.  I
prefer offline tools, and the anonymity I have a right to possess
(ha ha) in this country.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139104

On 12/26/18 1:30 PM, Rick C. Hodgin wrote:
> On Wednesday, December 26, 2018 at 1:20:23 PM UTC-5, Richard Damon wrote:
>> On 12/26/18 12:45 PM, Rick C. Hodgin wrote:
>>> On 12/26/2018 12:06 PM, Richard Damon wrote:
>>>> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
>>>>> I'm looking for a nicely distributed prng.  I'm using the built-
>>>>> in one with Visual C++ presently and it has really odd patterns
>>>>> which, when scaled into a lesser range (like 1-10), produce oft-
>>>>> repeated values.  I'll have to add logic to prohibit too many of
>>>>> any single integer appearing in a row, or over a short span, as
>>>>> there are times it will return four mapped to the same integer
>>>>> in the 1..10 range in a row.  That's not acceptable for this
>>>>> type of game's needs.  It also sometimes has an affinity for a
>>>>> certain set of values, like it will produce a lot of 3s, 5s, 8s,
>>>>> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
>>>>> 7s, and 10s, for example.  Weird.
>>>>
>>>> Beware of trying to force randomization by removing 'obviously
>>>> non-random' sequences, because ALL specific pattern should be equally
>>>> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
>>>> 10,000 numbers, so removing it makes the results LESS random.
>>>
>>> Agree.  If it were a game like Tetris, would you want or expect
>>> to get four of a particular type of piece in a row?  Or to have
>>> a predominance of a particular subset of the various pieces?
>>>
>>>> Also, given a given random number generator, there are better and worse
>>>> ways to extract a random subrange. For many generators, using something
>>>> like mod or anding the lower bits is very bad, as the lower bits are
>>>> less random than upper bits.
>>>
>>> I scale the result into the range.  The rand() function in C returns
>>> a value 0..32767 on my machine.  I use a formula like this:
>>>
>>>     const float MAX_RANGE = 9.0f;
>>>
>>>     // Get a random value in the range 1..10
>>>     lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);
>>>
>>> It works well, but the algorithm it uses doesn't seem to be a good
>>> prng.  Everyone who's test-played the game to date comments on it.
>>>
>>
>> In many implementations, rand() IS based on the sample code from K&R,
>> which is very old, very simple, and not very good. The fix isn't to add
>> ad hoc randomizer fixes like you were suggesting, but to use a better
>> random number generator, and a source of those algorithms was given earlier.
>>
>> Typically, the basic rand() function in the library is a simple cheap
>> generator, which gives you results comparable to the cost of it (not
>> great). For many purposes, it is good enough, but for many others,
>> particularly if 'patterns' can be discerned, it isn't.
> 
> I need help implementing one.  I tried to use <random> but could
> not get it to work properly.  I realize it was me doing it wrong,
> but the online tutorials I found showed code examples which would
> not compile in my instance of Visual Studio 2008.
> 

IF you share the code example and the error you get perhaps someone
could help,

<random> would be C++ code, so clc would be the wrong group.

You can contact me off line if you want, I'm on break this week so have
a bit of time.

[toc] | [prev] | [next] | [standalone]

#139113

On 12/26/2018 4:31 PM, Richard Damon wrote:
> IF you share the code example and the error you get perhaps someone
> could help,
> 
> <random> would be C++ code, so clc would be the wrong group.
> 
> You can contact me off line if you want, I'm on break this week so have
> a bit of time.

It was the block of code I posted in the other message.  But, I'd
rather not use C++ for such things.  The simple algorithm Chris
posted is fantastic for game play.  I haven't analyzed its output
sequences yet, but it did note on the wiki page that, "PCG-RXS-M-XS
(with 32-bit output) passes BigCrush with 36 bits of state (the
minimum possible)."

     https://en.wikipedia.org/wiki/Permuted_congruential_generator

     #include <stdint.h>
     static uint64_t state = 0x4d595df4d0f33173;
     // Or something seed-dependent
     static uint64_t const multiplier = 6364136223846793005u;
     static uint64_t const increment = 1442695040888963407u;
     // Or an arbitrary odd constant

     static uint32_t rotr32(uint32_t x, unsigned r)
     {
         return x >> r | x << (-r & 31);
     }

     void pcg32_init(uint64_t seed)
     {
         state = seed + increment;
         pcg32();
     }

     uint32_t pcg32(void)
     {
         uint64_t x = state;
         unsigned count = (unsigned)(x >> 59);       // 59 = 64 - 5

         state = x * multiplier + increment;
         x ^= x >> 18;                               // 18 = (64 - 27)/2
         return rotr32((uint32_t)(x >> 27), count);  // 27 = 32 - 5
     }

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139274

On 12/26/2018 1:31 PM, Richard Damon wrote:
> On 12/26/18 1:30 PM, Rick C. Hodgin wrote:
>> On Wednesday, December 26, 2018 at 1:20:23 PM UTC-5, Richard Damon wrote:
>>> On 12/26/18 12:45 PM, Rick C. Hodgin wrote:
>>>> On 12/26/2018 12:06 PM, Richard Damon wrote:
>>>>> On 12/26/18 10:58 AM, Rick C. Hodgin wrote:
>>>>>> I'm looking for a nicely distributed prng.  I'm using the built-
>>>>>> in one with Visual C++ presently and it has really odd patterns
>>>>>> which, when scaled into a lesser range (like 1-10), produce oft-
>>>>>> repeated values.  I'll have to add logic to prohibit too many of
>>>>>> any single integer appearing in a row, or over a short span, as
>>>>>> there are times it will return four mapped to the same integer
>>>>>> in the 1..10 range in a row.  That's not acceptable for this
>>>>>> type of game's needs.  It also sometimes has an affinity for a
>>>>>> certain set of values, like it will produce a lot of 3s, 5s, 8s,
>>>>>> and 9s, and very few 1s, 4s, 6s, and an average amount of 2s,
>>>>>> 7s, and 10s, for example.  Weird.
>>>>>
>>>>> Beware of trying to force randomization by removing 'obviously
>>>>> non-random' sequences, because ALL specific pattern should be equally
>>>>> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
>>>>> 10,000 numbers, so removing it makes the results LESS random.
>>>>
>>>> Agree.  If it were a game like Tetris, would you want or expect
>>>> to get four of a particular type of piece in a row?  Or to have
>>>> a predominance of a particular subset of the various pieces?
>>>>
>>>>> Also, given a given random number generator, there are better and worse
>>>>> ways to extract a random subrange. For many generators, using something
>>>>> like mod or anding the lower bits is very bad, as the lower bits are
>>>>> less random than upper bits.
>>>>
>>>> I scale the result into the range.  The rand() function in C returns
>>>> a value 0..32767 on my machine.  I use a formula like this:
>>>>
>>>>      const float MAX_RANGE = 9.0f;
>>>>
>>>>      // Get a random value in the range 1..10
>>>>      lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);
>>>>
>>>> It works well, but the algorithm it uses doesn't seem to be a good
>>>> prng.  Everyone who's test-played the game to date comments on it.
>>>>
>>>
>>> In many implementations, rand() IS based on the sample code from K&R,
>>> which is very old, very simple, and not very good. The fix isn't to add
>>> ad hoc randomizer fixes like you were suggesting, but to use a better
>>> random number generator, and a source of those algorithms was given earlier.
>>>
>>> Typically, the basic rand() function in the library is a simple cheap
>>> generator, which gives you results comparable to the cost of it (not
>>> great). For many purposes, it is good enough, but for many others,
>>> particularly if 'patterns' can be discerned, it isn't.
>>
>> I need help implementing one.  I tried to use <random> but could
>> not get it to work properly.  I realize it was me doing it wrong,
>> but the online tutorials I found showed code examples which would
>> not compile in my instance of Visual Studio 2008.
>>
> 
> IF you share the code example and the error you get perhaps someone
> could help,
> 
> <random> would be C++ code, so clc would be the wrong group.
> 
> You can contact me off line if you want, I'm on break this week so have
> a bit of time.
> 

You are a nice person!

[toc] | [prev] | [next] | [standalone]

#139107

Richard Damon <Richard@Damon-Family.org> writes:
[...]
> In many implementations, rand() IS based on the sample code from K&R,
> which is very old, very simple, and not very good. The fix isn't to add
> ad hoc randomizer fixes like you were suggesting, but to use a better
> random number generator, and a source of those algorithms was given earlier.
[...]

Some rand() implementations are even worse than the sample code
from K&R.  In the NetBSD implementation, the low order bit of the
value returned by rand() alternates 0 and 1, the low order 2 bits
repeat with a cycle of length 4. etc.  The K&R implementation
doesn't do that.

https://github.com/Keith-S-Thompson/crude_rand_test

-- 
Keith Thompson (The_Other_Keith) kst@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#139095

On 26/12/2018 17:45, Rick C. Hodgin wrote:
> On 12/26/2018 12:06 PM, Richard Damon wrote:

>> Also, given a given random number generator, there are better and worse
>> ways to extract a random subrange. For many generators, using something
>> like mod or anding the lower bits is very bad, as the lower bits are
>> less random than upper bits.
> 
> I scale the result into the range.  The rand() function in C returns
> a value 0..32767 on my machine.  I use a formula like this:
> 
>      const float MAX_RANGE = 9.0f;
> 
>      // Get a random value in the range 1..10
>      lfValue = 1 + (int)(MAX_RANGE * (float)rand() / (float)RAND_MAX);
> 
> It works well,

I doubt it (how many 10s do you get?).

To get 9.0 before you add 1, the expression has to yield 1.0, but that 
only happens when rand() returns exactly 32767, which is about 1 in 32K 
rather than 1 in 10 or so.

To fix it, getting 0.0 to 1.0 first seems sound, but I would divide by 
RAND_MAX+1 to get 0.0 to 0.99999 so that the odd 1.0 never occurs. Then 
multiply by 10.0 (not 9.0), to give 0.0 to 9.9999. Then convert to int 
to give 0 to 9, then add 1.


  but the algorithm it uses doesn't seem to be a good
> prng.  Everyone who's test-played the game to date comments on it.

Actually C's, rand() doesn't seem too bad.

[toc] | [prev] | [next] | [standalone]

#139108

Bart <bc@freeuk.com> writes:
[...]
> Actually C's, rand() doesn't seem too bad.

The standard doesn't specify the algorithm used by rand().  It provides
a sample implementation, but not all implementations use it.  There are
some rand() implementations that are, in some ways, very bad.

rand() can be suitable of some purposes.  It's absolutely not suitable
for cryptographic purposes.

-- 
Keith Thompson (The_Other_Keith) kst@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#139089

On 12/26/2018 12:06 PM, Richard Damon wrote:
> Beware of trying to force randomization by removing 'obviously
> non-random' sequences, because ALL specific pattern should be equally
> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
> 10,000 numbers, so removing it makes the results LESS random.
> 
> Also, given a given random number generator, there are better and worse
> ways to extract a random subrange. For many generators, using something
> like mod or anding the lower bits is very bad, as the lower bits are
> less random than upper bits.

It wouldn't surprise me to learn that in math there's some kind of
law about how large random sequences, when scaled into small sets,
can potentially produce larger sets of repeating values than would
an algorithm designed to produce a smaller set of random numbers.

I have a VIA C7-M at home.  I don't have a working motherboard for
it any longer, but it had an on-die hardware rng on it.  It pro-
duced amazingly distributed random numbers when it was below about
40C.  Above 40C it began to favor values closer to 0 and 255 with
an 8-bit sample, with an obvious spike approaching those ends of
the 0..255 graph.

I worked with someone named Van Smith from Centaur back then on
that article, and he and I went over the math principles regarding
statistical significance of rng data.  He said even with the spikes
toward 0 and 255 at higher temperatures, the data was still truly
random, and could not be predicted, and was therefore valid.  I
told him the values were not usable outside of a need to have mere
random values, but if you were to ascribe meaning to them, such as
assigning pieces for a Tetris game (seven pieces, scaling those
hardware rng values would produce higher numbers of certain pieces,
and it would be unusable.  He disagreed.

I've always thought that hardware rng was amazing when cool.  It
was a near perfect distribution over small sets, and over larger
sets.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139101

On 12/26/18 12:59 PM, Rick C. Hodgin wrote:
> On 12/26/2018 12:06 PM, Richard Damon wrote:
>> Beware of trying to force randomization by removing 'obviously
>> non-random' sequences, because ALL specific pattern should be equally
>> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
>> 10,000 numbers, so removing it makes the results LESS random.
>>
>> Also, given a given random number generator, there are better and worse
>> ways to extract a random subrange. For many generators, using something
>> like mod or anding the lower bits is very bad, as the lower bits are
>> less random than upper bits.
> 
> It wouldn't surprise me to learn that in math there's some kind of
> law about how large random sequences, when scaled into small sets,
> can potentially produce larger sets of repeating values than would
> an algorithm designed to produce a smaller set of random numbers.
> 
> I have a VIA C7-M at home.  I don't have a working motherboard for
> it any longer, but it had an on-die hardware rng on it.  It pro-
> duced amazingly distributed random numbers when it was below about
> 40C.  Above 40C it began to favor values closer to 0 and 255 with
> an 8-bit sample, with an obvious spike approaching those ends of
> the 0..255 graph.
> 
> I worked with someone named Van Smith from Centaur back then on
> that article, and he and I went over the math principles regarding
> statistical significance of rng data.  He said even with the spikes
> toward 0 and 255 at higher temperatures, the data was still truly
> random, and could not be predicted, and was therefore valid.  I
> told him the values were not usable outside of a need to have mere
> random values, but if you were to ascribe meaning to them, such as
> assigning pieces for a Tetris game (seven pieces, scaling those
> hardware rng values would produce higher numbers of certain pieces,
> and it would be unusable.  He disagreed.
> 
> I've always thought that hardware rng was amazing when cool.  It
> was a near perfect distribution over small sets, and over larger
> sets.
> 

The issue isn't so much 'large range' to 'small range' but that some
PRNG have focused more on making sure the higher order bits have better
randomness than the lower order bits, in part because for most purposes
the behavior of higher order bits is more important, unless you do
something funny and take the lower bits.

In general, if you want a small range (1-N) uniform distributed random
number sequence, it is better to use a formula like
1 + (rand() / ((RAND_MAX+1)/N)
and throw out and values too big (which should be rare if N << RAND_MAX)

True random number generators can be very hard to get right. It is easy
to get true random events, but hard to get them with a uniform equal
distribution. Most good true random number generators follow the
hardware generation step with a 'whiting' step to spreed out the results
(and which often reduces the number of bits you got out). How hard you
whiten is based on how good of results you need.

[toc] | [prev] | [next] | [standalone]

#139090

On 12/26/2018 12:06 PM, Richard Damon wrote:
> Beware of trying to force randomization by removing 'obviously
> non-random' sequences, because ALL specific pattern should be equally
> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
> 10,000 numbers, so removing it makes the results LESS random.
> 
> Also, given a given random number generator, there are better and worse
> ways to extract a random subrange. For many generators, using something
> like mod or anding the lower bits is very bad, as the lower bits are
> less random than upper bits.

Perhaps what I need to do is operate a constant shift so that even if
it does produce large sequences of identical values, they will not be
the same piece.  Something like this:

     int get_rand(int max_range)
     {
         return (int)((float)max_range * (float)rand() / (float)RAND_MAX);
     }

     const int MAX_RANGE = 9;

     int xlat_map[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
     int xlat_op = 0;

     // Get a random value in the range 1..10
     lfValue = xlat_map[(xlat_op + 1 + get_rand(MAX_RANGE)) % 10];
     xlat_op = (xlat_op + get_rand(9)) % 10;

Something like that so it will cycle through translating the values
in a shifting manner, which is itself randomly moving through the
values.

I'll have to do some testing.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139100

On 12/26/18 1:08 PM, Rick C. Hodgin wrote:
> On 12/26/2018 12:06 PM, Richard Damon wrote:
>> Beware of trying to force randomization by removing 'obviously
>> non-random' sequences, because ALL specific pattern should be equally
>> likely, so 4 6s in a row (from a 1-10 draw) should happen once every
>> 10,000 numbers, so removing it makes the results LESS random.
>>
>> Also, given a given random number generator, there are better and worse
>> ways to extract a random subrange. For many generators, using something
>> like mod or anding the lower bits is very bad, as the lower bits are
>> less random than upper bits.
> 
> Perhaps what I need to do is operate a constant shift so that even if
> it does produce large sequences of identical values, they will not be
> the same piece.  Something like this:
> 
>     int get_rand(int max_range)
>     {
>         return (int)((float)max_range * (float)rand() / (float)RAND_MAX);
>     }
> 
>     const int MAX_RANGE = 9;
> 
>     int xlat_map[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
>     int xlat_op = 0;
> 
>     // Get a random value in the range 1..10
>     lfValue = xlat_map[(xlat_op + 1 + get_rand(MAX_RANGE)) % 10];
>     xlat_op = (xlat_op + get_rand(9)) % 10;
> 
> Something like that so it will cycle through translating the values
> in a shifting manner, which is itself randomly moving through the
> values.
> 
> I'll have to do some testing.
> 

If the generator is good, then this sort of thing won't be needed, but a
scrambling function like this won't hurt (just cost cpu cycles).

If the generator is bad, than this sort of thing will change what sort
of statistics are bad. It may well be that this will move the bad
statistic to one that doesn't affect you as much, and may be an
acceptable band-aid.

Better would be to try and use a better base random number generator.

[toc] | [prev] | [next] | [standalone]

#139085

On 26/12/2018 15:58, Rick C. Hodgin wrote:
> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:

>> However this depends entirely on the PRNG used. The point of my example
>> is to show how easy it is to superimpose a 'multi-channel' API on a
>> single-stream PRNG.)
> 
> I agree.  That's what I intended to do, but I didn't know where
> there was good prng source code that was in the Public Domain.
> 
> I'm looking for a nicely distributed prng.  I'm using the built-
> in one with Visual C++ presently and it has really odd patterns
> which, when scaled into a lesser range (like 1-10), produce oft-
> repeated values.

Really? I tried the simple PRNG I showed, using a%10 to produce values 
from 0 to 9, which is supposed to be really bad idea, and got this 
distribution over 1 billion calls for each of the digits:

   0: 100011113
   1: 99989920
   2: 100009423
   3: 100004327
   4: 99991057
   5: 100000307
   6: 99998986
   7: 100014477
   8: 99982849
   9: 99997541

A perfect distribution would have 100,000,000 of each, so these are out 
by 1 in 10,000 or so.

-- 
bart

[toc] | [prev] | [next] | [standalone]

#139087

On 12/26/2018 12:42 PM, Bart wrote:
> On 26/12/2018 15:58, Rick C. Hodgin wrote:
>> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:
> 
>>> However this depends entirely on the PRNG used. The point of my example
>>> is to show how easy it is to superimpose a 'multi-channel' API on a
>>> single-stream PRNG.)
>>
>> I agree.  That's what I intended to do, but I didn't know where
>> there was good prng source code that was in the Public Domain.
>>
>> I'm looking for a nicely distributed prng.  I'm using the built-
>> in one with Visual C++ presently and it has really odd patterns
>> which, when scaled into a lesser range (like 1-10), produce oft-
>> repeated values.
> 
> Really? I tried the simple PRNG I showed, using a%10 to produce values from 0 
> to 9, which is supposed to be really bad idea, and got this distribution over 
> 1 billion calls for each of the digits:
> 
>    0: 100011113
>    1: 99989920
>    2: 100009423
>    3: 100004327
>    4: 99991057
>    5: 100000307
>    6: 99998986
>    7: 100014477
>    8: 99982849
>    9: 99997541
> 
> A perfect distribution would have 100,000,000 of each, so these are out by 1 
> in 10,000 or so.

Re-process the prng in groups of 5s and 10s and see how many sequences
you have with 1 of each, 2 of each, 3 of each, etc.

The issue isn't distribution over 1 billion calls.  It's distribution
over blocks of 5s or 10s, producing large chains of duplicates in those
small sets.

-- 
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#139088

On 12/26/18 12:42 PM, Bart wrote:
> On 26/12/2018 15:58, Rick C. Hodgin wrote:
>> On Wednesday, December 26, 2018 at 10:48:31 AM UTC-5, Bart wrote:
> 
>>> However this depends entirely on the PRNG used. The point of my example
>>> is to show how easy it is to superimpose a 'multi-channel' API on a
>>> single-stream PRNG.)
>>
>> I agree.  That's what I intended to do, but I didn't know where
>> there was good prng source code that was in the Public Domain.
>>
>> I'm looking for a nicely distributed prng.  I'm using the built-
>> in one with Visual C++ presently and it has really odd patterns
>> which, when scaled into a lesser range (like 1-10), produce oft-
>> repeated values.
> 
> Really? I tried the simple PRNG I showed, using a%10 to produce values
> from 0 to 9, which is supposed to be really bad idea, and got this
> distribution over 1 billion calls for each of the digits:
> 
>   0: 100011113
>   1: 99989920
>   2: 100009423
>   3: 100004327
>   4: 99991057
>   5: 100000307
>   6: 99998986
>   7: 100014477
>   8: 99982849
>   9: 99997541
> 
> A perfect distribution would have 100,000,000 of each, so these are out
> by 1 in 10,000 or so.
> 

The low order bits of many random number gererators tend to be well
distributed, but often have patterned between them. Try running an
analysis of first order transition, a 2d histogram of consecutive
values. Some are so bad that the LSB almost always alternates between
one and zero, and this shows up in transition histograms. There are a
number of these sorts of test, which different PRNG do better at than
others.

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web