Messages in this thread | | | Date | Sat, 23 Jan 1999 08:12:29 -0700 (MST) | From | Colin Plumb <> | Subject | Re: Random number generator for skiplists |
| |
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
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |