Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Bart, a tcc "issue"
Date: Sun, 10 Nov 2019 06:04:10 -0800
Organization: A noiseless patient Spider
Lines: 71
Message-ID: <868sonde05.fsf@linuxsc.com>
References: <uRIwF.17878$kE3.891@fx36.iad> <bYoxF.132400$Ko9.64189@fx48.iad> <86k189ejbd.fsf@linuxsc.com> <87sgmw3ajx.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="451385503b6e65ada0ba6f97513c8763"; logging-data="29901"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+rv/12FilAwFVXsAcgiyqVKuXW9ApefMU="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:JCk3kkISgZMOwkyTuP16pVDq1lQ= sha1:Ys/uYSOSic9ovGrtDk+0w1VcCSw=
Xref: csiph.com comp.lang.c: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.