The Box-Muller Technique

July 20th, 2007

So you want a random number from the Normal (Gaussian) distribution, but all you have is a simple random number generator which gives you values from [0.0, 1.0). This came up for me when implementing a Monte Carlo simulation of electron emission from a hot metal surface into vacuum.

The brute-force method for this would be something like this:

  1. Calculate the value of the cumulative distribution function (CDF), i.e. the integral of the Normal distribution, at many points and normalize the whole CDF so that its values fit into the range [0.0, 1.0].
  2. Pick a random number in the range [0.0, 1.0]
  3. Map that random number onto the CDF and find the abscissa where that point is located. This is the random number you want.

This is in fact the general form of the solution to the problem of getting a random number out of any known continuous distribution, and is especially useful when the distribution is not known analytically. But I knew ahead of time that calculating the CDF would be a real bear so I searched around for something easier.

It turns out this problem was attacked in the 1950s in a nice way by Box and Muller. They came up with a nice algorithm for getting random numbers from the Normal distribution which is known as the Box-Muller technique. Several references, including Wikipedia, list more or less the same code for implementing the technique. I found this discussion to be useful. The following code listing gives the “polar form” which returns a random number from the Normal distribution with mean m and standard deviation s. Calls to ranf() yield random floats in [0.0, 1.0].


float box_muller(float m, float s)
{
float x1, x2, w, y1;
static float y2;
static int use_last = 0;

if (use_last) /* use value from previous call */
{
y1 = y2;
use_last = 0;
}
else
{
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 * log( w ) ) / w );
y1 = x1 * w;
y2 = x2 * w;
use_last = 1;
}

return( m + y1 * s );
}

The Camino Browser

June 26th, 2007

Stumbled across this little beauty today and so far I love it. Seems to work better than Firefox and renders controls like check boxes and combo boxes in the true Aqua style.


Get Camino!

My Programmer Type

June 25th, 2007

DHSB? I answered a few humorous questions and this is what I got.

You’re a Doer.

You are very quick at getting tasks done. You believe the outcome is the most important part of a task and the faster you can reach that outcome the better. After all, time is money.

You like coding at a High level.

The world is made up of objects and components, you should create your programs in the same way.

You work best in a Solo situation.

The best way to program is by yourself. There’s no communication problems, you know every part of the code allowing you to write the best programs possible.

You are a liBeral programmer.

Programming is a complex task and you should use white space and comments as freely as possible to help simplify the task. We’re not writing on paper anymore so we can take up as much room as we need.

My new workout video

June 18th, 2007

Can you believe this?

The Surface of the Future

May 31st, 2007

Looks like Microsoft has been up to something really wonderful in the last few years. I have always thought that keyboards and mice were outdated, but this is really quite a big leap. Here’s a broad new canvas for user-interface designers to play on; I’m sure we’ll get some imaginative products out of this technology in the next decade.

Separately, I have thought for a while now that I’d use a mobile device for all my computing needs if I had some other way to interface with it. Which is to say, I don’t want to learn Palm handwriting and I don’t want to type on those idiotic smart-phone keyboards. But if I could plunk my mobile device down on one of these smart surfaces and interact with it that way, voilá, you have a new customer.

If only Microsoft weren’t such a bully I’d like to invest right now.

Commuter Rewards

May 30th, 2007

I started logging my commute back in the fall of last year. Partly I wanted to see how I was making the 5-mile trip from my Emory-area home to my King district office. We do have a family car, so that’s definitely one option I use. But I also love to bicycle, and I wanted another affirmation that cycling is a “good” thing.

It’s called Commuter Rewards because they actually send you rewards. I got a $25 gift card in the mail just for logging my commute. Wow, that’s awesome.

More Wedding Photos

May 23rd, 2007

We’ve just started to gather with the photos from the wedding weekend. Right now I’ve posted pictures from my cousin Julia and my friend Josh.

Many folks have yet to send us pictures that they took. For information on how to get your pictures to me, you can email me or call me. I can’t wait to see what you have.

Oh, and if you want higher resolution copies of any of these, just let me know and I can make them available to you.

Just Married

May 22nd, 2007

Sean and Monica, newlyweds

Photo by Julia Nowlan-Sundari Ide

New Home Page Live

May 8th, 2007

A new version of the Scarlet Antenna LLC home page is now live as of this evening. I chose to keep it simple. A few words about what we do and a javascript-obfuscated email link. I rather like the hint of a red border around the main div which plays nicely with the red antenna on the ant.

Including code with QuickCode

May 5th, 2007

If you want to include your program code in a WordPress blog post, use the quickcode tag once you have installed the QuickCode plugin for your blog.

As an example, I’l include a little ditty from Ruby:

name = ask(”what is your name?”)

puts “very nice to meet you, #{name}”

1.upto(name.length) do |i|

{

puts “I can spell the first #{i.to_s} letters”

}

UPDATE: I’ve given up on Quick Code so ignore this post.