Coding Challenge #95: Approximating the Value of Pi

hello happy pi day I have to admit this is take number two I kind of messed up the first time I am going to do a coding challenge where I am going to approximate the value of pi now what's running here right now is the actual number pi I mean someone should fact check that this is correct compare it to pi day org slash million which I think has the first million digits of pi but this is a processing sketch using a particular algorithm to calculate all the digits of pi one at a time it will go on forever it will get very very very slow pretty quickly I will come back to this in a future video but what I'm gonna do in this video is font is look at a way to approximate the value of pi now this came in as a suggestion from originally from a Kraus fifty-three on github for how to look at random particles that end up in a circle or outside of a circle interesting that's something to do with the area of the circle so I'm gonna diagram this out I should also mention thank you to the stem coding YouTube channel and a stem coding project which has a ton of videos in various topics using programming and coding to teach different types of STEM related topics it's wonderful they have a video you can find a link to it in this in this video's description basically doing exactly the same thing that I'm about to try to do probably better but you know I'm gonna do my best would give it my all and I'm gonna do this in processing which is a Java based programming environment if you're not familiar with it I'm sure I'll link to some video where I talk about what processing is okay we're gonna let this run and I'm gonna come over here to talk about a method that I'm going to use to approximate the digits of pi now there is something in our world known as a circle it is a beautiful round shape it is a shape that I'm not going to be able to draw but I'm going to attempt to I'm gonna move over here just give myself more room here is a circle now if you were to look up formula for circumference of a circle or you would find that it's equal to some called two PI R this is the formula for the circumference of a circle now what are these things well two is the number 2 R refers to the radius center to the edge R this is the same length anywhere from the center of circle to any edge point and pi well this is this sort of magic number 3.1415926 that's all I can remember might not even gotten to in the six right good we're gonna approximate it we're gonna see if we can get better than my memory tells me so how can I use this fact to calculate the number pi well one thing I could do is I could get a piece of string and I could wrap it around here in my perfect circle that I could undo the string I could get a tape measure I could measure it and then whatever that is if I knew the value of R I could solve for the value of pi that would work I should mention by the way just because I know someone's gonna say something in the comments and it's not today today is not towel day I'll come back and do this with tau but tau is a number the Greek letter tau or tau PI being spelled with English letters or Roman letters P I is essentially well pi is half our tau is two pi I don't know I don't want to get into which one is which but this is often used because then we could say the circumference is just tau R but there anyway this opens up a big can of worms that I don't want to go down so I'm not gonna do this string method let's look at another two formulas from geometry so so one thing is what's the formula for the area of this circle well hasn't it looks quite similar and there's a special relationship there that's a topic for another time but PI R squared so PI R squared is the area of this circle now let's think of saying what if I put a square as a bounding box of that circle a perfect square and I can draw that over here with this idea of our being here so the sides of this square are twice the length of our the area of the square is the width of a rectangle the width height a square just being the side squared so the area so this is the area of the circle the area of the square is six four four two times two is four R squared so look at that four R squared PI R squared now imagine something there's a relationship here right there's a relationship between the area of a let's say the area of the circle to the area of the square that relationship can be expressed as a ratio I could say the area of the circle PI R squared - the area of the square for R squared the ars cancel out the ratio is pi divided by 4 or I could say that pi equals 4 times that ratio in a way but what do I mean by this exactly what I mean well I play here why are we even here how am I going to use this to approximate so in the in the original github post it said well simulate it with physics so we could imagine one physic scenario is throwing darts what if I were to just throw random darts on the wall at the wall well there would go all over the place some darts would land within the square but not in the circle and some darts would land within the circle but not within the square so in a way I can kind of imagine the ratio of the area of the circle to the area of the square as the number of darts that land within the circle divided by the number of darts that have landed in the square now three have landed in the circle and four have landed in the square so I could say pi in this case pi is approximately four times the circle count divided by the square count which is equal to 3 divided by 4 4 times 3 divided by 4 is what 3 so there is my approximation of pi 3.0 so that's right I mean it's not very good but only through four darts the more darts that I throw if I did this infinitely and fill the entire space I would get closer and closer and closer to a better approximation of the number pi so this is what I'm going to implement in code now I really really want to just use for my dart throwing the numbers from this million random digits book I'm tempted to use the random.org API which gives but I think I'll probably just use the processing random function which is a pseudo-random number generator that's another topic but that I will come back to okay so let's go over the code actually before I go to the code I wrote this in such a weird way what I mean is four times the circle count over the square count this equal sign was sort of a problem there I'm replacing the circle count with three the square count with four so it's four times three over four and that's how I get three apologies for that alright so I'm back in the code look at this we're still getting digits of pi here but slowly over time unfortunate I'm gonna stop this program and I'll be running again later and I'm gonna go to a blank sketch whoops I'm just gonna close this and I'm gonna go to a blank sketch okay so what are the first things that I need to do let's create a window that's 400 by 400 let's give it a background of zero yeah zero that's fine stroke 255 then let's call the ellipse function at and let's I think life our life might be easier if I just do translate to the center to put the zero zero at the center yeah why not and so the ellipse is going to be at 0 0 with a radius a radius of 200 the ellipse function expects a diameter so the radius is 200 the diameter is 400 and then we're gonna do we're gonna say I'm gonna say no fill and I'm going to say rectangle also 0 0 400 400 and let's say stroke weight 4 whoa Oh Rex mode and I wanna say rect mode Center okay and let's make the size actually a little bit bigger so I can sort of see the outline what I want to do now is I want to start throwing the darts so I'm gonna use the Processing's random number function which is random and I'm gonna say right here I'm gonna do this at the end let's do this is the end of draw draw is a loop that happens over and over again if you haven't used processing before and this is the java programming language with a extra set of functionality for drawing x equals random I'm just saying and let's let's actually let's make a variable a global variable called R which is equal to 200 so I'm gonna say R times 2r times 2r times 2r times 2 I'm gonna make a random number between negative R and R and a Y which is a random number between negative R and R then I'm going to draw a point at that X Y so let's do our dart throwing okay look at that so one thing is I'm getting something starry flickering thing so I really want to just draw this in setup as kind of the initial background and then I don't want to redraw the background again but I think I probably will need the translate in both places there we go so now you can see I am filling the space with dots so now what I need to figure out as I need to count the dots that are well I know the total dot and actually all of the dots I don't have to test if dots are within the square because I've set this up in such a way that it basically can only create dots that are within the square so what I need to do is determine how many dots are within the circle so let me do this I'm gonna say if R if so first I need to get the distance what is the distance between 0 0 and X Y so this is how far from the center is that point to be honest i i weirdly in all every case of life I would use the distance function but for some reason right now I feel like it's worth noting that pi is not being used here that the distance function is actually using the Pythagorean theorem because if I know the X offset from the center and the y offset from the center then this hypotenuse of this right triangle x squared plus y squared equals H squared eighth best Pythagorean theorem H is the square root of x squared plus y squared so I I kind of want just for the some weird arbitrary sense of purity to say square root of x times X plus y times y and if that distance is less than less than or equals or just less than let's say less than mm this is just an approximation anyway less than R I'm going to say stroke stroke let's make it a greenish color okay here we go otherwise stroke 255 here we go oops and I need another curly bracket here we go so we can see now and let's let's make it a I don't know I'm gonna pick some arbitrary colors that are gonna not look very nice I'm gonna do my best and here we go so we have two different colors we have this kind of green I pick colors that are quite similar so okay right I could by the way I could do this without randomness I could just check all of the pixels but I like I like the random method and let me let me make these colors quite a bit more different there we go so we can see I've got some blue ones and you can see if they're on the line you know depending on where they are because I have a stroke width of two they're either blue or green so that could use some finesse in the chat the live chat that's going on I see someone's asking what is float float is the datatype so unlike in JavaScript which a lot of my other tutorials in I would just say let X or var X or context depending on how I feel London even getting a float is a floating point decimal number okay hmm now so now we need to do is we need to count so what I'm gonna do is I'm going to say I'm gonna say I'm gonna say int I'm gonna using an integer total equals zero an int circle equals zero so this is going to be total it's going to mean the total number of dots circle is going to be the number of dots that are in the circle and what I'm going to do is I am going to say now I'm going to look back at my formula write pi equals four times the total number of circle divided by the total number of total so pi and I'm going to say P ie just not to be confused with the actual there is a constant called pi that's available in processing I guess I could do lowercase PI processing wouldn't but I'll just say pi because pi is delicious pi equal Minnie that's really like kind of beep upset people float pi equals four times circle divided by total and let's put those in parentheses just for fun now here's the thing there's a couple of problems with this number one total I don't want total to be zero it will never be zero because I'm going to immediately say total plus plus like as soon as I pick a point I'm increasing so at least the first time it runs through this total will be one and then of course if it's within the radius circle is plus plus and so let me say print line pi so let's just look it let's run this and see what we get I keep getting a zero why do I get zero I don't get anything so this has to do with integer arithmetic so integer math these are both integers circle and total so even if I say 10 divided by 20 that's 0 remainder remainder 10 or 20 divided by 19 divided by 20 is 0 remainder 19 so it's always going to give me the 0 so I need to explicitly convert one of these to a float I think I might change this to double to for more precision but this should now give me you can see here I am slowly and slowly getting closer and closer perhaps to the value of pi' let's let this run for a little bit okay I'm back I've let this run for just a couple minutes you can see that I'm not really I had some kind of getting something that looks kind of like PI I'm a little bit higher than PI I start to ask myself the question what's going wrong here well my one guess that I have is that I haven't been so exactly thoughtful about my distance check that maybe that like sort of border of what's on the line versus not on the line is something that I need to think about more deeply the resolution is this kind of an issue there but the other issue might be just the way that floating point math works in the java programming language I might need a different data structure data type that allows me for sort more precision so hold on I'll be right back I'm gonna make some adjustments in the code well one issue is so look at this nice drawing first of all one issue is certainly that I'm spending all this time drawing just to get like one point at a time 30 frames or 60 frames per second so one thing I can absolutely do is there's no reason why I couldn't just put a little for loop in here and say hey let's do a hundred points per frame and what I'm going to do I don't want what I'm gonna do is I'm gonna say let's make a PI a variable outside of that loop just so when the loop finishes I can take a look at what the value of pi is so now I could do a hundred points at a time and you can see how much faster this is sort of filling up the drawing and we can now go look and see what have I got here yeah so I think I think we just have a lot of randomness here and now I'm getting 3.14 when it's you know we're converging it as best we can so I think we've done a pretty good job at approximating pi think maybe I could actually be done a couple things that people noted one is I could actually get rid of the square root from this program and just look at r-squared that could be my comparison that's gonna square root is very slow expensive calculation I could fix some white space here another thing that I could do is let's just try this with like ten thousand and see what we get pretty good per day but a pretty pie all right thank you everybody this is me oh no no no no let's let's go a little step further let's use doubles let's see if using double actually does anything so what is a double so processing natively actually doesn't really support the double data type any number that you have in a variable is stored in memory and so floating-point numbers there's an infinite amount of decimal numbers between any two integers but we don't have an infinite amount of memory on our computer so we allow locate a certain number of bits so floating points allocate a certain number of bits doubles allocate more so if we really need to do precise mathematics and then there's other Java classes and implications for really big numbers but let's at least change this to double let's change this to double and I'm gonna I'm gonna have to use casting because double is not and I'm gonna change this just going to change this to double as well I'm gonna be really I'm gonna overdo it I don't need to I think I need to change all of these but now I should see that this and by the way I don't need to calculate it I don't know why I did that I can just calculate it once there and I wrote float and let's make this double okay so now let's take a look at this and one thing we can see is already there are more digits appearing in the print line statement and maybe maybe I think there's just so much randomness that's part of this that ultimately ultimately I'm not so sure that we're gonna get much anything that's really that accurate out of this method but this is nice to see we've consistently got 1.41 now which is right if only we could get a five here one point four one five let's see we get a five here come on get a five I saw five five consistently so maybe over time as we do this over and over again now one thing might be it maybe we could make who we make this drawing any prettier I mean one thing that I might choose to do is make a stroke wait that's actually more like it's actually at like that's more like 0.1 so a very light stroke maybe you can't see that it also makes a stroke weight of one but maybe give some alpha so some transparency there we go this I don't know that's kind of interesting looks kind of like I'm looking under a microscope I'm gonna let this run for a while and I'll just be back in a couple minutes to check where it got to I actually I'm back because I got a good comment from the chat which is that I could choose to try to make this test a bit more precise so I could make this a double I could cast the X as a double and again I'm gonna just overdo it and cast everything so let let's take a look at let's let's cast all of those as doubles and let's run this one more time we can see it filling up here and it seems to be running at a perfectly reasonable frame rate so I'm actually gonna try to do this ten thousand times per frame well now it's a little bit slow so I cut my animation to be fast oh that was that was a hundred thousand let's just go with ten thousand okay so let's take a look okay I'll be back in a minute let's see how many digits we can kind of get and see how close we're doing and back again so you can see this kind of algorithm it's not gonna converge very quickly there's a lot of noise in it from the randomness but one thing I could do to add to this program is try to keep track of which one is the best so there is in Java natively let's let me take out this print line for a second and what I'm going to do so I'm going to say print line so processing natively has the constant pi but Java also has the constant pi that is in the math package so let me look at both of those and you can see that that one is a double so this is the actus is actually what's stored is type at many digits in math dot Pi in Java so what I'm going to do is I am going to create I'm gonna create a variable called record pi and I am going to set record PI equal to 0 just as its initial value I don't need to set it down there I'm sorry I can just set it up here then what I'm going to do is I'm going to look at double the difference between math dot pi minus record PI and let's take the absolute value of that and I also need to oh can I guess I have to do math dot absolute for because I have doubles so I'm gonna take the difference between matha pi in the record pi then so this is actually really the record difference then I'm going to look at the difference between the PI I just calculated my math dot pi minus the PI I just calculated so if if the difference is less than the record difference if we've gotten one that's closer then the difference is now the record difference is now the difference and the record PI why did I use an underscore did I use an underscore that's sort of unnecessary record pi equals zero and then record PI then record PI is that new PI and what I could do is whenever I have a new record I could print out record pi so let's take a look and see what I get in the console there and in a way I kind of want to do that every time because I feel like I should give it a chance and this is not a big calculation to do I might as well do this every single time even though I'm only drawing every so often so let's put all this inside of this loop and let's run it and we can see the this is now currently the record one point four one five nine two six hey I know I don't know like how many digits have I gotten correct alright so let's go look at the actual digits of pi so I'm gonna go to pi day org slash million and I don't need that many of them this is going to be plenty just the first line here let's open up TextEdit let's put this in here and let's make this a little bit bigger let's go back to the processing sketch oops let's bring this down here how many did you show I have and let's take a look and compare so so far we have gotten one is correct 4 is correct one is correct five is correct nine is correct two is correct six is correct five is correct my font size is not the same ah have I gotten as close as I can get no no this is wrong 6 is correct 5 is correct 3 is correct ah okay so I'm just gonna give myself a couple minutes to take a short break and I'll come back and see if anything got a little closer all right thanks for watching this coding challenge there are so many ways this could be improved you could sort of plot the difference you could visualize these numbers and kind of like highlight which digits are correct which are incorrect there's so many you could think about how you're drawing this you could get your you could make the random numbers double that you're picking I don't know if that would really help you could use my favorite website random or which has an API for random numbers really not gonna make your program run faster but there is so much that you could try to do so if you make something with this coding challenge please share it with me in the comments below you can also go to the coding train com website there's a place where you could link to your shared version I will also release a JavaScript version of this that you can run in the browser and maybe actually that's a might be an easier way to also display the results so thanks for watching I hope you enjoyed this pi day coding challenge [Music]

Channel: The Coding Train

Views: 504,527

Rating: 4.8753686 out of 5

Keywords: live, programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, live stream, itp nyu, class, challenge, codingtrain, code challenge, code, processing, processing java tutorial, monte carlo pi, pi, pi day, approximate pi, estimating pi using monte carlo, estimating pi with darts, estimating pi with monte carlo, estimating pi, pi processing, pi java, processing double

Id: 5cNnf_7e92Q

Length: 27min 32sec (1652 seconds)

Published: Wed Mar 14 2018