Changeset 6010
 Timestamp:
 Mar 9, 2007, 5:24:03 AM (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/ccl/level0/X86/x86numbers.lisp
r5966 r6010 137 137 (singlevaluereturn)) 138 138 139 #140 Date: Mon, 3 Feb 1997 10:04:08 0500141 To: infomcl@digitool.com, wineberg@franz.scs.carleton.ca142 From: dds@flavors.com (Duncan Smith)143 Subject: Re: More info on the random number generator144 Sender: ownerinfomcl@digitool.com145 Precedence: bulk146 139 147 The generator is a Linear Congruential Generator:148 140 149 X[n+1] = (aX[n] + c) mod m150 151 where: a = 16807 (Park&Miller recommend 48271)152 c = 0153 m = 2^31  1154 155 See: Knuth, Seminumerical Algorithms (Volume 2), Chapter 3.156 157 The period is: 2^31  2 (zero is excluded).158 159 What makes this generator so simple is that multiplication and addition mod160 2^n1 is easy. See Knuth Ch. 4.3.2 (2nd Ed. p 272).161 162 ab mod m = ...163 164 If m = 2^n1165 u = ab mod 2^n166 v = floor( ab / 2^n )167 168 ab mod m = u + v : u+v < 2^n169 ab mod m = ((u + v) mod 2^n) + 1 : u+v >= 2^n170 171 What we do is use 2b and 2n so we can do arithemetic mod 2^32 instead of172 2^31. This reduces the whole generator to 5 instructions on the 680x0 or173 80x86, and 8 on the 60x.174 175 Duncan176 177 #178 179 ;;; Use the two fixnums in state to generate a random fixnum >= 0 and < 65536180 ;;; Scramble those fixnums up a bit.181 182 (defun %nextrandomseed (state)183 (let* ((seed (dpb (ldb (byte 16 13) (%svref state 1))184 (byte 16 16)185 (ldb (byte 16 13) (%svref state 2)))))186 (multiplevaluebind (seedlow seedhigh) (%multiply seed (* 2 48271))187 (setq seed (logand #xffffffff (+ seedlow seedhigh)))188 (setf (%svref state 1) (ash (ldb (byte 16 16) seed) 13)189 (%svref state 2) (ash (ldb (byte 16 0) seed) 13))190 (dpb (ldb (byte 8 0) seedlow) (byte 8 8) (ldb (byte 8 3) seedhigh)))))191 141 192 142
Note: See TracChangeset
for help on using the changeset viewer.