randomizing integers

[Mantorok Redgormor]

Not sure if this is possible, but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive) without
using rand() and in standard C?

 

[Mike Wahler]

Not sure if this is possible, but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive) without
using rand() and in standard C?

If you write your own random number generator function
using only standard C, then yes, sure.

Why can't you use 'rand()'?

-Mike

 

[Default User]

Not sure if this is possible, but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive) without
using rand() and in standard C?

I'm not sure why the restriction, but search the web for PRN generators
in C. The Mersenne Twister may fit the bill for you.




Brian Rodenborn

 

[Keith Thompson]

If you write your own random number generator function
using only standard C, then yes, sure.

Why can't you use 'rand()'?

Possibly because implementations of rand() tend to be poor.

 

[pete]

Not sure if this is possible, but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive) without
using rand() and in standard C?

/* BEGIN new.c */

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

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101

void shuffle(int *, int, long unsigned*);

int main(void)
{
int deck[CARDS_IN_DECK] = {0};
long unsigned seed = LU_RAND_SEED;
int counter;

shuffle(deck, CARDS_IN_DECK, &seed);
counter = CARDS_IN_DECK;
while (counter--) {
printf("%d\n", deck[counter]);
}
return 0;
}

void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

/* END new.c */

 

[Irrwahn Grausewitz]

#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437) [...]
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

Remark #1:
If the OP's intention was to avoid rand() because of its poor
quality (in some, maybe most) implementations, I don't think
the above algorithm is a great improvement.

Remark #2:
The quality of the builtin rand() function can be improved by
not using the (one or two) least significant bits of the
pseudo-random numbers it produces.

Remark #3:
If a special distribution of numbers is required, there are a
lot of RNGs freely available on the web.

Regards,

Irrwahn

 

[pete]

#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437) [...]
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

Remark #1:
If the OP's intention was to avoid rand() because of its poor
quality (in some, maybe most) implementations, I don't think
the above algorithm is a great improvement.

Remark #2:
The quality of the builtin rand() function can be improved by
not using the (one or two) least significant bits of the
pseudo-random numbers it produces.

Remark #3:
If a special distribution of numbers is required, there are a
lot of RNGs freely available on the web.

Except that, you have invented OP's reason.
One reason to code your own rand, is to make a program portable.
The rand macro in the above program serves that purpose.

 

[Mantorok Redgormor]

Not sure if this is possible, but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive) without
using rand() and in standard C?

/* BEGIN new.c */

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

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101

void shuffle(int *, int, long unsigned*);

int main(void)
{
int deck[CARDS_IN_DECK] = {0};
long unsigned seed = LU_RAND_SEED;
int counter;

shuffle(deck, CARDS_IN_DECK, &seed);
counter = CARDS_IN_DECK;
while (counter--) {
printf("%d\n", deck[counter]);
}
return 0;
}

void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

/* END new.c */

Perfect. Just one question though, how did you come up with a seed
that would produce a remainder with no duplicates between 1 and 100
inclusive?

Thanks for the responses


- nethlek

 

[Arthur J. O'Dwyer]

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

Perfect. Just one question though, how did you come up with a seed
that would produce a remainder with no duplicates between 1 and 100
inclusive?

Hmm... Well, the LCRNG pete used (69069*x + (2*c+1)) does have the
full period of all 2^32 (or whatever) values, according to "Theorem A"
on this web page

http://www.cz3.nus.edu.sg/~yzchen/teach/comphys/sec03.html

But you seem to be under the impression that the values yielded by
the expression LU_RAND(*seed) % (i + 1) will "cycle through"
the range [0..101) exactly once, and that's just false. Luckily,
pete's algorithm doesn't rely on that.

The algorithm is an "insertion un-sort": you pick a random position
in the current list, insert the new value there, and move the old
value at that position to the end of the list. AFAICT it's a
perfectly good scrambling algorithm.

HTH,
-Arthur

(pete: What if (r==i)? Undefined behavior caused by accessing
array[r] before a value has been stored there... ;-))

 

[Peter Nilsson]

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

....
(pete: What if (r==i)?

Doesn't matter

Undefined behavior caused by accessing array[r] before a value has been stored
there... ;-))

This is allowed since the old value is being used to calculate the new one,
albeit the same value. It's no different to x = x;

Perhaps you're thinking of cases like...

array[array] = x;

....where array == i, which is undefined.

 

[Peter Nilsson]

Possibly because implementations of rand() tend to be poor.

Kind of catch-22 for implementors. Why waste time building a serious rand()
when virtually anyone who has a serious use for it will generally ignore it!

 

[pete]

pete wrote:

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101

void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

...
(pete: What if (r==i)?

Doesn't matter

Undefined behavior caused by accessing array[r]
before a value has been stored
there... ;-))

This is allowed since the old value is being
used to calculate the new one,
albeit the same value. It's no different to x = x;

(x = x) is undefined behavior if x is uninitialized.

The problem was addressed by this line of code:

int deck[CARDS_IN_DECK] = {0};

which Arthur snipped.

 

[lawrence.jones]

Possibly because implementations of rand() tend to be poor.

I think it's more accurate to say that one particular (popular)
implementation's rand() was so spectacularly poor that it's been burned
into peoples' memories (and now gone down in history) that you shouldn't
trust it.

-Larry Jones

We seem to be out of gun powder. -- Calvin

 

[pete]

Mantorok Redgormor wrote:

Not sure if this is possible,
but is there some way to randomize a set
of integers from 0 to n(more specifically 0 to 100 inclusive)
without using rand() and in standard C?

#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437) [...]
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

One reason to code your own rand, is to make a program portable.
The rand macro in the above program serves that purpose.

It falls short of the portability mark.

#define LU_RAND(S) ((S) = (69069 * (S) + 362437) & 0xffffffff)

would make LU_RAND(S) portable.

 

[Barry Schwarz]

pete wrote:

/**
#define LU_RAND_SEED (long unsigned)time(0)
/*/
#define LU_RAND_SEED 123456789LU
/**/
#define LU_RAND(S) ((S) = 69069 * (S) + 362437)

#define CARDS_IN_DECK 101

void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
}

...
(pete: What if (r==i)?

Doesn't matter

Undefined behavior caused by accessing array[r] before a value has been stored
there... ;-))

This is allowed since the old value is being used to calculate the new one,
albeit the same value. It's no different to x = x;

If x has never been initialized with a value, then the code invokes
undefined behavior since it does try to evaluate x before assigning
that value to x.

Perhaps you're thinking of cases like...

array[array] = x;

...where array == i, which is undefined.

Why do you think this is undefined? array evaluates properly to i
so array[array] also evaluates properly to the i-th element of the
array into which the current value of x is stored.


<<Remove the del for email>>

 

[pete]

pete wrote:
void shuffle(int *array, int n, long unsigned* seed)
{
int i, r;

for (i = 1; n > i; ++i) {
r = LU_RAND(*seed) % (i + 1);
array = array[r];
array[r] = i;
}
} ...
(pete: What if (r==i)?
Undefined behavior caused by accessing array[r]
before a value has been stored
there... ;-))

(x = x) is undefined behavior if x is uninitialized.

The problem was addressed by this line of code:

int deck[CARDS_IN_DECK] = {0};

The following definition, is the way that I have shuffle()
archived in my collection of toy programs:

void shuffle(int *array, int n)
{
int i, r;

array[0] = 0;
for (i = 1; n > i; ++i) {
r = rand() % (i + 1);
array = 0;
array = array[r];
array[r] = i;
}
}

I altered shuffle() for this post
and I should have commented the code
about the special array requirements
which arose from the removal of the zero value assignments.
The first element of the array needs to be zero.
That is most obvious for the case when n equals 1.
The rest of the elements also need to be initialized,
though the specific values don't matter.

I don't think that I needed to comment what the function does
nor that array should be a pointer to the first element
of an int array, with at least n elements.

 

[Peter Nilsson]

On Sun, 28 Sep 2003 11:22:04 +1000, "Peter Nilsson"

Perhaps you're thinking of cases like...

array[array] = x;

...where array == i, which is undefined.

Why do you think this is undefined? array evaluates properly to i
so array[array] also evaluates properly to the i-th element of the
array into which the current value of x is stored.

6.5p2:

Between the previous and next sequence point an object shall have its
stored value modified at most once by the evaluation of an expression.
Furthermore, the prior value shall be read only to determine the value
to be stored.

The expression violates the second sentence. The value of array is *not*
being used to compute the *new* value of array. Instead, it is being used
to derive an lvalue. Other requirements aside, the expression is fine so
long as array is not i.

I recall there was some discussion in comp.std.c about what kinds of
implementations would actually have a problem with this. I don't think
anyone found an actual implementation, but it wasn't thought to be totally
beyond the realms of possibility either.