Big Factorials - Numberphile

Подписаться 4,5 млн

Просмотров 381 тыс.

50% 1

Large factorials and the use of Stirling's Approximation. Featuring Professor Ken McLaughlin.
More links & stuff in full description below ↓↓↓
Professor McLaughlin is based at Colorado State University: www.math.colostate.edu/~kenmcl/
We filmed this during his time at the Mathematical Sciences Research Institute.
69 Factorial: • 69! - Numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9

Наука

Опубликовано:

23 мар 2022

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 915

@_thank_you_ 2 года назад

on an unrelated note, Prof. McLaughlin's voice is one of the best in the game hands down. i want him to tell me everything will be okay while explaining combinatorics to my kids

@bolehtahan 2 года назад

He has very neat handwriting too

@heartache5742 2 года назад

i can't listen to this accent

@wearwolf2500 2 года назад

@@heartache5742 He sounds very American to me.

@TKing2724 2 года назад

I wish my mathematics professors sounded like him, I can understand what he's saying.

@ingvarhallstrom2306 2 года назад

Sounds like an educated New York dialect to me? Slihgtly downtoned. But it is what I Imagine a New York psychiatrist would sound like.

@younesabid5481 2 года назад

- ...it's a bit of a shortcut but you don't get it exactly right! - That's exactly right.

@jorgesaxon3781 2 года назад

That not exactly right

@HasekuraIsuna 2 года назад

@@jorgesaxon3781 That's exactly right!

@ptousig 2 года назад

It's kind of a "Parker Factorial".

@chessandmathguy 2 года назад

The fact that you don't get it exactly right is exactly right. 🤣

@theastronomicalmouse1828 2 года назад

@Kurniawan Adhi r/wooooosh

@patback9708 2 года назад

Prof. McLaughlin: It's off by almost 2, that doesn't seem so close, right? Me, an engineer: Seems close enough!

@MichaelPiz 2 года назад

Perfection is, properly, an engineering term.

@Antiphar 2 года назад

Prediction and measurement in the same order of magnitude? Pop the champagne!

@qugart. 2 года назад

It's like the engineer's π. π is more than 3, so it's obviously 4. Let's say 10, to play it safe.

@MichaelPiz 2 года назад

@@qugart. It's more like, we live in the real world, not Plato's imagination, so if the value is within appropriate tolerances then it's perfect.

@redumptious2544 2 года назад

So basically off by e..

@jeojavi 2 года назад

3:18 "But you don't get it exactly right" "That's exactly right" Loved this

@TheWaterMiners 2 года назад

For those we are still confused about the part where their ratio gets closer to one while their difference increases, think about it like this: 1 and 2 have a ratio of 0.5 and a difference of one. 900 and 1000 have a ratio of 0.9, which is closer to 1, but a difference of 100, which is much larger.

@alexcubed4270 2 года назад

I think the more confusing part is how the ratio can be 1 without the numbers being the same

@QuantumHistorian 2 года назад

@@alexcubed4270 The ratio isn't 1, it just gets closer and closer 1 as N gets bigger. To put it precisely, for any number you give me greater than 1 (say, 1.5 or even 1.0000000000000000001), I can find an N such that N!/approximation is between 1 and it. AND, that holds for all N larger than that one too.

@TheWaterMiners 2 года назад

@@alexcubed4270 well it's just approaching 1

@alexcubed4270 2 года назад

@@QuantumHistorian Ahh i see, yea the concept of infinity/infinite digits is always a bit confusing and tricky

@jindmen 2 года назад

@@alexcubed4270 It's not really 1, it just gets closer and closer to it. The definition of the limit doesn't need it to be precisely the 1, but when the N goes to infinity, it gets "infinitely" close. The definition says something like: For anyhow small surroundings of the value you pick - let's name it 'd', there is a point from where the value is always closer to 1 than the picked 'd'.

@jan_kulawa 2 года назад

Back when I started following this channel, I struggled to follow Matt Parker's calculations, but was nonetheless interested in the results enough to pursue the subject further. Today, from the title alone, I correctly guessed the video was about Stirling's asymptotic approximation for factorials. Cheers from Brazil! And thanks for being a substantial (a mathematician would say, non-trivial) part of my life.

@Nickelodeon81 2 года назад

Brazil factorial? impressive

@fernandovalner 2 года назад

salve

@fonkbadonk5370 2 года назад

@@Nickelodeon81 Must have a brazillion digits!

@daniell.garcia1748 2 года назад

Graaande

@bryanchandler3486 2 года назад

That's so awesome how you've progressed! Congratulations!

@Dysiode 2 года назад

I love how clear Professor is, making sure to explain terms that may be unfamiliar and even just stating what he's going to do! "I'm going to rewrite that whole ratio," makes it clear your brain doesn't have to be paying precise attention for new information. It would be an absolute joy to take a class with him

@aperson2703 2 года назад

For physics the number of particles in a typical system is on the order 10^22 so this approximation is incredibly accurate. Also taking the log makes it much nicer to work with.

@Vasu-qn6kj 2 года назад

Interesting. ( I'm also talking about your name)

@yourguard4 2 года назад

@@Vasu-qn6kj would be interesting, when he would turn out to be a bot :P

@sharpnova2 2 года назад

@@yourguard4 a Russian bot, planted to sew dissent

@Mayur7Garg 2 года назад

Thank you! I was thinking how N^N was easier to compute than multiplying numbers 1 to N. Taking log of the equation actually makes so much more sense.

@BiscuitZombies 2 года назад

@@Mayur7Garg This but unironically.

@PhilipSmolen 2 года назад

I remember using Sterling's approximation in school. It was nice to be able to use Big O notation with a factorial. And we used to prove that a sorting algorithm couldn't do better than O(n · log(n)).

@Tombsar 2 года назад

Note: O(nlogn) is the best a sorting algorithm can do on average if you are limited to only doing pairwise comparisons between elements. You can actually go faster if you are allowed to exploit other information about the data. See radix sort for an example that achieves linear complexity on lexicographical data.

@vishalcseiitghy 2 года назад

God's algorithm

@PeterGaunt 2 года назад

I love your knack of asking exactly the right questions of the people you meet.

@cariboubearmalachy1174 2 года назад

"You don't get it exactly right" "That's exactly right."

@delecti 2 года назад

I'm so curious how that could be faster. The approximation includes N^N, which is just a many multiplication operations as factorial on it's own, and then it also has all the other complicated operations added in.

@l0rdbulb 2 года назад

That's exactly what I'm thinking. N^N is multiplying N numbers, and so is N!. So is that also approximated somehow?

@Peterwhy 2 года назад

My guess is, to calculate N^N, you can repeatedly square N, so the number of multiplications is O(log N).

@PedroContipelli2 2 года назад

@@Peterwhy This is correct

@joelkuhn9880 2 года назад

I was curious about this too, so I searched fast power algorithm, and found exactly that. Basically, given x^y, you can rewrite that as (x^2)^(y/2) as long as y is even. If it's not, you set an x aside to multiply later, and keep halving your exponent and squaring your base so it finishes in log2 time.

@biocode0 2 года назад

@@joelkuhn9880 Or use logarithms.

@markday3145 2 года назад

I really like the way the professor explains things. I'd like to see more videos with him.

@samstarlight160 2 года назад

3:20 "You dont get it exactly right" "That's exactly right" Got a laugh out of me

@jacemandt 2 года назад

In other words: the limit of their ratio is 1, but the limit of their difference isn't 0. The limit of the difference isn't any number, because the difference keeps growing as N gets very big. Taking a difference vs. taking a ratio both measure "sameness", but in different ways.

@jonrutherford6852 2 года назад

For me, as a non-mathematician, this was nothing short of thrilling. I had no idea there was a way apart from barebones multiplication to find the value of a factorial -- at least a very close approximation. To hear of its value to mathematicians was a bonus! Very well done, and many thanks.

@TheofilosMouratidis 2 года назад

In computer science terms, a factorial is an always increasing number of computations, while the approximation is almost constant. So if you have N! you do N multiplications, but with the approximation you do always a bit more than 4. So now you can calculate factorials really fast.

@rewrose2838 2 года назад

@@TheofilosMouratidis *you can roughly approximate factorials really fast.

@TheofilosMouratidis 2 года назад

@@rewrose2838 yeah, this formula can be improved to calculate for the error ratio for extra correction, some kind of overfitting polynomial if it doesn't get too complicated.

@landsgevaer 2 года назад

@@TheofilosMouratidis ...and you need a couple of exp(x) and ln(x) that are more involved than integer multiplication. I know that these are pretty fast on current cpu's. But for us mere mortals... (Moreover, you could argue that if n! was implemented as a cpu function as well, then that thing itself was just a single operation.)

@4k-os 2 года назад

@@TheofilosMouratidis How do you compute something to the power of N without doing N computations?

@jaerik99 2 года назад

Professor McLaughlin is a great educator. More of him please!

@PnlBtr 2 года назад

Strongly agree, Any topic.

@cliftonchurch6039 2 года назад

I completely agree. There's something in his presentation that I personally found very easy to follow. I feel like this was the first theoretical math(s) video that I wasn't thinking "okay, I didn't follow that, but I trust you. It sounds right enough, I think?" but instead was thinking "okay, of course. That makes absolute sense."

@jsb3605 Год назад

I agree very pleasant to listen to. Also I appreciate that he didn't give us he "math is fun" act which I grew tired of over time on this channel

@gsurfer04 2 года назад

As a computational chemist, I can confirm Stirling's approximation is very handy. However, when manipulating the mathematical formulae for thermodynamics we stick to the factorial form as it often simplifies to N+1 etc.

@TateFM 2 года назад

Professor McLaughlin does such a fantastic job breaking this down and making it really interesting for even just a layman (but appreciator) of math. His passion reminds me so much of a professor who taught me Calculus I in college too. The passion is infectious which is what makes this channel so special.

@Kaepsele337 2 года назад

One instance where this pops up in physics, even at the Bachelors level, is in the calculation of entropy of a system. Entropy is a measure of how many ways a system can be in terms of the positions and momenta of its particles and still be the same volume, temperature and pressure. An important thing is that if you exchange the position and momentum of two indistinguishable particles, you do not actually get a new state. So to prevent that you count the same state multiple times, you have to divide by the number of ways you can permute the particles of the system, which is N!. For a macroscopic system, N is of the order of avocados constant, so around 10^24. You can imagine why the approximation is kinda useful here, especially since you have to take the logarithm to get to the entropy.

@dlevi67 2 года назад

Avocado's constant is Singingbanana's favourite number!

@mentox6592 2 года назад

Mmm I’d really go for an Avogadro right now!

@letsgocamping88 2 года назад

Thing with avocados constant is that you have such a small window in which to use it.

@Eriochrom 2 года назад

@Guest6265: Being a chemist, I scrolled down looking exactly for this great answer (to avoid double posting it). The typo is just unfortunate, yet funny =)

@unvergebeneid 2 года назад

e and pi really crop up in the darndest places 🤯 Like, there's an uncountable number of irrational numbers. These two have no right to be so overrepresented! 😄

@phasm42 2 года назад

That integral near the end is called the Gamma function, for anyone interested.

@codediporpal 2 года назад

I'm just blown away that this channel continues to produce fascinating content, much of which I was completely unaware of. So much to say about numbers!

@PopeLando 2 года назад

I just realised for the first time that the reason the number is called the "factorial" might be because even if we don't know the value of say, 100!, we know that all the numbers up to 100 are factors of it.

@Fogmeister 2 года назад

Hah, I’d never thought of that before. 👍🏻

@IllusoryMaze 2 года назад

The ultimate anti-prime.

@inefffable 2 года назад

∞! The All-Time Greatest Anti-Prime

@nickbeaumont1637 2 года назад

Which is exactly how you easily prove the infinity of primes with factorials - if there were a largest prime, its factorial plus 1 would have no factors, and thus be prime, a contradiction

@tomkerruish2982 2 года назад

@@inefffable Infinity factorial is the square root of 2 pi. (This is "proven" via shenanigans similar to those used to "prove" that the sum 1+2+3+... "equals" -1/12.)

@JustcallmeJayrot 2 года назад

More Prof. McLaughlin! He's terrific!

@CartoType 2 года назад

Great presenter, fascinating content. More from Professor McLaughlin please.

@stayawakestudios 2 года назад

I can't wait to watch Matt Parker approximate PI using that equation and a large, hand calculated, factorial

@jordanrobberecht7003 2 года назад

All videos by Brady are absolutely gold. 100! Stars out of 5

@ffggddss 2 года назад

Thank you all for attending this first course in our series. In the next course, we develop Stirling's Series for factorial, of which Stirling's Approximation is just the 1st term. In it, you'll see how the second term determines how that ratio's difference from 1 behaves as N->∞ . . . Fred

@timseguine2 2 года назад

This reminds me, one of the things that surprised me initially when I started to study math at university was that, contrary to school math where the focus is usually on exact answers and equations, most "real" math is based on approximations and inequalities.

@grimshawr 2 года назад

The beautiful thing about this approximation is that it captures the transition from Quantum Mechanics to Classical Mechanics & Thermodynamics. You can derive all the laws of physics that we've understood for 150-350 years from the stochastic behavior of many quantized particles.

@emmanuelagudo4918 Год назад

Something magical about worded problem solving questions that involve Factorials. The logic is so fluid, it is so beautiful. Imagine riding a super fast elevator for quite odd structures, or yet kind of navigating a complex query but then it is arranged in a certain fashion that can be ultimately deduce from Fibonacci sequence. Amazing! thank you!

@Kippster29 2 года назад

Taking a course in Statistical Physics and we use this approximation ALL the time. It really makes things a lot easier

@johnchessant3012 2 года назад

There's some motivation for this formula using the integral of log(x), which is x*log(x) - x. Notice that log(n!) is just the sum of the logs of 1, 2, 3, up to n, and this "should" be close to the integral of log(x) from 1 to n. So we should expect log(n!) and n*log(n) - n to be relatively close, and exponentiating gives n! ~ n^n e^(-n). Of course, the sqrt(2pi*n) part is a more complicated story.

@briandublidi4708 2 года назад

I was literally programming a function for pi which used factorial for incredibly high numbers. love you numberphile

@ez_is_bloo 2 года назад

This is probably one of the more digestible vids here. Loved Prof. McLaughlin

@jared_bowden 2 года назад

1:00 - *flashbacks from diff-eq class* 1:19 - "Oh, ok, this isn't the Gamma Function" 9:55 - "wai- no, no, I'VE BEEN DUPED!!"

@martinepstein9826 2 года назад

9:55 In case any viewers haven't learned what integrals are, he's saying that you can find e.g. 5 factorial by graphing y = x^5 * e^(-x) for positive x and taking the area between the curve and the x axis.

@abhaysharma2261 2 года назад

This is such a classic numberphile video!

@asparkdeity8717 2 года назад

Had a couple of questions which asked to prove Stirling’s formula by considering bounds for a certain integral and using Wallis’ product, and just now I get recommended a video in this, perfect!

@Terratops474 2 года назад

One of the greatest things about math is that numbers get bigger if you're more excited about them.

@katakana1 2 года назад

I'm so excited about big numbers that most of the videos on my channel detail them.

@jentlejeniuskat 2 года назад

Anyone who likes this statement and isn't already subscribed to Matt Parker's channel "Stand-up Maths" should check it out, because this sounds exactly like the kind of thing he'd say.

@asatzhh 2 года назад

I want to address on the ratio. I want to notice that the ratio 1.00083 is roughly 1+1/(12*100) and the ratio and 1.00004 is roughly 1+1/(12*2000). In fact, in general we expect the ratio to be 1+1/(12n)

@VavelOnline 2 года назад

Wouldn't it be possible to multiply the approximation with this approximation of the ratio to enhance the former?

@markbrown2450 2 года назад

Wow! Professor McLaughlin is a great speaker with a great tone and style. I look forward to seeing him on more videos.

@rhodexa 2 года назад

_“[•••] You don't get it exactly right - that's exactly right”_ loved it

@aminzahedim.7548 2 года назад

I remember learning about the Sterling’s Approximation in my undergrad thermodynamics course while studying the concept of entropy and then again in real analysis I. I could readily prove the formula using a Riemannian sum of the area under the curve ln(x) over 1 to N as compared to its definite integral, up to the constant sqrt(2*pi). I then spent A LOT of time thinking how two numbers can actually grow further apart and yet their ratio converge to 1. Here’s an example of a simple-yet same in essence-situation I came up with: take f(x)=x^2 and g(x)=x^2+x. The difference, g-f grows without bound as x gets larger and larger, but the RATIO f/g-or vice versa, in this case-converges to 1, the ratio of the largest powers’ coefficients (both being 1, in this case). If I’m not mistaken, this is the same “asymptomatic freedom” condition as discussed in the study of quantum field theories; the expansion has to approximate the nonlinear fields in the same sense.

@iammegan6626 2 года назад

That's.... Amazing! I never tbought that could be possible

@DingDimlewitz 2 года назад

First time I see prof. McLaughlin on numberphile. Has he been in some other videos? We need more videos with him, he is awesome.

@MattSeremet 2 года назад

Growing up in the US I never heard what factorials were until sometime in college, and even then it was through research for a personal programming project (nothing to do with school work). Any talk of learning or practicing in school fills me with a great big "I WISH!!"

@mitchellsteindler 2 года назад

Where did you go to school that you didn't learn factorial? Pretty sure I learned that in 7th grade...

@nikolaimikuszeit3204 2 года назад

like others mentioned before, I came across this during my classes on thermodynamics. Very useful.

@YossiSirote 2 года назад

The approximation can be improved very considerably by multiplying by e^(1/(12n+1/2))

@joemiller947 2 года назад

I entered this into desmos and it's amazing how close it is, did you figure this out yourself?

@katakana1 2 года назад

A slight improvement from that is just multiplying the original by 1+1/(12n)

@gabor6259 2 года назад

Now where does _that_ come from?

@lelouch1722 2 года назад

@@gabor6259 You can either use an asymptotic approximation of the gamma function, or an asymptotic development of ln(n!) using Mac-Laurin series. The stirling approximation is just an approximation of order one, but you can approximate with an higher order. So you can multiply by 1+1/(12n) to get an even better approximation or 1+1/(12n)+1/(288n^2) which is even better or 1+1/(12n)+1/(288n^2) - 139/51840n^3 which is even better etc. You can found the coefficients on the gamma function page probably

@forcelifeforce 2 года назад

@@lelouch1722 -- You mean for it to be 139/(51840n^3) on the end.

@TheSmegPod 2 года назад

so basically the approximation itself doesn't get any more accurate, but the numbers just get so crazy big that the margin for error relative to the total size of the number becomes proportionally less and less?

@aliwelchoo 2 года назад

Kinda, the approximation does get better slowly, hence the tending to ratio of one, just the numbers get bigger faster than the accuracy improves. So the absolute difference can grow while the relative difference shrinks

@seanmcdermott4634 2 года назад

May be one of my favorite speakers I’ve seen on this channel

@matthiasoc7141 2 года назад

I always love Numberphile, but every so often one will come along that just grabs me. This is sure to spark some investigation of my own!

@Taylor-rx4yb 2 года назад

Wow I just graduated with my math degree from CSU! It's cool to see someone you know on Numberphile!

@jamescollier3 2 года назад

cool

@kitty13kitty 2 года назад

I liked seeing the trailing 0's, it got me thinking "ok, so we got every 10's place" 10->100 is +11 "Every number that ends in 5 will get a corresponding 2 factor" gives us another +10 "50 actually nets us one more" +1 And finally, I saw that 5^n numbers, (25, 75) we picked up another trailing for another +2 There are 24 shown. And yes, I sat there for 25 min looking for where all the 0's came from.

@vsm1456 2 года назад

I noticed that bunch of zeros too :D

@kitty13kitty 2 года назад

@@vsm1456 I wonder if any of the "carry 1" from a factor of 5 will ever produce an additional trailing 0.

@bur2000 2 года назад

This is also helpful to quickly estimate the number of digits of a huge factorial: N * log(N) - N/ln(10). Or further simplified so you can actually do it in your head: N * log(N) - 0.43*N. For log(N) just use the number of digits of N.

@Hidegety1 2 года назад

That was very refreshing episode

@markphc99 2 года назад

It occurs to me that saying that the function converges in the limit isn't very useful necessarily - it depends on the rate of convergence. I'm reminded of the harmonic series here : add 1+ 1/2 +1/3+1/4 etc it grows to infinity (diverges) but ridiculously slowly. Also if you know the rate of convergence then you can correct for the error somewhat , provided you know that the estimate is always smaller or larger than the true sum

@HeyRandal 2 года назад

It is very useful to know that the ratio doesn't get bigger. I posted a question about your 2nd point.

@TheReubenthegreat 2 года назад

It's obviously quicker to calculate 3! as 1 × 2 × 3 = 6, and 100! using the approximation, so I wonder at what point between them is it equally as fast.

@gustavoexel5569 2 года назад

Well, your question is really interesting, and I'm sure there's a decent and rigorous way of answering it, however I don't know that way, so I computed it many times and timed it. Turns out that after N=225 Stirling's formula was faster, but that could change in orders of magnitude depending on the efficiency of the implementation (which I'm sure mine was far from optimal). Still, it's a numerical value answering your question.

@NoActuallyGo-KCUF-Yourself 2 года назад

It depends on who or what is doing the computation and using what algorithm.

@howdyimflowey4341 2 года назад

@@gustavoexel5569 For my implementation (iterative factorial and 32-bit integer/floats) the threshold is passed when N=50. Seems useful for big factorials, but it is a LOT slower for calculating smaller ones.

@gustavoexel5569 2 года назад

@@howdyimflowey4341 You know, I also implemented an iterative factorial, but it was really trash. I guess there's more efficient ways to compute the factorial. In the end I ended up using a thrid-party implementation, since I did it with Python I used numpy.

@ChristopherBonis 2 года назад

Finally, a Numberphile video that I understood completely.

@Kaesekuchen002 2 года назад

Great voice to listen to and nice explanations!

@aseq2 2 года назад

And here I am, not even knowing how N^N would be easier to compute than N!, let alone the rest of the approximation.

@AmnonSadeh 2 года назад

Here's what I (layman) was missing from this video: How come nⁿ requires less calculations than n! ? (not even talking about the rest of the formula) The fact that he did stuff "offline" (5:21) didn't help much... But I think I got it now? Let's take n=8 for example Naively I thought 8⁸ requires almost 8 multiplications: 8⋅8⋅8⋅8⋅8⋅8⋅8⋅8. About as much multiplications needed for 8!: 1⋅2⋅3⋅4⋅5⋅6⋅7⋅8. However, we can take shortcuts! The result of the first multiplication x=8⋅8 can be reused: x⋅x⋅x⋅x, and then again with y=x⋅x we can rewrite it as y⋅y. So we're done after just 3 multiplications. In other words 8⁸ can be expressed as ((8²)²)² which is easier to deal with and the same approach can be used for any number.

@TheFlynCow 2 года назад

Yup. Knuth Volume 2 has a section on it.

@hebl47 2 года назад

With clever use of logarithms you can translate any N^N to 10^M (M = N*log N). It only takes one step (and a calculator or a taylor series to compute the logarithm). As your N increases, so does the number of steps to calculate N!, whereas N^N always takes the same amount of steps if you translate it as I said above. Of course this only works if you're not after perfect precision.

@jqerty 2 года назад

Great question! I had to think about it. One solution I found is that N^N = e^(N* log(N)), which does not require N stepts.

@eu4um 2 года назад

This is such a cool concept and seems almost counterintuitive.

@MrMas9 2 года назад

Would love to see more from this guy!

@colep9247 2 года назад

Those who know Stirlings Formula: 🤓 Those who know the Gamma Function: 😎

@SixOhhGeeTeeOhh 2 года назад

if you say numbers louder, they get bigger

@ThatGuyWithDiabetes 2 года назад

I like the clarity in the professor's speech - The words flow quite naturally. Also, it's getting hard to wrap my head around the limit ratio - The digits of difference increase between the exact and approx. but they tend to "become one" as N goes to inf.

@jindmen 2 года назад

In a fraction doesn't matter how many numbers there are (as long as there are same number of them up and down), the thing that matters is the first few

@Galakyllz 2 года назад

I love how both e and tau show up in this equation.

@stephenandrusyszyn3444 2 года назад

So, when you take the factorial of infinity using the approximation, you get the exact value, but compared to the actual value the error is infinite. Gotta love math!

@looney1023 2 года назад

Well you can't the factorial of infinity ;D

@JohnSmith-nx7zj 2 года назад

It’s not really that surprising a concept. It’s like comparing the functions y = x^2 + x and y = x^2. The gap between them grows without bound but their ratio clearly approaches 1.

@gustavoexel5569 2 года назад

Well, we don't have to analyze the extreme case (infinity). As N grows larger and larger the value of the error also grows, but that makes sense. Even though the ratio between the exact value and the approximation approaches 1, since it's not exactly one, that tiny deviation from one multiplied by a REALLY REALLY LARGE number is going to "blow up" to a really large number.

@relaxd0ntd01t 2 года назад

One of my burning questions from this is: Is one (between the true factorial and the aproximatino) strictly larger than the other? or is one sometimes bigger, and sometimes smaller? My current assumption is that N! will be always larger than the approximation

@NoActuallyGo-KCUF-Yourself 2 года назад

I was thinking that too. N! is usually bigger than anything.

@mitchellsteindler 2 года назад

It's always larger and increasingly so

@effuah 2 года назад

N! is always bigger by a factor of roughly 1+1/(12N)

@theastronomicalmouse1828 2 года назад

@@effuah Would that therefore not be part of the approximation equation, so as to make it more accurate?

@effuah 2 года назад

@@theastronomicalmouse1828 you could make that part of the approximation, there is an infinite number of extra terms to make it exact. The idea of the Stirling formula like presented is to have it simple, but close enough. More terms means more hassle. The last time I used the formula it was for N≥8, so already around 1-2% error and I knew there were other, larger errors and I only needed the order of magnitude of the factorial, so it was ok. In the most common use case of Thermodynamics the N is in the order of trillions and more. There it just doesn't matter to have more accuracy since you use assumptions about the world that don't hold to that high accuracy.

@Adam-kx8kg 2 года назад

Really enjoyed this video, looking forward to more form this prof

@nunixnunix04 2 года назад

this professor is great at explaining! please make more videos with him

@georgeaallan 2 года назад

I like this guy

@patricktho6546 2 года назад

3:05 why? roots etc are also recursive, infinite to be exact, so why can this be better than a finite product?

@MAP233224 2 года назад

because you can also quickly approximate them very accurately

@justsomeguy5628 2 года назад

I guess if this were done by a computer, you can approximate the root up to the possible level of precision, or a ridiculously high precision, and it won't take very long. But this may be harder to implement, and the added efficiency may even go away given different computer specs

@yogeshwagh2849 2 года назад

I'd say it's somehow related to time/space complexity of the algorithm.. for traditional multiplication method it'd take more time just to compute 100! Because you're need to multiply each integer through a loop.. but in case of calculating approximation it's just few multiplications the computer needs to deal with (multiplication between n^n,exp(-n) etc..) .. in other words lesser time complexity

@SailSmBi 2 года назад

I had the same thought. The first term is n^n which seems like it would require multiplying n digits together which is the same complexity as n!

@comma_thingy 2 года назад

@@SailSmBi You can write n in its base 2 form, say 100110, then n^n is the same as (n^2)(n^4)(n^32), meaning you only have to calculate n^ powers of two, which can be done via repeated squaring (up to log_2(n) times), then multiplying these terms together (another log_2(n) operations). Whether this is done in practice I'm not sure however

@felixmerz6229 2 года назад

What a great educator.

@joshyman221 2 года назад

For anyone wondering, the reason it’s easier to work with stirrings approximation is immediate if you take the logarithm of both sides in which case: log(n!)=nlog(n)-n+1/2log(2pi*n). You can then take the right hand side and exponential it (base e) which is much nicer to compute!

@Rob9 2 года назад

I was wondering why N^N was easier to compute than N! ... is this why?

@joshyman221 2 года назад

@@Rob9 yep! Infact it’s often the case especially in physics to work with log(n!) rather than n! (Due to how entropy is defined)

@sebastienverdier 2 года назад

"The approximation captures almost 5 digits" 4 : "Am I a joke to you?"

@rhoddryice5412 2 года назад

4 is almost 5. =)

@Hoxle-87 2 года назад

Another question could had been “are there efforts to find a better approximation?” Or “what’s keeping us from finding a better approximation?”

@harmidis 2 года назад

Great teacher, therefor great professor. More videos with Ken McLaughlin please. Thanks!

@jwebes 2 года назад

Oh man I remember this exact topic from a physics exam in university. I think we had to prove that the limit does go 1 having never seen the equation before in the lectures.

@compechdev 2 года назад

Haven't watched the video yet but 100! is (much) bigger than googol

@kennethluo4934 2 года назад

i haven't watched it yet either but i think they might be closer than you're implying, since we know 100! will be smaller than 100^100, which is (10^2)^100 or 10^200, a googol being 10^100, so 100^100 is a googol squared, and we know 100! is much less than 100^100 and by extension around the same as a googol edit: nevermind it has been brought to my attention by a calculator that 100! is around 10^157 so much smaller than a googol

@compechdev 2 года назад

@@kennethluo4934 that is 57 digits bigger than googol, so it's not much smaller

@forcelifeforce 2 года назад

@@compechdev *Wrong!* That is that many different magnitudes away from the other number! So, either correct your post, or delete it.

@compechdev 2 года назад

@@forcelifeforce Googol = 10^100 = 1 with 100 zeros after it. According to the other reply, 100! = 10^157 = 1 with 157 zeros after it.

@Phroggster 2 года назад

Not going to lie, I laughed every time he said 2π, as τ is such a better constant. Still, I appreciate knowing this approximation, thanks Numberphile!

@soorian6493 2 года назад

I feel like if he felt the need to explain what a factorial was to the audience, saying Tau without explanation to that same audience wouldn't be wise.

@TheNoerdy 2 года назад

This man is a treasure

@danielfranco2255 2 года назад

Damn his voice is so clear and eloquent, with that voice that guy could convince anybody of anything.

@pafnutiytheartist 2 года назад

The approximation is actually faster to compute only if you are dealing with logs of the number. If you do N^N in normal integers you need to multiply N numbers - same as N!

@Vangeli100 2 года назад

Mind blowing !

@DeGuerre 2 года назад

Another place this turns up is in statistics and probability when you're in the "long tail" region. There are situations like in genome-wide association studies where you need to calculate probabilities from a binomial distribution, which means you need to calculate "n choose k", but n might be several billion. Because the numbers involved are so extreme, we often work work in logarithm space, so instead of n!/(k! (n-k)) p^k (1-p)^(n-k), you compute the logarithm of this, which is log(n!) - log(k!) - log((n-k)!) + k log p + (n-k) log (1-p). All of those log-factorials are easily estimated with Stirling's approximation.

@LookToWindward 2 года назад

Definitely need a Numberphile2 video on this showing the derivation

@Yora21 2 года назад

Reminds me of the Fermi Approximation: Don't worry about exact numbers, just round every value of your equation to 10, 100, 1000, and so on to get a basic ballpark estimate for what scale your result will be.

@sillygooseguy Месяц назад

this is the best approximation of the number 1 that ive ever seen

@sinu7582 2 года назад

This is just amazing ☺️

@denisdaly1708 2 года назад

Fascinating

@cubicinfinity2 2 года назад

While I could have understood this all with just a few sentences (already knowing most of the material), it was great how he took the time to explain everything clearly. I also get what he's saying about the integral, even though that wasn't what he wanted to get into a lot: Factorial is a discrete thing, but that's the same thing you do in calculus: Take something continuous and turn it into something discrete so you can figure out what the continuous function is. So in this case, N! is already discretized and we're just using some calculus to figure out what that imaginary continuous function is.

@ricardoabh3242 2 года назад

The engineering function! Love it

@michaelmcnally1242 2 года назад

When I was an undergrad, maybe 1979, we wrote a program to compute 100! explicitly. The program involved a multiplication algorithm that operated on a list of one-digit numbers. It had to be written such that the work-in-progress was saved periodically, because we only had permissions sufficient to run a single program for a limited amount of time on the campus CDC 6600. It took the better part of a day, and of course we were so worn out after doing it that we did not do any sort of correctness check, but the resulting number (printed on a lot of greenbar paper) certainly had a lot of zeros at the end, which is what you'd expect.

@conrad5342 2 года назад

Thank you, I was not aware of that limit paradox.

@romain.guillaume 2 года назад

For those who wonder why it is quicker to compute the approximation, it is because for power calculation we can use fast exponentiation. Basically you write your exponent in binary and compute recursively the powers of the form x^(2^n) using the fact that 2^(2^(n+1)) = (2^(2^n))^2 Then you just have to multiply the results corresponding to your binary exponent. This way, you effectively compute the n^n and e^-n part. The computation of a square root is also fast thanks to fast converging series which requires an almost fix number of operations for the same precision

@Pepso8P 2 года назад

This is exactly the comment I was looking for, thanks! It didn't make sense to me as the approximation clearly requires more calculations than the factorial does, not to mention the size of the N to the power of N is bigger. After reading your comment I realized that what you said is exactly what I learned in school, it just didn't cross my mind.

@romain.guillaume 2 года назад

@@Pepso8P my pleasure ^^

@berndbeispielmensch 2 года назад

This is really interesting. I would love to see a video about why that approximation is so much easier to computer. Maybe that would suitable for the computerphile channel.

@user-hh2bz9ev4p 2 года назад

Another famous approximation which has ratio goes to 1 but difference goes to infinity is classical formula of PNT, prime number theorem where number of primes less than or equal to N is approximately N/log(N) (when base of log is e)

@berndeckenfels 2 года назад

Should be mentioned that N to the power of N also has N multiplications, but can be optimized as you can use divide and conquer since the factors are (unlike factorials) constant