From: Jim Choate <ravage@EINSTEIN.ssz.com>
Date: Sat, 31 Oct 1998 02:10:47 +0800
To: cypherpunks@EINSTEIN.ssz.com (Cypherpunks Distributed Remailer)
Subject: Re: Random array (fwd)
Message-ID: <199810301748.LAA25557@einstein.ssz.com>
MIME-Version: 1.0
Content-Type: text



Forwarded message:

> Date: Fri, 30 Oct 1998 08:53:20 -0800
> From: Jim Gillogly <jim@acm.org>
> 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.

                                                     Confucius

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