[104793] in Cypherpunks
RE:
daemon@ATHENA.MIT.EDU (Stephen Dennis)
Wed Oct 28 21:11:15 1998
From: Stephen Dennis <sdennis@svdltd.com>
To: coderpunks@toad.com
Date: Wed, 28 Oct 1998 16:56:15 -0800
Reply-To: Stephen Dennis <sdennis@svdltd.com>
If you are trying to make every element in the original array A equally
likely to occur in any position of the final array A, then your snippet
doesn't work ... regardless of SWAP_TIMES.
Try this instead:
#define NELEMENTS 256
A[NELEMENTS];
for (int i = 0; i < NELEMENTS-1; i++)
{
for (int j = i+1; j < NELEMENTS; j++)
{
int x = getrand2(j)
swap(A[i],A[x]);
}
}
A crude getrand2 is:
#define getrand2(x) (getrand()%(x))
but that doesn't have a flat distribution unless the maximum range of
getrand() is divisable by (x+1)....blah blah blah.
Here's a better one:
int getrand2(int x)
{
long n;
if (x <= 0)
return -1;
do
{
n = random(); // returns an evenly-distributed
psuedo-random number on [0,LONG_MAX]
} while (LONG_MAX - n < x);
return (n % x);
}
-----Original Message-----
From: Anonymous [mailto:nobody@replay.com]
Sent: Wednesday, October 28, 1998 3:32 PM
To: coderpunks@toad.com
Subject:
In the following snippet of pseudo-code, what should the value of
SWAP_TIMES be to make the array A[] random, assuming
that getrand() returned a truly random integer between
0 and 255
A[256];
for(i=0;i<SWAP_TIMES;i++){
x=getrand();
y=getrand();
swap(A[x],A[y]);
}
Thanks
