From: Lutz Euler <leuler@us...>  20120501 13:58:48

The branch "master" has been updated in SBCL: via 18911695a5625fc908b8c07e97d33bf54749a962 (commit) from ef61e6c46ca429b84a61e90efcd7ac11261f92c7 (commit)  Log  commit 18911695a5625fc908b8c07e97d33bf54749a962 Author: Lutz Euler <lutz.euler@...> Date: Tue May 1 15:57:03 2012 +0200 Fix the DEFTRANSFORM of RANDOM for hairy integer types. With integer types that are neither an interval nor a single known value the DEFTRANSFORM used to generate an expression that had two problems: First, it yielded very uneven distributions of random values for most arguments to RANDOM that are not very small. Second, it used a too small RANDOMCHUNK under 64 bits word size thus never generating numbers larger than (1 (EXPT 2 32)) even if RANDOM's argument was larger than (EXPT 2 32). Fix this by giving up the transform in these cases. Add a new file "tests/random.pure.lisp" containing tests for this.  src/compiler/floattran.lisp  3 + tests/random.pure.lisp  62 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+), 1 deletions() diff git a/src/compiler/floattran.lisp b/src/compiler/floattran.lisp index 3efdaa1..8d2eaed 100644  a/src/compiler/floattran.lisp +++ b/src/compiler/floattran.lisp @@ 97,7 +97,8 @@ ;; KLUDGE: a relatively conservative treatment, but better ;; than a bug (reported by PFD sbcldevel towards the end of ;; 200411.  '(rem (randomchunk (or state *randomstate*)) num)))) + (giveupir1transform + "Argument type is too complex to optimize for.")))) ;;;; float accessors diff git a/tests/random.pure.lisp b/tests/random.pure.lisp new file mode 100644 index 0000000..ef0f398  /dev/null +++ b/tests/random.pure.lisp @@ 0,0 +1,62 @@ +;;;; various RANDOM tests without side effects + +;;;; This software is part of the SBCL system. See the README file for +;;;; more information. +;;;; +;;;; While most of SBCL is derived from the CMU CL system, the test +;;;; files (like this one) were written from scratch after the fork +;;;; from CMU CL. +;;;; +;;;; This software is in the public domain and is provided with +;;;; absolutely no warranty. See the COPYING and CREDITS files for +;;;; more information. + +(inpackage :cluser) + +;;; Tests in this file that rely on properties of the distribution of +;;; the random numbers are designed to be fast and have a very low +;;; probability of false positives, generally of the order of (expt 10 60). +;;; These tests are not intended to assure the statistical qualities of the +;;; pseudo random number generator but to help find bugs in its and RANDOM's +;;; implementation. + +;; When the type of the argument of RANDOM is a set of integers, a +;; DEFTRANSFORM triggered that simply generated (REM (RANDOMCHUNK) NUM), +;; which has two severe problems: The resulting distribution is very uneven +;; for most arguments of RANDOM near the size of a random chunk and the +;; RANDOMCHUNK used was always 32 bits, even under 64 bit wordsize which +;; yields even more disastrous distributions. +(withtest (:name (:random :integer :setofintegers :distribution)) + (let* ((high (floor (expt 2 33) 3)) + (mid (floor high 2)) + (fun (compile nil `(lambda (x) + (random (if x ,high 10))))) + (n1 0) + (n 10000)) + (dotimes (i n) + (when (>= (funcall fun t) mid) + (incf n1))) + ;; Half of the values of (RANDOM HIGH) should be >= MID, so we expect + ;; N1 to be binomially distributed such that this distribution can be + ;; approximated by a normal distribution with mean (/ N 2) and standard + ;; deviation (* (sqrt N) 1/2). The broken RANDOM we are testing here for + ;; yields (/ N 3) and (* (sqrt N) (sqrt 2/9)), respectively. We test if + ;; N1 is below the average of (/ N 3) and (/ N 2). With a value of N of + ;; 10000 this is more than 16 standard deviations away from the expected + ;; mean, which has a probability of occurring by chance of below + ;; (expt 10 60). + (when (< n1 (* n 5/12)) + (error "bad RANDOM distribution: expected ~d, got ~d" (/ n 2) n1)))) + +(withtest (:name (:random :integer :setofintegers :chunksize)) + (let* ((high (expt 2 64)) + (fun (compile nil `(lambda (x) + (random (if x ,high 10))))) + (n 200) + (x 0)) + (dotimes (i n) + (setf x (logior x (funcall fun t)))) + ;; If RANDOM works correctly, x should be #b111...111 (64 ones) + ;; with a probability of 1 minus approximately (expt 2 194). + (unless (= x (1 high)) + (error "bad RANDOM distribution: ~16,16,'0r" x))))  hooks/postreceive  SBCL 