uniform random distribution

[aegis]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

I consider the use of a table to keep track to be
a pretty idiotic approach though. Anyone have
another way of doing it, up their sleeve?

 

[osmium]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

I consider the use of a table to keep track to be
a pretty idiotic approach though. Anyone have
another way of doing it, up their sleeve?

What you ask for is not a random number. You might be interested in
shuffle, which you can find via google.

 

[Rouben Rostamian]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

I consider the use of a table to keep track to be
a pretty idiotic approach though. Anyone have
another way of doing it, up their sleeve?

Here is one way to do this. Make an array of "int a[n-m+1]" and
populate it with the numbers m, m+1, ... n in the usual order.
Then define a function shuffle_array() that receives that array
and shuffle its elements. Use the shuffled array as the source
for your "random numbers". Something like this should do:

void shuffle_array(int *a, size_t len)
{
size_t i;

for (i=len-1; i>1; i--) {
size_t j = myrand(i);
int tmp = a;
a = a[j];
a[j] = tmp;
}
}

Writing the function "size_t myrand(size_t n)" which returns
a random number in the range 0..(n-1) is left as an exercise.

 

[Michael Mair]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

I consider the use of a table to keep track to be
a pretty idiotic approach though. Anyone have
another way of doing it, up their sleeve?

This _is_ a pretty idiotic approach.
Use a builtin congruence generator of your own with
a long or exhausting cycle and store the last number
generated. If you are again at your starting number,
you need a new generator and have to rebuild your
user list.
Easier, but less opaque: Take a prime number p and
use a generating root (don't know the correct English
term) to iterate through 1 .. p-1.
Example: 11
5*5=25, 25%11=3
3*5=15, 15%11=4
4*5=20, 20%11=9
9*5=45, 45%11=1
->5,3,4,9,1(,5) looks random enough
7,5,2,3,10,4,6,9,8,1 is another

However, this is more a question for
comp.programming

If you have an algorithm and implemented it in C, you
can of course come back to expose it to our
criticism


Cheers
Michael

 

[Martin Ambuhl]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

Make an array initialized to have values
m, m+1, ..., n-1, n.
Shuffle the array.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

The strategy I suggested above is better than these.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

Obviously not. Further, the rand() % N method is not recommended at
all. See <http://www.eskimo.com/~scs/C-faq/q13.16.html>.

 

[CBFalconer]

What you ask for is not a random number. You might be interested
in shuffle, which you can find via google.

I don't think this introduces bias, but lets try:

typedef struct item {
size_t index;
long random;
} item;

intem *itemarray;
size_t i;

itemarray = malloc((m-n) * sizeof *itemarray);
....

while (something) {
for (i = 0; i < (m-n); i++) {
itemarray.index = i + (m-n);
itemarray.random = rand;
}
/* sort *itemarray on the random field */
....
for (i = 0; i < (m-n); i++) {
/* use the non-recurring value in itemarray.index */
}
....
}
free(itemarray);

which has only one call to rand per item, and no need to worry
about the value of RAND_MAX. There is no need to set the index
field after the first use. The sort is operating on integers so it
can be very fast, especially if a layer of indirection is added by
an array of pointers to item. Quicksort (not qsort()) is probably
suitable here.

 

[Lawrence Kirby]

I don't think this introduces bias, but lets try:

typedef struct item {
size_t index;
long random;
} item;

intem *itemarray;
size_t i;

itemarray = malloc((m-n) * sizeof *itemarray);

From the problem spec. I would expect n to be larger than m.

....

while (something) {
for (i = 0; i < (m-n); i++) {
itemarray.index = i + (m-n);

i + n (or i + m)?

itemarray.random = rand;
rand()

}
/* sort *itemarray on the random field */
....
for (i = 0; i < (m-n); i++) {
/* use the non-recurring value in itemarray.index */
}
....
}
free(itemarray);

which has only one call to rand per item, and no need to worry
about the value of RAND_MAX.

There is possible bias here in the case of equal .random values.
Depending on the values of RAND_MAX and the size of the range having such
collisions may be likely. In that case the final positions will depend in
some fashion on the initial ordering.

....

Lawrence

 

[Julian V. Noble]

is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?

Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.

I could build a table I suppose as I call
rand and any number in that table already
can be ignored. So I can sit and call rand
until I get the desired number that is not yet
in the list.

So if I want (inclusive) 0..3
then imagine rand() % (3 + 1) working as desired.

I consider the use of a table to keep track to be
a pretty idiotic approach though. Anyone have
another way of doing it, up their sleeve?

You are shuffling. Jon Bentley's book, "Programming Pearls", discusses
both how (and why!) to do it.


--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the
toothache patiently."

-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.