🚀 go-pugleaf

In article <36984@sdcc12.ucsd.edu>, whart@cs.ucsd.edu (Bill Hart) writes:
|> I have an application for which I need to generate a random 'vector' of 
|> bits of length N.  I have looked at stuff in Numerical Recipies for
|> generating a random sequence of bits, but it remains unclear whether
|> such a generator would be appropriate for generating a random
|> vector of bits.
|> 
|> I need/want to have the distribution of vectors remain 'random'.  Right
|> now I'm generating a random float in [0,1> and testing to see
|> if it is less than 0.5 or not.  This works, but I'm sure there is
|> a better way of doing this.

Standard warnings:

    1) Your current technique is OK, but do NOT break up a random float
into multiple bits to save on efficiency.  Some techniques will survive
this but others will not.

    2) Don't trust Numerical Recipes - about half of its techniques are
reliable, but the others contain serious traps.  In this case it is not
too bad, though your reservations about whether its techniques extend to
vectors are fully justified.

Perhaps the best method for your application is a Tausworthe (also called
shift-register, primitive polynomial over GF(2), etc.) with a generating
polynomial of order at least N.  Knuth and others have details, but finding
a good one is non-trivial and dependent on the size of N, whether it varies
and what degree of randomness you need.  Much of the theory of this sort of
generator is in hardware-related journals.

I am afraid that there is no simple solution to the general case of random
vectors of bits, but there are several fairly reliable ones.


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm@cl.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679