Skip to content
← Back to Community
The Monte Carlo method explained
Profile icon
h
has Hacker Plan
DynamicSquid

Thanks to [this] (https://www.youtube.com/watch?v=pvimAM_SLic) 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:

Screenshot (23)

Oh, and the circle:

Screenshot (27)

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).

math

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!

math2

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!

Hopefully that made sense, and is actually readable. Please let me know in the comments if you need me to explain something.

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 */ // but I added comments anyway if you’re curious :) 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:

1000 - 3.148

Screenshot (28)

10’000 - 3.1356

Screenshot (29)

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

Screenshot (30)

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!

Voters
Profile icon
reachtarunhere
Profile icon
mkw
Profile icon
HenryZelonka1
Profile icon
AngeloVarlotta
Profile icon
CodingGoose
Profile icon
LizFoster
Profile icon
SilentShadowBla
Profile icon
JamesHorne1
Profile icon
CodingCactus
Profile icon
jleko75
Comments
hotnewtop
Profile icon
c4syner

This is actually super interesting. Nice project!

Profile icon
DynamicSquid

@c4syner Thanks! Glad you enjoy!

Profile icon
Highwayman

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 though?

Profile icon
DynamicSquid

@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 better?

Profile icon
Highwayman

@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().

Profile icon
xxpertHacker

@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?

Profile icon
Highwayman

@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 :)

Profile icon
DynamicSquid

@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

Profile icon
JaneJLocane

Very cool. Thanks!

Profile icon
DynamicSquid

@JaneJLocane Glad you liked it!

Profile icon
reachtarunhere

Very cool. Thanks for the lucid explanation!

Profile icon
DynamicSquid
Profile icon
FlaminHotValdez

squid handwriting reveal?

Profile icon
DynamicSquid

@FlaminHotValdez 😲 is it neat?

Profile icon
FlaminHotValdez

@DynamicSquid Yeah. DEFINITELY better than mine.

Profile icon
xxpertHacker

Why did you use

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

instead of

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.

Profile icon
DynamicSquid

@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.

Profile icon
xxpertHacker

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

Profile icon
DynamicSquid

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

Profile icon
xxpertHacker

@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.

Profile icon
AmazingMech2418

@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.

Profile icon
xxpertHacker

@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?

Profile icon
AmazingMech2418

@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.

Profile icon
xxpertHacker

@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?

Profile icon
AmazingMech2418

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