Simple Random Generators

October 15, 2013

We all need (pseudo)random numbers sooner or later. Are they hard to generate? Depends. If you want them to be really strong (that is, very random), yes, it’s difficult. If you merely need something random-looking, well, you still need some number theory, but it’s rather not complicated.

roulette

Let’s have a look at three simple types: additive, multiplicative, and the infamous linear congruential generator.

Read the rest of this entry »


The Inversion Method (Generating Random Sequences IV)

June 28, 2011

In the first post of this series, I discussed how to generate permutations of sequences using the Fisher-Yates method and I explained (although indirectly) how a linear congruential generator works. In a second post, I explained how to generate 2D points uniformly and randomly distributed a triangle, discussing the method of rejection. In a third post, I’ve discussed how to generate points on a sphere.

All these methods have something in common: they are based on the uniform (pseudo)random generator, and they map uniform numbers onto a shape (or move numbers around, in the first case). What if we need another density function than uniform?

Read the rest of this entry »


Random Points in a Triangle (Generating Random Sequences II)

October 5, 2010

In the first post of this series, I discussed a method to generate a random (guaranteed) permutation. On another occasion, I presented a method to recycle expensive random bits. Today, I will discuss something I had to do recently: generate random points inside a triangle.

Read the rest of this entry »


Generating Random Sequences (part I)

September 29, 2009

Every once in a while, we need a random sequence. Whether to test a data structure’s performance or to run probabilistic unit tests, the provided rand primitive from your favorite programming language has several limitations. First, it’s been known for a while that if most implementations of the C standard library rand() function are not very random, despite being “good enough” in great many cases. Second, and more importantly, it does not allow you to easily control the period nor to generate a permutation on 0\ldots n-1, for example.

dice

There are many methods of generating pseudo-random number sequences. Not all exhibit the same properties and, accordingly, a method may be more useful in one case and perfectly useless in another. High quality pseudo-random number generation is a notoriously hard endeavor, but there is a number of very simple algorithms that will get you out of trouble for certain specific tasks. Let us consider, for example, the example where the pseudo-random generator must generate the numbers in 0\ldots{}n-1 exactly once, in a random order, of course, in exactly n draws.

Read the rest of this entry »


Follow

Get every new post delivered to your Inbox.

Join 74 other followers