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

Groups > comp.lang.c > #21572

Re: useful macros

Show all headers | View raw

"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnmx4pgogp.fsf@nuthaus.mib.org...
> "BartC" <bc@freeuk.com> writes:
> [...]
>> I use a function random(a..b) which returns a random integer from a to b
>> inclusive (in a scripting language, but it calls C's rand()).
>>
>> I've just tested this, and over a large number of calls, it seems to
>> produce
>> a uniform distribution down to 0.001% and better. (And it doesn't know
>> what
>> RAND_MAX is except that it might be as low as 32767.)
> [...]
>
> Does it perform multiple calls to rand() in some cases?

Yes (two calls each time). Just to guarantee enough bits to play with. The
distribution might not be ideal, but it works reasonably well and it's easy
enough to add some variability if needed.

> If not, it's not possible to get a completely uniform distribution, a
> problem that might be difficult to see on a system with, say, RAND_MAX
> == 2147483647.
>
> For example, if RAND_MAX==32767, then there are exactly 32768 equally
> likely results from rand(). random(0..30000), if it depends on a single
> call to rand(), will return some results twice as often as others;
> random(0..40000) cannot return all possible results.

Yes; the basic calculation, for a range of a..b, is rand()%(b-a+1)+a. Since
it uses a remainder operation, you might expect some results to appear more
often than others, and this test shows that:

#include <stdio.h>
#include <stdlib.h>

int main(void){
#define M 100000000
#define N 30000
int counts[N]={0};
int i,j,k,r;

for (k=1; k<=M; ++k) {
 r=rand();
 ++counts[r%N];
}

for (i=0; i<15; ++i)
  printf("%d: %d Dev: %d\n",i,counts[i], counts[i]-(M/N));

puts("...");

for (i=N-15; i<N; ++i)
  printf("%d: %d Dev: %d\n",i,counts[i], counts[i]-(M/N));
}

But change the r=rand() line to r=rand()<<15 | rand(), and deviation on each
count is far more variable. So it's just necessary to make sure the a..b
range is much smaller than the range of the rand() function. And quite often
you will only need a narrow range.

-- 
Bartc 

Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

useful macros Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-26 13:08 -0700
  Re: useful macros winndy <jiaoyk@gmail.com> - 2012-05-29 20:26 -0700
    Re: useful macros Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-30 00:47 -0700
      Re: useful macros Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-05-30 16:45 +0100
        Re: useful macros James Kuyper <jameskuyper@verizon.net> - 2012-05-30 13:10 -0400
          Re: useful macros Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-05-30 21:54 +0100
          Re: useful macros "BartC" <bc@freeuk.com> - 2012-05-30 23:24 +0100
            Re: useful macros James Kuyper <jameskuyper@verizon.net> - 2012-05-30 18:55 -0400
              Re: useful macros "BartC" <bc@freeuk.com> - 2012-05-31 00:45 +0100
            Re: useful macros Keith Thompson <kst-u@mib.org> - 2012-05-30 17:53 -0700
              Re: useful macros "BartC" <bc@freeuk.com> - 2012-05-31 10:29 +0100

csiph-web