lkml.org 
[lkml]   [1999]   [Jan]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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/

\
 
 \ /
  Last update: 2005-03-22 13:49    [W:0.026 / U:0.356 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site