In article <87k6ojltot.fsf@kafka.homenet>,
israel  <rambam@bigpond.net.au> wrote:
>Terje Mathisen <terje.mathisen@hda.hydro.com> writes:
>
>> The fun part is that not only will they write Hamlet, in all living
>> and dead languages expressible on said typewriter, they will also
>> write them with all possible typos.
>
>I have always wanted to read a version in which the prince was named
>Omelette.

http://www.bigidea.com/videos/veggietales/vt015/default.htm


dave

-- 
Dave Vandervies                                  dj3vande@csclub.uwaterloo.ca
You know, you should never say something like "No one is expecting..." on
Usenet. It is just too easy to disprove. The preferred form is "No one in his
right mind is expecting..."       --Stephan H.M.J. Houben in comp.lang.scheme

> Clifford Heath <no@spam.please> wrote:

> And yes, I know MD5 isn't perfect :-).

Nor was your email msg to me, Clifford :-)
Unreplyable, and no clues of what the address might be.

-- 
Regards, Bob Niland                        mailto:name@ispname.tld
http://www.access-one.com/rjn           email4rjn AT yahoo DOT com
NOT speaking for any employer, client or Internet Service Provider.

In comp.arch Guy Macon <http://www.guymacon.com/> wrote:
> gavin@allegro.com (Gavin Scott) writes:

>> And unfortunately almost all programming language runtime systems 
>> have historically used generators with at best 32-bit math (some
>> are even limited to 16 bits!)

> Are you perhaps confusing using 32-bit math with having a 
> 32-bit internal state?  The RC4 algorithm uses 8-bit math, 
> has a 256-byte internal state, and works quite well as a
> pseudorandom number generator.

Yes sorry, I meant to say that the internal state was limited.  The
math used for the calculations should not be relevant.

G.

In article <wcc64ztocwq.fsf@shell01.TheWorld.com>,
Robert A Duff <bobduff@shell01.TheWorld.com> writes:
|> gavin@allegro.com (Gavin Scott) writes:
|> 
|> > In comp.arch Robert A Duff <bobduff@shell01.theworld.com> wrote:
|> > > Ada has some requirements on the built-in (pseudo) random number
|> > > generators.  See:
|> > 
|> > > http://www.adaic.org/standards/95aarm/html/AA-G-2-5.html
|> > 
|> > > I don't really understand this stuff.  Does it result in "terrible",
|> > > as you say, output?

I could produce a generator that passed all those, and was close to
terrible, but would have to work at it.

|> > Nice short summary of Knuth's tests for randomness in there.
|> > 
|> > But it only requires a period of 2^31-1,
|> 
|> 2**31-2, actually.  I'm not sure why it's not 2**31-1.

To allow a 'pure' multiplicative generator with a modulus of 2**31-1.

|> > Looks like a nice formal requirement that the PRNG at least not be
|> > abysmally bad :-)
|> > 
|> > But those requirements still don't get you a PRNG that you'd want to
|> > use for any serious application I think.

Agreed.

|> > Offhand I don't recall whether the simple linear congruential generators
|> > can be constructed to pass Knuth's tests or not (Knuth probably says).

No, not at all.  Knuth is, at best, an elementary introduction and
contains some blind spots.  There are ways of generating excellent
linear congruential generators (clue: VERY large moduli).

|> The (pseudo) random number generator included in GNAT (the free Ada
|> compiler) has this comment.  And we use the same algorithm in our
|> compiler (SofCheck, Inc.):
|> 
|> --  Note: the implementation used in this package was contributed by
|> --  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
|> --  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
|> --  particular choices for P and Q chosen here guarantee a period of
|> --  562,085,314,430,582 (about 2**49), and the generated sequence has
|> --  excellent randomness properties. For further details, see the
|> --  paper "Fast Generation of Trustworthy Random Numbers", by Robert
|> --  Eachus, which describes both the algorithm and the efficient
|> --  implementation approach used here.

Oh, Lordy!  Please, NO!  I haven't seen the latter paper, but the
former is SERIOUSLY misleading - note that I am not criticising its
mathematics, but the way that it presents them for the layman.

Blum, Blum and Shub is an interesting result, but most non-specialists
will miss that it is a randomness-expansion method - very unlike more
traditional generators.  Furthermore, it will expand N bits to N^k
for some (unknown) value of k, but not necessarily beyond - I have a
test that will cause it to fail at 2^(N/3), with no knowledge of the
internals.  And, lastly, the proof is asymptotic and therefore may
not work for small numbers (which, in pure mathematics terms, may
mean any reasonable ones).

|> I haven't read the paper (and probably wouldn't understand it if I did).
|> Does this (2**49) seem reasonable?  Good?  Better than usual?
|> It certainly seems to exceed the requirements of the Ada language
|> standard.

Bad.  Better than the obsolete and trash generators, nowhere near
state of the art in 1970.  A period of 2^49 means that you should
NEVER use more than 2^32 numbers in a complete simulation.

|> In your opinion, should a language standard require a PRNG that *can* be
|> used in serious applications, or should it make some minimal
|> requirements, and let the serious people roll their own?

Given the extreme specialisation of this area, neither.  It should
either not include one at all, or two with specifications like:

    double random_a (void);

This is intended for use in statistical simulations.  Its precise
algorithm shall be implementation-defined.

    unsigned char *random_b (void);

This is intended for use in cryptography.  Its precise algorithm
shall be implementation-defined.

Do more than that, and 99.99% of people WILL get it badly wrong.


Regards,
Nick Maclaren.

gavin@allegro.com (Gavin Scott) writes:

> And unfortunately almost all programming language runtime systems 
> have historically used generators with at best 32-bit math (some
> are even limited to 16 bits!)

Are you perhaps confusing using 32-bit math with having a 
32-bit internal state?  The RC4 algorithm uses 8-bit math, 
has a 256-byte internal state, and works quite well as a
pseudorandom number generator.

"Dennis M. O'Connor" wrote:
> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote ...
> 
... snip ...
>>
>> I haven't read the paper (and probably wouldn't understand it if
>> I did). Does this (2**49) seem reasonable?
> 
> If the thing is run at 1GHz it would repeat in about 150 hours.
> So it is probably fine for a SW implementation driving, say,
> Monte Carlo simulation, but I wouldn't use it as the basis
> of a stream cipher on a gigabit/sec communication link.
> 
>> In your opinion, should a language standard require a PRNG that
>> *can* be used in serious applications, or should it make some
>> minimal requirements, and let the serious people roll their own?
> 
> Serious people won't trust the compiler's PRNG anyway.
> So don't worry about it too much.

I would say that is a fair assesment.  Whatever is supplied is
probably adequate for most Monte Carlo or solitaire use, but needs
investigation when lives or money are involved.  There is no such
thing as an uncrackable cipher (except possibly the one time pad). 
The great advantage of a PRNG is that it IS repeatable, so that it
can be used to thrash software and algorithms, implement regression
testing, etc.  That is a serious use, so I would quibble with your
dividing line terminology :-)

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcc64ztocwq.fsf@shell01.TheWorld.com...
> In your opinion, should a language standard require a PRNG that *can* be
> used in serious applications, or should it make some minimal
> requirements, and let the serious people roll their own?

The serious people will always roll their own because it's not in their
nature to rely on others' code regardless of what properties it claims -- 
claims which may be false in practice, regardless of standards.  Even if
your PRNG is perfect they'll reimplement the same algorithm (or a better
one) on their own rather than risk you screwing up their product with a
well-intentioned change down the road.

IMHO, a language should have minimal requirements because an implementation
can always provide a higher quality -- but never lower.  Let the buyer make
the decision on what is most important to them.

S

-- 
Stephen Sprunk        "Stupid people surround themselves with smart
CCIE #3723           people.  Smart people surround themselves with
K5SSS         smart people who disagree with them."  --Aaron Sorkin

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote ...
> The (pseudo) random number generator included in GNAT (the free Ada
> compiler) has this comment.  And we use the same algorithm in our
> compiler (SofCheck, Inc.):
>
> --  Note: the implementation used in this package was contributed by
> --  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
> --  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
> --  particular choices for P and Q chosen here guarantee a period of
> --  562,085,314,430,582 (about 2**49), and the generated sequence has
> --  excellent randomness properties. For further details, see the
> --  paper "Fast Generation of Trustworthy Random Numbers", by Robert
> --  Eachus, which describes both the algorithm and the efficient
> --  implementation approach used here.
>
> I haven't read the paper (and probably wouldn't understand it if I did).
> Does this (2**49) seem reasonable?

If the thing is run at 1GHz it would repeat in about 150 hours.
So it is probably fine for a SW implementation driving, say,
Monte Carlo simulation, but I wouldn't use it as the basis
of a stream cipher on a gigabit/sec communication link.

> In your opinion, should a language standard require a PRNG that *can* be
> used in serious applications, or should it make some minimal
> requirements, and let the serious people roll their own?

Serious people won't trust the compiler's PRNG anyway.
So don't worry about it too much.
--
Dennis M. O'Connor    dmoc@primenet.com 

gavin@allegro.com (Gavin Scott) writes:

> In comp.arch Robert A Duff <bobduff@shell01.theworld.com> wrote:
> > Ada has some requirements on the built-in (pseudo) random number
> > generators.  See:
> 
> > http://www.adaic.org/standards/95aarm/html/AA-G-2-5.html
> 
> > I don't really understand this stuff.  Does it result in "terrible",
> > as you say, output?
> 
> Nice short summary of Knuth's tests for randomness in there.
> 
> But it only requires a period of 2^31-1,

2**31-2, actually.  I'm not sure why it's not 2**31-1.

>...which certainly isn't useful
> for security applications (given a very small number of sequential
> outputs from such a generator you can predict the next value to be
> generated with fairly high probability etc.).
> 
> Looks like a nice formal requirement that the PRNG at least not be
> abysmally bad :-)
> 
> But those requirements still don't get you a PRNG that you'd want to
> use for any serious application I think.
> 
> Offhand I don't recall whether the simple linear congruential generators
> can be constructed to pass Knuth's tests or not (Knuth probably says).

OK, thanks.

The (pseudo) random number generator included in GNAT (the free Ada
compiler) has this comment.  And we use the same algorithm in our
compiler (SofCheck, Inc.):

--  Note: the implementation used in this package was contributed by
--  Robert Eachus. It is based on the work of L. Blum, M. Blum, and
--  M. Shub, SIAM Journal of Computing, Vol 15. No 2, May 1986. The
--  particular choices for P and Q chosen here guarantee a period of
--  562,085,314,430,582 (about 2**49), and the generated sequence has
--  excellent randomness properties. For further details, see the
--  paper "Fast Generation of Trustworthy Random Numbers", by Robert
--  Eachus, which describes both the algorithm and the efficient
--  implementation approach used here.

I haven't read the paper (and probably wouldn't understand it if I did).
Does this (2**49) seem reasonable?  Good?  Better than usual?
It certainly seems to exceed the requirements of the Ada language
standard.

I can give more implementation details, if you're interested
(this is free software).

In your opinion, should a language standard require a PRNG that *can* be
used in serious applications, or should it make some minimal
requirements, and let the serious people roll their own?

- Bob

In comp.arch Robert A Duff <bobduff@shell01.theworld.com> wrote:
> Ada has some requirements on the built-in (pseudo) random number
> generators.  See:

> http://www.adaic.org/standards/95aarm/html/AA-G-2-5.html

> I don't really understand this stuff.  Does it result in "terrible",
> as you say, output?

Nice short summary of Knuth's tests for randomness in there.

But it only requires a period of 2^31-1, which certainly isn't useful
for security applications (given a very small number of sequential
outputs from such a generator you can predict the next value to be
generated with fairly high probability etc.).

Looks like a nice formal requirement that the PRNG at least not be
abysmally bad :-)

But those requirements still don't get you a PRNG that you'd want to
use for any serious application I think.

Offhand I don't recall whether the simple linear congruential generators
can be constructed to pass Knuth's tests or not (Knuth probably says).

G.