Random Number Generation -----> Hardware or Software?

...while responding to a post by a particular individual who has, in the past, done what you described but not for the reason you gave. I don't killfile when I am losing an argument, but rather when someone stops having a reasoned discourse and engages in personal attacks.

No and no. I made a neutral statement about why I killffile. The fact that it is in a reply to you shows that you have not engaged in personal attacks - at least not since I changed my news reader and had to start a new killfile - and thus are not includes in the class "killfiled." If you were, I would not have seen your post, and thus would not have replied to it.

Ada has some requirements on the built-in (pseudo) random number generators. See:

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

- Bob

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.

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

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

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.

Serious people won't trust the compiler's PRNG anyway. So don't worry about it too much.

-- Dennis M. O'Connor snipped-for-privacy@primenet.com

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

... snip ...

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

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.

In article , Robert A Duff writes: |> snipped-for-privacy@allegro.com (Gavin Scott) writes: |> |> > In comp.arch Robert A Duff wrote: |> > > Ada has some requirements on the built-in (pseudo) random number |> > > generators. See: |> > |> > >

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

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

G.

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

-- Regards, Bob Niland mailto: snipped-for-privacy@ispname.tld

email4rjn AT yahoo DOT com NOT speaking for any employer, client or Internet Service Provider.

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