unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* random doesn't feel very random
@ 2012-08-24  5:47 Ivan Kanis
  2012-08-24  6:22 ` Tassilo Horn
                   ` (4 more replies)
  0 siblings, 5 replies; 43+ messages in thread
From: Ivan Kanis @ 2012-08-24  5:47 UTC (permalink / raw)
  To: emacs devel

I am using random for generating music play list. I have found that it
is not random enough. It keeps playing the same tracks.

I have even wrote a cache of recently played tracks so that it tries
harder. Obviously it's a band aid.

Yes I am just talking about "feeling" here. I don't know how to prove
that random does not work. Is it even possible?

On a side note are we using /dev/random?
-- 
Ivan Kanis
http://ivan.kanis.fr

Wisdom denotes the pursuing of the best ends by the best means.
    -- Francis Hutcheson

I am listening to "Captain Beefheart - Im Gonna Booglarize You Baby".



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24  5:47 random doesn't feel very random Ivan Kanis
@ 2012-08-24  6:22 ` Tassilo Horn
  2012-08-24 17:19   ` random doesn't feel very random, random doesn't feel very random, " Ivan Kanis
  2012-08-24  6:30 ` Leo
                   ` (3 subsequent siblings)
  4 siblings, 1 reply; 43+ messages in thread
From: Tassilo Horn @ 2012-08-24  6:22 UTC (permalink / raw)
  To: Ivan Kanis; +Cc: emacs devel

Ivan Kanis <ivan.kanis@googlemail.com> writes:

> Yes I am just talking about "feeling" here. I don't know how to prove
> that random does not work. Is it even possible?

You can test it at least.  Some methods are discussed here.

  http://www.johndcook.com/Beautiful_Testing_ch10.pdf

Bye,
Tassilo



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24  5:47 random doesn't feel very random Ivan Kanis
  2012-08-24  6:22 ` Tassilo Horn
@ 2012-08-24  6:30 ` Leo
  2012-08-24 22:48   ` Richard Stallman
  2012-08-24  7:03 ` Stephen J. Turnbull
                   ` (2 subsequent siblings)
  4 siblings, 1 reply; 43+ messages in thread
From: Leo @ 2012-08-24  6:30 UTC (permalink / raw)
  To: emacs-devel

On 2012-08-24 13:47 +0800, Ivan Kanis wrote:
> I am using random for generating music play list. I have found that it
> is not random enough. It keeps playing the same tracks.
>
> I have even wrote a cache of recently played tracks so that it tries
> harder. Obviously it's a band aid.
>
> Yes I am just talking about "feeling" here. I don't know how to prove
> that random does not work. Is it even possible?
>
> On a side note are we using /dev/random?

That is probably because we have only one global random state and many
packages reset it from time to time (see message-unique-id). No we are
not using /dev/random and should not be.

Ideally we should call (random t) only once or allow multiple random
states.

Leo




^ permalink raw reply	[flat|nested] 43+ messages in thread

* random doesn't feel very random
  2012-08-24  5:47 random doesn't feel very random Ivan Kanis
  2012-08-24  6:22 ` Tassilo Horn
  2012-08-24  6:30 ` Leo
@ 2012-08-24  7:03 ` Stephen J. Turnbull
  2012-08-24  9:10   ` Paul Eggert
  2012-08-24 12:45 ` OT: appropriateness of "random" for playlist generation (was: random doesn't feel very random) Jeremiah Dodds
  2012-08-24 14:37 ` random doesn't feel very random Drew Adams
  4 siblings, 1 reply; 43+ messages in thread
From: Stephen J. Turnbull @ 2012-08-24  7:03 UTC (permalink / raw)
  To: Ivan Kanis; +Cc: emacs devel

Ivan Kanis writes:

 > I am using random for generating music play list. I have found that it
 > is not random enough. It keeps playing the same tracks.

What do you mean by that?  I have two somewhat different situations
where there are plausible hypotheses besides "random is broken".

What seems most likely is that it always plays *the same tracks in
the same order*.  You may have made a programming error or it may be
that the pseudo-random number generator always starts from the same
seed (this is useful so that a uniformly distributed sequence can be
replicated if necessary -- obviously this is bad if you are using
randomness as a security measure, though).  This is the case for GNU
random(3), which always uses the seed 1.

To avoid this behavior, use `(random t)' for the first call to
`random'.  This uses time and some other environmental information to
set the seed.  It's not cryptographically strong, so a sufficiently
smart cracker can probably predict what you're listening to.  I hope
your life doesn't depend on the secrecy of your playlist, though. :-)

If it always plays tracks from the same subset of your collection, but
in different orders, you may have made a programming error.

 > Yes I am just talking about "feeling" here. I don't know how to prove
 > that random does not work. Is it even possible?

Sure.  Analyze the code.  You won't find it in Emacs, though, on most
systems it uses the system random number generator, usually random(3)
it looks like.  On a GNU system this is a nonlinear additive feedback
PRNG.

If you want to prove it without knowing the algorithm, that's a lot
more difficult.  The basic techniques are in D. Knuth's The Art of
Computer Programming, Vol. 2: Seminumerical Algorithms.  The state of
the art has advanced since then, but if you can detect non-randomness
with your flesh-and-blood ears, Knuth's tests will be enough.

 > On a side note are we using /dev/random?

No, and that shouldn't be done for a system RNG.  Period.  It's (a)
expensive (system call), (b) can block (since it depends on the
dynamic environment), and (c) dangerous (it depletes your entropy pool
which can slow or cripple security applications that really need it).

Even using /dev/urandom to generate the seed would be overkill in
almost all applications, and I wouldn't trust anybody in Emacs to
write code for an application that needs that level of randomness.
(That doesn't mean there are no such experts among Emacs developers,
it just means I haven't seen anybody display appropriate credentials
on emacs-devel.  It's a *very* specialized field.)



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24  7:03 ` Stephen J. Turnbull
@ 2012-08-24  9:10   ` Paul Eggert
  2012-08-24 17:45     ` Stephen J. Turnbull
  0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2012-08-24  9:10 UTC (permalink / raw)
  To: Stephen J. Turnbull; +Cc: Ivan Kanis, emacs devel

On 08/24/2012 12:03 AM, Stephen J. Turnbull wrote:
> That doesn't mean there are no such experts among Emacs developers,
> it just means I haven't seen anybody display appropriate credentials
> on emacs-devel.

I'm not sure what you mean by "credentials".  Is there a secret
handshake we have to use?  Or does published code suffice?

http://git.savannah.gnu.org/cgit/coreutils.git/tree/gl/lib/rand-isaac.c

An analysis is here:

http://burtleburtle.net/bob/rand/isaacafa.html

I haven't bothered to put this stuff into Emacs, but it shouldn't
be that hard to add if there's a real need.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* OT: appropriateness of "random" for playlist generation (was: random doesn't feel very random)
  2012-08-24  5:47 random doesn't feel very random Ivan Kanis
                   ` (2 preceding siblings ...)
  2012-08-24  7:03 ` Stephen J. Turnbull
@ 2012-08-24 12:45 ` Jeremiah Dodds
  2012-08-24 14:37 ` random doesn't feel very random Drew Adams
  4 siblings, 0 replies; 43+ messages in thread
From: Jeremiah Dodds @ 2012-08-24 12:45 UTC (permalink / raw)
  To: Ivan Kanis; +Cc: emacs devel

Ivan Kanis <ivan.kanis@googlemail.com> writes:

> I am using random for generating music play list. I have found that it
> is not random enough. It keeps playing the same tracks.
>
> I have even wrote a cache of recently played tracks so that it tries
> harder. Obviously it's a band aid.
>
> Yes I am just talking about "feeling" here. I don't know how to prove
> that random does not work. Is it even possible?
>
> On a side note are we using /dev/random?

FWIW, I've never found even "good" random algorithms to be good for the
purposes of playing music, especially when your collection is large. 

I like to listen to albums as a whole, and in particular I'd like to
listen to random albums that I haven't heard before, if any are
present. A lot of times, this can end up with you hearing multiple
artists in a row.

I actually went so far as to write my own little mp3 player that uses
an algorithm that can be summed up as "play me a random album from a
random artist that was not the last artist played", which sounds a lot
more "random" to my ears, but is technically much more stable.

-- 
Jeremiah Dodds

blog       : http://jdodds.github.com
github     : https://github.com/jdodds
freenode   : exhortatory
twitter    : kaens



^ permalink raw reply	[flat|nested] 43+ messages in thread

* RE: random doesn't feel very random
  2012-08-24  5:47 random doesn't feel very random Ivan Kanis
                   ` (3 preceding siblings ...)
  2012-08-24 12:45 ` OT: appropriateness of "random" for playlist generation (was: random doesn't feel very random) Jeremiah Dodds
@ 2012-08-24 14:37 ` Drew Adams
  4 siblings, 0 replies; 43+ messages in thread
From: Drew Adams @ 2012-08-24 14:37 UTC (permalink / raw)
  To: 'Ivan Kanis', 'emacs devel'

[-- Attachment #1: Type: text/plain, Size: 42 bytes --]

Dilbert gets the last word on randomness.

[-- Attachment #2: dilbert-random-generator.gif --]
[-- Type: image/gif, Size: 33642 bytes --]

^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random
  2012-08-24  6:22 ` Tassilo Horn
@ 2012-08-24 17:19   ` Ivan Kanis
  2012-08-24 18:50     ` Stephen J. Turnbull
  0 siblings, 1 reply; 43+ messages in thread
From: Ivan Kanis @ 2012-08-24 17:19 UTC (permalink / raw)
  To: emacs devel

Tassilo Horn <tsdh@gnu.org> wrote:

> You can test it at least.  Some methods are discussed here.
>
>   http://www.johndcook.com/Beautiful_Testing_ch10.pdf

Thanks I'll look if I find the time and the inclination.

"Stephen J. Turnbull" <stephen@xemacs.org> wrote:

> To avoid this behavior, use `(random t)'

I do.

> I hope your life doesn't depend on the secrecy of your playlist,
> though. :-)

Nope ;)

> If it always plays tracks from the same subset of your collection, but
> in different orders, you may have made a programming error.

It sort of does that. Here's the function that picks music up. I have
attached the rest of the code if you'd like to see more.

(defun ivan-emms-pick-album (dir length with-cache)
  "Return a LENGTH albums in a directory DIR.
If WITH-CACHE is non-nil exclude albums that are in cache."
  (let* ((index 0)
         (ret (make-vector length nil))
         (album (ivan-emms-list-subdir
                 (concat ivan-emms-dir dir)))
         (album-length (length album))
         ring)
    (when with-cache
      (setq ring (ivan-emms-last-load)))
    (while (< index length)
      (aset ret index
            (nth (if with-cache
                     (let* ((r (random album-length))
                            (album (nth r album)))
                       (while (ring-member ring r)
                         (setq r (random album-length)
                               album (nth r album)))
                       (ring-insert ring album)
                       r)
                   (random album-length))
                 album))
      (setq index (1+ index)))
    (when with-cache
      (ivan-emms-last-save ring))
    ret))

> If you want to prove it without knowing the algorithm, that's a lot
> more difficult.  The basic techniques are in D. Knuth's The Art of
> Computer Programming, Vol. 2: Seminumerical Algorithms.  The state of
> the art has advanced since then, but if you can detect non-randomness
> with your flesh-and-blood ears, Knuth's tests will be enough.

It's noted.
-- 
Ivan Kanis
http://ivan.kanis.fr

A facility for quotation covers the absence of original thought.
    -- Lord Peter Wimsey

I am listening to "Serge Gainsbourg - Initials B.B.".



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24  9:10   ` Paul Eggert
@ 2012-08-24 17:45     ` Stephen J. Turnbull
  0 siblings, 0 replies; 43+ messages in thread
From: Stephen J. Turnbull @ 2012-08-24 17:45 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Ivan Kanis, emacs devel

Paul Eggert writes:
 > On 08/24/2012 12:03 AM, Stephen J. Turnbull wrote:
 > > That doesn't mean there are no such experts among Emacs developers,
 > > it just means I haven't seen anybody display appropriate credentials
 > > on emacs-devel.
 > 
 > I'm not sure what you mean by "credentials".

That doesn't really matter.  The point is what the credentials are
for.  I wrote:

    Even using /dev/urandom to generate the seed would be overkill in
    almost all applications, and I wouldn't trust anybody in Emacs to
    write code for an application that needs that level of randomness.

You see, I'm not talking about credentials for *implementing* a
(P)RNG, I'm talking about *using* it.  I'm saying that if you *need* a
(P)RNG of that quality, nobody I know could write the rest of the
application in Emacs Lisp and be sure it's as good as the (P)RNG is.

That doesn't mean there's anything *wrong* with implementing a better
PRNG for Lisp.  But I personally wouldn't bother.  random(3) is plenty
good enough for me.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random
  2012-08-24 17:19   ` random doesn't feel very random, random doesn't feel very random, " Ivan Kanis
@ 2012-08-24 18:50     ` Stephen J. Turnbull
  2012-08-25  7:46       ` Ivan Kanis
  0 siblings, 1 reply; 43+ messages in thread
From: Stephen J. Turnbull @ 2012-08-24 18:50 UTC (permalink / raw)
  To: Ivan Kanis; +Cc: emacs devel

Ivan Kanis writes:
 > "Stephen J. Turnbull" <stephen@xemacs.org> wrote:

 > > To avoid this behavior, use `(random t)'
 > 
 > I do.

Where?  I don't see it in your `ivan-emms-pick-album' function.  Note,
this will only help across Emacs sessions; within one session the
random function should maintain state across calls to your function,
so it should give different sequences every time as long as you never
exist Emacs.

 > > If it always plays tracks from the same subset of your
 > > collection, but in different orders, you may have made a
 > > programming error.
 > 
 > It sort of does that.

I still don't understand what buggy behavior you are seeing.  Without
a precise description, it's hard to guess what might be wrong in your
code or in `random'.

 > (defun ivan-emms-pick-album (dir length)
 >   "Return a LENGTH albums in a directory DIR."
 >   (let* ((index 0)
 >          (ret (make-vector length nil))
 >          (album (ivan-emms-list-subdir
 >                  (concat ivan-emms-dir dir)))
 >          (album-length (length album)))
 >     (while (< index length)
 >       (aset ret index
 >             (nth (random album-length) album))
 >       (setq index (1+ index)))
 >     ret))

That's the code without WITH-CACHE.  I don't see any problems with it.

Unfortunately the attachment seems to have been stripped so I don't
know what might be going wrong in `ivan-emms-list-subdir' or the code
that calls `ivan-emms-pick-album'.  (Probably nothing, but I can't
review it.)

If you do `M-x (ivan-emms-list-subdir (concat ivan-emms-dir "FOO")) RET'
(with some value for FOO that actually exists and contains albums),
does the answer look right?




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24  6:30 ` Leo
@ 2012-08-24 22:48   ` Richard Stallman
  2012-08-24 22:57     ` Andreas Schwab
  0 siblings, 1 reply; 43+ messages in thread
From: Richard Stallman @ 2012-08-24 22:48 UTC (permalink / raw)
  To: Leo; +Cc: emacs-devel

    That is probably because we have only one global random state and many
    packages reset it from time to time (see message-unique-id).

Why would extra invocations of (random t) cause repetitive behavior?

    Ideally we should call (random t) only once or allow multiple random
    states.

Supporting multiple random seeds would be a natural thing to do
if there is some advantage in sticking with one random seed
for a particular purpose, or if there is some harm in doing
(random t) extra times.  But what reason could there be for that?
Except studying the pseudorandom number generator, that is.

--
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24 22:48   ` Richard Stallman
@ 2012-08-24 22:57     ` Andreas Schwab
  2012-08-25 20:55       ` Richard Stallman
  0 siblings, 1 reply; 43+ messages in thread
From: Andreas Schwab @ 2012-08-24 22:57 UTC (permalink / raw)
  To: rms; +Cc: Leo, emacs-devel

Richard Stallman <rms@gnu.org> writes:

>     That is probably because we have only one global random state and many
>     packages reset it from time to time (see message-unique-id).
>
> Why would extra invocations of (random t) cause repetitive behavior?

Depends on how random your seed is.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random
  2012-08-24 18:50     ` Stephen J. Turnbull
@ 2012-08-25  7:46       ` Ivan Kanis
  0 siblings, 0 replies; 43+ messages in thread
From: Ivan Kanis @ 2012-08-25  7:46 UTC (permalink / raw)
  To: Stephen J. Turnbull; +Cc: emacs devel

[-- Attachment #1: Type: text/plain, Size: 1435 bytes --]

"Stephen J. Turnbull" <stephen@xemacs.org> wrote:

> Ivan Kanis writes:
>  > "Stephen J. Turnbull" <stephen@xemacs.org> wrote:
>
>  > > To avoid this behavior, use `(random t)'
>  > 
>  > I do.
>
> Where?   I don't see it in your `ivan-emms-pick-album' function

I call it once in the callee function ivan-emms-random-album. I attached
the source again.

> this will only help across Emacs sessions; within one session the
> random function should maintain state across calls to your function,
> so it should give different sequences every time as long as you never
> exist Emacs.

I exit emacs everyday, would that have an effect on the randomness?
Should I save the seed somewhere to have better result?

> Unfortunately the attachment seems to have been stripped so I don't
> know what might be going wrong in `ivan-emms-list-subdir' or the code
> that calls `ivan-emms-pick-album'.  (Probably nothing, but I can't
> review it.)

I have put the code source on my web site in case the attachment gets
stripped again:

http://ivan.kanis.fr/ivan-emms.el

> If you do `M-x (ivan-emms-list-subdir (concat ivan-emms-dir "FOO")) RET'
> (with some value for FOO that actually exists and contains albums),
> does the answer look right?

It looks good:

(length (ivan-emms-list-subdir (concat ivan-emms-dir "music"))) => 769
-- 
Ivan Kanis
http://ivan.kanis.fr

An open foe may prove a curse,
But a pretended friend is worse.
    -- John Gay

[-- Attachment #2: ivan-emms.el --]
[-- Type: application/emacs-lisp, Size: 7181 bytes --]

^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-24 22:57     ` Andreas Schwab
@ 2012-08-25 20:55       ` Richard Stallman
  2012-08-25 23:25         ` Leo
  2012-08-26  9:06         ` Ivan Kanis
  0 siblings, 2 replies; 43+ messages in thread
From: Richard Stallman @ 2012-08-25 20:55 UTC (permalink / raw)
  To: Andreas Schwab; +Cc: sdl.web, emacs-devel

    > Why would extra invocations of (random t) cause repetitive behavior?

    Depends on how random your seed is.

(random t) calculates a seed based on the current time.
Unless it is done repeatedly in a very short time, that
should make a different seed each time.

Unless there is a bug in the code that initializes the seed.

--
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-25 20:55       ` Richard Stallman
@ 2012-08-25 23:25         ` Leo
  2012-08-26 13:12           ` Richard Stallman
  2012-08-26  9:06         ` Ivan Kanis
  1 sibling, 1 reply; 43+ messages in thread
From: Leo @ 2012-08-25 23:25 UTC (permalink / raw)
  To: rms; +Cc: Andreas Schwab, emacs-devel

On 2012-08-26 04:55 +0800, Richard Stallman wrote:
> (random t) calculates a seed based on the current time.
> Unless it is done repeatedly in a very short time, that
> should make a different seed each time.

Every time I compose an email, (random t) is called. So the random
number stream I am getting is disrupted i.e. I am no longer getting an
uniform distribution.

Leo



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-25 20:55       ` Richard Stallman
  2012-08-25 23:25         ` Leo
@ 2012-08-26  9:06         ` Ivan Kanis
  1 sibling, 0 replies; 43+ messages in thread
From: Ivan Kanis @ 2012-08-26  9:06 UTC (permalink / raw)
  To: rms; +Cc: Andreas Schwab, sdl.web, emacs-devel

Richard Stallman <rms@gnu.org> wrote:

>     > Why would extra invocations of (random t) cause repetitive behavior?
>
> (random t) calculates a seed based on the current time.
> Unless it is done repeatedly in a very short time, that
> should make a different seed each time.

I had emacs play the same track after two starts. My emacs takes few
seconds to start.

It happened on Ubuntu 10.10 or Debian 6.0.

Does the function random not take into account the seconds when it's
seeded?
-- 
Ivan Kanis
http://ivan.kanis.fr

Everyone thinks of changing the world, but no one thinks of changing
himself.
    -- Leo Tolstoy

I am listening to "Plan B - She Said".



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-25 23:25         ` Leo
@ 2012-08-26 13:12           ` Richard Stallman
  2012-08-26 14:24             ` Achim Gratz
  0 siblings, 1 reply; 43+ messages in thread
From: Richard Stallman @ 2012-08-26 13:12 UTC (permalink / raw)
  To: Leo; +Cc: schwab, emacs-devel

    Every time I compose an email, (random t) is called. So the random
    number stream I am getting is disrupted i.e. I am no longer getting an
    uniform distribution.

If that is really true, maybe the code to set the seed needs to be
changed.  Maybe it only gives you seed values from a subset of all
those possible.

Perhaps instead of initializing the seed based on the time, it should
change the seed based on the time.  That way, all possible seeds
could occur after (random t).

--
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-26 13:12           ` Richard Stallman
@ 2012-08-26 14:24             ` Achim Gratz
  2012-08-26 23:22               ` Leo
                                 ` (2 more replies)
  0 siblings, 3 replies; 43+ messages in thread
From: Achim Gratz @ 2012-08-26 14:24 UTC (permalink / raw)
  To: emacs-devel

Richard Stallman writes:
> If that is really true, maybe the code to set the seed needs to be
> changed.  Maybe it only gives you seed values from a subset of all
> those possible.
>
> Perhaps instead of initializing the seed based on the time, it should
> change the seed based on the time.  That way, all possible seeds
> could occur after (random t).

Re-seeding a PRNG inside the same application is misguided even when
there are multiple consumers of the sequence.  Provided the PRNG is of
sufficient quality, partial sequences aren't any less random.  Therefore
the PRNG should be seeded once at start-up, from a good source of
entropy.  The only application for re-seeding is to provide a repeatable
sequence (but Emacs' random doesn't allow for that since you can't give
the seed value directly) or if the PRNG state has been compromised.

Given the widespread use of (random t) it should probably be made a
no-op and a separate API to provide a local state for application that
wish to control it for whatever reason should be made available.


Regards,
Achim.
-- 
+<[Q+ Matrix-12 WAVE#46+305 Neuron microQkb Andromeda XTk Blofeld]>+

Waldorf MIDI Implementation & additional documentation:
http://Synth.Stromeko.net/Downloads.html#WaldorfDocs




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-26 14:24             ` Achim Gratz
@ 2012-08-26 23:22               ` Leo
  2012-08-27  0:50               ` Stefan Monnier
  2012-08-27  3:41               ` Richard Stallman
  2 siblings, 0 replies; 43+ messages in thread
From: Leo @ 2012-08-26 23:22 UTC (permalink / raw)
  To: emacs-devel

On 2012-08-26 22:24 +0800, Achim Gratz wrote:
> Given the widespread use of (random t) it should probably be made a
> no-op and a separate API to provide a local state for application that
> wish to control it for whatever reason should be made available.

Agree.

Leo




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-26 14:24             ` Achim Gratz
  2012-08-26 23:22               ` Leo
@ 2012-08-27  0:50               ` Stefan Monnier
  2012-08-27  6:31                 ` Simon Leinen
  2012-08-27  3:41               ` Richard Stallman
  2 siblings, 1 reply; 43+ messages in thread
From: Stefan Monnier @ 2012-08-27  0:50 UTC (permalink / raw)
  To: Achim Gratz; +Cc: emacs-devel

> Therefore the PRNG should be seeded once at start-up, from a good
> source of entropy.

I tend to agree.

> Given the widespread use of (random t) it should probably be made a
> no-op and a separate API to provide a local state for application that
> wish to control it for whatever reason should be made available.

IIRC Emacs fails to seed its PRNG at start (IOW it is seeded with
a constant), which is why many packages use (random t).

So I think the right thing to do now is to do seed it at startup, then
make (random t) a no-op.

We could consider adding a way to get the PRNG state and reset it later,
but since the PRNG state is Emacs-wide and Emacs is more like an OS than
like an application w.r.t its packages, such an interface would need to
allow several named PRNGs, so you'd call (random N <id>) to get the next
"random" number from <id>'s stream.


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-26 14:24             ` Achim Gratz
  2012-08-26 23:22               ` Leo
  2012-08-27  0:50               ` Stefan Monnier
@ 2012-08-27  3:41               ` Richard Stallman
  2012-08-27  4:48                 ` Stefan Monnier
  2012-08-27  5:17                 ` Achim Gratz
  2 siblings, 2 replies; 43+ messages in thread
From: Richard Stallman @ 2012-08-27  3:41 UTC (permalink / raw)
  To: Achim Gratz; +Cc: emacs-devel

    Given the widespread use of (random t) it should probably be made a
    no-op and a separate API to provide a local state for application that
    wish to control it for whatever reason should be made available.

It is a feature that, if you don't call (random t), `random' returns
a predictable sequence.  That is good for debugging.

Perhaps we should create a different interface for that feature
and make the default truly random.

--
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-27  3:41               ` Richard Stallman
@ 2012-08-27  4:48                 ` Stefan Monnier
  2012-08-31  9:41                   ` Eli Zaretskii
  2012-08-27  5:17                 ` Achim Gratz
  1 sibling, 1 reply; 43+ messages in thread
From: Stefan Monnier @ 2012-08-27  4:48 UTC (permalink / raw)
  To: rms; +Cc: Achim Gratz, emacs-devel

> It is a feature that, if you don't call (random t), `random' returns
> a predictable sequence.  That is good for debugging.

I wonder how often this has been useful.  Since most/any package that
uses `random' will want the sequence to be unpredictable, many packages
call (random t) at various times, so before you can benefit from such
a feature, you'll need to disable those (random t) that would otherwise
get in the way.

It would be much simpler to always seed the PRNG at startup from
"unpredictable" data and then provide a (random-seed N) which you can
call explicitly to reset the PRNG to a predictable state if/when you
need it for debugging.

> Perhaps we should create a different interface for that feature
> and make the default truly random.

Exactly (for some value of "truly random").


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-27  3:41               ` Richard Stallman
  2012-08-27  4:48                 ` Stefan Monnier
@ 2012-08-27  5:17                 ` Achim Gratz
  2012-08-31  9:42                   ` Eli Zaretskii
  1 sibling, 1 reply; 43+ messages in thread
From: Achim Gratz @ 2012-08-27  5:17 UTC (permalink / raw)
  To: emacs-devel

Richard Stallman writes:
> It is a feature that, if you don't call (random t), `random' returns
> a predictable sequence.  That is good for debugging.

I recognize that, but it leads directly to the mis-use of (random t) all
over the place.  Wouldn't it be better (in the absence of any API
changes) to have an option to start Emacs with a predictable seed for
debugging and have it use a random seed otherwise?

> Perhaps we should create a different interface for that feature
> and make the default truly random.

Yes.  Again, if applications within Emacs care about that sort of thing
it would really be necessary for them to be able to use their own PRNG
state rather than Emacs' global one, which isn't possible with the
current API.


Regards,
Achim.
-- 
+<[Q+ Matrix-12 WAVE#46+305 Neuron microQkb Andromeda XTk Blofeld]>+

Factory and User Sound Singles for Waldorf Q+, Q and microQ:
http://Synth.Stromeko.net/Downloads.html#WaldorfSounds




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-27  0:50               ` Stefan Monnier
@ 2012-08-27  6:31                 ` Simon Leinen
  0 siblings, 0 replies; 43+ messages in thread
From: Simon Leinen @ 2012-08-27  6:31 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: Achim Gratz, emacs-devel

[-- Attachment #1: Type: text/plain, Size: 1028 bytes --]

On Mon, Aug 27, 2012 at 2:50 AM, Stefan Monnier <monnier@iro.umontreal.ca>wrote:

> > Therefore the PRNG should be seeded once at start-up, from a good
> > source of entropy.
>
> IIRC Emacs fails to seed its PRNG at start (IOW it is seeded with
> a constant), which is why many packages use (random t).
>
> So I think the right thing to do now is to do seed it at startup, then
> make (random t) a no-op.
>
> We could consider adding a way to get the PRNG state and reset it later,
> but since the PRNG state is Emacs-wide and Emacs is more like an OS than
> like an application w.r.t its packages, such an interface would need to
> allow several named PRNGs, so you'd call (random N <id>) to get the next
> "random" number from <id>'s stream.


What about implementing the Common Lisp conventions for treating PRNG
state, i.e. an optional state argument to RANDOM, and a variable
*RANDOM-STATE*?
Instead of (RANDOM T), people could say something like (SETQ *RANDOM-STATE*
(MAKE-RANDOM-STATE T)) if they really want.
-- 
Simon.

[-- Attachment #2: Type: text/html, Size: 1401 bytes --]

^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-27  4:48                 ` Stefan Monnier
@ 2012-08-31  9:41                   ` Eli Zaretskii
  2012-08-31 15:06                     ` Stefan Monnier
  0 siblings, 1 reply; 43+ messages in thread
From: Eli Zaretskii @ 2012-08-31  9:41 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: Stromeko, rms, emacs-devel

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Mon, 27 Aug 2012 00:48:47 -0400
> Cc: Achim Gratz <Stromeko@nexgo.de>, emacs-devel@gnu.org
> 
> > It is a feature that, if you don't call (random t), `random' returns
> > a predictable sequence.  That is good for debugging.
> 
> I wonder how often this has been useful.

??? A pseudo-random sequence is always deterministic, that's what the
"pseudo" part is about.  I'm sure you already know that.

> Since most/any package that uses `random' will want the sequence to
> be unpredictable

??? A pseudo-random sequence looks and feels as an unpredictable one.
Moreover, you cannot have a non-predictable sequence out of a PRNG at
all.  I'm sure you already know that.

> many packages call (random t) at various times

Those packages have a bug that needs to be fixed.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-27  5:17                 ` Achim Gratz
@ 2012-08-31  9:42                   ` Eli Zaretskii
  2012-08-31 15:07                     ` Stefan Monnier
  0 siblings, 1 reply; 43+ messages in thread
From: Eli Zaretskii @ 2012-08-31  9:42 UTC (permalink / raw)
  To: Achim Gratz; +Cc: emacs-devel

> From: Achim Gratz <Stromeko@nexgo.de>
> Date: Mon, 27 Aug 2012 07:17:45 +0200
> 
> Richard Stallman writes:
> > It is a feature that, if you don't call (random t), `random' returns
> > a predictable sequence.  That is good for debugging.
> 
> I recognize that, but it leads directly to the mis-use of (random t) all
> over the place.  Wouldn't it be better (in the absence of any API
> changes) to have an option to start Emacs with a predictable seed for
> debugging and have it use a random seed otherwise?

IMO, it would be better to fix the packages that misuse '(random t)'.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31  9:41                   ` Eli Zaretskii
@ 2012-08-31 15:06                     ` Stefan Monnier
  2012-08-31 15:23                       ` chad
                                         ` (2 more replies)
  0 siblings, 3 replies; 43+ messages in thread
From: Stefan Monnier @ 2012-08-31 15:06 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: Stromeko, rms, emacs-devel

>> > It is a feature that, if you don't call (random t), `random' returns
>> > a predictable sequence.  That is good for debugging.
>> I wonder how often this has been useful.
> ??? A pseudo-random sequence is always deterministic, that's what the
> "pseudo" part is about.  I'm sure you already know that.

Yes, obviously I know that.  So you've misunderstood what I said.
I'm saying that I highly doubt that the fact that `random' always
returns the exact same stream unless you explicitly call (random t)
has been often useful (and used) for debugging in practice.

>> many packages call (random t) at various times
> Those packages have a bug that needs to be fixed.

My point was that those bugs make the above "feature" more difficult to
use, making it that much more doubtful that it has ever been useful.

As for whether they're bugs or not: I tend to agree that they're bugs,
but since currently our PRNG is not automatically seeded, those packages
that need their `random' to vary (IOW basically every package that
uses random) have no other choice but to call (random t) explicitly at
various times.
So to fix those bugs, we have to:
- change Emacs's initialization so that it seeds its PRNG.
- eliminate most/all calls to (random t), which is best done by changing
  `random' to do nothing when called with argument t (after all,
  re-seeding wouldn't make it less predictable anyway).


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31  9:42                   ` Eli Zaretskii
@ 2012-08-31 15:07                     ` Stefan Monnier
  2012-08-31 17:50                       ` Eli Zaretskii
  0 siblings, 1 reply; 43+ messages in thread
From: Stefan Monnier @ 2012-08-31 15:07 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: Achim Gratz, emacs-devel

> IMO, it would be better to fix the packages that misuse '(random t)'.

How?


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 15:06                     ` Stefan Monnier
@ 2012-08-31 15:23                       ` chad
  2012-08-31 17:50                       ` Eli Zaretskii
  2012-08-31 23:04                       ` Leo
  2 siblings, 0 replies; 43+ messages in thread
From: chad @ 2012-08-31 15:23 UTC (permalink / raw)
  To: emacs-devel@gnu.org discussions


On 31 Aug 2012, at 08:06, Stefan Monnier <monnier@IRO.UMontreal.CA> wrote:
> 
> So to fix those bugs, we have to:
> - change Emacs's initialization so that it seeds its PRNG.

To aid in debugging, perhaps seed the PRNG in site-start, so -Q
disables it?

*Chad




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 15:06                     ` Stefan Monnier
  2012-08-31 15:23                       ` chad
@ 2012-08-31 17:50                       ` Eli Zaretskii
  2012-08-31 19:43                         ` Stefan Monnier
  2012-08-31 23:04                       ` Leo
  2 siblings, 1 reply; 43+ messages in thread
From: Eli Zaretskii @ 2012-08-31 17:50 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: Stromeko, rms, emacs-devel

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: rms@gnu.org, Stromeko@nexgo.de, emacs-devel@gnu.org
> Date: Fri, 31 Aug 2012 11:06:45 -0400
> 
> >> > It is a feature that, if you don't call (random t), `random' returns
> >> > a predictable sequence.  That is good for debugging.
> >> I wonder how often this has been useful.
> > ??? A pseudo-random sequence is always deterministic, that's what the
> > "pseudo" part is about.  I'm sure you already know that.
> 
> Yes, obviously I know that.  So you've misunderstood what I said.

Obviously.

> I'm saying that I highly doubt that the fact that `random' always
> returns the exact same stream unless you explicitly call (random t)
> has been often useful (and used) for debugging in practice.

Not in Emacs, but in other software, the equivalent functionality has
proven useful to me many times.  You basically cannot debug software
that uses PRNG without this.  E.g., if two supposedly-identical runs
diverge at some point in the random numbers they show in some
variable, you _know_ you have a clue for debugging.

> As for whether they're bugs or not: I tend to agree that they're bugs,
> but since currently our PRNG is not automatically seeded, those packages
> that need their `random' to vary (IOW basically every package that
> uses random) have no other choice but to call (random t) explicitly at
> various times.

If you are trying to convince me that our PRNG should be seeded at
startup, them I'm sold on that a long time ago.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 15:07                     ` Stefan Monnier
@ 2012-08-31 17:50                       ` Eli Zaretskii
  0 siblings, 0 replies; 43+ messages in thread
From: Eli Zaretskii @ 2012-08-31 17:50 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: Stromeko, emacs-devel

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: Achim Gratz <Stromeko@nexgo.de>, emacs-devel@gnu.org
> Date: Fri, 31 Aug 2012 11:07:10 -0400
> 
> > IMO, it would be better to fix the packages that misuse '(random t)'.
> 
> How?

Like you suggested:

> So to fix those bugs, we have to:
> - change Emacs's initialization so that it seeds its PRNG.
> - eliminate most/all calls to (random t), which is best done by changing
>   `random' to do nothing when called with argument t (after all,
>   re-seeding wouldn't make it less predictable anyway).



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 17:50                       ` Eli Zaretskii
@ 2012-08-31 19:43                         ` Stefan Monnier
  2012-09-01  1:18                           ` Paul Eggert
  0 siblings, 1 reply; 43+ messages in thread
From: Stefan Monnier @ 2012-08-31 19:43 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: Stromeko, rms, emacs-devel

> If you are trying to convince me that our PRNG should be seeded at
> startup,

Yes, that's the subject under discussion.

> them I'm sold on that a long time ago.

Alright, then let's make the change,


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 15:06                     ` Stefan Monnier
  2012-08-31 15:23                       ` chad
  2012-08-31 17:50                       ` Eli Zaretskii
@ 2012-08-31 23:04                       ` Leo
  2 siblings, 0 replies; 43+ messages in thread
From: Leo @ 2012-08-31 23:04 UTC (permalink / raw)
  To: emacs-devel

On 2012-08-31 23:06 +0800, Stefan Monnier wrote:
> As for whether they're bugs or not: I tend to agree that they're bugs,
> but since currently our PRNG is not automatically seeded, those packages
> that need their `random' to vary (IOW basically every package that
> uses random) have no other choice but to call (random t) explicitly at
> various times.

I have seen packages using the accidental return value of (random t) so
the misuse of (random t) is indeed misuse.

Leo




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-08-31 19:43                         ` Stefan Monnier
@ 2012-09-01  1:18                           ` Paul Eggert
  2012-09-01  7:19                             ` Achim Gratz
                                               ` (2 more replies)
  0 siblings, 3 replies; 43+ messages in thread
From: Paul Eggert @ 2012-09-01  1:18 UTC (permalink / raw)
  To: Stefan Monnier; +Cc: Eli Zaretskii, Stromeko, rms, emacs-devel

On 08/31/2012 12:43 PM, Stefan Monnier wrote:
> Alright, then let's make the change,

I committed something to do that, in trunk bzr 109833 and
109834.

One thing that wasn't discussed was how to set the
seed, for people who want to do debugging and who want
repeatable random sequences.  Trunk bzr 109833 does that by letting
one execute (random "STRING"), where the contents of the string
determine the seed.  If this doesn't seem to be a good idea,
I'll volunteer to rip it out, or change it, or whatever.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01  1:18                           ` Paul Eggert
@ 2012-09-01  7:19                             ` Achim Gratz
  2012-09-01 13:19                               ` Paul Eggert
  2012-09-02 12:27                               ` Jason Rumney
  2012-09-01  7:22                             ` Ivan Kanis
  2012-09-01 11:13                             ` joakim
  2 siblings, 2 replies; 43+ messages in thread
From: Achim Gratz @ 2012-09-01  7:19 UTC (permalink / raw)
  To: emacs-devel

Paul Eggert writes:
> I committed something to do that, in trunk bzr 109833 and
> 109834.

Thank you.  On systems having a better source of entropy (like
/dev/urandom), the init value should be taken from that source rather
than the "mix PID with current time" hack.

> One thing that wasn't discussed was how to set the
> seed, for people who want to do debugging and who want
> repeatable random sequences.

I don't think it's a good idea to be able to change the global PRNG
state in general.  So the (random "S") interface should be a NOP (just
like `(random t)´ now is) unless debugging is on.  Since you would
likely want to control the initial state as well, this should probably
be controlled by a new commandline option that also allows to set the
initial state (or fall back to always using the same "magic" initial
state if none is provided).

I still think the cleanest way would be to allow packages to have a
private PRNG state bound to a variable and then each call to (random)
will advance the private state rather than the global one.  This would
require to use nrand48 instead of lrand48 or setstate (for old random),
so this might have portability implications.  For debugging the global
PRNG state could be made accessible in this case.


Regards,
Achim.
-- 
+<[Q+ Matrix-12 WAVE#46+305 Neuron microQkb Andromeda XTk Blofeld]>+

Waldorf MIDI Implementation & additional documentation:
http://Synth.Stromeko.net/Downloads.html#WaldorfDocs




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01  1:18                           ` Paul Eggert
  2012-09-01  7:19                             ` Achim Gratz
@ 2012-09-01  7:22                             ` Ivan Kanis
  2012-09-01 11:13                             ` joakim
  2 siblings, 0 replies; 43+ messages in thread
From: Ivan Kanis @ 2012-09-01  7:22 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Eli Zaretskii, Stromeko, emacs-devel, Stefan Monnier, rms

Paul Eggert <eggert@cs.ucla.edu> wrote:

> On 08/31/2012 12:43 PM, Stefan Monnier wrote:
>> Alright, then let's make the change,
>
> I committed something to do that, in trunk bzr 109833 and
> 109834.

Thanks! I will let you know if I get better results.
-- 
Ivan Kanis
http://ivan.kanis.fr

In this world nothing can be said to be certain,
except death and taxes.
    -- Benjamin Franklin



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01  1:18                           ` Paul Eggert
  2012-09-01  7:19                             ` Achim Gratz
  2012-09-01  7:22                             ` Ivan Kanis
@ 2012-09-01 11:13                             ` joakim
  2 siblings, 0 replies; 43+ messages in thread
From: joakim @ 2012-09-01 11:13 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Eli Zaretskii, Stromeko, emacs-devel, Stefan Monnier, rms

Paul Eggert <eggert@cs.ucla.edu> writes:

> On 08/31/2012 12:43 PM, Stefan Monnier wrote:
>> Alright, then let's make the change,
>
> I committed something to do that, in trunk bzr 109833 and
> 109834.
>
> One thing that wasn't discussed was how to set the
> seed, for people who want to do debugging and who want
> repeatable random sequences.  Trunk bzr 109833 does that by letting
> one execute (random "STRING"), where the contents of the string
> determine the seed.  If this doesn't seem to be a good idea,
> I'll volunteer to rip it out, or change it, or whatever.

I would like this interface very much!
-- 
Joakim Verona



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01  7:19                             ` Achim Gratz
@ 2012-09-01 13:19                               ` Paul Eggert
  2012-09-04 19:19                                 ` Nix
  2012-09-02 12:27                               ` Jason Rumney
  1 sibling, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2012-09-01 13:19 UTC (permalink / raw)
  To: Achim Gratz; +Cc: emacs-devel

On 09/01/2012 12:19 AM, Achim Gratz wrote:
> On systems having a better source of entropy (like
> /dev/urandom), the init value should be taken from that source rather
> than the "mix PID with current time" hack.

This is on my list of things to do, as a gnulib project.
Among other things, I plan to use the RDRAND instruction
available on current Intel processors, as that's much
faster and better than /dev/urandom.

> allow packages to have a
> private PRNG state bound to a variable and then each call to (random)
> will advance the private state rather than the global one.

That would make sense.

Care to propose an exact API for that?  Now's a good time
to implement something like that, if we're going to do it.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01  7:19                             ` Achim Gratz
  2012-09-01 13:19                               ` Paul Eggert
@ 2012-09-02 12:27                               ` Jason Rumney
  2012-09-02 13:08                                 ` Stefan Monnier
  1 sibling, 1 reply; 43+ messages in thread
From: Jason Rumney @ 2012-09-02 12:27 UTC (permalink / raw)
  To: Achim Gratz; +Cc: emacs-devel

Achim Gratz <Stromeko@nexgo.de> writes:

>> One thing that wasn't discussed was how to set the
>> seed, for people who want to do debugging and who want
>> repeatable random sequences.
>
> I don't think it's a good idea to be able to change the global PRNG
> state in general.

For some uses of pseudo-random numbers, repeatability is desirable.

Not every problem that requires randomness involves security.




^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-02 12:27                               ` Jason Rumney
@ 2012-09-02 13:08                                 ` Stefan Monnier
  0 siblings, 0 replies; 43+ messages in thread
From: Stefan Monnier @ 2012-09-02 13:08 UTC (permalink / raw)
  To: Jason Rumney; +Cc: Achim Gratz, emacs-devel

>>> One thing that wasn't discussed was how to set the
>>> seed, for people who want to do debugging and who want
>>> repeatable random sequences.
>> I don't think it's a good idea to be able to change the global PRNG
>> state in general.
> For some uses of pseudo-random numbers, repeatability is desirable.

Other than debugging, such repeatability needs generally imply the need
to use a separate PRNG, rather than the global one.

> Not every problem that requires randomness involves security.

Lack of repeatability is a feature that's not only needed by security,
but by the need to behave differently each time, otherwise the user
gets bored.
And AFAICT, all uses of `random' in Elisp currently fall in this camp.


        Stefan



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-01 13:19                               ` Paul Eggert
@ 2012-09-04 19:19                                 ` Nix
  2012-09-04 20:07                                   ` Paul Eggert
  0 siblings, 1 reply; 43+ messages in thread
From: Nix @ 2012-09-04 19:19 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Achim Gratz, emacs-devel

On 1 Sep 2012, Paul Eggert told this:

> On 09/01/2012 12:19 AM, Achim Gratz wrote:
>> On systems having a better source of entropy (like
>> /dev/urandom), the init value should be taken from that source rather
>> than the "mix PID with current time" hack.
>
> This is on my list of things to do, as a gnulib project.
> Among other things, I plan to use the RDRAND instruction
> available on current Intel processors, as that's much
> faster and better than /dev/urandom.

... except if your /dev/urandom is seeded from some other hardware
source. This is fairly often true, as such sources are available very
cheaply nowadays. Since /dev/urandom is Linux-specific, and since the
Linux kernel already has patches upstream to use RDRAND to supply
randomness (but *not* entropy-estimate) to /dev/urandom, I'd recommend
using /dev/urandom unconditionally, certainly for rare seeding
operations like this where the cost of a kernel ring transition is
insignificant.

Let the OS do this stuff, it's what it's for.

-- 
NULL && (void)



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-04 19:19                                 ` Nix
@ 2012-09-04 20:07                                   ` Paul Eggert
  2012-09-04 20:11                                     ` Nix
  0 siblings, 1 reply; 43+ messages in thread
From: Paul Eggert @ 2012-09-04 20:07 UTC (permalink / raw)
  To: Nix; +Cc: Achim Gratz, emacs-devel

On 09/04/2012 12:19 PM, Nix wrote:
> I'd recommend using /dev/urandom unconditionally,
> certainly for rare seeding operations

Yes, gnulib will have a module to do that, and that's
good enough for rare operations, but it's not enough
in general.  Applications like 'shred' need lots of random
data and /dev/urandom is too slow for that.  For example,
on my platform (AMD Phenom II X4 910e, x86-64, Fedora 17,
coreutils 8.19):

$ time dd if=/dev/urandom of=/dev/null ibs=12k obs=12k count=100000
100000+0 records in
100000+0 records out
1228800000 bytes (1.2 GB) copied, 92.9543 s, 13.2 MB/s

real	1m32.957s
user	0m0.100s
sys	1m32.563s
$ time shred --size=1200000k --iterations=1 /dev/null

real	0m0.670s
user	0m0.491s
sys	0m0.072s

Both applications wrote the same amount of random data to
/dev/null, using the same 12k blocksize.

Originally, 'shred' used /dev/urandom, but users
(rightly) complained that it was a pig, so we went with
something faster -- in this example, over 100x faster.



^ permalink raw reply	[flat|nested] 43+ messages in thread

* Re: random doesn't feel very random
  2012-09-04 20:07                                   ` Paul Eggert
@ 2012-09-04 20:11                                     ` Nix
  0 siblings, 0 replies; 43+ messages in thread
From: Nix @ 2012-09-04 20:11 UTC (permalink / raw)
  To: Paul Eggert; +Cc: Achim Gratz, emacs-devel

On 4 Sep 2012, Paul Eggert told this:

> On 09/04/2012 12:19 PM, Nix wrote:
>> I'd recommend using /dev/urandom unconditionally,
>> certainly for rare seeding operations
>
> Yes, gnulib will have a module to do that, and that's
> good enough for rare operations, but it's not enough
> in general.

Oh, agreed. But Emacs already *has* a PRNG, and nobody is suggesting
replacing it, just changing how it's seeded (and maybe making it support
multiple state vectors). For a single seeding, /dev/random is quite
enough.

>              Applications like 'shred' need lots of random
> data and /dev/urandom is too slow for that.  For example,

Oh yes, definitely agreed. You can get random noise sources on the order
of kilobits per second cheaply, but anything much faster than that
requires a PRNG anyway, so /dev/random devolves into an expensive one of
those.

-- 
NULL && (void)



^ permalink raw reply	[flat|nested] 43+ messages in thread

end of thread, other threads:[~2012-09-04 20:11 UTC | newest]

Thread overview: 43+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2012-08-24  5:47 random doesn't feel very random Ivan Kanis
2012-08-24  6:22 ` Tassilo Horn
2012-08-24 17:19   ` random doesn't feel very random, random doesn't feel very random, " Ivan Kanis
2012-08-24 18:50     ` Stephen J. Turnbull
2012-08-25  7:46       ` Ivan Kanis
2012-08-24  6:30 ` Leo
2012-08-24 22:48   ` Richard Stallman
2012-08-24 22:57     ` Andreas Schwab
2012-08-25 20:55       ` Richard Stallman
2012-08-25 23:25         ` Leo
2012-08-26 13:12           ` Richard Stallman
2012-08-26 14:24             ` Achim Gratz
2012-08-26 23:22               ` Leo
2012-08-27  0:50               ` Stefan Monnier
2012-08-27  6:31                 ` Simon Leinen
2012-08-27  3:41               ` Richard Stallman
2012-08-27  4:48                 ` Stefan Monnier
2012-08-31  9:41                   ` Eli Zaretskii
2012-08-31 15:06                     ` Stefan Monnier
2012-08-31 15:23                       ` chad
2012-08-31 17:50                       ` Eli Zaretskii
2012-08-31 19:43                         ` Stefan Monnier
2012-09-01  1:18                           ` Paul Eggert
2012-09-01  7:19                             ` Achim Gratz
2012-09-01 13:19                               ` Paul Eggert
2012-09-04 19:19                                 ` Nix
2012-09-04 20:07                                   ` Paul Eggert
2012-09-04 20:11                                     ` Nix
2012-09-02 12:27                               ` Jason Rumney
2012-09-02 13:08                                 ` Stefan Monnier
2012-09-01  7:22                             ` Ivan Kanis
2012-09-01 11:13                             ` joakim
2012-08-31 23:04                       ` Leo
2012-08-27  5:17                 ` Achim Gratz
2012-08-31  9:42                   ` Eli Zaretskii
2012-08-31 15:07                     ` Stefan Monnier
2012-08-31 17:50                       ` Eli Zaretskii
2012-08-26  9:06         ` Ivan Kanis
2012-08-24  7:03 ` Stephen J. Turnbull
2012-08-24  9:10   ` Paul Eggert
2012-08-24 17:45     ` Stephen J. Turnbull
2012-08-24 12:45 ` OT: appropriateness of "random" for playlist generation (was: random doesn't feel very random) Jeremiah Dodds
2012-08-24 14:37 ` random doesn't feel very random Drew Adams

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).