random doesn't feel very random

random doesn't feel very random

[Ivan Kanis]

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".

Re: random doesn't feel very random

[Tassilo Horn]

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

Re: random doesn't feel very random

[Leo]

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

random doesn't feel very random

[Stephen J. Turnbull]

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.)

Re: random doesn't feel very random

[Paul Eggert]

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.

OT: appropriateness of "random" for playlist generation (was: random doesn't feel very random)

[Jeremiah Dodds]

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

RE: random doesn't feel very random

[Drew Adams]

[-- 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 --]

Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random

[Ivan Kanis]

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.".

Re: random doesn't feel very random

[Stephen J. Turnbull]

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.

Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random

[Stephen J. Turnbull]

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?

Re: random doesn't feel very random

[Richard Stallman]

    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

Re: random doesn't feel very random

[Andreas Schwab]

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."

Re: random doesn't feel very random, random doesn't feel very random, Re: random doesn't feel very random

[Ivan Kanis]

[-- 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 --]

Re: random doesn't feel very random

[Richard Stallman]

    > 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

Re: random doesn't feel very random

[Leo]

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

Re: random doesn't feel very random

[Ivan Kanis]

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".

Re: random doesn't feel very random

[Richard Stallman]

    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

Re: random doesn't feel very random

[Achim Gratz]

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

Re: random doesn't feel very random

[Leo]

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

Re: random doesn't feel very random

[Stefan Monnier]

> 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

Re: random doesn't feel very random

[Richard Stallman]

    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

Re: random doesn't feel very random

[Stefan Monnier]

> 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

Re: random doesn't feel very random

[Achim Gratz]

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

Re: random doesn't feel very random

[Simon Leinen]

[-- 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 --]

Re: random doesn't feel very random

[Eli Zaretskii]

> 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.

Re: random doesn't feel very random

[Eli Zaretskii]

> 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)'.

Re: random doesn't feel very random

[Stefan Monnier]

>> > 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

Re: random doesn't feel very random

[Stefan Monnier]

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

How?


        Stefan

Re: random doesn't feel very random

[chad]

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

Re: random doesn't feel very random

[Eli Zaretskii]

> 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.

Re: random doesn't feel very random

[Eli Zaretskii]

> 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).

Re: random doesn't feel very random

[Stefan Monnier]

> 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

Re: random doesn't feel very random

[Leo]

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

Re: random doesn't feel very random

[Paul Eggert]

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.

Re: random doesn't feel very random

[Achim Gratz]

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

Re: random doesn't feel very random

[Ivan Kanis]

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

Re: random doesn't feel very random

[joakim]

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

Re: random doesn't feel very random

[Paul Eggert]

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.

Re: random doesn't feel very random

[Jason Rumney]

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.

Re: random doesn't feel very random

[Stefan Monnier]

>>> 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

Re: random doesn't feel very random

[Nix]

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)

Re: random doesn't feel very random

[Paul Eggert]

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.

Re: random doesn't feel very random

[Nix]

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)