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: Fri, 08 Nov 2019 20:59:34 -0800
Organization: A noiseless patient Spider
Lines: 59
Message-ID: <86k189ejbd.fsf@linuxsc.com>
References: <uRIwF.17878$kE3.891@fx36.iad> <bYoxF.132400$Ko9.64189@fx48.iad>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="bd07fdb0e7610947dc98257bdadc7724"; logging-data="3889"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+s2TPt+mEUSqbSFvbopo/kTQ5o+C2PuTM="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:uAzLsEegL9q4I5w2EuA0ug16thU= sha1:YuzzkwAVBE15QnAsWeePLp18S04=
Xref: csiph.com comp.lang.c: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.