Changeset 6010


Ignore:
Timestamp:
Mar 9, 2007, 5:24:03 AM (13 years ago)
Author:
gb
Message:

Do %next-random-seed more portably.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/ccl/level-0/X86/x86-numbers.lisp

    r5966 r6010  
    137137  (single-value-return))
    138138 
    139 #|
    140 Date: Mon, 3 Feb 1997 10:04:08 -0500
    141 To: info-mcl@digitool.com, wineberg@franz.scs.carleton.ca
    142 From: dds@flavors.com (Duncan Smith)
    143 Subject: Re: More info on the random number generator
    144 Sender: owner-info-mcl@digitool.com
    145 Precedence: bulk
    146139
    147 The generator is a Linear Congruential Generator:
    148140
    149    X[n+1] = (aX[n] + c) mod m
    150 
    151 where: a = 16807  (Park&Miller recommend 48271)
    152        c = 0
    153        m = 2^31 - 1
    154 
    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 mod
    160 2^n-1 is easy.  See Knuth Ch. 4.3.2 (2nd Ed. p 272).
    161 
    162     ab mod m = ...
    163 
    164 If         m = 2^n-1
    165            u = ab mod 2^n
    166            v = floor( ab / 2^n )
    167 
    168     ab mod m = u + v                   :  u+v < 2^n
    169     ab mod m = ((u + v) mod 2^n) + 1   :  u+v >= 2^n
    170 
    171 What we do is use 2b and 2n so we can do arithemetic mod 2^32 instead of
    172 2^31.  This reduces the whole generator to 5 instructions on the 680x0 or
    173 80x86, and 8 on the 60x.
    174 
    175 -Duncan
    176 
    177 |#
    178 
    179 ;;; Use the two fixnums in state to generate a random fixnum >= 0 and < 65536
    180 ;;; Scramble those fixnums up a bit.
    181 
    182 (defun %next-random-seed (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     (multiple-value-bind (seed-low seed-high) (%multiply seed (* 2 48271))
    187       (setq seed (logand #xffffffff (+ seed-low seed-high)))
    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) seed-low) (byte 8 8) (ldb (byte 8 3) seed-high)))))
    191141
    192142
Note: See TracChangeset for help on using the changeset viewer.