Skip lists are a handy data structure, but the fact that the nodes

are variable-sized is something of an implementation hassle.

An RNG for the purpose is not hard to concoct; George Marsaglia

recently posted some good building blocks to a few relevant newsgroups

(sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physics).

Here's his KISS (keep it simple, stupid) generator.

All variables are 32-bit quantities. You can use any of the

three sub-generators as well.

static unsigned z=362436069, w=521288629, jsr=123456789, jcong=380116160;

/* Any non-zero seeds will do */

#define znew ((z=36969*(z&65535)+(z>>16))<<16)

#define wnew ((w=18000*(w&65535)+(w>>16))&65535)

#define MWC (znew+wnew)

#define SHR3 (jsr ^= jsr<<17, jsr ^= jsr>>13, jsr ^= jsr<<5)

#define CONG (jcong=69069*jcong+1234567)

#define KISS ((MWC^CONG)+SHR3)

He also has some longer-period table-driven generators.

--

-Colin