* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id @ 2011-07-18 16:42 Leo 2011-07-19 14:57 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-18 16:42 UTC (permalink / raw) To: 9118; +Cc: Lars Magne Ingebrigtsen Function message-unique-id seeds the RNG every time it runs and relies on its undocumented return value. Should something like this be applied? --- a/message.el +++ b/message.el @@ -5484,7 +5484,8 @@ ;; Don't use microseconds from (current-time), they may be unsupported. ;; Instead we use this randomly inited counter. (setq message-unique-id-char - (% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20))))) + (% (1+ (or message-unique-id-char + (logand (random most-positive-fixnum) (1- (lsh 1 20))))) ;; (current-time) returns 16-bit ints, ;; and 2^16*25 just fits into 4 digits i base 36. (* 25 25))) Diff finished. Tue Jul 19 00:34:45 2011 Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-18 16:42 bug#9118: 23.3.50; Don't seed the RNG in message-unique-id Leo @ 2011-07-19 14:57 ` Lars Magne Ingebrigtsen 2011-07-19 15:14 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-07-19 14:57 UTC (permalink / raw) To: Leo; +Cc: 9118 Leo <sdl.web@gmail.com> writes: > Function message-unique-id seeds the RNG every time it runs and relies > on its undocumented return value. Should something like this be applied? > > --- a/message.el > +++ b/message.el > @@ -5484,7 +5484,8 @@ > ;; Don't use microseconds from (current-time), they may be unsupported. > ;; Instead we use this randomly inited counter. > (setq message-unique-id-char > - (% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20))))) > + (% (1+ (or message-unique-id-char > + (logand (random most-positive-fixnum) (1- (lsh 1 20))))) Unfortunately, Emacs doesn't seed itself on startup, so (random x) will return the same thing every time you start Emacs. So I don't think changing this is appropriate at this time. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-19 14:57 ` Lars Magne Ingebrigtsen @ 2011-07-19 15:14 ` Leo 2011-07-19 15:24 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-19 15:14 UTC (permalink / raw) To: Lars Magne Ingebrigtsen; +Cc: 9118 On 2011-07-19 22:57 +0800, Lars Magne Ingebrigtsen wrote: > Unfortunately, Emacs doesn't seed itself on startup, so (random x) will > return the same thing every time you start Emacs. > > So I don't think changing this is appropriate at this time. But you can arrange to seed it once when that file is loaded. No need to seed it every time. BTW, (random t) produces no random numbers. (loop repeat 5 collect (random t)) => (2265815277832325116 2265815277832325116 2265815277832325116 2265815277832325116 2265815277832325116) Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-19 15:14 ` Leo @ 2011-07-19 15:24 ` Lars Magne Ingebrigtsen 2011-07-19 15:44 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-07-19 15:24 UTC (permalink / raw) To: Leo; +Cc: 9118 Leo <sdl.web@gmail.com> writes: > But you can arrange to seed it once when that file is loaded. No need to > seed it every time. Calling it once every time you send an email isn't really heavy usage of the re-seeding. > BTW, (random t) produces no random numbers. > > (loop repeat 5 collect (random t)) > > => > > (2265815277832325116 2265815277832325116 2265815277832325116 > 2265815277832325116 2265815277832325116) Oops. :-) Fixed now. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-19 15:24 ` Lars Magne Ingebrigtsen @ 2011-07-19 15:44 ` Leo 2011-07-19 15:49 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-19 15:44 UTC (permalink / raw) To: Lars Magne Ingebrigtsen; +Cc: 9118 On 2011-07-19 23:24 +0800, Lars Magne Ingebrigtsen wrote: >> But you can arrange to seed it once when that file is loaded. No need to >> seed it every time. > > Calling it once every time you send an email isn't really heavy usage of > the re-seeding. But every seeding interrupts the internal random state (which is out of our control at the moment) and break the users' train of random numbers. Also if you grep (random t) in the lisp/, you can see there is some effort in making a package only change the random state at most once. Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-19 15:44 ` Leo @ 2011-07-19 15:49 ` Lars Magne Ingebrigtsen 2011-07-20 2:12 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-07-19 15:49 UTC (permalink / raw) To: Leo; +Cc: 9118 Leo <sdl.web@gmail.com> writes: > But every seeding interrupts the internal random state (which is out of > our control at the moment) and break the users' train of random numbers. > > Also if you grep (random t) in the lisp/, you can see there is some > effort in making a package only change the random state at most once. Once per package? That means that it's called many times in a single Emacs session, so I don't really see the problem. This should really be fixed by Emacs calling `(random t)' at startup. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-19 15:49 ` Lars Magne Ingebrigtsen @ 2011-07-20 2:12 ` Leo 2011-07-20 20:28 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-20 2:12 UTC (permalink / raw) To: 9118; +Cc: Lars Magne Ingebrigtsen On 2011-07-19 23:49 +0800, Lars Magne Ingebrigtsen wrote: > Once per package? That means that it's called many times in a single > Emacs session, so I don't really see the problem. Only at the time of loading a package and only a package or two in the following do I use. After loading the packages, they won't change the rng any more. But calling (random t) every time a function is called just gets in the way, that means I am no longer getting a uniform distribution from the RNG. Also (random t) is much more predictable. ,---- | ChangeLog.6:6494: (life): Do (random t) only once and only when `life' is called. | allout-widgets.el:1351:;; (random t) | calc/calc-comb.el:575: (random t) | gnus/message.el:4788: (format "%x%x%x" (random) (random t) (random)) | gnus/message.el:5494: (% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20))))) | net/sasl.el:186: (% (1+ (or sasl-unique-id-char (logand (random t) (1- (lsh 1 20))))) | org/org-id.el:322: (random t) | play/5x5.el:957:(random t) | play/animate.el:204:(random t) | play/blackbox.el:260: (random t) | play/cookie1.el:57:(random t) | Binary file play/cookie1.elc matches | play/dissociate.el:97:(random t) | play/doctor.el:1620:(random t) | play/dunnet.el:3013:(random t) | play/gomoku.el:1200:(random t) | play/landmark.el:1686:(random t) | play/life.el:125: (random t)) | play/mpuz.el:38:(random t) ; randomize | play/tetris.el:639:(random t) | play/zone.el:683:(random t) | server.el:97: (when val (random t)) | type-break.el:584: (random t) `---- > This should really be fixed by Emacs calling `(random t)' at startup. That should leave for the user to do. Common Lisp also does no seeding at start up. Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-20 2:12 ` Leo @ 2011-07-20 20:28 ` Lars Magne Ingebrigtsen 2011-07-21 4:45 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-07-20 20:28 UTC (permalink / raw) To: Leo; +Cc: 9118 Leo <sdl.web@gmail.com> writes: > That should leave for the user to do. Common Lisp also does no seeding > at start up. LispWorks seeds at start-up. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-20 20:28 ` Lars Magne Ingebrigtsen @ 2011-07-21 4:45 ` Leo 2011-07-21 11:57 ` Juanma Barranquero 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-21 4:45 UTC (permalink / raw) To: Lars Magne Ingebrigtsen; +Cc: 9118 On 2011-07-21 04:28 +0800, Lars Magne Ingebrigtsen wrote: >> That should leave for the user to do. Common Lisp also does no seeding >> at start up. > > LispWorks seeds at start-up. Indeed, some do some don't. I wonder if Emacs should? It will be just one line change. Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-21 4:45 ` Leo @ 2011-07-21 11:57 ` Juanma Barranquero 2011-07-21 15:58 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Juanma Barranquero @ 2011-07-21 11:57 UTC (permalink / raw) To: Leo; +Cc: Lars Magne Ingebrigtsen, 9118 On Thu, Jul 21, 2011 at 06:45, Leo <sdl.web@gmail.com> wrote: > Indeed, some do some don't. I wonder if Emacs should? Many systems (languages, etc.) have a facility to seed the RNG with a specific seed (saved from a previous run, for example), so you can have repeated runs with the exact same sequence of random numbers, if needed. That can be useful for simulation, testing, etc. AFAIK, the Emacs RNG does not allow that at the lisp level, so it would be better to automatically seed it and remove the many (random t) calls, which, as has been pointed out, can in fact be harmful for the quality of the generated random number series, if called repeatedly. Juanma ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-21 11:57 ` Juanma Barranquero @ 2011-07-21 15:58 ` Leo 2011-07-31 15:39 ` Lars Magne Ingebrigtsen 0 siblings, 1 reply; 13+ messages in thread From: Leo @ 2011-07-21 15:58 UTC (permalink / raw) To: Juanma Barranquero; +Cc: Lars Magne Ingebrigtsen, 9118 On 2011-07-21 19:57 +0800, Juanma Barranquero wrote: > Many systems (languages, etc.) have a facility to seed the RNG with a > specific seed (saved from a previous run, for example), so you can > have repeated runs with the exact same sequence of random numbers, if > needed. That can be useful for simulation, testing, etc. > > AFAIK, the Emacs RNG does not allow that at the lisp level, so it > would be better to automatically seed it and remove the many (random > t) calls, which, as has been pointed out, can in fact be harmful for > the quality of the generated random number series, if called > repeatedly. I agree completely. How about something along these lines? (note: before this patch (random 1.0) is equivalent to (random most-positive-fixnum)). === modified file 'src/fns.c' --- src/fns.c 2011-07-05 02:51:15 +0000 +++ src/fns.c 2011-07-21 15:47:30 +0000 @@ -69,15 +69,15 @@ } DEFUN ("random", Frandom, Srandom, 0, 1, 0, - doc: /* Return a pseudo-random number. + doc: /* Return a non-negative pseudo-random number less than LIMIT. All integers representable in Lisp are equally likely. On most systems, this is 29 bits' worth. -With positive integer LIMIT, return random number in interval [0,LIMIT). -With argument t, set the random number seed from the current time and pid. -Other values of LIMIT are ignored. */) +Optional argument LIMIT defaults to `most-positive-fixnum'. +With argument t, set the random number seed from the current time + and pid and return nil. */) (Lisp_Object limit) { - EMACS_INT val; + EMACS_INT val, denominator; Lisp_Object lispy_val; if (EQ (limit, Qt)) @@ -85,24 +85,28 @@ EMACS_TIME t; EMACS_GET_TIME (t); seed_random (getpid () ^ EMACS_SECS (t) ^ EMACS_USECS (t)); + return Qnil; } - if (NATNUMP (limit) && XFASTINT (limit) != 0) - { - /* Try to take our random number from the higher bits of VAL, - not the lower, since (says Gentzel) the low bits of `random' - are less random than the higher ones. We do this by using the - quotient rather than the remainder. At the high end of the RNG - it's possible to get a quotient larger than n; discarding - these values eliminates the bias that would otherwise appear - when using a large n. */ - EMACS_INT denominator = (INTMASK + 1) / XFASTINT (limit); - do - val = get_random () / denominator; - while (val >= XFASTINT (limit)); - } - else - val = get_random (); + if (NILP (limit)) + XSETINT (limit, MOST_POSITIVE_FIXNUM); + + CHECK_NATNUM (limit); + + if (XFASTINT (limit) == 0) + xsignal1 (Qargs_out_of_range, limit); + + /* Try to take our random number from the higher bits of VAL, + not the lower, since (says Gentzel) the low bits of `random' + are less random than the higher ones. We do this by using the + quotient rather than the remainder. At the high end of the RNG + it's possible to get a quotient larger than n; discarding + these values eliminates the bias that would otherwise appear + when using a large n. */ + denominator = (INTMASK + 1) / XFASTINT (limit); + do + val = get_random () / denominator; + while (val >= XFASTINT (limit)); XSETINT (lispy_val, val); return lispy_val; } @@ -5009,4 +5013,5 @@ void init_fns (void) { + Frandom (Qt); } ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-21 15:58 ` Leo @ 2011-07-31 15:39 ` Lars Magne Ingebrigtsen 2011-07-31 16:02 ` Leo 0 siblings, 1 reply; 13+ messages in thread From: Lars Magne Ingebrigtsen @ 2011-07-31 15:39 UTC (permalink / raw) To: Leo; +Cc: Juanma Barranquero, 9118 Leo <sdl.web@gmail.com> writes: > +With argument t, set the random number seed from the current time > + and pid and return nil. */) This would break old (buggy) usages, so it seems unnecessary. -- (domestic pets only, the antidote for overdose, milk.) bloggy blog http://lars.ingebrigtsen.no/ ^ permalink raw reply [flat|nested] 13+ messages in thread
* bug#9118: 23.3.50; Don't seed the RNG in message-unique-id 2011-07-31 15:39 ` Lars Magne Ingebrigtsen @ 2011-07-31 16:02 ` Leo 0 siblings, 0 replies; 13+ messages in thread From: Leo @ 2011-07-31 16:02 UTC (permalink / raw) To: Lars Magne Ingebrigtsen; +Cc: Juanma Barranquero, 9118 On 2011-07-31 23:39 +0800, Lars Magne Ingebrigtsen wrote: > Leo <sdl.web@gmail.com> writes: > >> +With argument t, set the random number seed from the current time >> + and pid and return nil. */) > > This would break old (buggy) usages, so it seems unnecessary. The fix is straightforward. It is worth the small trouble. I can take care of fixing all the handful of occurrences in Emacs source. Leo ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2011-07-31 16:02 UTC | newest] Thread overview: 13+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2011-07-18 16:42 bug#9118: 23.3.50; Don't seed the RNG in message-unique-id Leo 2011-07-19 14:57 ` Lars Magne Ingebrigtsen 2011-07-19 15:14 ` Leo 2011-07-19 15:24 ` Lars Magne Ingebrigtsen 2011-07-19 15:44 ` Leo 2011-07-19 15:49 ` Lars Magne Ingebrigtsen 2011-07-20 2:12 ` Leo 2011-07-20 20:28 ` Lars Magne Ingebrigtsen 2011-07-21 4:45 ` Leo 2011-07-21 11:57 ` Juanma Barranquero 2011-07-21 15:58 ` Leo 2011-07-31 15:39 ` Lars Magne Ingebrigtsen 2011-07-31 16:02 ` Leo
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.