Big Factorials - Numberphile

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.colos...
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/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoun...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9

[@_thank_you_]

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]

He has very neat handwriting too

[@heartache5742]

i can't listen to this accent

[@wearwolf2500]

@@heartache5742 He sounds very American to me.

[@ingvarhallstrom2306]

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

[@ingvarhallstrom2306]

I've tried to search for a biography, it seems he have worked in Colorado and Arizona. But he studied mathematics at NYU in the early 90's so it supports my New York connection.

[@younesabid5481]

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

[@jorgesaxon3781]

That not exactly right

[@HasekuraIsuna]

@@jorgesaxon3781 That's exactly right!

[@ptousig]

It's kind of a "Parker Factorial".

[@mrstutoring]

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

[@theastronomicalmouse1828]

@Kurniawan Adhi r/wooooosh

[@jeojavi]

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

[@patback9708]

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

[@MichaelPiz]

Perfection is, properly, an engineering term.

[@Antiphar]

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

[@qugart.]

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

[@MichaelPiz]

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

So basically off by e..

[@jan_kulawa]

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]

Brazil factorial? impressive

[@fernandovalner]

salve

[@fonkbadonk5370]

@@Nickelodeon81 Must have a brazillion digits!

[@daniell.garcia1748]

Graaande

[@bryanchandler3486]

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

[@Dysiode]

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

[@TheWaterMiners]

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]

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

[@QuantumHistorian]

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

@@alexcubed4270 well it's just approaching 1

[@alexcubed4270]

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

[@jindmen]

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

[@PeterGaunt]

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

[@PhilipSmolen]

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]

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]

God's algorithm

[@jonrutherford6852]

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]

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]

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

[@TheofilosMouratidis]

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

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

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

[@aperson2703]

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]

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

[@yourguard4]

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

[@sharpnova2]

@@yourguard4 a Russian bot, planted to sew dissent

[@Mayur7Garg]

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]

@@Mayur7Garg This but unironically.

[@delecti]

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]

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

[@Peterwhy]

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

[@PedroContipelli2]

@@Peterwhy This is correct

[@joelkuhn9880]

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]

@@joelkuhn9880 Or use logarithms.

[@markday3145]

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

[@TateFM]

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.

[@jaerik99]

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

[@PnlBtr]

Strongly agree, Any topic.

[@cliftonchurch6039]

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

[@samstarlight160]

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

[@cariboubearmalachy1174]

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

[@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!

[@Kaepsele337]

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]

Avocado's constant is Singingbanana's favourite number!

[@mentox6592]

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

[@letsgocamping88]

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

[@Eriochrom]

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

[@gsurfer04]

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.

[@JustcallmeJayrot]

More Prof. McLaughlin! He's terrific!

[@codediporpal]

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!

[@jacemandt]

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.

[@jordanrobberecht7003]

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

[@CartoType]

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

[@abhaysharma2261]

This is such a classic numberphile video!

[@timseguine2]

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]

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.

[@Kippster29]

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

[@sillygooseguy]

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

[@martinepstein9826]

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.

[@brian-bed]

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

[@jared_bowden]

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!!"

[@phasm42]

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

[@stayawakestudios]

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

[@seanmcdermott4634]

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

[@johnchessant3012]

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.

[@ez_is_bloo]

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

[@SixOhhGeeTeeOhh]

if you say numbers louder, they get bigger

[@asparkdeity8717]

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!

[@Taylor-rx4yb]

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

[@jamescollier3]

cool

[@christopherbonis]

Finally, a Numberphile video that I understood completely.

[@Terratops474]

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

[@katakana1]

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

[@jentlejeniuskat]

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.

[@bur2000]

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.

[@ffggddss]

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

[@rhodexa]

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

[@DingDimlewitz]

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]

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]

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

[@PopeLando]

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]

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

[@IllusoryMaze]

The ultimate anti-prime.

[@inefffable]

∞! The All-Time Greatest Anti-Prime

[@nickbeaumont1637]

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]

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

[@joshyman221]

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]

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

[@joshyman221]

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

[@unvergebeneid]

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! 😄

[@crowreligion]

Well, the answer involved exponents, and e is related to exponential functions.

[@danielfranco2255]

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

[@aminzahedim.7548]

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]

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

[@MrMas9]

Would love to see more from this guy!

[@asatzhh]

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]

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

[@matthiasoc7141]

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!

[@kitty13kitty]

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]

I noticed that bunch of zeros too :D

[@kitty13kitty]

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

[@Kaesekuchen002]

Great voice to listen to and nice explanations!

[@markphc99]

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]

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

[@nikolaimikuszeit3204]

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

[@TheReubenthegreat]

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]

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]

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

[@howdyimflowey4341]

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

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

[@Galakyllz]

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

[@YossiSirote]

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

[@joemiller947]

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

[@katakana1]

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

[@gabor6259]

Now where does _that_ come from?

[@lelouch1722]

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

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

[@markbrown2450]

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

[@TheSmegPod]

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]

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

[@ThatGuyWithDiabetes]

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]

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

[@aseq2]

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

[@Hidegety1]

That was very refreshing episode

[@AmnonSadeh]

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]

Yup. Knuth Volume 2 has a section on it.

[@hebl47]

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]

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.

[@jwebes]

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.

[@colep9247]

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

[@romain.guillaume]

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]

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]

@@Pepso8P my pleasure ^^

[@relaxd0ntd01t]

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]

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

[@mitchellsteindler]

It's always larger and increasingly so

[@effuah]

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

[@theastronomicalmouse1828]

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

[@effuah]

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

[@greensombrero3641]

Sterling's approximation wins the gold medal.

[@emmata98]

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

[@MAP233224]

because you can also quickly approximate them very accurately

[@justsomeguy5628]

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]

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]

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]

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

[@thecakeredux]

What a great educator.

[@sebastienverdier]

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

[@rhoddryice5412]

4 is almost 5. =)

[@MinecraftMasterNo1]

"You don't get it exactly right" "That's exactly right" The duality of man

[@stephenandrusyszyn3444]

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]

Well you can't the factorial of infinity ;D

[@JohnSmith-nx7zj]

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]

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.

[@nunixnunix04]

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

[@georgeaallan]

I like this guy

[@clemdawn2037]

"..So you don't get it exactly right." "That's exactly right."

[@Hoxle-87]

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

[@kaberigomes2117]

What's interesting is, such approximation required people to discover e, pie, root and all such discoveries in maths. 🤩 Maths is so interesting.

[@Phroggster]

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]

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.

[@mienzillaz]

- you don't get it exactly right. - that's exactly right Amazing

[@compechdev]

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

[@kennethluo4934]

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]

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

[@forcelifeforce]

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

[@compechdev]

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

[@TheNoerdy]

This man is a treasure

[@rickseiden1]

Matt Parker would love this video! He loves when pi pops out unexpectedly.

[@justinnehls9191]

This guy has taught me more in 10 min than 2months in a prevcalculus class. The way he explained it was dummy proof

[@LookToWindward]

Definitely need a Numberphile2 video on this showing the derivation

[@cubicinfinity2]

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.

[@JonSebastianF]

(3:15) *Brady:* _Okay, so it’s a bit of a hack here, it’s a bit of a short-cut, but you don’t get it exactly right?_ *Ken:* _That’s exactly right!_

[@pafnutiytheartist]

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!

[@harmidis]

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

[@DeGuerre]

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.

[@ariellima5929]

“So it’s a bit of a shortcut, but you don’t get it exactly right” “That’s exactly right”

[@eu4um]

This is such a cool concept and seems almost counterintuitive.

[@michaelmcnally1242]

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.

[@김승태-k2b]

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)