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 2 of 2 — ← Prev page 1 [2]

#147884

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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.

Ahh, I was wondering if someone would call me on this.  I should
have known you would spot it.  Indeed it is the case that the code
shown tacitly assumes UINT_MAX > INT_MAX.  Perhaps a reasonable
choice under the circumstances, but in any case it was made
consciously.

Now that this has been pointed out, I feel obliged to write a new
version that works even for such unusual implementations.  As it
turns out it isn't much harder than the first version:

    int
    uniform_no_greater_than( unsigned k ){
        unsigned r;
        unsigned d = k >= RAND_MAX ? 1 : (RAND_MAX - k) / (k+1) + 1;
        assert(  k <= RAND_MAX  );

        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 );

        if(  a < 0  ? b > a+RAND_MAX  : b-a > RAND_MAX  ){
            return  interval_too_large(),  a;
        }

        return  a + uniform_no_greater_than( b - a );
    }

The splitting into cases with ?: is done to avoid signed overflow
or division by zero.  Apart from that it's pretty much the same
as the first version.

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

#147907

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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.

Ahem.  Please review this version:

    int
    uniform_no_greater_than( unsigned k ){
        unsigned r = 0;
        assert(  k <= RAND_MAX  );

        if(  k > 0  ){
            unsigned d = k >= RAND_MAX ? 1 : (RAND_MAX - k) / (k+1) + 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 );

        if(  a < 0  ? b > a+RAND_MAX  : b-a > RAND_MAX  ){
            return  interval_too_large(),  a;
        }

        return  a + uniform_no_greater_than( b - a );
    }

The version just previously posted has a problem if k is 0 in
implementations where RAND_MAX == UINT_MAX.

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

#147916

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
<cut>
>> Are you considering edge cases in the C standard?  If so, one of those
>> has RAND_MAX == UINT_MAX.
>
> Ahem.  Please review this version:
>
>     int
>     uniform_no_greater_than( unsigned k ){
>         unsigned r = 0;
>         assert(  k <= RAND_MAX  );
>
>         if(  k > 0  ){
>             unsigned d = k >= RAND_MAX ? 1 : (RAND_MAX - k) / (k+1) + 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 );
>
>         if(  a < 0  ? b > a+RAND_MAX  : b-a > RAND_MAX  ){
>             return  interval_too_large(),  a;
>         }
>
>         return  a + uniform_no_greater_than( b - a );
>     }

Nice.  I thought it would be messier to accommodate this oddity.

-- 
Ben.

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

#147936

On 11/8/2019 8:59 PM, Tim Rentsch wrote:
> 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.
> 

Fwiw, off topic wrt integers, a while ago I just used an epsilon to deal 
with random intervals wrt rand(). Sometimes RAND_MAX does not get hit 
often enough for my needs, so I adjusted epsilon. Heck, is rand() even 
guaranteed to return RAND_MAX at all? Well, I used this code for a 
fractal, so it was good enough, wrt 0...1 being a unit interval:
__________________________________
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


double ct_rand()
{
     return rand() / (RAND_MAX - 0.);
}


int main(void)
{
     {
         unsigned long n = 2000000;
         double eps = .00000666;

         for (unsigned long i = 0; i < n; ++i)
         {
             double rnum = ct_rand();

             //printf("i[%lu]:rnum = %lf\n", i, rnum);

             if (1. - rnum < eps)
             {
                 double dif = eps - (1. - rnum);
                 printf("i[%lu]:rnum = %lf, %lf\n", i, rnum, dif);

                 rnum = 1.; // artificially set high...
             }
         }
     }

     printf("\n\nfin...\n");

     return 0;
}
__________________________________


Pretty nasty... ;^)

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

#147942

On 11/11/19 5:44 AM, Chris M. Thomasson wrote:
...
> ... Heck, is rand() even 
> guaranteed to return RAND_MAX at all? ...
As the standard itself notes in footnote 295:
"There are no guarantees as to the quality of the random sequence
produced and some implementations are known to produce sequences with
distressingly non-random low-order bits. Applications with particular
requirements should use a generator that is known to be sufficient for
their needs."

Note, in particular, that an implementation of rand() which always
returned 0 would satisfy all of the standard's applicable requirements.

As a practical matter, a uniform distribution over the range
[0,RAND_MAX] is fairly trivial to arrange, and can reasonably be
expected of any half-way serious implementation, even though the
standard fails to make any such guarantee. But don't expect anything
more than a uniform distribution.

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

#148013

On 11/11/2019 10:57 AM, James Kuyper wrote:
> On 11/11/19 5:44 AM, Chris M. Thomasson wrote:
> ...
>> ... Heck, is rand() even
>> guaranteed to return RAND_MAX at all? ...
> As the standard itself notes in footnote 295:
> "There are no guarantees as to the quality of the random sequence
> produced and some implementations are known to produce sequences with
> distressingly non-random low-order bits. Applications with particular
> requirements should use a generator that is known to be sufficient for
> their needs."
> 
> Note, in particular, that an implementation of rand() which always
> returned 0 would satisfy all of the standard's applicable requirements.
> 
> As a practical matter, a uniform distribution over the range
> [0,RAND_MAX] is fairly trivial to arrange, and can reasonably be
> expected of any half-way serious implementation, even though the
> standard fails to make any such guarantee. But don't expect anything
> more than a uniform distribution.
> 

Nice. Fwiw, check this out:

https://youtu.be/7n8LNxGbZbs

This should be kept in an isolation booth and just spit out nibbles... ;^)

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

#148203

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:

> On 11/8/2019 8:59 PM, Tim Rentsch wrote:
>
>> 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.
>
> Fwiw, off topic wrt integers, a while ago I just used an epsilon to
> deal with random intervals wrt rand().  Sometimes RAND_MAX does not get
> hit often enough for my needs, so I adjusted epsilon.  Heck, is rand()
> even guaranteed to return RAND_MAX at all?  [...]

Two comments.

One, if you want a random number generator with some guaranteed
minimal level of quality, don't use rand().  It's easy enough to
write a simple PRNG with an adequate minimal level of quality.

Two, if you want good floating-point values (of precision double
or higher), don't use rand().  The outputs of rand() are too
coarse to be a good source of 'double' values.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web