Algorithm for generating normally distributed random values in C?

views:

163

answers:

+2 Q:

Algorithm for generating normally distributed random values in C?

Possible Duplicate:
Converting a Uniform Distribution to a Normal Distribution

Hello.

I'd like to know of any algorithm implemented in C which can take a random value between 0 and 1, the mean and standard deviation and then return a normally distributed result.

I have too little brainpower to figure this out for myself right now.

I can't find anything useful on the internet.

Thank you.

+10 A:

Box-Muller is the transform you need.

Doug Currie 2010-10-09 18:46:59

Thank you for the answer but I need a C implementation or readable pseudocode, not an incomprehensible wikipedia page.

Matthew Mitchell 2010-10-09 19:15:44

I wasn't trying to be rude there, I just need something I can comprehend and use straight away. I am looking for a decent website for that algorithm however, so thank you for your suggestion.

Matthew Mitchell 2010-10-09 19:18:20

+8 A:

There's already been the suggestion for Box Muller, but a computationally simpler approach is simply to take advantage of the central-limit theorem; add enough independent random variables together, and the result will approximate a normal distribution.

Oli Charlesworth 2010-10-09 18:50:08

Thank you for the answer. Will this be efficient enough since many random numbers are needed? Apparently 32 are needed to get a good enough representation.

Matthew Mitchell 2010-10-09 19:22:12

@Matthew Mitchell: It's not possible to answer that answer definitively, without knowing your platform or your accuracy requirements. Your best bet may be to implement both methods and profile. All I can say is that the Box-Muller transform requires evaluations of log, cos, and sqrt, which may well be expensive.

Oli Charlesworth 2010-10-09 19:41:31

It's only for AI and doesn't have to be 100% accurate. Since the function will only be needed seldom I think the speed isn't important anyway.

Matthew Mitchell 2010-10-09 19:44:00

I can't find a *working* Box Muller C function anywhere. I'm giving up on that front. I will try and test the central-limit algorithm. Thanks for your help.

Matthew Mitchell 2010-10-09 19:45:28

@Matthew Mitchell: That's a good response! There are far too many people that obsess over optimising the speed/performance of an algorithm without stopping to check whether it's actually necessary to do so.

Oli Charlesworth 2010-10-09 19:45:30

The normal distribution representation is supposed to represent a standard normal distribution, right? That's important since I need to be able to set the mean and standard deviation correctly.

Matthew Mitchell 2010-10-09 19:47:57

I believe all you need to do is sum your *N* uniform variables (in [0,1]), sutract 0.5'N', and divide by sqrt('N') to get a standard normal distribution.

Oli Charlesworth 2010-10-09 19:52:31

All of the sudden I think I remember doing this for A-level mathematics. That was a year ago. I should remember these things a little better. XD

Matthew Mitchell 2010-10-09 19:55:20

Ah yes, the standard deviation of the means is the standard deviation of the distribution divided by the square root of the sample size. For random numbers between 0 and 1 the standard deviation is 0.316227766 I hope.

Matthew Mitchell 2010-10-09 20:16:31

Well with a little fiddling I got something which works reasonably. For my purposes at least. http://utilitybase.com/paste/wjw I was unable to find a very good histogram utility to test it though.

Matthew Mitchell 2010-10-09 20:50:58

+1 (and a lot more if I could give it!) for central limit theorem. I was about to give this answer before I scrolled down and saw you'd already written it.

R.. 2010-10-09 22:41:52

ansaurus

tags:

views:

answers:

Algorithm for generating normally distributed random values in C?

related questions