Biased Random Bitstreams

In the newsgroup comp.arch Achim Gratz asked:

I'm looking for a) any information on the creation of pseudorandom bitstreams with a predetermined density of 1's or 0's.

This is actually quite an interesting problem, if one is concerned with performance. First, lets point out that a sufficient answer can be made quite easily:

SampleBit[i] = (RandFloat(0.0, 1.0) < Density);

Which just requires a good random number generator. Now as to the matter of performance, I proposed an approach where a typical word based random number generator is used. And I noted the following:

Density = 0.25: SampleWord[i] = RandWord() & RandWord(); Density = 0.125: SampleWord[i] = RandWord() & RandWord() & RandWord(); Density = 0.75: SampleWord[i] = RandWord() | RandWord(); Density = 0.875: SampleWord[i] = RandWord() | RandWord() | RandWord(); Density = 0.625: SampleWord[i] = (RandWord() & RandWord()) ^ (RandWord() | RandWord()) Density = 0.1875: SampleWord[i] = RandWord() & RandWord() & (RandWord() | RandWord());

Basically, given the set P of all possible densities that can be constructed, then for any x, y in P, we have that (x*y), (x+y-x*y) and (x+y-2*x*y) (corresponding to &, or, and exclusive or) are also in the set P. P also contains 0.5 (just calling RandWord()). Using this approach, one can approximate any given density with low accuracy fairly quickly.

More random distributions

In the newsgroup comp.programming Andrew asked:

I'm trying to get an algorithm that would pick up a random integer number between 1 and n with a monotonically linear decreasing probability of chosing each element.

I came up with two solutions. Here is the first:

which was improved by Michael Mendelsohn as

I stumbled upon the second idea when considering other alternative distribution modification functions: