[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Random array (fwd)

Forwarded message:

> Date: Fri, 30 Oct 1998 08:53:20 -0800
> From: Jim Gillogly <[email protected]>
> Subject: Re: Random array (fwd)

> Jim Choate responded:
> > If I understand the process. Each array would cycle through in parallel
> > sorting 2 elements of each array. Once that was finished we'd then sort the
> > arrays themselves according to some process. From your description it seems
> > to imply that you're going to sort the 1st element descending at that point.
> > This in effect mis-orders each array after every sort.
> >
> > This sort of system is an IFS and could lead to determinism (ie a cycle of
> > sort patterns that repeat endlessly) or chaos (ie a pattern that doesn't
> > repeat). It in and of itself doesn't guarantee any randomness merely a
> > continously munged sort.
> I expressed myself badly.  Steve Gibbons posted a message
> to Coderpunks expressing more clearly what I had in mind:
> Fill up the high bits of your N words with random numbers and
> the low bits with an index from 0 to N-1.  Sort the array, then
> mask off the high bits.  If the random numbers were unique, you
> are left with a randomly shuffled array.

Ah, ok I think I have it.....

 So we start out with N words (2 bytes):

   0  1  2  ...  n-2 n-1 n
   *  *  *       *   *   *

 15...8 7...0
   rng   ind

So the ordering of bits 8-15 moves the originaly ordered indexes to
positions correlated to relative magnitude of the rng part.

That certainly looks like it'd work.

Thanks for the clarification.

       To know what is right and not to do it is the worst cowardice.


       The Armadillo Group       ,::////;::-.          James Choate
       Austin, Tx               /:'///// ``::>/|/      [email protected]
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-