From: hrubin@mentor.cc.purdue.edu (Herman Rubin)
Subject: Re: Goals, Cost, and Flexibility (was Re: "Training" of programmers)
Organization: Purdue University Statistics Department
Date: Sat, 3 Oct 1992 13:34:09 GMT

In article <1992Oct2.161500.25379@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>In article <BvF75z.GBA@mentor.cc.purdue.edu> hrubin@mentor.cc.purdue.edu (Herman Rubin) writes:
>>In article <1992Sep29.232852.22456@CS.ORST.EDU> crowl@jade.CS.ORST.EDU (Lawrence Crowl) writes:
>>>In article <Bv1G5B.AGn@mentor.cc.purdue.edu>
>>>hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>>>>In article <1992Sep22.212534.14185@CS.ORST.EDU>
>>>>crowl@jade.CS.ORST.EDU (Lawrence Crowl) writes:

>>>>This is one of the problems with the current HLLs, the inability to use
>>>>"mathematical" type notation.  I admit that I have not used these aspects
>>>>of C enough to have the syntax right.

>Have you tried J? It's an ascii-based APL derivative. Arrays are arrays,
>and issues like word size, etc., are hidden as much as possible from
>the user. It is the duty of the implementor of J to make it run
>quickly when you perform an operation such as:
>       bitvec i. 1
>to locate the index of the first "1" in bitvec.

There are two types of users involved here; the one who runs the final
applications program, and the one who produces the algorithm.  In many
simulation problems, the algorithms have not been mass produced, and
often the two are the same.

Some of the problems I have mentioned, like unexpected buffer emptying,
are extremely costly in these languages.  I HAVE considered the problem,
and can identify the cost considerations in such a way that the user can
reduce the costs somewhat.  But it is necessary to think at the machine
level to do this.

Look at the bit vector suggestion above.  The random bit vector is going
to be produced by taking a block of words from the random word vector.
To do this, it is clear that one wants the random word vector to be 
composed of all random bits, something not done in most implementations,
but generally no more costly than what is done.  Now one can get around
this by using a separate generator, but this adds to cost.

Also, finding the distance to the next 1 will be needed "gazillions" of
times.  It has an importance comparable to addition or multiplication.

>>>It's time for you to put up some work.  Write up a C (or Fortran, or some
>>>other high-level language) subroutine, using whatever number representation
>>>you deem appropriate, that generates nonuniform random numbers.  I must be
 
>Lawrence has the right idea here: Write the SIMPLEST program you can
>which GETS THE RIGHT RESULT, WITHOUT CONCERN FOR PERFORMANCE.

>In that way, us statistics-ignorant types can then understand the
>specification of your problem. Once WE understand that, suggestions for
>software/hardware/language design improvements can follow.

>Getting caught up in details of performance 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.  And even here, performance is important.  Shamir, Blum,
and others have come up with cryptographically strong pseudo-random number
generators.  It is possible that one might want to use these to seed simpler
procedures, but the factor of hundreds compared to the one I have suggested
is far too large to make them widely used.  There is no single right result;
when one wants a million independent standard normal random variables, the
only thing which has to be right is the distribution.  Independence is extremely
important and extremely difficult to obtain in the uniform random variables--in
fact, pseudo-random numbers cannot hope to do more than approximate it.

>>changing the size of the buffers changes the results.

>This sounds like you have made a basic error in design.

There are costly ways to get around this problem, but only costly ones.
To see why, one will normally start with uniform random numbers.  Now 
suppose one is generating exponential random numbers and normal random
numbers.  Let us oversimplify; suppose we use 500 uniforms to generate
exponentials, and then a procedure using uniforms and exponentials to
generate normals, and cycle this.  This will yield one set of results.
But if the 500 is changed to 600, the first 100 used in the previous
procedure to generate normals are now no longer there.  Obviously the
answers will be different.  Other indeterminacies will make the results
totally different after the first million.  Even a slight change in
the numerical procedure, resulting in a different roundoff, can do
this.

To avoid this, it would be necessary to preserve the "pedigree" of 
every random number used, and considering that there are reused test
random variables, this is not likely to be worth the effort.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@snap.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
Newsgroups: comp.arch,comp.lang.misc