I°) Monte Carlo Method, what is it ?!
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes:optimization, numerical integration, and generating draws from a probability distribution.
Cf. Wikipedia.
II°) And… what about it ?
For being able to approximate PI with this method, we will need to play a game : dart throwing. The structure is an circle inside a square.
1- Empty target 2- Mid Game 3- Full Target
The dart can reach either the square or the circle. By counting the number of darts inside the circle, compared to the total number of darts throwed, we can approximate π.
Indeed, if we take care of the ratio between the area of a circle and the square, which corresponded to the number of darts compared to the total number of darts, we can have an approximation of π. There is only condition : the total darts number need to be high enough.
Ratio = Aire cercle / Aire carré
= π*R² / 4*R²
= π / 4
π = 4 * Ratio
This method is valide if we are using an stationary probability distribution.
III°) Pseudo code
- Display the structure (square and circle)
- For each dart, send it randomly
- Check if the dart arrived inside the circle, count.
- Display the dart final destination, calculate the PI approximation, and got the best score.
- Repeat step 2.
IV°) Code
// *****************************************************************************
// PARAMETERS
// *****************************************************************************
float r = 480; // Radius
int total = 0; // Cnt
int circle = 0; // Cnt
int nbrDarts = 10000; // Nbr of Darts by frame
double record_PI; // Get the best approx
int correctDigit; // Get the correct number of digit
// *****************************************************************************
// SETUP
// *****************************************************************************
void setup() {
size(960, 960);
surface.setLocation(0, 0);
background(0);
translate(width/2, height/2);
stroke(0, 0, 255);
strokeWeight(3);
noFill();
ellipse(0, 0, 2*r-4, 2*r-4);
rectMode(CENTER);
rect(0, 0, 2*r-4, 2*r-4);
record_PI = 0;
}
// *****************************************************************************
// DRAW
// *****************************************************************************
void draw() {
translate(width/2, height/2);
double pi = 0;
strokeWeight(0.5);
// Throw 10 000 darts at the time
for (int i = 0; i < nbrDarts; i++) {
// Create the dart
double x = random(-r, r);
double y = random(-r, r);
// Check if it is inside the circle area, or not
double d = (double)(x*x + y*y);
if (d < (double)r*(double)r) {
stroke(0, 255, 0, 100); // Inside the circle
circle++;
} else {
stroke(255, 0, 0, 100);
}
total++;
// Display it
point((float)x, (float)y);
// Calculate the approximation of pi
pi = (double)4 * ((double)circle / (double)total);
// Getting the best record and displaying it on the console
double recordDiff = Math.abs(Math.PI - record_PI);
double diff = Math.abs(Math.PI - pi);
if (diff < recordDiff) {
recordDiff = diff;
record_PI = pi;
correctDigit = findDifference(Math.PI, pi); // Get the correct digit number of the approximation of PI
if (correctDigit < 0) correctDigit = 0;
println(record_PI + " , nbr good digits = " + correctDigit);
}
}
}
// *****************************************************************************
// METHODS
// *****************************************************************************
// ******************************************
int findDifference(double a, double b) {
Character ch = Character.MIN_VALUE;
String a_s = Double.toString(a).replace('.', ch);
String b_s = Double.toString(b).replace('.', ch);
for (int i = 0; i < Math.min(a_s.length(), b_s.length()); i++) {
if (a_s.charAt(i) != b_s.charAt(i)) return i-1;
}
return 0;
}
V°) Results
In this simulation, i’m throwing 10 000 darts by frame of animation. By getting an FPS of 60, I’m throwing 600 000 darts by seconds. The corect digits number increase fastly before stabilising at 11, which represent my own limit : I’m using double parameters.
I’m getting :
Isdinval's Coding Experiments 