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

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

Bart, a tcc "issue"

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

Contents

  Bart, a tcc "issue" DFS <nospam@dfs.com> - 2019-11-06 18:40 -0500
    Re: Bart, a tcc "issue" Bart <bc@freeuk.com> - 2019-11-07 00:03 +0000
      Re: Bart, a tcc "issue" Bart <bc@freeuk.com> - 2019-11-07 00:06 +0000
      Re: Bart, a tcc "issue" Bart <bc@freeuk.com> - 2019-11-07 01:44 +0000
    Re: Bart, a tcc "issue" James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-07 10:05 -0500
      Re: Bart, a tcc "issue" DFS <nospam@dfs.com> - 2019-11-07 13:22 -0500
      Re: Bart, a tcc "issue" DFS <nospam@dfs.com> - 2019-11-08 09:19 -0500
        Re: Bart, a tcc "issue" James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-08 11:03 -0500
    Re: Bart, a tcc "issue" Manfred <noname@add.invalid> - 2019-11-07 18:22 +0100
      Re: Bart, a tcc "issue" Manfred <noname@add.invalid> - 2019-11-07 18:30 +0100
    Re: Bart, a tcc "issue" Richard Damon <Richard@Damon-Family.org> - 2019-11-08 20:51 -0500
      Re: Bart, a tcc "issue" Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 20:59 -0800
        Re: Bart, a tcc "issue" Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-09 23:16 +0000
          Re: Bart, a tcc "issue" Richard Damon <Richard@Damon-Family.org> - 2019-11-09 20:27 -0500
            Re: Bart, a tcc "issue" Bart <bc@freeuk.com> - 2019-11-10 01:38 +0000
              Re: Bart, a tcc "issue" Richard Damon <Richard@Damon-Family.org> - 2019-11-09 20:59 -0500
                Re: Bart, a tcc "issue" Keith Thompson <kst-u@mib.org> - 2019-11-09 19:22 -0800
            Re: Bart, a tcc "issue" Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 03:04 +0000
              Re: Bart, a tcc "issue" Richard Damon <Richard@Damon-Family.org> - 2019-11-09 23:04 -0500
                Re: Bart, a tcc "issue" Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 13:15 +0000
          Re: Bart, a tcc "issue" Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 06:04 -0800
          Re: Bart, a tcc "issue" Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-10 07:49 -0800
            Re: Bart, a tcc "issue" Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-10 17:49 +0000
        Re: Bart, a tcc "issue" "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-11 02:44 -0800
          Re: Bart, a tcc "issue" James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-11 13:57 -0500
            Re: Bart, a tcc "issue" "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-14 16:51 -0800
          Re: Bart, a tcc "issue" Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:03 -0800

Page 1 of 2  [1] 2  Next page →

#147688 — Bart, a tcc "issue"

I wrote a distribution of characters counter, and on tcc (0.9.26) on 
Windows it always undercounts the last character in the set (9).  If you 
have tcc on Windows maybe you could test it.  Doesn't happen on 
gcc/MSYS2/Windows.

6 = 16258
7 = 16177
8 = 16068
9 = 14980

6 = 16134
7 = 15964
8 = 16144
9 = 15074

6 = 16074
7 = 16123
8 = 16132
9 = 15304

6 = 16180
7 = 16083
8 = 16337
9 = 15149

6 = 16126
7 = 16162
8 = 16138
9 = 15271

6 = 16116
7 = 16043
8 = 15987
9 = 15056

=====================================================================
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <string.h>

int randNbr(int low, int high) {
   return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
}

int main(void) {

   int i=0,j=0,k=0,cnt=0;

   srand(time(NULL));
	
   char charset[63] = 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
   int charsetLen = strlen(charset);
   printf("n = 1000000\n");
   for(i=0;i<charsetLen;i++) {
     for(j=0;j<1000000;j++) {
       k = randNbr(0,charsetLen-1);
       if(charset[i] == charset[k]) {cnt++;}
     }
     printf("%c = %d\n",charset[i],cnt);
     cnt=0;
   }
exit(0);
}

=====================================================================

[toc] | [next] | [standalone]

#147690

On 06/11/2019 23:40, DFS wrote:
> I wrote a distribution of characters counter, and on tcc (0.9.26) on 
> Windows it always undercounts the last character in the set (9).  If you 
> have tcc on Windows maybe you could test it.  Doesn't happen on 
> gcc/MSYS2/Windows.


Do you mean the count for 9 is lower than expected?

I can see that, but it's not a tcc thing, I see it on gcc/Windows too. 
(Maybe gcc/MSYS2 uses a wider random number range; what is RAND_MAX on 
gcc/MSYS2?)

 >      printf("%c = %d\n",charset[i],cnt);

With 1000000 samples divided 62 ways, you expect an average 16129 per 
character. So print instead cnt-1629 to show the deviation more clearly.

9 will have a larger deviation (up to -900 instead of max of +/- 250 or so).

On Windows, RAND_MAX is only 32767 (0 to 32767), which divided by 62 
gives 528.5; you will get an unbalanced number for the last interval 
because it will occur less frequently.

If I use a crude method of widening the range from 15 to 30 bits like this:

int randNbr(int low, int high) {
     int span=high-low+1;
     return ((rand()<<15)+rand()) % span+low;
}

then I see a better distribution on the 9s.

So, it would be interesting to see whether gcc/MSYS RAND_MAX is bigger.

>    char charset[63] = 

Just use [] here. Then the array will be as big as needed to accommodate 
string+terminator.

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

#147692

On 07/11/2019 00:03, Bart wrote:
> On 06/11/2019 23:40, DFS wrote:
>> I wrote a distribution of characters counter, and on tcc (0.9.26) on 
>> Windows it always undercounts the last character in the set (9).  If 
>> you have tcc on Windows maybe you could test it.  Doesn't happen on 
>> gcc/MSYS2/Windows.
> 
> 
> Do you mean the count for 9 is lower than expected?
> 
> I can see that, but it's not a tcc thing, I see it on gcc/Windows too. 
> (Maybe gcc/MSYS2 uses a wider random number range; what is RAND_MAX on 
> gcc/MSYS2?)
> 
>  >      printf("%c = %d\n",charset[i],cnt);
> 
> With 1000000 samples divided 62 ways, you expect an average 16129 per 
> character. So print instead cnt-1629 to show the deviation more clearly.

That should be 16129:

    printf("%c = %d\n",charset[i],cnt-16129);

(This is only for a span of 62 and 1000000 total random numbers.)

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

#147695

On 07/11/2019 00:03, Bart wrote:
> On 06/11/2019 23:40, DFS wrote:
>> I wrote a distribution of characters counter, and on tcc (0.9.26) on 
>> Windows it always undercounts the last character in the set (9).  If 
>> you have tcc on Windows maybe you could test it.  Doesn't happen on 
>> gcc/MSYS2/Windows.

> 
> So, it would be interesting to see whether gcc/MSYS RAND_MAX is bigger.

I've tried Linux under my Windows system (bloody thing takes 6 minutes 
to start up so I try to avoid it). It appears to have a 31-bit RAND_MAX 
value. This program seemed to give a more even distribution on my Linux, 
but it can also give funny numbers if you're not careful with that 
random number function.

(Getting random numbers equally distributed among 0..N-1 is difficult 
when N is not a power of 2. Here it's 62. I think a bigger RAND_MAX 
helps, but this is not my field.)

This code seemed to work reasonably well on Linux:

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

int randNbr(int low, int high) {
     int span=high-low+1;
     return (rand()) % span+low;
}

int main(void) {

   int i=0,j=0,k=0,cnt=0;

   srand(time(NULL));

   char charset[63] = 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
   int charsetLen = strlen(charset);
   printf("RAND_MAX= %d\n",RAND_MAX);
   printf("n = 1000000\n");
   for(i=0;i<charsetLen;i++) {
     for(j=0;j<1000000;j++) {
       k = randNbr(0,charsetLen-1);
       if(charset[i] == charset[k]) {cnt++;}
     }
//    printf("%c = %d\n",charset[i],cnt-16129);
     printf("%c = %d\n",charset[i],cnt);
     cnt=0;
   }

   exit(0);
}

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

#147714

On 11/6/19 6:40 PM, DFS wrote:
> I wrote a distribution of characters counter, and on tcc (0.9.26) on 
> Windows it always undercounts the last character in the set (9).  If you 
> have tcc on Windows maybe you could test it.  Doesn't happen on 
> gcc/MSYS2/Windows.
> 
> 6 = 16258
> 7 = 16177
> 8 = 16068
> 9 = 14980
> 
> 6 = 16134
> 7 = 15964
> 8 = 16144
> 9 = 15074
> 
> 6 = 16074
> 7 = 16123
> 8 = 16132
> 9 = 15304
> 
> 6 = 16180
> 7 = 16083
> 8 = 16337
> 9 = 15149
> 
> 6 = 16126
> 7 = 16162
> 8 = 16138
> 9 = 15271
> 
> 6 = 16116
> 7 = 16043
> 8 = 15987
> 9 = 15056
> 
> =====================================================================
> #include <stdlib.h>
> #include <stdio.h>
> #include <time.h>
> #include <math.h>
> #include <string.h>
> 
> int randNbr(int low, int high) {
>    return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
> }
> 
> int main(void) {
> 
>    int i=0,j=0,k=0,cnt=0;
> 
>    srand(time(NULL));
> 	
>    char charset[63] = 
> "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
>    int charsetLen = strlen(charset);
>    printf("n = 1000000\n");
>    for(i=0;i<charsetLen;i++) {
>      for(j=0;j<1000000;j++) {

Note: conforming implementations of C can have INT_MAX < 1000000. For
portable code, I'd recommend declaring j to be int_fast32_t or long,
rather than int.

>        k = randNbr(0,charsetLen-1);
>        if(charset[i] == charset[k]) {cnt++;}

That if-condition throws away roughly 61 out of 62 of the random numbers
you generate. See below for a more efficient approach.

>      }
>      printf("%c = %d\n",charset[i],cnt);
>      cnt=0;
>    }
> exit(0);> }

    int main(void)
    {
        const char charset[] =
            "abcdefghijklmnopqrstuvwxyz"
            "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
            "0123456789";
    #define CHARS (sizeof charset - 1)
        int cnt[CHARS]={0};
        for(int_fast32_t j=0; j<1000000; j++)
            cnt[randNbr(0, CHARS)]++;
        for(int i=0; i<CHARS; i++)
            printf("%c: %d\n", charset[i], cnt[i]);
        return 0;
    }

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

#147734

On 11/7/2019 10:05 AM, James Kuyper wrote:


> That if-condition throws away roughly 61 out of 62 of the random numbers
> you generate. See below for a more efficient approach.
> 
>>       }
>>       printf("%c = %d\n",charset[i],cnt);
>>       cnt=0;
>>     }
>> exit(0);> }
> 
>      int main(void)
>      {
>          const char charset[] =
>              "abcdefghijklmnopqrstuvwxyz"
>              "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>              "0123456789";
>      #define CHARS (sizeof charset - 1)
>          int cnt[CHARS]={0};
>          for(int_fast32_t j=0; j<1000000; j++)
>              cnt[randNbr(0, CHARS)]++;
>          for(int i=0; i<CHARS; i++)
>              printf("%c: %d\n", charset[i], cnt[i]);
>          return 0;
>      }


my orig: 3.64
yours  : 0.09

Nice!

I used a technique like that recently, to count letters when searching 
for anagrams.

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

#147770

On 11/7/2019 10:05 AM, James Kuyper wrote:
> On 11/6/19 6:40 PM, DFS wrote:


>>         k = randNbr(0,charsetLen-1);
>>         if(charset[i] == charset[k]) {cnt++;}
> 
> That if-condition throws away roughly 61 out of 62 of the random numbers
> you generate. See below for a more efficient approach.
> 
>>       }
>>       printf("%c = %d\n",charset[i],cnt);
>>       cnt=0;
>>     }
>> exit(0);> }
> 
>      int main(void)
>      {
>          const char charset[] =
>              "abcdefghijklmnopqrstuvwxyz"
>              "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>              "0123456789";
>      #define CHARS (sizeof charset - 1)
>          int cnt[CHARS]={0};
>          for(int_fast32_t j=0; j<1000000; j++)
>              cnt[randNbr(0, CHARS)]++;

you meant      cnt[randNbr(0, CHARS-1)]++;


>          for(int i=0; i<CHARS; i++)
>              printf("%c: %d\n", charset[i], cnt[i]);
>          return 0;
>      }
> 

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

#147779

On 11/8/19 9:19 AM, DFS wrote:
> On 11/7/2019 10:05 AM, James Kuyper wrote:
>> On 11/6/19 6:40 PM, DFS wrote:
> 
> 
>>>         k = randNbr(0,charsetLen-1);
>>>         if(charset[i] == charset[k]) {cnt++;}
>>
>> That if-condition throws away roughly 61 out of 62 of the random numbers
>> you generate. See below for a more efficient approach.
>>
>>>       }
>>>       printf("%c = %d\n",charset[i],cnt);
>>>       cnt=0;
>>>     }
>>> exit(0);> }
>>
>>      int main(void)
>>      {
>>          const char charset[] =
>>              "abcdefghijklmnopqrstuvwxyz"
>>              "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
>>              "0123456789";
>>      #define CHARS (sizeof charset - 1)
>>          int cnt[CHARS]={0};
>>          for(int_fast32_t j=0; j<1000000; j++)
>>              cnt[randNbr(0, CHARS)]++;
> 
> you meant      cnt[randNbr(0, CHARS-1)]++;
> 
> 
>>          for(int i=0; i<CHARS; i++)
>>              printf("%c: %d\n", charset[i], cnt[i]);
>>          return 0;
>>      }

You're right.
Incidentally, if you want to get some insight into why you're getting
the biased results that you see, I recommend modifying randNbr() to
eterministically cycle through the entire range of permitted values:

static int randNbr(int low, int high)
{
    static int rnd = 0;
    if(rnd >= RAND_MAX)
        rnd = 0;
    else
        rnd++;
    return low + rnd/(RAND_MAX / (high - low + 1) + 1);
}

And replace 1000000 with RAND_MAX+1L, so it goes through exactly one
full cycle. When you see the results, stop and think about them, and I
think you'll see what the problem is.

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

#147725

On 11/7/2019 12:40 AM, DFS wrote:
> I wrote a distribution of characters counter, and on tcc (0.9.26) on 
> Windows it always undercounts the last character in the set (9).  If you 
> have tcc on Windows maybe you could test it.  Doesn't happen on 
> gcc/MSYS2/Windows.
> 

As Bart pointed out, this is not specific to tcc, but it is related to 
the value of RAND_MAX instead.
The cause of this behavior is that you have a mistake in the randNbr 
function: it does not map correctly the [0, RAND_MAX ] interval to [low, 
high], in particular it does not map the last interval entirely, so you 
get less counts on that interval because the distribution of rand() is 
uniform.

> 
> =====================================================================
> #include <stdlib.h>
> #include <stdio.h>
> #include <time.h>
> #include <math.h>
> #include <string.h>
#include <assert.h>
> 
> int randNbr(int low, int high) {
      // the following is not correct: it should be:
      return low + (rand() * (long long)(high - low + 1)) / (RAND_MAX + 1);
>    // return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
> }
> 
> int main(void) {
> 
>    int i=0,j=0,k=0,cnt=0;
> 
>    srand(time(NULL));
> 
>    char charset[63] = 
> "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
>    int charsetLen = strlen(charset);
>    printf("n = 1000000\n");
>    for(i=0;i<charsetLen;i++) {
>      for(j=0;j<1000000;j++) {
>        k = randNbr(0,charsetLen-1);
          assert(charsetLen > k);
>        if(charset[i] == charset[k]) {cnt++;}
>      }
>      printf("%c = %d\n",charset[i],cnt);
>      cnt=0;
>    }
> exit(0);
> }
> 
> =====================================================================

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

#147726

On 11/7/2019 6:22 PM, Manfred wrote:

Hmm. I am afraid I introduced a possible overflow - added an extra (long 
long) cast to avoid it.

>> int randNbr(int low, int high) {
>       // the following is not correct: it should be:
>       return low + (rand() * (long long)(high - low + 1)) / ((long long)RAND_MAX + 1);
>>    // return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
>> } 

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

#147804

On 11/6/19 6:40 PM, DFS wrote:
> I wrote a distribution of characters counter, and on tcc (0.9.26) on
> Windows it always undercounts the last character in the set (9).  If you
> have tcc on Windows maybe you could test it.  Doesn't happen on
> gcc/MSYS2/Windows.
> 

This is a fundamental problem. A very simple version of it would be to
try to take 12 apples and divide them into 5 (or 7) equal piles (without
cutting any of them).

The 12 apples are the RAND_MAX possible values.

The 5 piles are the buckets you are putting them into.

If the number of buckets doesn't exactly divide into the number of
results you can get from the random number generator, the output won't
be equally likely. This most noticeable when the number of possible
numbers is smaller.

The simplest solution would be to throw away a few of the random
numbers, so that the number of 'usable' random numbers is a multiple of
the number of buckets.

The simple modification to the code is rather than using:
(low + rand() / (RAND_MAX / (high - low + 1) + 1))
use
(low + rand() / (RAND_MAX / (high - low + 1)))
and redraw if the result is > high.

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

#147809

Richard Damon <Richard@Damon-Family.org> writes:

> On 11/6/19 6:40 PM, DFS wrote:
>
>> I wrote a distribution of characters counter, and on tcc (0.9.26) on
>> Windows it always undercounts the last character in the set (9).  If you
>> have tcc on Windows maybe you could test it.  Doesn't happen on
>> gcc/MSYS2/Windows.
>
> This is a fundamental problem.  A very simple version of it would be to
> try to take 12 apples and divide them into 5 (or 7) equal piles (without
> cutting any of them).
>
> The 12 apples are the RAND_MAX possible values.
>
> The 5 piles are the buckets you are putting them into.
>
> If the number of buckets doesn't exactly divide into the number of
> results you can get from the random number generator, the output won't
> be equally likely.  This most noticeable when the number of possible
> numbers is smaller.
>
> The simplest solution would be to throw away a few of the random
> numbers, so that the number of 'usable' random numbers is a multiple of
> the number of buckets.
>
> The simple modification to the code is rather than using:
> (low + rand() / (RAND_MAX / (high - low + 1) + 1))
> use
> (low + rand() / (RAND_MAX / (high - low + 1)))
> and redraw if the result is > high.

It's interesting -- three different people posted corrections or
improvements to the uniform interval code, and all of the revisions
have been a little bit off in one way or another.  Care is needed to
deal with edge cases correctly.

    int
    uniform_less_than( unsigned k ){
        unsigned d, r;

        if(  k-1 > RAND_MAX  ||  k == 0  )  oops_someone_messed_up();

        d = (RAND_MAX - (k-1)) / k + 1;
        do  r = rand()/d;  while(  r >= k  );

        return  r;
    }

    int
    uniform_on_closed_interval( int a, int b ){
        if(  a > b  )  return  uniform_on_closed_interval( b, a );

        return  a + uniform_less_than( b + 1u - a );
    }

A good test for a uniform closed-interval RNG is to check that
it handles the interval 0..RAND_MAX, including both endpoints,
correctly.

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

#147859

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
<cut>
> It's interesting -- three different people posted corrections or
> improvements to the uniform interval code, and all of the revisions
> have been a little bit off in one way or another.  Care is needed to
> deal with edge cases correctly.
>
>     int
>     uniform_less_than( unsigned k ){
>         unsigned d, r;
>
>         if(  k-1 > RAND_MAX  ||  k == 0  )  oops_someone_messed_up();
>
>         d = (RAND_MAX - (k-1)) / k + 1;
>         do  r = rand()/d;  while(  r >= k  );
>
>         return  r;
>     }
>
>     int
>     uniform_on_closed_interval( int a, int b ){
>         if(  a > b  )  return  uniform_on_closed_interval( b, a );
>
>         return  a + uniform_less_than( b + 1u - a );
>     }
>
> A good test for a uniform closed-interval RNG is to check that
> it handles the interval 0..RAND_MAX, including both endpoints,
> correctly.

Are you considering edge cases in the C standard?  If so, one of those
has RAND_MAX == UINT_MAX.

-- 
Ben.

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

#147860

On 11/9/19 6:16 PM, Ben Bacarisse wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> <cut>
>> It's interesting -- three different people posted corrections or
>> improvements to the uniform interval code, and all of the revisions
>> have been a little bit off in one way or another.  Care is needed to
>> deal with edge cases correctly.
>>
>>     int
>>     uniform_less_than( unsigned k ){
>>         unsigned d, r;
>>
>>         if(  k-1 > RAND_MAX  ||  k == 0  )  oops_someone_messed_up();
>>
>>         d = (RAND_MAX - (k-1)) / k + 1;
>>         do  r = rand()/d;  while(  r >= k  );
>>
>>         return  r;
>>     }
>>
>>     int
>>     uniform_on_closed_interval( int a, int b ){
>>         if(  a > b  )  return  uniform_on_closed_interval( b, a );
>>
>>         return  a + uniform_less_than( b + 1u - a );
>>     }
>>
>> A good test for a uniform closed-interval RNG is to check that
>> it handles the interval 0..RAND_MAX, including both endpoints,
>> correctly.
> 
> Are you considering edge cases in the C standard?  If so, one of those
> has RAND_MAX == UINT_MAX.
> 

Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
or some other odd architecture). And yes, if you want to deal with that
sort of machine a lot of care needs to be taken, as a lot of things we
often take for granted aren't true, like that an unsigned can count the
number of values between any two signed numbers!!

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

#147861

On 10/11/2019 01:27, Richard Damon wrote:
> On 11/9/19 6:16 PM, Ben Bacarisse wrote:

>
>> Are you considering edge cases in the C standard?  If so, one of those
>> has RAND_MAX == UINT_MAX.
>>
> 
> Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
> if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
> or some other odd architecture). And yes, if you want to deal with that
> sort of machine a lot of care needs to be taken, as a lot of things we
> often take for granted aren't true, like that an unsigned can count the
> number of values between any two signed numbers!!


RAND_MAX seems to be 15 bits on Windows (32767). I've long since used 
multiple calls to rand() to construct a wider 30-bit since 15 bits is 
far too small. 32 bit unsigned is possible, but I recently just used my 
own routines which return numbers within a full 64-bit unsigned range.

An effective RAND_MAX of 2**64-1.

(I'm not sure why RAND_MAX features in those routines anyway. I think if 
a random value can be the full width of an int, then it is not needed.)

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

#147862

On 11/9/19 8:38 PM, Bart wrote:
> On 10/11/2019 01:27, Richard Damon wrote:
>> On 11/9/19 6:16 PM, Ben Bacarisse wrote:
> 
>>
>>> Are you considering edge cases in the C standard?  If so, one of those
>>> has RAND_MAX == UINT_MAX.
>>>
>>
>> Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
>> if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
>> or some other odd architecture). And yes, if you want to deal with that
>> sort of machine a lot of care needs to be taken, as a lot of things we
>> often take for granted aren't true, like that an unsigned can count the
>> number of values between any two signed numbers!!
> 
> 
> RAND_MAX seems to be 15 bits on Windows (32767). I've long since used
> multiple calls to rand() to construct a wider 30-bit since 15 bits is
> far too small. 32 bit unsigned is possible, but I recently just used my
> own routines which return numbers within a full 64-bit unsigned range.
> 
> An effective RAND_MAX of 2**64-1.
> 
> (I'm not sure why RAND_MAX features in those routines anyway. I think if
> a random value can be the full width of an int, then it is not needed.)

rand() is not required to generate a random number using all the bits of
the int (your observation that Windows only generates 15 bits
demonstrates that), so RAND_MAX is needed to tell the program the range
of results that rand will generate.

While it is quite possible to generate random number generators that
generate a full 64 bits at a time, such a generator can't be used
directly as rand(), as rand returns an int, and on those machines int
can't express 2*64-1.

I will also say that the standard rand() function shouldn't be used if
you need a random number with known good characteristics, as the
Standard doesn't define much in the way of requirements on rand(), and
may implementations at least used to just use the example out of K&R
which was a simple 15 bit LCG which is about as minimal as you can get
for a random number generator.

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

#147866

Richard Damon <Richard@Damon-Family.org> writes:
[...]
> I will also say that the standard rand() function shouldn't be used if
> you need a random number with known good characteristics, as the
> Standard doesn't define much in the way of requirements on rand(), and
> may implementations at least used to just use the example out of K&R
> which was a simple 15 bit LCG which is about as minimal as you can get
> for a random number generator.

The standard also includes a sample algorithm, probably the same as
the one in K&R.  And some implementations, particularly the one used
by NetBSD, are even worse than the sample algorithm in the standard,
returning alternating even and odd numbers.  The low-order 2 bits
repeat with a cycle length of 4, the low-order 3 bits with a cycle
length of 8, and so on.

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

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

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

#147865

Richard Damon <Richard@Damon-Family.org> writes:

> On 11/9/19 6:16 PM, Ben Bacarisse wrote:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>> <cut>
>>> It's interesting -- three different people posted corrections or
>>> improvements to the uniform interval code, and all of the revisions
>>> have been a little bit off in one way or another.  Care is needed to
>>> deal with edge cases correctly.
>>>
>>>     int
>>>     uniform_less_than( unsigned k ){
>>>         unsigned d, r;
>>>
>>>         if(  k-1 > RAND_MAX  ||  k == 0  )  oops_someone_messed_up();
>>>
>>>         d = (RAND_MAX - (k-1)) / k + 1;
>>>         do  r = rand()/d;  while(  r >= k  );
>>>
>>>         return  r;
>>>     }
>>>
>>>     int
>>>     uniform_on_closed_interval( int a, int b ){
>>>         if(  a > b  )  return  uniform_on_closed_interval( b, a );
>>>
>>>         return  a + uniform_less_than( b + 1u - a );
>>>     }
>>>
>>> A good test for a uniform closed-interval RNG is to check that
>>> it handles the interval 0..RAND_MAX, including both endpoints,
>>> correctly.
>> 
>> Are you considering edge cases in the C standard?  If so, one of those
>> has RAND_MAX == UINT_MAX.
>
> Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
> if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
> or some other odd architecture). And yes, if you want to deal with that
> sort of machine a lot of care needs to be taken, as a lot of things we
> often take for granted aren't true, like that an unsigned can count the
> number of values between any two signed numbers!!

Yes, it's a gruesome corner case for some types of code.

-- 
Ben.

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

#147867

On 11/9/19 10:04 PM, Ben Bacarisse wrote:
> Richard Damon <Richard@Damon-Family.org> writes:
> 
>> Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
>> if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
>> or some other odd architecture). And yes, if you want to deal with that
>> sort of machine a lot of care needs to be taken, as a lot of things we
>> often take for granted aren't true, like that an unsigned can count the
>> number of values between any two signed numbers!!
> 
> Yes, it's a gruesome corner case for some types of code.
> 

It's only a corner case if you need to be able to work on machines that
unusual. I would guess very few programs/libraries really need that
level of portability. I suspect most programs have other assumptions
(like what OS they are designed for) that more strictly limit the
machines they need to work on.

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

#147877

Richard Damon <Richard@Damon-Family.org> writes:

> On 11/9/19 10:04 PM, Ben Bacarisse wrote:
>> Richard Damon <Richard@Damon-Family.org> writes:
>> 
>>> Since rand() returns an int, the only way for RAND_MAX to be UINT_MAX is
>>> if UINT_MAX == INT_MAX (which generally means a Signed-Magnitude machine
>>> or some other odd architecture). And yes, if you want to deal with that
>>> sort of machine a lot of care needs to be taken, as a lot of things we
>>> often take for granted aren't true, like that an unsigned can count the
>>> number of values between any two signed numbers!!
>> 
>> Yes, it's a gruesome corner case for some types of code.
>
> It's only a corner case if you need to be able to work on machines that
> unusual. I would guess very few programs/libraries really need that
> level of portability.

I might even guess that none do!  It's really just a theoretical problem
that comes up when the notion of 100% portable C code is considered.

-- 
Ben.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web