If you're only checking the individual pixels, you only need to test 160,000 positions for pi (400x400). So nest a counting loop for X (1 to 400) inside a counting loop for Y (1 to 400) and test each pixel in only 160,000 iterations. No need for random numbers.
Even worse, the whole "recordPI" stuff is some automated cherry-picking. Whenever the approximation goes from "too high" to "too low", we know that 4*circle/total is a low approximation but 4*circle/(total-1) was high. Since the latter is exactly 4*circle/(total-1)(total) more than the former, we know that one of those is at most half that difference, or less than 2/total² (since circle
Of course, you can check in your program how accurate your approximations are -- but the approximation subroutine must work without knowledge of pi. The safest way to do it is to run your subroutine and only introduce the true digits of pi in the function calling the approximation subroutine.
You could have tried to increase number of pixels. I think the randomness actually gave better results. In fact 400x400 = 160000 pixels, if all the pixels are counted (without randomness) the number of pixels inside the circles are 160000 / pi ~= 50.929 so the error of the ratio is 160000/50929 = 3.1416 already at the fourth figure. But I don't know I didn't tried XD
@@OtjPlateo also you don't need to random inside the actual square from (-r , r) you can consider r to Double.MAX_VALUE and and map into the square you want to show if you want, that will lead you to the max precision with double
@ That won't give you any extra precision with a double format, as the calculations would be the same, except with a much higher exponent value. The fraction part of the double would still have the same precision.
The effect of including points on the border or not quickly diminishes as the total number of points increases (from a mathematical standpoint, the surface occupied by the border is exactly zero).
13:12 Float is actually not a floating point decimal number, it is a floating point binary number. Most of the time, the behavior of binary numbers is ok for what we use them for. But sometimes, it is not (banks do not use binary numbers for example, they actually use computed decimal algebraic numbers). In this last case however, computing speed of such numbers is really slower than computing speed of binary numbers.
You can do this but remove the randomness. Compute y for each x on 1/4 of the unit circle. The more values of x you compute for (at regular intervals the more accurate your result. It is not random and always converges. You could perform recursive interlaced sampling to progressively refine your answer without discarding results. Note it is the average ratio of y/1 that you're looking for (equivalent of area on the unit square). I think this a kind of Newton's method, especially if your recursively refine (interlace over x). 1/4 circle will speed convergence unlike the Monte Carlo sampling.
Exactly. If the radius of the circle is r, the # of points with x-coordinate x0 equals 1 + 2 [ sqrt(r² - x²) ], where [n] equals the number n rounded down to an integer. You don't even have to compute sqrt, you can start with q = [r] as an initial guess for sqrt(r² - 0²) (which will be exact). Then, you can check if q² > r² - x², and as long as it is, subtract 1 from q. That'll finally generate a q satisfying q²
This was the method I used as well. The primary limitation you run into is the expensive squaring used with the distance formula. You could opt to only try to use it every few x values and simply estimate the rise over run for the x's in-between. Beyond that, I haven't figured out a way to optimize it.
@@Rexvideowow There's more gas in the tank, rise over run is valid and trivial (half the area of the differential rectangle). The other trick is to realize that as the derivative increases the bisected gap affects the area the most, so weighting the divisions towards the tangential edge of the quarter circle will produce an inherently improved result for a fixed number of samples, if you can weight efficiently and appropriately. The sample splitting the greatest rise over run differential area is always the biggest convergence. It is unlikely to be memory efficient though when contemplating the data and heuristics needed to support this type of algorithm.
@@achtsekundenfurz7876 As I said elsewhere r is best assumed to be 1.0 and elided for peak efficiency and clarity, you can always multiply by r² or 2r etc. later if needed.
@@Rexvideowow New method that scales accuracy with O(log(n_effective_samples)) performance provided you have precision. Bisect the 0-90 degree cord and normalize, repeat with the 0-45 degree cord, etc effectively doubling sample equivalence for each bisect. Normalization needs a square root, but it's worth it eventually. Compute area of the thinnest triangle at some arbitrary precision (or as you go to watch convergence). Scale up area by 4*(2^(bisections-1)) to estimate area of circle which is also pi on the unit circle. It needs a load of square roots but converges faster due to sample equivalent convergence doubling with each bisection. Its Achilles' heel is precision loss in the arithmetic but I reckon it can deliver a lot of decimal places fast before that's a problem.
The pocket calculators used in schools nowadays are more powerful than the computers nasa had in the 60's, so I find it highly likely that this approximation of pi would work for sending astronauts to the moon.
Draw a square around the moon, send some astronauts, count how many rockets hit the moon, divide that number by the total and multiply by 4... You get Pi !! What a good way to calculate pi !!
@@autumnhd even the computers back then however, could use a much more accurate and precise value of pi, as they would only need to use said value in one multiplication expression. Here, he's trying to go through hundreds of thousands of iterations of something to find a value. The NASA computers didn't need to recalculate a value for pi every time they wanted to use it.
@@figfox2425 and for an extra challenge: have fun trying to take gravity into account (as a higher than otherwise expected proportion of rockets will hit the moon due to its attraction)
alan smithee While yes, Nasa didn't have to recalculate pi everytime they wanted to use it, and that they likely had a more precise version of pi, they would still be able to land someome on the moon using the approximate produced in this video. You only need a few digits to be accurate.
I personally prefer not to use the sqrt function because it is a lot slower. I would instead leave distance squared and compare it to the squared radius. EDIT: Oh, you changed it yourself
He is using doubles, so the precision is much larger than is displayed anyway. He could have turned off displaying points for an even greater performance boost, and used xorshift random number generators to be faster as well.
Math: 6:39 PI = 4 * A/B = [4 now missing] valueForA/valueForB = valueForA 5:57 canceling out the r -> only one removed from the solution Code: Is it not possible to get x and y to be doubles (and have random values) too? Instead (double) x * (double) x + (double) y * (double) y... just to improve the calculations for the distance without improving the position of each dart? o.O Updating recordDiff and then throwing it away? (Small optimisation possible)
We practise this in my university, it's a Monte Carlo simulation about this same problem, we have to program it in C and make it multithreading using OpenMP.
This actually sounds like a problem that would be really easy to simulate with a GPU, as each GPU core can have it's own total and circle counter, and you just add em up to get a more accurate value.
lol seriously? Sorry if am wrong but I know java a bit and methods are declared like "method name" (arguments) and not like just "method name" etc. How can it be Java man?
He didn't use it to calculate it faster, the calculation wasn't improved by that. He used it to make it not print out every estimate but rather make it just print out the best ones.
Another approach that just came in to my mind would be to "draw" a triangle where sides A and B are equal to R, and gamma (the angle between A and B) would be 360/X where X equals any multiple of 360 (x1, x2,.. x5,.. x100,... depending on how you would like your accuracy/resolution). After that you find the length of missing side C and multiply it by X getting an estimated circumference of your circle (think of drawing an octagon but with way more sides). From there you can calculate estimated PI.
Oh boy, I was just working on a monte carlo approximation (for a hard double integral) and I just knew by looking at the thumbnail that you were using it !!! Monte carlo is a cool method, plus I always feel like I'm some sort of rich gambler at a casino roulette while working on it :p
I did this challange before, with Scratch and C++, I used the method that we have a square side x and a quarter circle radius 2x, then using Pythagorean theorem to calculate the area of the circle. I tried that method with Scratch and had a result of 3.14159265, But I found that to find the next digit, you'll need about 10 times more than the last digit, so I used the slightly better method, is using the Bayer problem (1/1 + 1/4 + 1/9 + ...) with C++ and I have the result of 3.14159265, so I think we will have some better method to do that instead of count the dots :)
The problem is that the random() function is not truly random Generate each and every pixel and see if it falls in the circle is more accurate. Also use a bigger square.
17:00 I see another slowdown in the code, and that's you're declaring float every frame. Declare it in global scope once and it'll be much faster. Declaration of variables is expensive
Dont think that matters at all w modern compilers (optimization, also its really hard to know if a global var would be faster, it might actually be slower). You shouldnt try to micro optimize like that
Quantum Cuber yeah it is surprisingly hard to get truely random numbers. You are paying for the effort required to make sure those numbers are as random as possible
For circular area, pi is okay. But for circumference the constant is more than pi, because in tiny angles the length of tan base line and sin base line are practically identical, WHILE there is still space between both tan and sin base lines. So the arc becomes longer even than tan base line. Pi = 3.17157
I know it's a bit late to answer but i want to point out what hindered you to calculate pi more accurately. Think about it this way: If you have a grid of points and you draw a circle inside the grid. The ratio of Points inside the Circle over the ratio of Points in outside the circle will get more accurate when you have either more points on the grid = a denser grid, or simply a larger grid and a larger circle. And then if that ratio is more accurate your calculation of Pi will be more accurate. (basicly what you explained in the video) But you didnt realize that that was exactly what got in your way: if you do the Random function millions of times times after a few seconds it wont become random anymore... Based on your precision of the randomness, the points on your drawing will create a tiny grid. So what you could have done to calculate Pi more accurate is either get random double s or draw on a bigger canvas (not sure on that one tho ^^) But nice Video, keep it up :)
> if you do the Random function millions of times times after a few seconds it wont become random anymore... not true. although the random function generating a random float rather than a double would decrease the precision of the estimate, that is correct.
Zac K so if I tell you to pick a whole number from 0 to 9 over and over again and mark that point on a number line. After some time you will get a line with 10 dots. Now do the same but this time you that you can use tenths and not just whole numbers. The result will be a line with 100 points on it.
no i agree with that perfectly well. i interpreted what i quoted as you saying the random function loses entropy if its called too many times regardless of the domain of values which would be completely false, but im now assuming you just worded that specific part a bit weirdly.
>> if you do the Random function millions of times times after a few seconds it wont become random anymore... >not true. Actually, half-true, because there's not such thing as a "random function" (by definition) but Random is actually a pseudo-random function. Therefore, the values returned do have a pattern, but it will only show after *gazillions* of calls to the function (millions is not enough).
I think you can simplify the math even more by not taking a square of 2R but by taking only a square of side R. The formula then becomes ratio = pi * R² / R² = pi which avoid multiplying by 4 at the end. Anyway, it's an interesting way of approaching the problem using statistics!
What you have done here is normally called "monte carlo" method and came from the mind of Enrico Fermi. The great problem with this method, implemented in this way, is that you have to DEFINE a circle and inside the function that you use to define the circle you have to use PI. So basically your approximation will be limited by the approximation of PI stored in the library used to define the circle (that could be to the 10000 decimal or more, id depends, i think is pushed to the limit of double)
Great point! But in this case I am using a formula for euclidean distance to check if the point is within the circle. So while Pi is needed to draw the circle, for the actual math here no Pi is needed!
Sin square plus cos square equal one means derived surface waves is a number. So most numbers are orthogonal wave surfaces added. Division of wave surfaces gives i. Surface is a number ratios of integral. So pi is a integral ratios of 90. Which means the sun stars galaxies exist because of resonance and the universe expand because of resonance.
I'm only at 6:53, so I apologise if you cover this further through the video, but the example you just gave was that if you randomly placed pixels upon the canvas, where the circle and square were drawn, then did the Maths, you could approximate PI. Could you not just count the number of pixels of the area of the square (pixSq), then the number inside the circle only (pixCi), and then use those figures to do the calculations? You'd just have to do pixSq-pixCi to get how many were in the square's corners
Including the points on the circle will definitely improve this number. Now you have considered only the points with distances which are less than sqft( x*x + y*y ) .. But when we consider the points with distances which are less than or EQUAL TO sqft(x*x +y*y) Then the number should have substantially improved.
Here's a short script i wrote in Python without using random. r = 10000 # increase radius for more accuracy r2 = r*r d = r+1+r # radius on both sides of 0 column/row total = d*d inside = 0 # only need to calculate one corner for y in range(-r,0): for x in range(-r,0): if x*x+y*y
Wait, I'm pretty sure whatever was running in the beginning isn't an algo calculating Pi. It's just storing it in a string, then pausing the screen for some (micro)seconds after printing the next digit, and the amount of seconds it sleeps is based somewhat on the iterator 'i'. That's what I can gather from the text editor shown in the background at the beginning and the fact that the end program wasn't anywhere close to doing what was shown initially. IT'S CRAZY NO ONE IS MENTIONING IT!!
Here is the code for what I was running the beginning! github.com/CodingTrain/Pi-Day-2018/blob/master/PiCalc/PiCalc.pde (The text file is what this sketch writes out!)
At the following link you can find a high-level algorithm implementation in the Sidef programming language: github.com/trizen/sidef/blob/master/scripts/Interactive/pi.sf Feel free to adapt and translate the code to any other language of choice.
Why not use 22 divided by 7 to calculate PI. Ive probably missed the point here so consider this a curious question. Maybe my memory from school is not serving me well but I remember being taught that 22 over 7 is another representation of PI. By the way, I like your channel. You have a good style. Thanks
22/7 is greater than π by about 1 part in 2500 (22/7 - π = 0.001264489...) 355/113 is greater than π by about 1 part in 12,000,000 (355/113 - π = 0.000000266764...) Fred
I was playing around with this algorithm, picking random dots in a processing window and seeing which of the total was within a circle in the center of the window. It was always 78.53% of them, give or take. I was wondering why that exact number. Turns out 0.7853... is one quarter of PI.
Interestingly enough this formula also works def print_pi(x, z=0): for i in range (1, x, 4): z += 1/i for i in range (3, x, 4): z -= 1/i print(z * 4) print_pi(#as high as your pc can handle XDD)
A point on the perimeter should be considered inside the circle, no ? If no, a point on the perimeter of the square should'nt be considered inside the square either. Or maybe you need to exclude all points on the permiter of both the circle and the square ?
Apofoo That’s a good point, i think points on a certain geometrical figure should be considered as inside but the problem is you could have two points on same line with the center (0,0) both on the limit of the circle but not at same distance from the center (due to precision...) so what is the limit of the circle then? I’ve been thinking about that for a while yet no solution for my code...
Including or excluding the border shouldn't matter for somewhat complicated math reasons having to deal with infinite sets of points and measuring areas of those sets.
There is actually as many points as his program can handle and this number is well defined (due to the limitaion of double) A perimeter is composed by an infinite number of point but (in computer science) we have to define a precision and work with it. Including or excluding it, will change the result.
Let me demonstrate that: if you have two numbers with some number of digits precision. We'll say that means there's N possible values of your float. So take one as your radius. Take the other as the angle. So for every value of your radius from 0 to 1 you have N angles around the circle. So you have something order of N^2 possible points. Taking away the perimeter is taking away N points from N^2s which introduces an "error" of 1/N. Ie there is an error on order on precision of your float. This doesn't actually say anything new, and does not,therefore, introduce any new problems. All this really says is eventually your ability to write down PI is limited by the precision of your floats. This isn't a new statement. Eventually all representations of irrational numbers run into this problem.
If you brute force went through every pixel in the window, with two for loops, how much closer would you get to the value of pi than throwing random dots?
To make it a monte-carlo simulation you would have to take the average value of multiple runs of the simulation. Of course that just one run is not going to converge to an accurate answer. But the average does a much better job.
Stop using (slow) random. Count all the pixels in a gigantic imaginary square. Use Bresenham's Circle Drawing Algorithm to calculate the changing radius of the circle as y increases, and count the number of pixels falling inside it. You only need to do it for a quarter square. Use a number-as-string library to do the division, once, or periodically. Maybe once a second using multi tasking with a sleep.
i made my own method to approximate the value of pi without using random numbers first using a computer draw a circle-- its circumference is how many steps it took to draw the circlr then draw a semicircle and record the distance between the end point and the start poinf then divide the circle circumference between the semicircle diameter
Nice job Dan, happy belated Pi Day! Maybe you could look more into casting because you totally overused it. Also, I think using double instead of float for the x,y-coordinates would help improve the estimation.
I learn from p5js are from function setup() {...} and function draw() {...} in windows OS but why professor used (void set) and (void draw) here? Thank you for your kindly help!
Ah! This is because I'm using Processing (java) which has a similar API to p5.js, but the syntax is Java! See: processing.org/. You can find the p5 code on my website: thecodingtrain.com/challenges/95-approximating-the-value-of-pi
Wouldn't it be more intuitive to draw green circle inside of blue square and then counting the pixels green in comparison to the blue? Instead of build your guess on statistics "experiment"
i programmed this exact thing a couple of years ago after watching physicsgirl's video about physically throwing darts to approximate pi. just for fun i shortened it down to a handful of lines and left it running for days on end, in that time it got fairly stable around the correct value plus/minus 0.0001. my code: www.openprocessing.org/sketch/407317
i don't know how long he let it go at the end, but isn't it problematic to use int for the count of the dots? if your programm is fast enough you could run out of space in the (2^31)-1 number (~2 billion). and in his last version of the program he doesn't see if he goes out of bounds of the int.
I double dog dare you to write this in eight bit assembler to 32 bits of precision. You can only use integer arithmetic with only add, subtract, and bit shifting.
Don't really understand coding but... Isn't it cheating to have a function that has the real value of Pi inside of your coding to compare to what you're getting? Kinda defeats the purpose and reasonings as to why one would need to create a programme to make Pi in the first place if this function exists
24:50
Ah yes.
Pi.
1.415926.
That's the one.
yeah, that bugged me too
10pi-30
He said it so many times x.x
@@DerToasti or (pi-3)*10
@@MinePlayersPE no, learn order of operations.
TCT at 01:50: "I can't draw circles"
TCT at 02:00: * _draws a surprisingly good circle_ *
Nice, you reverse-jinxed it!
It is actually called "Monte Carlo method"
Works great with Doom Fang Pauldron
I got a house in Monte Carlo swag swag Moneyboy
@@SumriseHD ich bin connected in chicago
@@lattenkack3592 Ich hab Juice so wie Pago
If you're only checking the individual pixels, you only need to test 160,000 positions for pi (400x400). So nest a counting loop for X (1 to 400) inside a counting loop for Y (1 to 400) and test each pixel in only 160,000 iterations.
No need for random numbers.
Even worse, the whole "recordPI" stuff is some automated cherry-picking.
Whenever the approximation goes from "too high" to "too low", we know that 4*circle/total is a low approximation but 4*circle/(total-1) was high. Since the latter is exactly 4*circle/(total-1)(total) more than the former, we know that one of those is at most half that difference, or less than 2/total² (since circle
Of course, you can check in your program how accurate your approximations are -- but the approximation subroutine must work without knowledge of pi. The safest way to do it is to run your subroutine and only introduce the true digits of pi in the function calling the approximation subroutine.
You could have tried to increase number of pixels. I think the randomness actually gave better results. In fact 400x400 = 160000 pixels, if all the pixels are counted (without randomness) the number of pixels inside the circles are 160000 / pi ~= 50.929 so the error of the ratio is 160000/50929 = 3.1416 already at the fourth figure. But I don't know I didn't tried XD
Go up!
Nice catch, but there is no need to try more pixels, just get random doubles for both x and y. (instead of random ints).
~= you mean ≅
@@OtjPlateo also you don't need to random inside the actual square from (-r , r) you can consider r to Double.MAX_VALUE and and map into the square you want to show if you want, that will lead you to the max precision with double
@ That won't give you any extra precision with a double format, as the calculations would be the same, except with a much higher exponent value. The fraction part of the double would still have the same precision.
The fact that he has to get this deep into pi just for a video is phenomenal. Keep it up dude.
I wonder if your estimations would have been marginally closer if you had used "if (d
i didnt watch the video yet but if hes using floating point variables than the equal case is very very rare
The effect of including points on the border or not quickly diminishes as the total number of points increases (from a mathematical standpoint, the surface occupied by the border is exactly zero).
13:12 Float is actually not a floating point decimal number, it is a floating point binary number. Most of the time, the behavior of binary numbers is ok for what we use them for. But sometimes, it is not (banks do not use binary numbers for example, they actually use computed decimal algebraic numbers). In this last case however, computing speed of such numbers is really slower than computing speed of binary numbers.
You are my favorite guy on the internet. I wish I knew you personally. I’d suspect you’d make any of my days brighter. You = 👍
You can do this but remove the randomness. Compute y for each x on 1/4 of the unit circle. The more values of x you compute for (at regular intervals the more accurate your result. It is not random and always converges. You could perform recursive interlaced sampling to progressively refine your answer without discarding results. Note it is the average ratio of y/1 that you're looking for (equivalent of area on the unit square). I think this a kind of Newton's method, especially if your recursively refine (interlace over x). 1/4 circle will speed convergence unlike the Monte Carlo sampling.
Exactly. If the radius of the circle is r, the # of points with x-coordinate x0 equals 1 + 2 [ sqrt(r² - x²) ], where [n] equals the number n rounded down to an integer. You don't even have to compute sqrt, you can start with q = [r] as an initial guess for sqrt(r² - 0²) (which will be exact). Then, you can check if
q² > r² - x², and as long as it is, subtract 1 from q. That'll finally generate a q satisfying q²
This was the method I used as well. The primary limitation you run into is the expensive squaring used with the distance formula. You could opt to only try to use it every few x values and simply estimate the rise over run for the x's in-between. Beyond that, I haven't figured out a way to optimize it.
@@Rexvideowow There's more gas in the tank, rise over run is valid and trivial (half the area of the differential rectangle). The other trick is to realize that as the derivative increases the bisected gap affects the area the most, so weighting the divisions towards the tangential edge of the quarter circle will produce an inherently improved result for a fixed number of samples, if you can weight efficiently and appropriately. The sample splitting the greatest rise over run differential area is always the biggest convergence. It is unlikely to be memory efficient though when contemplating the data and heuristics needed to support this type of algorithm.
@@achtsekundenfurz7876 As I said elsewhere r is best assumed to be 1.0 and elided for peak efficiency and clarity, you can always multiply by r² or 2r etc. later if needed.
@@Rexvideowow New method that scales accuracy with O(log(n_effective_samples)) performance provided you have precision. Bisect the 0-90 degree cord and normalize, repeat with the 0-45 degree cord, etc effectively doubling sample equivalence for each bisect. Normalization needs a square root, but it's worth it eventually. Compute area of the thinnest triangle at some arbitrary precision (or as you go to watch convergence). Scale up area by 4*(2^(bisections-1)) to estimate area of circle which is also pi on the unit circle. It needs a load of square roots but converges faster due to sample equivalent convergence doubling with each bisection. Its Achilles' heel is precision loss in the arithmetic but I reckon it can deliver a lot of decimal places fast before that's a problem.
Send astronauts to the moon using the results of this estimation. If they live, you win!
The pocket calculators used in schools nowadays are more powerful than the computers nasa had in the 60's, so I find it highly likely that this approximation of pi would work for sending astronauts to the moon.
Draw a square around the moon, send some astronauts, count how many rockets hit the moon, divide that number by the total and multiply by 4... You get Pi !!
What a good way to calculate pi !!
@@autumnhd even the computers back then however, could use a much more accurate and precise value of pi, as they would only need to use said value in one multiplication expression. Here, he's trying to go through hundreds of thousands of iterations of something to find a value.
The NASA computers didn't need to recalculate a value for pi every time they wanted to use it.
@@figfox2425 and for an extra challenge: have fun trying to take gravity into account (as a higher than otherwise expected proportion of rockets will hit the moon due to its attraction)
alan smithee
While yes, Nasa didn't have to recalculate pi everytime they wanted to use it, and that they likely had a more precise version of pi, they would still be able to land someome on the moon using the approximate produced in this video. You only need a few digits to be accurate.
I personally prefer not to use the sqrt function because it is a lot slower. I would instead leave distance squared and compare it to the squared radius.
EDIT: Oh, you changed it yourself
"If you were to look up"
*looks up*
"circumference of a circle"
We've been tricked, we've been backstabbed and we've quite possibly been bamboozled
Making the radius larger would have helped aswell, lets say 10 times larger, calculations are 10 times more accurate
i think accuracy increases by
1/✓n
Not making it stupid random would have helped!
He is using doubles, so the precision is much larger than is displayed anyway. He could have turned off displaying points for an even greater performance boost, and used xorshift random number generators to be faster as well.
Man, this channel is incredible. Thanks! Watching all your videos! You're so fun.
You could also use area of a polygon to approximate the area of a circle and increase the number of sides.
THIS IS EXACTLY WHAT I WANTED!!! Thank you so much
Math:
6:39 PI = 4 * A/B = [4 now missing] valueForA/valueForB = valueForA
5:57 canceling out the r -> only one removed from the solution
Code:
Is it not possible to get x and y to be doubles (and have random values) too?
Instead (double) x * (double) x + (double) y * (double) y... just to improve the calculations for the distance without improving the position of each dart? o.O
Updating recordDiff and then throwing it away? (Small optimisation possible)
We practise this in my university, it's a Monte Carlo simulation about this same problem, we have to program it in C and make it multithreading using OpenMP.
sound painful
sounds reallllyyy tedious, but I'm curious. Do you have the code lying around by any chance?
This actually sounds like a problem that would be really easy to simulate with a GPU, as each GPU core can have it's own total and circle counter, and you just add em up to get a more accurate value.
Not quite. A monte carlo simulation method works by taking the average of multiple runs, not just seeing if one run converges
I love this guy's channel he is so creative with javascript
ntt This is Java
no, it's javascript, not java. There's a big difference between those two.
Pump Reactivation Project Dude, you have to be trolling. He's using Processing with Java, not p5.js, in this video. It's very obvious.
lol seriously? Sorry if am wrong but I know java a bit and methods are declared like "method name" (arguments) and not like just "method name" etc. How can it be Java man?
Pump Reactivation Project Nah, you are trolling. If not, this is clearly Java especially considering Processing is made for Java.
I did this in python with turtle, it works really well, thanks!
O my gosh, the concept by which you teach is absolutely amaaazing
The fact that he explain me this in a unicorn shirt makes me even more comfortable
Soo you used pi to calculate pi accurately ... Nice.
sujaan kumar *used the estimate of pi to calculate the estimate of that value...
This method does not use pi, that is the whole point of it.
Ninjaznexx he used it in the end to calculate pi faster
He didn't use it to calculate it faster, the calculation wasn't improved by that. He used it to make it not print out every estimate but rather make it just print out the best ones.
Yes he did the circle drawing algorithm uses pi to draw a circle. Yes it is not necessary to make the approximation but it's still there
Another approach that just came in to my mind would be to "draw" a triangle where sides A and B are equal to R, and gamma (the angle between A and B) would be 360/X where X equals any multiple of 360 (x1, x2,.. x5,.. x100,... depending on how you would like your accuracy/resolution). After that you find the length of missing side C and multiply it by X getting an estimated circumference of your circle (think of drawing an octagon but with way more sides). From there you can calculate estimated PI.
Just found out that archimedes did came up with that idea more than 2000 years ago
Oh boy, I was just working on a monte carlo approximation (for a hard double integral) and I just knew by looking at the thumbnail that you were using it !!!
Monte carlo is a cool method, plus I always feel like I'm some sort of rich gambler at a casino roulette while working on it :p
3:53 Holy smokes I just realised that d(area)/dr = circonference and it makes perfect sense !
I did this challange before, with Scratch and C++, I used the method that we have a square side x and a quarter circle radius 2x, then using Pythagorean theorem to calculate the area of the circle. I tried that method with Scratch and had a result of 3.14159265, But I found that to find the next digit, you'll need about 10 times more than the last digit, so I used the slightly better method, is using the Bayer problem (1/1 + 1/4 + 1/9 + ...) with C++ and I have the result of 3.14159265, so I think we will have some better method to do that instead of count the dots :)
The problem is that the random() function is not truly random
Generate each and every pixel and see if it falls in the circle is more accurate.
Also use a bigger square.
Actually we can speed things up a lot, because we can use the Pythagorean theorem to count the number of dots in each row
17:00 I see another slowdown in the code, and that's you're declaring float every frame. Declare it in global scope once and it'll be much faster. Declaration of variables is expensive
Dont think that matters at all w modern compilers (optimization, also its really hard to know if a global var would be faster, it might actually be slower). You shouldnt try to micro optimize like that
@@Nilrem8 optimization gives me orgasm
Are we just gonna overlook that someone is getting rich off of a random numbers book?
He shows a book filled with random numbers in the start
Generating random numbers takes a lot of effort and they are very useful. So I mean I don't mind someone getting paid for their services
Quantum Cuber yeah it is surprisingly hard to get truely random numbers. You are paying for the effort required to make sure those numbers are as random as possible
That’s just capitalism
He's not getting rich, he IS Rich. Michael D. Rich, CEO of the RAND corporation who edited the book: en.wikipedia.org/wiki/Michael_D._Rich
For circular area, pi is okay. But for circumference the constant is more than pi, because in tiny angles the length of tan base line and sin base line are practically identical, WHILE there is still space between both tan and sin base lines. So the arc becomes longer even than tan base line. Pi = 3.17157
Tell me, where can i get this hoodie? Its awesome ;p
It’s from Target. 😂
I know it's a bit late to answer but i want to point out what hindered you to calculate pi more accurately.
Think about it this way:
If you have a grid of points and you draw a circle inside the grid.
The ratio of Points inside the Circle over the ratio of Points in outside the circle will get more accurate when you have
either more points on the grid = a denser grid, or simply a larger grid and a larger circle.
And then if that ratio is more accurate your calculation of Pi will be more accurate. (basicly what you explained in the video)
But you didnt realize that that was exactly what got in your way:
if you do the Random function millions of times times after a few seconds it wont become random anymore...
Based on your precision of the randomness, the points on your drawing will create a tiny grid.
So what you could have done to calculate Pi more accurate is either get random double s or draw on a bigger canvas (not sure on that one tho ^^)
But nice Video, keep it up :)
> if you do the Random function millions of times times after a few seconds it wont become random anymore...
not true.
although the random function generating a random float rather than a double would decrease the precision of the estimate, that is correct.
Zac K so if I tell you to pick a whole number from 0 to 9 over and over again and mark that point on a number line. After some time you will get a line with 10 dots.
Now do the same but this time you that you can use tenths and not just whole numbers. The result will be a line with 100 points on it.
no i agree with that perfectly well.
i interpreted what i quoted as you saying the random function loses entropy if its called too many times regardless of the domain of values which would be completely false, but im now assuming you just worded that specific part a bit weirdly.
Zac K yea sorry, I'm not a native English speaker
>> if you do the Random function millions of times times after a few seconds it wont become random anymore...
>not true.
Actually, half-true, because there's not such thing as a "random function" (by definition) but Random is actually a pseudo-random function. Therefore, the values returned do have a pattern, but it will only show after *gazillions* of calls to the function (millions is not enough).
I think you can simplify the math even more by not taking a square of 2R but by taking only a square of side R.
The formula then becomes ratio = pi * R² / R² = pi which avoid multiplying by 4 at the end.
Anyway, it's an interesting way of approaching the problem using statistics!
then the area of circle becomes pi * (r/2)^2 which is (pi/4) * r^2 and then you still have to multiply by 4 in the end
I am so glad you didn't use the ellipse function in any way other than for visuals.
Omg I'm in love with his hoodie
3:28
(2/√2) * pi = (√2/2) * tau
Yea now *sqrt(2) on both sides and you get 2pi=tau
We did this in a lab for our Concurrent and Parallel Programming class using multiple threads as it is easily parallelizable. Was fun.
R.I.P
Stephen Hawking
3/14/18
Pi Day
Einsteins birthday.
You mean 3/14...it's called Pi Day for a reason lol
It all comes full circle
Kyle Amoroso it depends on where u Live man.
+Kyle Amoroso some people use D/M/Y instead of M/D/Y
Its 1 month since Stephen Hawkings death
What you have done here is normally called "monte carlo" method and came from the mind of Enrico Fermi. The great problem with this method, implemented in this way, is that you have to DEFINE a circle and inside the function that you use to define the circle you have to use PI. So basically your approximation will be limited by the approximation of PI stored in the library used to define the circle (that could be to the 10000 decimal or more, id depends, i think is pushed to the limit of double)
Great point! But in this case I am using a formula for euclidean distance to check if the point is within the circle. So while Pi is needed to draw the circle, for the actual math here no Pi is needed!
I see your point, pretty good ! Thank you for the explanation
Sin square plus cos square equal one means derived surface waves is a number. So most numbers are orthogonal wave surfaces added. Division of wave surfaces gives i. Surface is a number ratios of integral. So pi is a integral ratios of 90. Which means the sun stars galaxies exist because of resonance and the universe expand because of resonance.
I'm only at 6:53, so I apologise if you cover this further through the video, but the example you just gave was that if you randomly placed pixels upon the canvas, where the circle and square were drawn, then did the Maths, you could approximate PI. Could you not just count the number of pixels of the area of the square (pixSq), then the number inside the circle only (pixCi), and then use those figures to do the calculations? You'd just have to do pixSq-pixCi to get how many were in the square's corners
Since there's four-fold symmetry in this simulation, could you get the same results using only one quarter of the circle? Just don't multiply by 4?
You'd still need to multiply by 4, you don't change the ratio of the points at all when you cut it into fourths.
Including the points on the circle will definitely improve this number.
Now you have considered only the points with distances which are less than sqft( x*x + y*y ) ..
But when we consider the points with distances which are less than or EQUAL TO sqft(x*x +y*y)
Then the number should have substantially improved.
wow unicorn hoodie. game over
Here's a short script i wrote in Python without using random.
r = 10000
# increase radius for more accuracy
r2 = r*r
d = r+1+r
# radius on both sides of 0 column/row
total = d*d
inside = 0
# only need to calculate one corner
for y in range(-r,0):
for x in range(-r,0):
if x*x+y*y
Wait, I'm pretty sure whatever was running in the beginning isn't an algo calculating Pi. It's just storing it in a string, then pausing the screen for some (micro)seconds after printing the next digit, and the amount of seconds it sleeps is based somewhat on the iterator 'i'. That's what I can gather from the text editor shown in the background at the beginning and the fact that the end program wasn't anywhere close to doing what was shown initially. IT'S CRAZY NO ONE IS MENTIONING IT!!
Here is the code for what I was running the beginning! github.com/CodingTrain/Pi-Day-2018/blob/master/PiCalc/PiCalc.pde (The text file is what this sketch writes out!)
The condition should have been
d*d < x*x + y*y for Circle count increment.
Just one little question.
Where did you get that unicorn sweater, it looks so neat.
Where can I get the version you showed first? The version that prints digit one by one?
At the following link you can find a high-level algorithm implementation in the Sidef programming language: github.com/trizen/sidef/blob/master/scripts/Interactive/pi.sf
Feel free to adapt and translate the code to any other language of choice.
I am curious for that one too, but i am unable to find it anywhere :(
https:/github.com/CodingTrain/PiDaygithub.com/CodingTrain/PiDay/github.com/CodingTrain/PiDay
Thank you!
The Coding Train but I can't seem to find the version that calculates number by number as you showed... There are other kinds.. :(
i tried your method but instead of a random x , y position i calculated line by line ( works pretty nicely)
where is the program like you've shown in the beginning?
hahaha that rainbow unicorn hoodie :p
Why not use 22 divided by 7 to calculate PI. Ive probably missed the point here so consider this a curious question. Maybe my memory from school is not serving me well but I remember being taught that 22 over 7 is another representation of PI.
By the way, I like your channel. You have a good style. Thanks
@@RampagingCoder When you say a few digits in, you mean before it starts repeating ?
22/7 is greater than π by about 1 part in 2500 (22/7 - π = 0.001264489...)
355/113 is greater than π by about 1 part in 12,000,000 (355/113 - π = 0.000000266764...)
Fred
plot the trajectory of the error and see if appears to be converging
I was playing around with this algorithm, picking random dots in a processing window and seeing which of the total was within a circle in the center of the window. It was always 78.53% of them, give or take. I was wondering why that exact number. Turns out 0.7853... is one quarter of PI.
What about the first program in the video wich computes one digit a time? How does it works?
Yay, its half TAU day!
Jacob Haig no
Haha Tau day is a day after my birthday. That's a good approximation I think haha
tau day. if the digits 6 and 8 swapped, it would be my nameday lol
Don't say that. Never say that. Don't even read it again. Pls No
I love your teaching sir
Can i use threading to speed it up?
Ohhhh it works on the Pythagoras theorem for it! Thats smart
It should be d
It should be if (d
Interestingly enough this formula also works
def print_pi(x, z=0):
for i in range (1, x, 4):
z += 1/i
for i in range (3, x, 4):
z -= 1/i
print(z * 4)
print_pi(#as high as your pc can handle XDD)
A point on the perimeter should be considered inside the circle, no ?
If no, a point on the perimeter of the square should'nt be considered inside the square either.
Or maybe you need to exclude all points on the permiter of both the circle and the square ?
Apofoo That’s a good point, i think points on a certain geometrical figure should be considered as inside but the problem is you could have two points on same line with the center (0,0) both on the limit of the circle but not at same distance from the center (due to precision...) so what is the limit of the circle then? I’ve been thinking about that for a while yet no solution for my code...
Including or excluding the border shouldn't matter for somewhat complicated math reasons having to deal with infinite sets of points and measuring areas of those sets.
There is actually as many points as his program can handle and this number is well defined (due to the limitaion of double)
A perimeter is composed by an infinite number of point but (in computer science) we have to define a precision and work with it.
Including or excluding it, will change the result.
Yes and that error is gong to be on the same order as the precision of your float or your double. It's negligible.
Let me demonstrate that:
if you have two numbers with some number of digits precision. We'll say that means there's N possible values of your float.
So take one as your radius. Take the other as the angle.
So for every value of your radius from 0 to 1 you have N angles around the circle.
So you have something order of N^2 possible points.
Taking away the perimeter is taking away N points from N^2s which introduces an "error" of 1/N. Ie there is an error on order on precision of your float.
This doesn't actually say anything new, and does not,therefore, introduce any new problems.
All this really says is eventually your ability to write down PI is limited by the precision of your floats. This isn't a new statement. Eventually all representations of irrational numbers run into this problem.
iwould you tell me if you already upload the code you were running ? at the beginning of the video?
Thank you, this was very helpful . I have a question though, can you limit the points used ? For example make an aproximation for just 10000 points.
rectMode(center);
Something about this is just really funny
Try including the points on the circumference using
Or just include them as half a point to start with, since that is the average between inclusion and exclusion.
That circle is pretty God damn decent
What if you add a lowpass filter to the pi output? Maybe the convergence stopped due to noise overpowering the output
In programming terms... Everything past two floating point decimals is total bull depending on scale....
If you brute force went through every pixel in the window, with two for loops, how much closer would you get to the value of pi than throwing random dots?
kevnar Less closer actually
That's nice. But as I know, random function is based on an algorithm. So in fact it's not totally random? Am I wrong?
Why not to try a larger canva? Does it change anything?
If you made the resolution of the canvas bigger wouldnt that result in a more accurate PI since the random will be more "random"?
you can use some trig and Pythagoreans theorem to calculate it in a less complicated way
teamlead from ibm told me this was an actual senior dev interview question cant remeber IBM or where but big bucks on the line.
To make it a monte-carlo simulation you would have to take the average value of multiple runs of the simulation. Of course that just one run is not going to converge to an accurate answer. But the average does a much better job.
If we made the square and circle huge this would give us a better approximation right? This was only 400x400
What about increasing the window size?🤔 -> much more points much more accuracy
Stop using (slow) random. Count all the pixels in a gigantic imaginary square. Use Bresenham's Circle Drawing Algorithm to calculate the changing radius of the circle as y increases, and count the number of pixels falling inside it. You only need to do it for a quarter square. Use a number-as-string library to do the division, once, or periodically. Maybe once a second using multi tasking with a sleep.
You can do that by dividing r*r in place of total and removing 4..
i made my own method to approximate the value of pi without using random numbers
first using a computer draw a circle-- its circumference is how many steps it took to draw the circlr
then draw a semicircle and record the distance between the end point and the start poinf
then divide the circle circumference between the semicircle diameter
Why don't you throw a dart on each pixel instead of randomly? Wouldn't be more precise?
Where is the code for the PiCalc sketch that appears on the begin of Coding Challenge #95?
Nice job Dan, happy belated Pi Day! Maybe you could look more into casting because you totally overused it. Also, I think using double instead of float for the x,y-coordinates would help improve the estimation.
I learn from p5js are from function setup() {...} and function draw() {...} in windows OS but why professor used (void set) and (void draw) here? Thank you for your kindly help!
Ah! This is because I'm using Processing (java) which has a similar API to p5.js, but the syntax is Java! See: processing.org/. You can find the p5 code on my website: thecodingtrain.com/challenges/95-approximating-the-value-of-pi
Wouldn't it be more intuitive to draw green circle inside of blue square and then counting the pixels green in comparison to the blue? Instead of build your guess on statistics "experiment"
i programmed this exact thing a couple of years ago after watching physicsgirl's video about physically throwing darts to approximate pi. just for fun i shortened it down to a handful of lines and left it running for days on end, in that time it got fairly stable around the correct value plus/minus 0.0001. my code: www.openprocessing.org/sketch/407317
FROM ALGERIA,THANKS VERY VERY VERY MATCH FOR YOUR LINKS.
±0.0001
Calculate PI by using the circumference and chord of a circle - result 3.1415928 (12 lines of code)
i don't know how long he let it go at the end, but isn't it problematic to use int for the count of the dots? if your programm is fast enough you could run out of space in the (2^31)-1 number (~2 billion). and in his last version of the program he doesn't see if he goes out of bounds of the int.
I double dog dare you to write this in eight bit assembler to 32 bits of precision. You can only use integer arithmetic with only add, subtract, and bit shifting.
Your biggest problem is the size of the circle and square. Increasing the size of them will increase precision.
Don't really understand coding but... Isn't it cheating to have a function that has the real value of Pi inside of your coding to compare to what you're getting? Kinda defeats the purpose and reasonings as to why one would need to create a programme to make Pi in the first place if this function exists
I just did one with thousands of iterations of 1/1 - 1/3 + 1/5 - 1/7 etc then times four
you chould increase the r for 200 to 10000;
some error come from the randomniess of the random function
You should set the window size to 400x400 again, because your square is slightly too big otherwise
u made my day man
Calculation d with a double makes no sense since x, y and r are all integers.
But I like double d's.
9:48 x and y variables are defined as floats. I don't know the behaviour of random(-r,r), but I would be surprised if it returned an integer result.