Sign in to follow this  
Pete Michaud

Gaussian Random Number Algorithm

Recommended Posts

I found this page which seems to be what I want, but I'm a little confused: The algorithm is:
float x1, x2, w, y1, y2;
 
do {
       x1 = 2.0 * ranf() - 1.0;
       x2 = 2.0 * ranf() - 1.0;
       w = x1 * x1 + x2 * x2;
} while ( w >= 1.0 );

w = sqrt( (-2.0 * ln( w ) ) / w );
y1 = x1 * w;
y2 = x2 * w;

Where ranf() is a uniform 0 to 1, pseudo-random number generator. Two things that confuse me here: 1) Depending on the language, ranf() might generate different numbers on each iteration of the loop, or it might generate the same numbers because the seed doesn't change. I'm guessing it's different numbers on each iteration, but I want to make sure. 2) The x1 and x2 are confusing me. I think there are x1 and x2 because the author wanted to demonstrate doing this twice, because otherwise I can't figure out why I'd want y1 AND y2 back when I'm trying to generate just one random number? I know that can't be the case, because both x1 and x2 are used together in the last line of the loop, but what do they represent exactly? http://www.taygeta.com/random/gaussian.html

Share this post


Link to post
Share on other sites
1: The random function should return a new random number on each call. Thus, calling it twice, as in the do-while-loop, shall return two different numbers for x1 and x2.

2: The Box-Müller algorithm generates two random numbers per iteration. First time you calculate y1 and y2, and return y1. Second time, you just return y2. Third time, you generate two new values for y1 and y2, and return y1. Fourth time, you return y2. And so on...

Share this post


Link to post
Share on other sites
You'll probably find the Ziggurat algorithm to be a more efficient method for generating numbers from a Gaussian distribution than any other method; though it's a little more complex to implement than the Box-Müller algorithm and it requires initialisation. On the whole (except in a few percent of drawn numbers) it avoids expensive trigonometric or logarithm functions.

Wikipedia entry

I have an implementation in C somewhere if you want it.

Share this post


Link to post
Share on other sites
I should've posted back here!

I came up with a different method that relies on the Central limit theorem. I can't copy and paste the code directly because it's "codified" in a list on the site, but if you visit this page you can see it:

Approximate Gaussian Random Number Generator

That one generates n uniform, random numbers (default n = 4), and converts them to the right scale given mu and sigma. I think it's pretty efficient for my purposes. What do you think?

Share this post


Link to post
Share on other sites
I explain it in the link there, actually. I know it's reasonable: it's just a way for me to randomize the traits of enemies. For example, the average goblin might be 4 feet tall, but I generate a random height based on maybe a 6" sigma, which means they tend to be about 4' but they could be as short as 2' or as tall as 6'. That's perfectly acceptable for my purpose.

Share this post


Link to post
Share on other sites
Yes, approximating a gaussian with a few uniform random samples averaged together is more than gaussian enough for that sort of purpose. Even with only two random samples the accuracy may be good enough for your purposes.

Share this post


Link to post
Share on other sites
I would say that such an approximation may even be better than using a true Gaussian distribution.

When approximating it with two uniform random variables, you have a triangular distribution with well defined lower and upper bounds for the random numbers. You know for sure what the smallest and largest goblins can be. A Gaussian distribution have no lower or upper limit, so sometimes, although perhaps very rarely, you may end up with an enormous goblin, or a goblin with negative height.

Share this post


Link to post
Share on other sites
Quote:
Original post by Brother Bob
I would say that such an approximation may even be better than using a true Gaussian distribution.

When approximating it with two uniform random variables, you have a triangular distribution with well defined lower and upper bounds for the random numbers. You know for sure what the smallest and largest goblins can be. A Gaussian distribution have no lower or upper limit, so sometimes, although perhaps very rarely, you may end up with an enormous goblin, or a goblin with negative height.


I completely agree. Here's an excerpt from the linked page:

Quote:
...The most you’ll ever get is 160, which is +4 sigma (n = 4, sigma = 15, 4 * 15 = 60). +4 sigma is greater than 99.9968% of the population, so it’s actually a really wide range for an approximate value. It’s helpful in my situation to know the upper and lower limits with certainty, because it allows me to plan my art accordingly. For example, if I know that Enemy X will never be larger than 200px tall on screen, then I’ll create the sprites that big. That way, that enemy will never look fuzzy.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this