Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!news.cs.indiana.edu!noose.ecn.purdue.edu!mentor.cc.purdue.edu!pop.stat.purdue.edu!hrubin
From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: Compilers and efficiency
Summary: Non-uniform random numbers
Message-ID: <12054@mentor.cc.purdue.edu>
Date: 8 May 91 15:46:00 GMT
References: <27fa3350.6bc2@petunia.CalPoly.EDU> <9782@mentor.cc.purdue.edu> <653@ctycal.UUCP>
Sender: news@mentor.cc.purdue.edu
Lines: 40

In article <653@ctycal.UUCP>, ingoldsb@ctycal.UUCP (Terry Ingoldsby) writes:
> In article <11411@mentor.cc.purdue.edu>, hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
> > In article <4082@batman.moravian.EDU>, halkoD@batman.moravian.EDU (David Halko) writes:
> > > In article <9782@mentor.cc.purdue.edu>, hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
> > > > In article <1991Apr5.172533.6717@agate.berkeley.edu>, doug@eris.berkeley.edu (Doug Merritt) writes:
> > > > > In article <1991Apr4.125122.1@capd.jhuapl.edu> waltrip@capd.jhuapl.edu writes:
 
> I had to leave the above 4 lines in, just cause it looks so awesome to see
> a discussion going so many levels deep :^)
 ...
> > Consider the following two operations, which comprise more than 25% of the 
> > operations in some highly efficient, from the "picocode" standpoint, methods
> > for generating non-uniform random numbers.
 
> > 1.  Examine a bit, and take some action depending on it.  Also, the next time
> > this is to be done, this bit effectively no longer exists.  It is necessary
> > to make provision at least somewhere for replenishing the supply of bits.
 
> > 2.  Find the distance to the next one in a bit stream.  The same considerations
> > as above apply.
 
> I have got to ask.  Why is it so generally important that the distance between
> bits can be determined efficiently.  Note that I want to know, `why is it
> important to ME, and to the general computing base?'.  This is the question
> that hardware designers and compiler writers ask themselves.

I believe most people are aware of the existence of simulation, including
Monte Carlo, or Las Vegas, methods for obtaining answers to otherwise
intractable problems.  In these, it is almost always the case that 
considerable use must be made of non-uniform random variables; the 
quantities of interest are usually exponential, normal, Cauchy, binomial,
Poisson, etc., and not uniform.

In any particular problem, it is quite likely that thousands or millions or
even billions of these random numbers will be used.  If this is not a situation
which calls for efficiency, it will do until a real one comes along. :-)
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet)   {purdue,pur-ee}!l.cc!hrubin(UUCP)