From: Faré <fa...@gm...> - 2009-11-14 03:45:30
Attachments:
mt1993-addon.lisp
|
Dear sbcl developers, while trying to use independent sources of randomness at work, we realized that (make-random-state t) was actually not so random, since it was initializing the state from a 32-bit time in second. So when plenty of processes and threads starting at about the same time were expecting to each have different PRNG sources for identifiers, we instead had a lot of clashes as they were systematically generating the very same identifiers. Oops. Attached is a "hot patch" to SBCL that I am intending to use at work. It makes (make-random-state t) use /dev/urandom as a source of randomness (works on linux - I'm sure how to get the same effect portably), and accepts simple arrays of (unsigned-byte 8) or (unsigned-byte 32) as seeds for the random-state (massaging them somewhat if they are not long enough). Is there anything obviously wrong with it? Would it be OK to merge that into the official SBCL? I'm willing to work on it until it's in a shape to be accepted officially. I realize for instance that the intermediate function may notably have to be renamed, though I'm not sure what to. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Politics is the only profession that does without learning, probably because those who suffer from mistakes are not the same as those who make them. -- Achille Tournier, Pensées d'automne |
From: Nikodemus S. <nik...@ra...> - 2009-11-14 07:40:40
|
2009/11/14 Faré <fa...@gm...>: > Is there anything obviously wrong with it? Would it be OK to merge > that into the official SBCL? I'm willing to work on it until it's in a I commented on this on #lisp -- just wanted to repeat some the same things here so that people can better disagree if I have badwrong ideas. 0. I think accepting numbers and arrays as seeds is a good idea. I'm side-stepping the issue of whether reading from /dev/urandom like this is OK. I don't know -- but even if that part is omitted, users needing that can still do it and use it to initialize random-state via the new array-seed interface. 1. Comments. The array-mangling code needs to be commented: What does it do, and how do we know it does it properly? Is this a know algorithm, or something cooked up for the purpose? 2. Documentation. The extended public API should be documented in the MAKE-RANDOM-STATE docstring (or if there is a new public function, there.) Semi-unrelated things that I wonder about -- but which I don't think are make-or-break issues for this patch: * Should we expose the state vector to the user (even as a copy?): it would make saving random-states somewhat easier, I guess. * Should we document the "optimal" seed array-element-type and length? * Should we implement eg. Yarrow (cryptographically secure PRNG) for use-cases like yours -- and make it selectable using *RANDOM-STATE-ALGORITHM* or something? Or just as a contrib? Cheers, -- Nikodemus |
From: Sidney M. <si...@si...> - 2009-11-14 14:23:40
|
Faré wrote, On 14/11/09 4:45 PM: > Attached is a "hot patch" to SBCL that I am intending to use at work. > It makes (make-random-state t) use /dev/urandom as a source of > randomness (works on linux - I'm sure how to get the same effect > portably), and accepts simple arrays of (unsigned-byte 8) or > (unsigned-byte 32) as seeds for the random-state (massaging them > somewhat if they are not long enough). Is there a reason not to base it on the init_by_array and init_genrand functions in the original updated Mersenne Twister code at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c Or did you base it on the initialization in the newer SIMD version at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html which I have to admit I have not looked at enough to understand? |
From: Faré <fa...@gm...> - 2009-11-15 13:17:07
Attachments:
mt19937-hotpatch.lisp
|
Thanks to Nikodemus and Sydney for their feedback. Here is an updated version of my "hotpatch" following their advice. I have tried to document the code, make it conform to SBCL standards, and reuse the seeding algorithm used by the authors of MT19937. If it gets positive review, I will re-submit as an actual SBCL diff. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Those who do not understand Lisp are condemned to reinvent Unix, poorly. -- Faré, without apologies to Henry Spencer. |
From: Faré <fa...@gm...> - 2009-11-15 17:04:33
Attachments:
mrs.diff
|
After some positive feedback from IRC, here is my patch in git --diff format. Also included is an update to init-random-state to use the same algorithm as the upstream authors in their latest C source. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Suicidal terrorists may have short shelf lives. -- John McCarthy |
From: Faré <fa...@gm...> - 2009-11-17 16:38:17
Attachments:
0001-Add-support-for-non-trivial-random-seeds.patch
|
OK, so the file compiled at the REPL, but wasn't valid as SBCL source, since it was using #+/#- instead or #!+/#!- and sb-unix instead of sb!unix. Here's another patch that does pass sh make.sh and even cd tests ; sh run-tests.sh ! [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Lie, n.: A very poor substitute for the truth, but the only one discovered to date. |
From: Faré <fa...@gm...> - 2009-11-19 17:26:37
Attachments:
0001-Add-support-for-non-trivial-random-seeds.patch
|
OK, here is another attempt for my patch to SBCL's PRNG initialization. Once again, it compiles cleanly for me (on 1.0.32.30 on linux/amd64), and appears to pass run-tests.sh. The differences wrt previous patch are as follows: * my reviewer Dominic Schulz suggested I compare the output of my patch to what the upstream authors have. And I indeed found two bugs in my patch, one in the initialization of the counter (I left the old 1 instead of the new 624), and one in my reading of a C conditional (I read it as "min", it was "max"). * With the understanding of iterations as "max" of input length and N, I updated the code to NOT strip the input length to 19968 bits anymore. Mix as much noise as you want! * I moved a few defconstants up and created a deftype, so I could use a little more abstraction in the initialization algorithm (just in case anyone decides to implement the more general version of MT, or just the standard 64-bit variant). Here is the code I used to compare the output of the patched SBCL to that of the original authors: (defun print-random-state (&optional (x *random-state*)) (loop :with s = (random-state-state x) :for i :from 2 :below 627 :do (progn (format t "~10D " (aref s i)) (when (= 1 (mod i 5)) (terpri))))) (defparameter *random-state-1* (make-random-state 1234567)) (print-random-state *random-state-1*) (defparameter *random-state-2* (make-random-state (make-array 4 :element-type '(unsigned-byte 32) :initial-contents '(#x123 #x234 #x345 #x456)))) (print-random-state *random-state-2*) (let ((*random-state* (make-random-state *random-state-2*))) (format t "1000 outputs of genrand_int32()~%") (loop :for i :below 1000 :do (progn (format t "~10D " (random-chunk *random-state*)) (when (= 4 (mod i 5)) (terpri))))) And for the original authors, I modified the main function of their mt19937ar.c into: void print_state (void) { int i; int n; for(n=mti,i=-1;i<N;i++,n=mt[i]) { printf("%10lu ", n); if (i%5==3) printf("\n"); } } int main(void) { int i; unsigned long init[4]={0x123, 0x234, 0x345, 0x456}, length=4; printf("state of init_genrand(1234567UL);\n") ; init_genrand(1234567UL); print_state(); printf("\n\n") ; printf("state of init_by_array({0x123, 0x234, 0x345, 0x456}, 4);\n") ; init_by_array(init, leng\ th); print_state(); printf("\n\n") ; printf("1000 outputs of genrand_int32()\n"); for (i=0; i<1000; i++) { printf("%10lu ", genrand_int32()); if (i%5==4) printf("\n"); } return 0; } Please don't take my word for it and triple check as you apply the patch. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c Once again, many thanks to Nikodemus, Sydney, Christophe, Dominic and Adlai. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] The naturalistic fallacy: "if it's natural, it's good." The anti-naturalistic fallacy: "if it's natural, it's bad." The a-naturalistic fallacy: "nature has no relationship to good and bad." |
From: Faré <fa...@gm...> - 2009-11-29 23:12:34
Attachments:
0001-Add-support-for-non-trivial-random-seeds.patch
|
Hi, Congratulations to Christophe for having released 1.0.33! Is there any reason not to include my PRNG patch now that 1.0.33 is released? Anything I can improve upon? Tests I should run? Anyone I should bribe? Hope you had a happy thanksgiving / unthanksgiving. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] I find television very educating: Every time somebody turns on the set, I go into the other room and read a book. -- Groucho Marx 2009/11/19 Faré <fa...@gm...>: > OK, here is another attempt for my patch to SBCL's PRNG initialization. > > Once again, it compiles cleanly for me (on 1.0.32.30 on linux/amd64), > and appears to pass run-tests.sh. > > The differences wrt previous patch are as follows: > * my reviewer Dominic Schulz suggested I compare the output of my > patch to what the upstream authors have. And I indeed found two bugs > in my patch, one in the initialization of the counter (I left the old > 1 instead of the new 624), and one in my reading of a C conditional (I > read it as "min", it was "max"). > * With the understanding of iterations as "max" of input length and N, > I updated the code to NOT strip the input length to 19968 bits > anymore. Mix as much noise as you want! > * I moved a few defconstants up and created a deftype, so I could use > a little more abstraction in the initialization algorithm (just in > case anyone decides to implement the more general version of MT, or > just the standard 64-bit variant). > > Here is the code I used to compare the output of the patched SBCL to > that of the original authors: > (defun print-random-state (&optional (x *random-state*)) > (loop :with s = (random-state-state x) > :for i :from 2 :below 627 :do > (progn > (format t "~10D " (aref s i)) > (when (= 1 (mod i 5)) (terpri))))) > > (defparameter *random-state-1* (make-random-state 1234567)) > > (print-random-state *random-state-1*) > > (defparameter *random-state-2* > (make-random-state > (make-array 4 :element-type '(unsigned-byte 32) > :initial-contents '(#x123 #x234 #x345 #x456)))) > > (print-random-state *random-state-2*) > > (let ((*random-state* (make-random-state *random-state-2*))) > (format t "1000 outputs of genrand_int32()~%") > (loop :for i :below 1000 :do > (progn > (format t "~10D " (random-chunk *random-state*)) > (when (= 4 (mod i 5)) (terpri))))) > > And for the original authors, I modified the main function of their > mt19937ar.c into: > > void print_state (void) > { > int i; > int n; > for(n=mti,i=-1;i<N;i++,n=mt[i]) { > printf("%10lu ", n); > if (i%5==3) printf("\n"); > } > } > > int main(void) > { > int i; > unsigned long init[4]={0x123, 0x234, 0x345, 0x456}, length=4; > printf("state of init_genrand(1234567UL);\n") ; > init_genrand(1234567UL); print_state(); > printf("\n\n") ; > printf("state of init_by_array({0x123, 0x234, 0x345, 0x456}, > 4);\n") ; init_by_array(init, leng\ > th); print_state(); > printf("\n\n") ; > printf("1000 outputs of genrand_int32()\n"); > for (i=0; i<1000; i++) { > printf("%10lu ", genrand_int32()); > if (i%5==4) printf("\n"); > } > return 0; > } > > Please don't take my word for it and triple check as you apply the patch. > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c > > Once again, many thanks to Nikodemus, Sydney, Christophe, Dominic and Adlai. > > [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] > The naturalistic fallacy: "if it's natural, it's good." > The anti-naturalistic fallacy: "if it's natural, it's bad." > The a-naturalistic fallacy: "nature has no relationship to good and bad." |