bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Lars Magne Ingebrigtsen]

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/

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Lars Magne Ingebrigtsen]

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/

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Lars Magne Ingebrigtsen]

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/

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Lars Magne Ingebrigtsen]

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/

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Juanma Barranquero]

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

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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);
 }

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Lars Magne Ingebrigtsen]

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/

bug#9118: 23.3.50; Don't seed the RNG in message-unique-id

[Leo]

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