From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Subject: Re: Goals, Cost, and Flexibility (was Re: "Training" of programmers)
Organization: Purdue University Statistics Department
Date: Thu, 15 Oct 1992 13:46:00 GMT

In article <1992Oct15.003551.3465@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>In article <TMB.92Oct13204647@arolla.idiap.ch> tmb@idiap.ch writes:
>>In article <BvJsCy.Jnx@mentor.cc.purdue.edu> hrubin@mentor.cc.purdue.edu (Herman Rubin) writes:

>>   someone writes:
>>   >Getting caught up in details of performance [of random number
>>   >generation] AT ALL is a mistake at this point.

>>   THIS is totally wrong.  Except for the initial generation of uniform random
>>   numbers, almost the entire literature on random number generation is concerned
>>   with performance. [lots of random discussions on the difficulties
>>   of generating "good random numbers" deleted]

>This ^^^ is totally wrong. We START by getting a specification for
>the numbers you (Herman) want to produce. THEN, you worry about HOW
>to produce them efficiently. WE (your audience) are still trying to 
>understand the problem. Once we understand it, AND NOT UNTIL THEN,
>we can propose solutions. Therefore, we STILL are seeking the specification,
>as a SIMPLE program in some common language such as Fortran or C.

It is generally not the case that the random numbers one wishes to use are
uniform.  There are, to my knowledge, no good direct ways of generating 
random varibles with such important distributions as exponential and normal
not starting with uniform.  Other distributions such as beta, gamma, binomial,
etc., also occur; these are handled by starting with uniform and then coming
up with some method.  There are literally an infinite number of methods to
do this, and different methods yield different, but equally valid, results.

>>If the fast generation of random numbers with better properties than
>>those that can be generated with current pseudo-random number
>>generators were really an important practical problem, you can bet
>>that every computer used for scientific computation would include a
>>little gadget to generate random numbers based on some physical
>>source; the hardware involved is well-known, quite simple, and would
>>probably not cost more than a few dollars nowadays (it was more
>>expensive when people stopped doing this for lack of interest).

>This is not exactly correct. ANY uses which I have for random numbers
>REQUIRE that they be reproducible. Otherwise, comparing algorithms, 
>ensuring that your last bug is fixed, etc., is IMPOSSIBLE.
>So, if the "little gadget" gave reproducible results, that would be fine.
>If not, it's useless for many purposes.

There are two problems here.  If one wants to check things, the numbers
produced by the physical process can be stored.  The other problem is
reproducibility of the final results.  This is immensely difficult, and
almost anything from buffer sizes to computer roundoff will destroy it.
One might want to use careful methods for TESTING a procedure, but I
can see no real way around it, except with certain difficult and 
expensive procedures, which I know how to provide, but require the
most careful programming.  Even without buffering, this problem can
occur very easily.

>>But if he really has to solve a problem that requires physical random
>>numbers, he can build himself a little board and plug it into his PC

This is not as easy as one would think.  Suppose you want the probability
of a bit being 0 to be .5 within an error of 10^(-10), given all other bits.
If one is going to do a complicated job, this seems reasonable.  Now maybe
one can test reasonably to 10^(-4), although .001 is more reasonable.  This
is not good enough, and there are ways around it involving multiple bits
and software.  Also, the slightly asymmetric behavior of a flip-flop when
being switched gives problems of this type.

>I suggested to Herman some time ago that an ASIC (Application-specific
>IC) or PGA (Programmable Gate Array) on a prototyping board stuck into
>his machine might be a cheap, simple, and effective solution.

This might be useful for some of the algorithms I have suggested.  It
is unlikely that I will have the time to look into this, but I can 
discuss what is needed with those who wish.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)
Newsgroups: comp.arch,comp.parallel