Everyone loves PI don’t they? Cherry, Apple, Blackberry and even Pumpkin is which is one of my all time favorites! Ok, I am not talking about that kind of pie or that geeky guy who called himself PI on Beauty and the Geek (love that show… why? Because I am a geek and wishing I could hook up with hot super model chicks who depend on my intelligence and willing to show their love because of it). I am talking about that PI which is the magical mathematical constant of the universe. The one which is said to never repeat and goes off into eternity. It is easily calculated by using the circumference of a circle divided by its diameter. But there are more fun ways to find the elusive PI. So put on your safari hat, grab your elephant gun, and lets go hunting on this entry of the Programmer’s Underground!

We can find PI using what is known a Monte Carlo method. The term Monte Carlo can be applied to a whole group of algorithms often in physical and mathematical systems. This one in particular uses the idea of a dartboard where a person simulates throwing a dart several times. Using randomness, the ratio to those darts that land in the dartboard verses those that land outside the dartboard will get close to PI with the increased number of throws. So for instance, usually throwing the dart 10,000 times will be closer to PI than throwing the dart only 100 times. It is extremely rare (if not impossible) to hit PI exactly, so in our program we are going to also show the difference away from PI we come. The method is described as PI = (4.0 * (hits / darts thrown))

To demonstrate this process we are going to use Java and whip up a nice little three function project. One function of course will be main. Main will ask the user for the number of dart throws they wish to do. It reads an integer and passes it to another function called computePI(). In this function we do a few things. We first create a random number generator which is going to generate us some double data types by calling nextDouble() and gives us an X and Y coordinate of where the dart landed. We pass these coordinates to our isInside() function determine if the darts fell inside or outside of the dartboard bounds.

To determine if the dart is inside or outside of the dartboard, we square the X coordinate and the Y coordinate, add them together and square root. If this distance is less than 1, meaning it is less than one unit away from the center of a circle, we know we are in the dartboard and thus return true. Otherwise if the distance is greater than or equal to 1, we are outside the dartboard. Simple enough right? To help you think of this, imagine a circle and picking a random point inside the circle. If the circle has a diameter of 2 (radius of 1), no point in the circle will be greater than 1 away from the center point.

So once the isInside() function has completed and returns true or false on whether or not we hit the dartboard or not, we increment the hit counter if it landed inside. At the end of our loop, we will then have how many darts hit the board and we know how many darts were thrown. We now plug them into the Monte Carlo method listed above and we get an estimate close to PI.

To determine the difference, in main(), we subtract our value from the value given by the constant PI in the Math Java package to determine how far we were off. As we increase the number of throws we do, we should see it get relatively closer to PI and the difference slowly decrease. As mentioned earlier, it is pretty much impossible to hit PI exactly using this method but we can get pretty close given enough throws.

The output of this program could also eventually be graphed (I will let you do that part) to show the general relationship of our algorithm verses the constant.

Here is our Java code to describe the process above…

import java.util.*; public class CalculatePI { // Print a very basic program description and ask for number of throws public static void main (String[] args) { Scanner reader = new Scanner (System.in); System.out.println("This program approximates PI using the Monte Carlo method."); System.out.println("It simulates throwing darts at a dartboard."); System.out.print("Please enter number of throws: "); int numThrows = reader.nextInt(); double PI = computePI(numThrows); // Determine the difference from the PI constant defined in Math double Difference = PI - Math.PI; // Print out the total results of our trials System.out.println ("Number of throws = " + numThrows + ", Computed PI = " + PI + ", Difference = " + Difference ); } // Determine if dart thrown is inside the dart board public static boolean isInside (double xPos, double yPos) { double distance = Math.sqrt((xPos * xPos) + (yPos * yPos)); return (distance < 1.0); } // Calculates PI based on the number of throws versus misses public static double computePI (int numThrows) { Random randomGen = new Random (System.currentTimeMillis()); int hits = 0; double PI = 0; for (int i = 1; i <= numThrows; i++) { // Create a random coordinate result to test double xPos = (randomGen.nextDouble()) * 2 - 1.0; double yPos = (randomGen.nextDouble()) * 2 - 1.0; // Was the coordinate hitting the dart board? if (isInside(xPos, yPos)) { hits++; } } double dthrows = numThrows; // Use Monte Carlo method formula PI = (4.0 * (hits/dthrows)); return PI; } }

You can follow along using the in code comments and the steps outlined prior to the code to see how things work. With a few tweaks here and there, this method could also be ported over to C++ or a .NET language if you so desire. The idea is there and pretty straight forward. Do what you like with the code but keep in mind that for simplicity sake, there is no error trapping in here. If you were to add checking, I would suggest trapping your errors when the user enters the value and determine they are entering an integer.

Now as all the relatives start making their way to your house for Christmas dinner, you can sit around the the fireplace and you can dazzle them with your Monte Carlo wizardry while sipping the eggnog. It might even get you a few more kisses under the mistletoe. Hey, hot super model chicks dig guys with brains. They even said so on TV!

Enjoy! ðŸ™‚

© 2024 The Coders Lexicon. All rights reserved. Privacy Policy