[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Torben Hoffmann]

(Re-send to list due to mail address change on gmail)

On Fri, May 28, 2010 at 08:42, Håkan Huss <huss01@REDACTED> wrote:

> 2010/5/28 Richard O'Keefe <ok@REDACTED>
>
> >
> > On May 28, 2010, at 1:12 AM, Björn-Egil Dahlberg wrote:
> >
> >> Is there no need for assigning unique numbers to the list when sorting
> it?
> >> I guess it boils down to how fair we want the list to be unsorted (or
> how
> >> one wants to word it).
> >>
> >
> > If we really had something generating 53-bit random floats,
> > the changes that a million-element list would get at least one
> > duplicate would be
> >        1 - (1 - 2**-53)**1,000,000
> > or roughly 2**-33.  Or put it another way: stop worrying.  The
> > RNG that Erlang uses has worse problems than that.  It was
> > great for its purpose in Quintus Prolog >25 years ago, but it
> > has long since been surpassed.
> >
>
> Even though I used random:uniform/2 in the example I posted, any serious
> use
> of random numbers should use the RNG functions in the crypto module
> instead.
> For the "tag and sort", use crypto:rand_bytes/1 and you can choose how many
> random bits you want the tag to have (and thus the probability of
> collision). For instance, tagging with crypto:rand_bytes(7) will get you a
> 56 bit random binary with good quality.
>
> Regards.
> /Håkan
>

Ah, you just happened to touch one of my pet peeves here!

The crypto module is great - for server installations. If you want to
distribute an application that needs crypto functionality you have to figure
out how to package the OpenSSL library as well (just correct me if I am
wrong).

To surpass that problem I have created a RNG based on a SHA function
including the proper seeding - see
http://github.com/lehoff/cryptographicfor some of the initial code.
WARNING: THAT CODE IS WORK IN PROGRESS, but the RNG seems to work.
The seeding is the only thing that requires some C code, but that is so
little that it is easy to write it up for the most popular platforms and
then add new platforms in case the application becomes popular.

So the code is in Erlang plus a C port - that seems easier to ship than the
crypto application + OpenSSL, but I could be mistaken.

Cheers,
Torben

-- 
http://www.linkedin.com/in/torbenhoffmann