Monday, March 26, 2012

Calculating for dummies

Some of my readers might not get very far into this blog post, because calculating is not exactly an exciting subject, particularly when it's "for dummies". That's a pity, though, because the demonstration that I'm about to provide is really quite amazing. I'm going to show you how to obtain a relatively precise value of pi without having to perform any serious mathematics whatsoever.

I can hear a wag saying that you can merely look up the value of pi in Google! Fair enough, but I'm talking here about a method of actually calculating pi, from scratch, rather than simply looking up the value. The final calculation involves little more than a bit of counting followed by a multiplication operation. So, let's go.

To perform the operations I'm about to describe, you'll need a device that fires some kind of projectiles in such a way that you can clearly distinguish their points of impact. An ideal device, for example, would be a so-called air gun that fires birdshot pellets, known as BB slugs.

Having made this high-tech suggestion, let me point out immediately that you can perform the required operations using far more down-to-earth resources. For example, you might use some kind of sticky goo such as chewing gum, or children's putty.

The only requirement is that you must be able to determine precisely the point of impact of each projectile. Marbles or pebbles have to be ruled out because it's almost impossible to determine their points of impact when thrown at a target. So, let's suppose that you've obtained some kind of suitable device...

• Obtain a big square of white cardboard, the bigger the better, and place it flat on the ground beneath a tall tree. Make sure it doesn't move, maybe with the help of a couple of metal spikes.

• Armed with your airgun, or whatever, and a good supply of projectiles, climb up into the tree, high above the square of white cardboard... which will be used as your target. [I forgot to point out that you should probably let your neighbors know beforehand that you're conducting a scientific experiment in computing... otherwise they might become unnecessarily alarmed.]

• Now, here's the essential part of the calculation procedure. You're expected to fire projectiles (slugs, chewing gum, goo, whatever) in the vague general direction of the square of white cardboard down on the ground. Above all, you have to fire at the cardboard in a totally random fashion, without ever aiming deliberately at any particular region of the square. In other words, your projectiles are expected to produce impacts that are scattered all over the cardboard in a completely random fashion. Indeed, if ever you aimed carefully, and you were such a good marksman that all your projectiles hit the middle of the cardboard, then the method I'm describing would not work at all.

• You're expected to carry on bombarding the target with projectiles for as long as possible, until the cardboard is completely covered in impacts.

• When you've produced a huge number of randomly-located impacts (let's say, to be generous, a few tens of thousands), climb down out of the tree and examine meticulously the bombarded square of cardboard. You will have understood by now that my method of "calculating for dummies" is a little weird. Call it a thought experiment, if you prefer.

• Using a corner of the cardboard as the center, draw a circle whose radius is equal to the length of a side of the square. Your big square of cardboard should look something like this:

• In the above representation, we've introduced a color code, to simplify our explanations. Points of impact inside the quadrant of the circle are indicated in red, and the others in blue.

• Start out by counting the number of red impacts, inside the quadrant, which we shall designate as Q. Then count the total number of impacts on the cardboard square, red + blue, which we shall designate as T.

• Divide Q by T, and multiply the result by 4. This will give you a value of pi.

It's easy to understand why this counting procedure should provide us with the value of pi. Consider the ratio of the area of the quadrant and that of the square. Elementary geometry tells us that this ratio is pi divided by 4. And, provided the impacts are scattered randomly over the entire square, then we can see intuitively that Q divided by T should be a good approximation to the value of this same ratio. To put it in simple terms, the quantity of impacts in any particular zone indicates, as it were, the relative area of that zone.

This approach to calculations was named in honor of one of the world's most prestigious gambling temples: the Monte Carlo casino in Monaco, on the French Riviera. When you use the Monte Carlo approach on a computer, you no longer need an airgun and BB slugs to produce your set of arbitrary points. You simply use an application capable of generating random numbers.

The Monte Carlo method of problem solving was invented in 1947 by John von Neumann and two of his colleagues, Stan Ulam and Nick Metropolis, at the Los Alamos National Laboratory in New Mexico. A small group of brilliant scientists, many of whom had recently arrived in the USA, had come together with the intention of designing the world's first full-fledged electronic computer, named Maniac, to be used primarily as a development tool for the hydrogen bomb.

When I started work as a computer programmer with IBM Australia in 1957, the Monte Carlo method had reached the zenith of its popularity as an almost magical problem-solving approach, which fascinated all of us. Today, over half a century later, Monte Carlo computational algorithms are still in widespread use in many simulation contexts.

The Monte Carlo method is entitled to an entire chapter in the middle of George Dyson's interesting and instructive history of computing, Turing's Cathedral.

No comments:

Post a Comment