Coding Challenge 161: Estimating π from Random Numbers with Euclid's Algorithm

🥧 Happy Pi Day 2021! This year I estimate the digits of π with random numbers and the probability of two integers being co-prime. thecodingtrain.com/challenges...
🎥 Matt Parker's Generating π from 1,000 random numbers: • Generating π from 1,00...
🎶 Pi Day song by Will from America: willfromamerica.com
🎨 Character design and animations by Jason Heglund jasonheglund.com/
🎬 Editing by Mathieu Blanchette
p5.js Web Editor Sketches:
🕹️ Estimating π from Random Numbers: editor.p5js.org/codingtrain/s...
🕹️ Estimating π from Digits of π: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge #160:...
🎥 All videos: • Coding Challenges
Links discussed in this video:
🔗 Probability of Two Integers Being Coprime: www.cut-the-knot.org/m/Probab...
🔗 Euclidean Algorithm: en.wikipedia.org/wiki/Euclide...
🔗 A Million Random Digits with 100,000 Normal Deviates: www.rand.org/pubs/monograph_r...
🔗 Quantum random numbers: qrng.anu.edu.au/
Other videos mentioned in this video:
Timestamps:
0:00 Happy Pi Day!
1:26 Explain! What does co-prime mean?
4:21 Explain! Euclid's Algorithm
8:40 Example! Finding the greatest common divisor.
9:55 Code! gcd() function with Euclid's Algorithm.
12:23 Code! Let's load the random digits.
14:39 Code! Let's use draw() for our loop.
16:13 Code! Co-prime or Co-factor?
17:44 Explain! How we are going to estimate π.
18:50 Code! Estimating π.
21:59 Code! Trying with digits of π.
22:54 Ideas! Thanks for watching!
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/Guides/com...
🚩 Suggest Topics: github.com/CodingTrain/Rainbo...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: kzbin.infojoin
🛒 Store: standard.tv/codingtrain
📚 Books: www.amazon.com/shop/thecoding...
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
🎶Pi Day song by / willfromamerica
🎶Music by Epidemic Sound: epidemicsound.com/creator
#PiDay #PiDay2021

[@tompov227]

If you choose substrings of 4 digits instead of 5 the estimation becomes 3.14159 🤯

[@gabenugget114]

It adds one digit?!??!?!?!?!?!?!🤯🤯🤯🤯🤯🤯🤯🤯

[@rainbowskeppy5292]

3.14159265358979323846264338

[@hikari1690]

It creates 10 times more data points so the estimate becomes more accurate. Sorry if you already know this 🤣

[@DerMathematicker]

i think we should just use 1 digit numbers

[@kabirbatra]

I'm in love with this editing style

[@anthonycannet1305]

It would take longer to run but instead of increasing index by 2, just increase it by one. Currently the program checks gcd(a,b) then gcd(c,d) and so on. Increasing by 1 would check every consecutive pair, so gcd(a,b) then gcd(b,c) then gcd(c,d) and so on. You get almost twice as many pairs of numbers which is one of the two things that affects how accurate this is. The other thing being how big your random numbers are. Another way to improve the estimation would be checking every number against every other number but that would take much much longer to run...

[@TheCodingTrain]

Great suggestion!

[@pvic6959]

I was thinking this too!

[@NStripleseven]

If you compared every number against every other, you wouldn’t even really need the random numbers, you could just use the numbers between one and whatever other number.

[@pvic6959]

@@NStripleseven I think the random numbers was more for fun.. though now I wonder what the results would be like if you used the first 10000 real integers :P

[@NStripleseven]

@@pvic6959 Could be interesting to try

[@adsoyad2607]

I did this exact thing inspired by the exact same video a year ago!

[@Rydergomes11]

same bruh

[@AliAli-wi2ys]

same 6 months ago

[@standupmaths]

That’s great to hear! I hope you enjoyed some random π.

[@adsoyad2607]

@Stand-Up Maths Well you can't get enough of pi can you? :D

[@gamesvrtech6666]

This morning the date on our clock showed us 3.14 and I immediately thought about you and your great videos. Thanks for beeing who you are, wish you all the best! Happy PiDay🍰🅿️ℹ️

[@jacobcowan3599]

The post-processing on this whole video is great XD love all the gags and running jokes And what a fun program, too!

[@ncot_tech]

You're not the only one who gets modulus/modulo mixed up. When I teach it, I just call it "mod" and avoid the whole problem ;-)

[@Carlosdreaming]

The video production is getting just better and better. Thanks. Great finale 🤯

[@CedLePingouin]

I'm a regular viewer, but I enjoyed this video even more. Love the animation at the beginning, the song, and the funny animated characters during the video. Great job :-)

[@xnick_uy]

I haven't visiting this channel for a while, and now I found a superb edition!! It was magnificent.

[@footballknight7]

Daniel you can use the series 3 + 4/(2*3*4) - 4/(4*5*6) + 4/(6*7*8)... to estimate PI! I did it in p5.js and got amazing results!

[@user-fw7ky1hd6f]

"The Best Video of the Coding Train Ever"

[@cortiazz5906]

Yo, nice intro! I love the whole "world" that you built up to this channel

[@rhevel]

Happy PI day! Great video as always ;)

[@darthtorus9341]

i love all the new cute animations added to the videos

[@kirby6551]

Awesome keep up the videos man!

[@grumpyparsnip]

Using the randomness of the digits of pi to estimate the digits of pi. That is beautiful.

[@gouravchouhan1790]

Short function for GCD, function GCD(a,b){ if(b == 1) return a; return GCD(b,a%b); }

[@egietje]

That wouldn't work if the random number b is 1 though, for example you put in a = 21 and b = 1, it'd output the greatest denominator being 21 whilst it is 1 Edit: I think you meant if (b == 0) return a;

[@j0code]

function GCD(a, b) { return b == 0 ? a : GDC(b, a%b); }

[@bastibob660]

@@j0code what does the "?" do

[@bastibob660]

@Free pizza for So as an example b=2 runs GDC again b= 0 returns a

[@hetsmiecht1029]

@@bastibob660 Precisely. It's called the ternary operator, in case you want to look it up.

[@straybasilisk2689]

Loved PI-ception at the end there!

[@ramkumars2329]

Hi Dan!!... i liked it!! especially the animations that you included in the video!!! plz keep those animations in the future videos as well!!.. Thanks a lot!

[@realcygnus]

Nifty as usual !

[@tomg0]

Another excellent video

[@RenatoSousaRS]

Love it!!!

[@beron_the_colossus]

Great video! I didn't get a notification for it, strange. Maybe because it's a premiere?

[@TheCodingTrain]

yeah, i think that might be the case

[@luismiguelgallegogomez8000]

Just love the song!

[@meher94]

These videos are so underated.

[@fakenamerealguy7084]

Fwiw, when you said recursion I smiled happily

[@lachainedudeveloppeur2556]

Great video

[@samuelgunter]

I would cache the results of the gcd call to prevent having to calculate the same gcd multiple times. this sounds crazy because you probably won't get many times of having the same 5 digit number, but the chance of a cache hit increases as it gets down to fewer digits. you can also do this cache check after the reordering of a and b to make sure it hit both (384, 78) and (78, 384)

[@ar25k46]

The song is so awesome lol

[@fiopio2422]

Hey! I am a big fan of you! I started learning javascript because of you, and sometimes I migrate your codes into python version with courses interface! I would like to propose you one possible topic fore some coding challenge, what about one virtual humanoid learning how to walk? really big project! or maybe something slightly easier, I would love to see that!

[@Operaatoors]

10:39 - just min and max functions. Or sort the array and then pick in order. Although, this version is good as well :)

[@sub-harmonik]

lol love the editing

[@singstardancestar1462]

Sir you explain very well, so I like your channel

[@jfdio29]

I thought it was going to be the version with Euclid's distance + Monte Carlo algorithm to estimate Pi. I'm happy to have learn something new!

[@TheCodingTrain]

maybe next year!

[@bokkenka]

If b>a, just get the gcd(b,a).

[@TheCodingTrain]

ah, i wish i had thought of this!

[@poof65]

Yeah, that's what I thought at first. Make a smart use of the recursion 👍

[@minghaoliang4311]

Invoking an additional call stack may use more memory than swapping 2 variables xd

[@mickjames01]

If b > a, then gcd(a,b): a%b -> 'b' goes into 'a' 0 times remainder 'a', therefore the next recursive call will be gcd(b,a). Thus, there is no need to worry if one is larger then the other.

[@beethovennine]

You rock!!!!

[@hrishinadgouda3358]

Love ❤️ it

[@joserubens6512]

hello good afternoon good video: I have a question and it is possible to use these codes in Buildbox 3d since it is js.

[@cnoize314]

Blueberry is my favorite kind of pie too!

[@haval00]

N8ce bro ♥️

[@grazzt519]

coprimecount starts at 0, so until a coprime pair is found, isnt there a division by zero going on? or am I missing something? (for pidigits, the first two 5 digit pair are not coprime, so javascript allows division by zero with no errors?)

[@angelcaru]

In JS, x / 0 returns Infinity

[@emmanuelkoutsoudakis4614]

Cool 🌈tutoring

[@martinkuhk]

While I personally prefer to use iteration to implement the Euclidean algorithm, the recursive solution does point out the essence of the algorithm clearly: gcd(a, b) = gcd(b,r).

[@liberto7077]

Random digits book: exists Chaotic functions: am i a joke to you?

[@aashsyed1277]

6/pi^2 is the reciprocle of sum of reciprocle squares!

[@JohnWasser]

Someone should publish “A Million Random Digits” but tweak the sets of 5 digits so that every adjacent pair is coprime. Imagine the delight of someone who does this experiment on the tweaked numbers. I wonder if the tweaking could be done so the digits and numbers still pass all usual tests for randomness. :)

[@xnick_uy]

I'm guessing they would fail the p(gcd(a,b)==1) -> 6/pi^2 test :)

[@roamingcelt]

You were so happy to use recursion and didn't use it in your if statement... if(b>a){ return gcd(b,a); } This would flip the two and bring in recursion.

[@oc_ociruiq6571]

Is it possible to suggest the basis that a beginner should begin with????

[@S197Bryan]

Is there a video where he uses luhn algorithm. I would love to see him implement it

[@DeeJayTeeLME]

Hi there Dan, hope you are well, my name is Thomas, I'm loving your videos and tutorials on javascript. I'm reaching out because I'm am trying to make a chrome extension but I am getting stuck. And was wondering if you could help me out with the parts Im getting stuck on. P.s I am pretty new to programming in general I have learned to program the basics in c# but some of the Concept of C-sharp don't always work in javascript. I would really appreciate it if you could help. Thank you Thomas.

[@TheCodingTrain]

Come and join the discord, it's a great place for getting help! thecodingtrain.com/discord

[@MAZ01001]

[13:45] could use Array.splice(start_index,count); let digits=[1,2,3,4,5,6,7,8,...]; let num = digits.splice(0,4); //num >> [1,2,3,4] //digits >> [5,6,7,8,...]

[@ShaneDavisDFTBA]

Does this imply that the digits of pi approach random and are equally represented?

[@hetsmiecht1029]

A non recursive version of the gcd function: function gcd(a, b) { if (b > a) [a, b] = [b, a]; while (b != 0) { [a, b] = [b, a%b]; } return a; } To be honest I don't really understand why some people think recursion is the answer to everything (slight exaggeration, but please do answer if you have an idea): if you can use a loop instead of using recursion, why would you not use a loop to save memory on the stack?

[@jetison333]

Sometimes recursion is easier to write and understand, and in some languages like c++ tail call recursion gets optimized into a loop by the compiler anyway.

[@dabs4270]

Recursion is cooler than loops Therefore, recursion > loops

[@RajJaiswal538]

Coding challenge idea: Make a random number generator WITHOUT using any random number generator Libraries or even the default one from js. If you think it does not deserve a seperate vid then please give any resources that explains how can any random number be generated Edit: spelling mistake

[@TheCodingTrain]

Yes, I 100% would like to do this!

[@daniellebarker7205]

Probably easiest way would be with the current time. in JS, Date.now() % 1000 will give you a pretty random number from 0 to 999

[@ricksidwell]

There are several ways to do this. Do a web search for "generate random number without math.random". (I tried posting a link, but I think KZbin flagged it as spam and deleted it.)

[@RajJaiswal538]

@@ricksidwell okay, I'll check it out. What I was trying was actually a kind of cheating. I calculated the xMousePosition and divided it by width of screen to get a random number from 0 and 1 but it's definately not that random

[@mateothode5603]

@@TheCodingTrain don’t forget hahaa

[@Brahvim]

10:38 Apparently, in my Computer Science book (About writing pure Java Console programs. It was for Grade 9, from the ICSE Board, India, since I am Indian, xD!) they had this question where they wanted us to swap two numbers WITHOUT using a temporary variable! I scratched my head a lot, tried to solve using addition and subtraction...some multiplication, but failed. Then I found the answer on stackoverflow. Here is the algorithm, (modified with shorthand operations!) ..it's simple and fun! Mind that 'a' stores the first number, and 'b' stores the second. a += b; b = a - b; a -= b; Although this just seems useless since it just puts useless load on the machine running the code, it is a great way to exchange the numbers stored in two variables without having to use a third, .....and looks smart, xD!!! Hope this *_IS_* a good way to handle it! :sweat_smile: And I don't think it works for negative numbers....maybe it does, but maybe it doesn't!!! Immediate edit: Here's another problem from the book I solved my self in a minute: Add two positive integers, (...or natural numbers xD) *WITHOUT* using the '+' operator!!! I DO NOT allow you to use a secret function that uses the '+' operator; I myself did it with some simple math :sweat_smile: (I should stop with the Discord emojis :grimacing:) Answer:

[@TheCodingTrain]

what a cool solution!!!!

[@markusosterle3958]

Hey I am new to the whole p5.js thing and am using the online editor. Somehow I am getting really bad performance and low framerate with the same code (on a good pc) any ideas how to fix it?

[@pvic6959]

ive always been a bit confused with that random numbers book. If a person were to "randomly" flip to a page, wouldnt it be more likely that the person chooses a page near the middle (I have no proof for this)? For instance, i dont think people will choose the first page 1% of the time out of a 100 page book. So how do we know that random numbers book is actually random? I wonder if there is a number there that is more likely to be chosen vs all the other numbers. Like "page X is most likely to be chosen. and the Yth number on a page is most likely to be chosen. So Yth number on Xth page is the most likely number to be chosen in the random numbers book.. making it not truly random"

[@tissuepaper9962]

The way to use the random numbers book is as follows: 1. Start from page 1, digit 1 and take as many digits as you need. 2. *Mark* or otherwise keep track of which is the next digit that you didn't use. 3. Next time you need random numbers, start from the place you marked instead of the beginning. 4. If you reach the end of the book, wrap right back around to the beginning. 5. Repeat 2-4 ad infinitum. Something I'm not sure about is what kind of distribution the random digit book claims to contain. Is a.) the distribution of digits uniform over the whole book, or b). is the *sequence* of digits constructed such that for any digit, the next digit has a uniform probability of being any number 0-9. Those might sound like the same statement, but they aren't. You could satisfy (a) and not satisfy (b) by constructing a book where the numbers go "0123456789" over and over forever, for example. You could satisfy (b) but not (a) by constructing the book from an ideal source of randomness, because it's highly unlikely that the number of each digit is exactly the same in a true random sample of digits. If (b) is true (which is my assumption, because it makes the book more useful), then the procedure I described above ensures that you don't influence the distribution by your choice of page. If (a) is true then it shouldn't matter where you start as long as you use an entire "unit" of digits, i.e. page, column, etc depending on how the numbers are grouped together when they're generated, i.e. if each individual page is guaranteed to have a uniform distribution, you need to use a whole page. If each chapter is guaranteed to have a uniform distribution, then you have to use a whole chapter, etc.

[@krccmsitp2884]

Without recursion, gcd() can be much faster and stack-friendly: function gcd(a, b) { while (b > 0) { [a, b] = [b, a % b]; } return a; }

[@JonathanMandrake]

In german, the problem with modulus and modulo doesn't exist, I don't even know if the german word modulus exists or is used in some fields of math I haven't learned yet, so there's no room for confusion : )

[@DerMathematicker]

if you have 2 numbers a*10+b and c*10+d, they aren't coprime if d*a-c*b is divisible by c*10+d, maybe, i think, possibly

[@DerMathematicker]

i've checked it again and it is true, but not the other way around.

[@willemkossen]

Does that second test prove the digits of pi actually represent random numbers?

[@fulvioabrahao]

No

[@NaNa-it9mi]

very funy

[@charliejulietdavies8715]

here's my obligatory two cents: javascript lists work kind of like tuples which makes swapping values easy: [a, b] = [b, a] boom

[@charliejulietdavies8715]

doh, i should have kept watching, i would have seen you remember that 😅

[@Wecoc1]

Pi is the only number you can eat [Newton cookie left the chat]

[@pvic6959]

17:15 a pair of numbers with GCD 442 :o

[@susmitkumarmishra339]

Hmm using 1 million digits of pi to get 3 digits of pi!, couldn't get more inefficient 😁

[@perkarlo]

wow

[@polaris6777]

Please help me, there is this annoying feature in p5 I just cannot turn off. Whenever I write something,it overwrites what was previously written instead of displacing it. I don't know what to do?

[@jetison333]

Press the insert key on your keyboard. That happened to me once and it was very annoying haha.

[@vilkillian]

The way that you used to make an array of random numbers isn't actually random. bc it's not random numbers, it's random digits. Probability of some digit being 0 is 1/10 Probability of only first digit in a 5-digit slices being 0 is lesser than 1/10, so you expect lesser 4 digit numbers than uniform distribution would give you Probability of only first 2 digits being 0 is way less than 1/100. So you expect way less 3 digits than uniform distribution would give you And so on... So your values absolutely not random and won't do for such an experiment and will create an error. But don't mind old programmer like me, i'm just picking :)

[@vilkillian]

and also, the less digits you use to make a number, the more "uniform" becomes resulting array, that's why people get really good estimates using 4 digit numbers

[@MrSefsdf]

I was searching for this comment :)

[@Moonbrony]

Hmm, I wonder if I could use an Arduino to read white noise to generate random numbers...

[@jakubkurdziel2407]

13:45 you could use the regex

[@strex2062]

22:00 oh yes var pie = TWO_PI / 2

[@EnDirectDeMaTete]

If you use 4 digits numbers you have 250000 numbers, by chance the estimate is then 3.14159... Happy Pi !

[@TheCodingTrain]

oh wow! I wish I had tried that!

[@ayanbahukhandi1869]

This man reminds me of Murray in the Stranger Things series, agree?

[@ratuldbro]

can anyone please tell which software he uses

[@Palontras]

He is actually spelled "Oiclid" :D

[@j0code]

Are you German? Weil "eu" spricht man im Deutschen "oi" :p

[@ratuldbro]

can anyone please tell me which software he uses 🤝🤝🤝

[@saksham01]

Did you mean half tau day?

[@Fun-Planet]

String.split would work, right?

[@TheCodingTrain]

Yes? Can you split by a number of characters rather than delimiter?

[@Fun-Planet]

@@TheCodingTrain oh haha for a moment I forgot how split works (can't use split). Another solution could be str.match(/.{5}/g) Good ol' regex magic

[@TheGreatAtario]

Hmm, someone either hired video production people or else has been spending COVID time learning it

[@devinshrees7060]

6:34 🤣🤣🤣🤣🤣

[@himanishmandal9556]

Hey all this is ok but could we have a pacman challenge next please.

[@jwrm22]

It hurts a bit, he solves the /0 by adding 1 to every number read from the book, instead of writing an exception in gcd().

[@toastyPredicament]

It's Valentine's day here c:

[@toastyPredicament]

Almost

[@toastyPredicament]

If you run a sine wave its value is 1 every second making it a timestamp measure c:

[@toastyPredicament]

I mean at 1 Hz

[@NStripleseven]

22:00 You used the Pi to calculate the Pi

[@JasimGamer]

10:45 this better 😃 [a,b] = [b,a];

[@moshly64]

Can't you just wrap around on the random data and continue processing ?

[@pseudotaco]

Technically yes, but that brings some problems. After running through the data any number of times, you will have the exact same pi estimation as after the first one, since the numbers just repeat. You would have to alter the data, for example by offsetting it

[@toastyPredicament]

Could I ask you out some day

[@toastyPredicament]

3.14228

[@Rydergomes11]

same

[@toastyPredicament]

I wish I could go out with you c:

[@vincenzochiaramida5389]

Why no one is interested in estimating 6 using pi^2 instead

[@Ferdyn94]

hm.. did he just make a pi(e) out of a pi(e)?

[@levantatanashvili6057]

da

[@toastyPredicament]

Don't click on the gf please

[@abbasmohamadelkarsifi8099]

He overcomplicated this too much