Generate random numbers following a normal distribution in C/C++

views:

1440

answers:

+5 Q:

Generate random numbers following a normal distribution in C/C++

Does anyone know how I could easily generate random numbers following a normal distribution in C/C++ ?

http://www.mathworks.com/access/helpdesk/help/toolbox/stats/normrnd.html

I don't want to use any of Boost.

I know that Knuth talk about this at length but I don't have his books at hands right know.

Thanks,

+4 A:

A quick and easy method is just to sum a number of evenly distributed random numbers and take their average. See the Central Limit Theorem for a full explanation of why this works.

Paul R 2010-02-24 11:20:33

+1 Very interesting approach. Is it verified to really give normally distributed sub ensembles for smaller groups?

Morlock 2010-02-24 12:53:00

@Morlock The larger the number of samples you average the closer you get to a Gaussian distribution. If your application has strict requirements for the accuracy of the distribution then you might be better off using something more rigorous, like Box-Muller, but for many applications, e.g. generating white noise for audio applications, you can get away with a fairly small number of averaged samples (e.g. 16).

Paul R 2010-02-24 13:25:26

Plus, how do you parametrize this to get a certain amount of variance, say you want a mean of 10 with a standard deviation of 1?

Morlock 2010-02-24 13:26:11

@Morlock: To get a given mean and SD you scale your underlying samples properly. Generally, the underlying samples, *u*, are uniform over 0 to 1. Make them uniform over -1 to +1 (compute 2 *u* -1). You can then add the desired mean and multiply to get the desired standard deviation.

S.Lott 2010-02-24 13:39:42

@Morlock If you scale your PRNG to give random numbers in the range -1.0 to +1.0 then you get a mean of 0.0 and a variance of 0.5 when you take a sufficiently large average. You can just linearly shift and scale either the input numbers or the output average to get whatever mean and variance you need.

Paul R 2010-02-24 13:39:52

@S.Lott I can easily see how to scale a distribution given a known SD and mean, as you suggest, but it looks a lot less straight forward to do so with a distribution generated using the central limit theorem, given that 3 values will affect the level of stochasticity: the number of 1) original random numbers; 2) values used in the averages; 3) averages done. I guess you must do quite a number of trials (1000s) to parametrize the whole thing before you can be comfortable to scale it appropriately :) Not that it would necessarily be very heavy on computation time. Cheers!

Morlock 2010-02-24 22:19:04

+2 A:

Use std::tr1::normal_distribution.

The std::tr1 namespace is not a part of boost. It's the namespace that contains the library additions from the C++ Technical Report 1 and is available in up to date Microsoft compilers and gcc, independently of boost.

Joe Gauterin 2010-02-24 11:23:09

TR1 is not boost.

Joe Gauterin 2010-02-24 11:31:13

TR1 is not standard, either.

anon 2010-02-24 11:39:00

He didn't ask for standard, he asked for 'not boost'.

Joe Gauterin 2010-02-24 11:43:48

+5 A:

The Box-Muller transform is what is commonly used. This correctly produces values with a normal distribution.

http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_for_normal_random_variables

http://en.wikipedia.org/wiki/Box_Muller_transform

The math is easy. You generate two uniform numbers and from those you get two normally distributed numbers. Return one, save the other for the next request of a random number.

S.Lott 2010-02-24 11:24:31

If you need speed, then the polar method is faster, though. And the Ziggurat algorithm even more (albeit much more complex to write).

Joey 2010-02-24 12:15:55

Here are some solutions ordered by ascending complexity.

Add 12 uniform numbers from 0-1 and subtract 6. This will match mean and standard deviation of a normale variable. An obvious drawback is that the range is limited to +/-6 - unlike a true normal distribution.
Box muller transform - was listed above, and is relatively simple to implement. If you need very precise samples however, be aware that the Box muller transform combined with some uniform generators suffers from an anomaly called Neave Effect. See e.g. page 13 of math.ucalgary.ca/~aware/amat601.21/docs/week4.pdf . (Sorry, I am forced to mutilate the link due to reputation.)
For best precision I suggest drawing uniforms and applying the inverse cumulative normal distribution to arrive at normal distributed variates. You can find a very good algorithm for the inverse cumulative normal distribution at

http://home.online.no/~pjacklam/notes/invnorm/#Overview

Hope that helps

Peter

Peter G. 2010-02-24 12:29:46

ansaurus

tags:

views:

answers:

Generate random numbers following a normal distribution in C/C++

related questions