2

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.

Community
  • 1
  • 1
Matthew Mitchell
  • 5,293
  • 14
  • 70
  • 122

2 Answers2

10

Box-Muller is the transform you need.

Doug Currie
  • 40,708
  • 1
  • 95
  • 119
  • Thank you for the answer but I need a C implementation or readable pseudocode, not an incomprehensible wikipedia page. – Matthew Mitchell Oct 09 '10 at 19:15
  • 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 Oct 09 '10 at 19:18
8

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.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • 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 Oct 09 '10 at 19:22
  • 1
    @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. – Oliver Charlesworth Oct 09 '10 at 19:41
  • 2
    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 Oct 09 '10 at 19:44
  • 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 Oct 09 '10 at 19:45
  • 1
    @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. – Oliver Charlesworth Oct 09 '10 at 19:45
  • 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 Oct 09 '10 at 19:47
  • 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. – Oliver Charlesworth Oct 09 '10 at 19:52
  • 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 Oct 09 '10 at 19:55
  • 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 Oct 09 '10 at 20:16
  • 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 Oct 09 '10 at 20:50
  • +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.. GitHub STOP HELPING ICE Oct 09 '10 at 22:41