Learn to Code via Tutorials on Repl.it!

← Back to all posts
The Monte Carlo method explained

Thanks to this youtuber for first introducing me to this problem.

In this tutorial, we’ll be solving a problem. Now this is actually one of my favourite problems cause it’s so ridiculous it makes absolutely no sense. Here’s the problem:

"Giving a bunch of randomly generated numbers between the values of 0 and 1...

approximate PI"

I know, this sounds absolutely nuts! Like what? Calculate PI using a bunch of numbers? How?? That's what I first said when I saw this problem. Well, let’s solve it!

Well first, let’s think about this problem. So you have an array of randomly generated values, and you’re trying to calculate PI. So let’s think, what do we use PI for? Or think about where you would see PI in the math world.

Maybe the area of a circle?

Hmm… we’re getting somewhere. But how are we going to relate a circle to a bunch of numbers? Well, what thing can have shapes and numbers?

Coordinate grid?

Try to take two numbers, and turn them into coordinates (first number is the x value, second is the y). Then plot them on a grid, and you should have something that looks like this:

Oh, and the circle:

Okay, but how do we calculate PI? Well, what formulas can we make of this? There isn’t a formula that solves for PI right away like: `PI = something`, however, there are formulas which contain PI, and then we can just solve for PI! So what formulas contain PI? Maybe:

``(𝜋r^2) / (2𝜋)^2 = (number of points in the circle) / (number of total points)``

So we did this by taking the area of the circle, and dividing that by the total number of points (think of the grid as a square). Remember, the points in shapes represent the areas of that shape. Well, like, if there’s 10 points in the circle, it doesn’t mean the circle’s area is 10, it is just a ratio of the area. And the more points we have, the better we can then represent the area, and the more accurate answer we have!

But wait, we must first solve the equation for PI (sorry if it’s a little blurry).

And there we go! We have PI is equal to points inside the circle divided by the total points, and multiplied by 4!

But how do we know if a point is in the circle? Well we can get the distance between that point and the center of the circle. But how do we find the distance between a point (x, y) and the center of the circle (0.5, 0.5)? Well we have to use the Pythagorean theorem!

So what I did was create two points, A and B, and basically just did some math. Oh, and remember to take the absolute value of the distance since we don’t want negatives!

So let’s code this (C++)!

``````#include <iostream>
#include <cmath>
#include <ctime>

int main()
{
srand(time(NULL)); // used to generate different random numbers

double total = 100; // total number of points
double inside = 0; // number of points in the circle

double x, y; // coordinates

for (int a = 0; a < total; ++a)
{
// generates a random number between 0 and 100, and divides
// it by 100 to make a decimal between 0 and 1

x = (rand() % 100) / 100.0;
y = (rand() % 100) / 100.0;

// using the Pythagorean theorem to calculate the distance
// between the center of the circle and the point

x = abs(0.5 - x);
y = abs(0.5 - y);

if (sqrt(x*x + y*y) <= 0.5) // 0.5 is the radius of the circle
inside += 1;
}

std::cout << 4 * (inside / total); // displaying the result
}``````

Output:

``3.2``

Close. But can we do better? Instead of creating 100 points, what about 1000?

Output:

``3.116``

Better. But how close can we get?

``````10’000      - 3.1236
100’000     - 3.13216
1’000’000   - 3.13904``````

Close enough. It really depends on your compiler on how big you can get.

Oh, and as a bonus, I did this in Processing and made some visuals! Cause who doesn’t like visuals?

``````long total = 1000; // total number of points that will be created
float inside = 0; // number of points inside the circle

int p1; // point 1 - x coordinate of dot
int p2; // point 2 - y coordinate of dot

void setup()
{
/* don't worry about any of the below code */

size(500, 500); // creates screen
background(255); // sets the colour of the background to white

noFill(); // makes circle transparent so we can see points inside
stroke(255, 0, 0); // sets circle outline to red
ellipse(250, 250, 500, 500); // draws circle

stroke(0, 0, 255); // sets the colour of the dots to blue

/* don't worry about any of the above code */

for (int a = 0; a < total; ++a) // this loop creates dots
{
p1 = int(random(0, 500)); // random x coordinate
p2 = int(random(0, 500)); // random y coordinate

ellipse(p1, p2, 1, 1); // draws dot at random x and y coordinates

// if the distance between the dot and the center is below 500 (radius of the circle)
if (dist(p1, p2, 250, 250) <= 250)
inside += 1;
}

print(4 * (inside / total)); // displays result to the console
}``````

Oh, and I used a 500 by 500 grid instead of a 1 by 1 since it’s easier to visualize. But the same idea. Also, there’s this thing called the `dist()` function in Processing that calculates the distance for you! Why can’t C++ have cool things like that? :(

Output:

``````(open the links if you want to see the pictures)

1000 - 3.148

10’000 - 3.1356

100’000 - 3.14716
(you can barely see the circle!)

I also modified this a little bit and created a loop, and after a few minutes of calculating, the closest I could come was `3.14156`. The actual value of PI is `3.14159`! So close!

Well, I’ll call that a success! We approximated PI using just random numbers!

Now what we did here was called the Monte Carlo method. We used a bunch of random samples to calculate a numeric value. Now in this tutorial, I used the Monte Carlo method to calculate PI, but you can you it for all sorts of things, even estimating stock prices!

Maybe I'll post another tutorial later explaining another cool thing we can do with this.

Well, hope you guys learned something cool today, and don’t forget to like!

reachtarunhere (1)

Very cool. Thanks for the lucid explanation!

c4syner (78)

This is actually super interesting. Nice project!

Highwayman (1442)

And suddenly a war had broken out between the #πthon and #C++Gang! It was chaos!!
BA BOOM

Anyways. Nice tutorial! It was super awesome learning that. Why did you use the c RNG instead of <random> though?

DynamicSquid (4550)

@Highwayman I get it, nice one lol. Also I don't know. This is like the first time I used a random number in C++, so I just picked the first one that came up on the web. Is <random> better?

Highwayman (1442)

@DynamicSquid oh lol. Yes, in this case yes. Well actually I’d say in most cases yes. It is a little daunting though to a beginner’s eyes I guess so maybe it was better that you used rand().

xxpertHacker (627)

@Highwayman Actually, I'd already made like 4 whole programs in C++ and JS to compete w/ LizFoster, and I had successfully gained higher approximations and at the same time wrote out my math and embarrassed her because she made comments on my math, but delayed in catching her errs.
This was weeks ago.
You should try to find my conversation w/ Liz here: EVEN MORE APPROXIMATIONS OF p, it's worth it.

Here's a few of my Repls on it, I'ma go make a share post to compete with Liz within the next 24 hours.

Wanna make a math / code 1 v 3?
LizFoster vs. StudentFires, Highwayman, and DynamicSquid?

Highwayman (1442)

@StudentFires 1)my WiFi died for like 3 days and my repl.it account might be taken away from me :( 2)I’m bad at collab. no thank you :)

DynamicSquid (4550)

@StudentFires So sorry I didn't see this post until @Highwayman commented on this (so now). Also I'm really busy writing a 2 page essay for school so I can't now, but I would love to another time

xxpertHacker (627)

Why did you use

``````x = (rand() % 100) / 100.0;
y = (rand() % 100) / 100.0;``````

``x = rand(), y = rand();``

Also,

``4 * (inside / total)``

could be

``4 * inside / total``

It's just left to right, the parenthesis don't matter. You can prove it using functions. I took a few minutes to prove this to myself, as I wasn't 100% sure: Parenthesis Test.

DynamicSquid (4550)

@StudentFires For the first one, I actually don't know. I'm still pretty new to the `rand()` function so I'm still learning. Als for the second one, I know that, but I kind of what it to symbolize a fraction, that's why I have the brackets. It's also looks neater in my opinion.

xxpertHacker (627)

@DynamicSquid Okay, well, C++'s `rand` returns a not random number in between 1 and 0.

DynamicSquid (4550)

@StudentFires Isn't that why I have to use a time seed? `srand(time(0))`

xxpertHacker (627)

@DynamicSquid It's still not random,; like it was mentioned either, try to use standard C++ methods, such as `<random>`, for random numbers, `std::string` for strings, `<array>` for arrays, `<functional>`, for functions, etc.

AmazingMech2418 (997)

@StudentFires C++, like most other languages, reads from left to right and evaluates things in parentheses separately and uses it to substitute. With `a()*(b()/c())`, it does what it does because it first reads `a()` which returns 2, then reads `b` and `c` which are 3 and 4 and then divides `b` and `c` and substitutes this value, let's say as `d` to result in `a*d` which then is evaluated to get your result. Parentheses still matter, but C++ reads the line, evaluating the functions from left to right and then uses the order of operations to return a value. Also, this wouldn't really matter unless you were doing something like `a/(b*c)` since `a*b/c` and `a*(b/c)` are the same. The parentheses in this case are just to make it more readable and to represent a fraction, as @DynamicSquid said.

xxpertHacker (627)

@AmazingMech2418 Just to confirm, will putting redundant parenthesis be ignored by the compiler, as all it needs to know in order to compile to binary is the order?

AmazingMech2418 (997)

@StudentFires Well, it depends what you mean by redundant. If you mean putting two sets of parentheses around an expression, then no. If you mean using parentheses where they are not needed due to the associative property, then no. If you mean parentheses in general, then yes. Parentheses are important for determining the order.

xxpertHacker (627)

@AmazingMech2418 If I use something like this:

``std::cout << ((((((((((2 + 2))))))))));``

Will the compiler just organize this as `2 + 2`? Interpreted languages like Python or JavaScript might have their performance impacted by this, but a compiled language would be fine, right?

AmazingMech2418 (997)

@StudentFires I'm not completely sure. I think it likely depends on the compiler you are using.