Changeset 13323
 Timestamp:
 Dec 22, 2009, 5:11:10 AM (10 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/newrandom/level0/l0numbers.lisp
r13314 r13323 1806 1806 ;;; too bad in a 64bit CCL, but the generator pretty much has to be 1807 1807 ;;; in LAP for 32bit ports. 1808 # x86target1808 #(or x8632target ppc32target x8664target) 1809 1809 (defun %mrg31k3p (state) 1810 1810 (let* ((v state)) … … 1845 1845 (declaim (inline %16randombits))) 1846 1846 1847 #x86target1848 1847 (defun %16randombits (state) 1849 (%nextrandomseed state)) 1850 1851 #+x86target 1852 (defun %16randombits (state) 1853 (logand #xffff (the fixnum (%mrg31kp3 state)))) 1848 (logand #xffff (the fixnum (%mrg31k3p state)))) 1854 1849 1855 1850 #+64bittarget … … 1862 1857 (fastmod (logior low (the fixnum (ash high 30))) 1863 1858 number))) 1864 1865 #1866 Date: Mon, 3 Feb 1997 10:04:08 05001867 To: infomcl@digitool.com, wineberg@franz.scs.carleton.ca1868 From: dds@flavors.com (Duncan Smith)1869 Subject: Re: More info on the random number generator1870 Sender: ownerinfomcl@digitool.com1871 Precedence: bulk1872 1873 The generator is a Linear Congruential Generator:1874 1875 X[n+1] = (aX[n] + c) mod m1876 1877 where: a = 16807 (Park&Miller recommend 48271)1878 c = 01879 m = 2^31  11880 1881 See: Knuth, Seminumerical Algorithms (Volume 2), Chapter 3.1882 1883 The period is: 2^31  2 (zero is excluded).1884 1885 What makes this generator so simple is that multiplication and addition mod1886 2^n1 is easy. See Knuth Ch. 4.3.2 (2nd Ed. p 272).1887 1888 ab mod m = ...1889 1890 If m = 2^n11891 u = ab mod 2^n1892 v = floor( ab / 2^n )1893 1894 ab mod m = u + v : u+v < 2^n1895 ab mod m = ((u + v) mod 2^n) + 1 : u+v >= 2^n1896 1897 What we do is use 2b and 2^n so we can do arithemetic mod 2^32 instead of1898 2^31. This reduces the whole generator to 5 instructions on the 680x0 or1899 80x86, and 8 on the 60x.1900 1901 Duncan1902 1903 #1904 1905 #+(and 32bittarget (not x86target))1906 (defun %nextrandomseed (state)1907 (multiplevaluebind (high low) (%nextrandompair (random.seed1 state)1908 (random.seed2 state))1909 (declare (type (unsignedbyte 15) high)1910 (type (unsignedbyte 16) low))1911 (setf (random.seed1 state) high1912 (random.seed2 state) low)1913 (logior high (thes fixnum (logand low (ash 1 15))))))1914 1859 1915 1860 ;;; When using a dead simple random number generator, it's reasonable … … 1958 1903 (* number ratio))) 1959 1904 1960 #+(and 32bittarget (not x86target))1961 (defun random (number &optional (state *randomstate*))1962 (if (not (typep state 'randomstate)) (reportbadarg state 'randomstate))1963 (cond1964 ((and (fixnump number) (> (the fixnum number) 0))1965 (locally (declare (fixnum number))1966 (if (< number 65536)1967 (fastmod (%nextrandomseed state) number)1968 (let* ((n 0)1969 (nhalf (ash (+ 15 (integerlength number)) 4)))1970 (declare (fixnum n nhalf))1971 (dotimes (i nhalf (fastmod n number))1972 (setq n (logior (the fixnum (ash n 16))1973 (the fixnum (%nextrandomseed state)))))))))1974 ((and (typep number 'doublefloat) (> (the doublefloat number) 0.0))1975 (%floatrandom number state))1976 ((and (typep number 'shortfloat) (> (the shortfloat number) 0.0s0))1977 (%floatrandom number state))1978 ((and (bignump number) (> number 0))1979 (%bignumrandom number state))1980 (t (reportbadarg number '(or (integer (0)) (float (0.0)))))))1981 1982 #+x86target1983 1905 (defun random (number &optional (state *randomstate*)) 1984 1906 (if (not (typep state 'randomstate)) (reportbadarg state 'randomstate))
Note: See TracChangeset
for help on using the changeset viewer.