Changeset 6006


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

Don't shift random seeds.

File:
1 edited

Legend:

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

    r5691 r6006  
    17171717         (low (ldb (byte 16 0) ticks)))
    17181718    (declare (fixnum high low))
    1719     (values (the fixnum (ash high (- 16 target::fixnum-shift)))
    1720             (the fixnum (ash low (- 16 target::fixnum-shift))))))
     1719    (values high low)))
    17211720
    17221721
     
    17371736     (t (report-bad-arg number '(or (integer (0)) (float (0.0)))))))
    17381737
    1739 (defun %bignum-random (number &optional state)
     1738
     1739#|
     1740Date: Mon, 3 Feb 1997 10:04:08 -0500
     1741To: info-mcl@digitool.com, wineberg@franz.scs.carleton.ca
     1742From: dds@flavors.com (Duncan Smith)
     1743Subject: Re: More info on the random number generator
     1744Sender: owner-info-mcl@digitool.com
     1745Precedence: bulk
     1746
     1747The generator is a Linear Congruential Generator:
     1748
     1749   X[n+1] = (aX[n] + c) mod m
     1750
     1751where: a = 16807  (Park&Miller recommend 48271)
     1752       c = 0
     1753       m = 2^31 - 1
     1754
     1755See: Knuth, Seminumerical Algorithms (Volume 2), Chapter 3.
     1756
     1757The period is: 2^31 - 2  (zero is excluded).
     1758
     1759What makes this generator so simple is that multiplication and addition mod
     17602^n-1 is easy.  See Knuth Ch. 4.3.2 (2nd Ed. p 272).
     1761
     1762    ab mod m = ...
     1763
     1764If         m = 2^n-1
     1765           u = ab mod 2^n
     1766           v = floor( ab / 2^n )
     1767
     1768    ab mod m = u + v                   :  u+v < 2^n
     1769    ab mod m = ((u + v) mod 2^n) + 1   :  u+v >= 2^n
     1770
     1771What we do is use 2b and 2n so we can do arithemetic mod 2^32 instead of
     17722^31.  This reduces the whole generator to 5 instructions on the 680x0 or
     177380x86, and 8 on the 60x.
     1774
     1775-Duncan
     1776
     1777|#
     1778
     1779#+64-bit-target
     1780(defun %next-random-pair (high low)
     1781  (let* ((n (nth-value
     1782             1
     1783             (%multiply 42871 (dpb (ldb (byte 15 0) high)
     1784                                      (byte 16 16)
     1785                                      (ldb (byte 16 0) low ))))))
     1786    (values (ldb (byte 16 16) n)
     1787            (ldb (byte 16 0) n))))
     1788
     1789(defun %next-random-seed (state)
     1790  (multiple-value-bind (high low) (%next-random-pair (%svref state 1)
     1791                                                     (%svref state 2))
     1792    (setf (%svref state 1) (ldb (byte 15 0) high)
     1793          (%svref state 2) low)
     1794    high
     1795    ))
     1796
     1797
     1798(defun %bignum-random (number state)
    17401799  (let* ((bits (+ (integer-length number) 8))
    17411800         (half-words (ash (the fixnum (+ bits 15)) -4))
Note: See TracChangeset for help on using the changeset viewer.