Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Bart, a tcc "issue" Date: Thu, 28 Nov 2019 16:03:10 -0800 Organization: A noiseless patient Spider Lines: 78 Message-ID: <86r21r8s75.fsf@linuxsc.com> References: <86k189ejbd.fsf@linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="81b92e3fa8397acac1ab5cf195ff75cd"; logging-data="8012"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19L1lQpceOpC4WpU16uhDiuzN+Qyp/+TiI=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:isZCCEPdEtI8S4fJpk5DA7VSKAk= sha1:uaSsnJY4b3wKqtkpHE2abVpFmuc= Xref: csiph.com comp.lang.c:148203 "Chris M. Thomasson" writes: > On 11/8/2019 8:59 PM, Tim Rentsch wrote: > >> Richard Damon 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.