Velocity Reviews > useful macros

# useful macros

BartC
Guest
Posts: n/a

 05-31-2012

"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "BartC" <(E-Mail Removed)> 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