Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu!hsdndev!husc6!genrad!stardent!wright
From: wright@Stardent.COM (David Wright)
Newsgroups: comp.arch
Subject: Re: Compilers and efficiency
Message-ID: <1991May8.205106.6039@Stardent.COM>
Date: 8 May 91 20:51:06 GMT
References: <9782@mentor.cc.purdue.edu> <11411@mentor.cc.purdue.edu> <653@ctycal.UUCP>
Organization: Stardent Computer Inc
Lines: 42

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

Hear hear.  And this leads to a second question of HR, which has been
posed once before but not answered (or I missed it):  Why does your
application have to work on a bit stream?  What is wrong with
instead computing the data about the bit stream, and passing the
results along as, say, pairs (a,b), where a is the number of
consecutive 0's and b the number of consecutive 1's in the current
part of the stream?

>Anyway, please tell us.  What is so interesting/useful about non-uniform
>random numbers?

Well, if he's generating numbers that conform to some other
distribution, the results certainly wouldn't be uniform random numbers
(though I think this is usually done by *starting* with a uniform
distribution and then manipulating that into, say, a Gaussian).

  -- David Wright, not officially representing Stardent Computer Inc
     wright@stardent.com  or  uunet!stardent!wright

Groucho:  America is waiting to hear him sing!
Chico:    Well, he can sing pretty loud, but not that loud.
                          -- A Night at the Opera