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.

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

@hmpret

2 жыл бұрын

@@jorgesaxon3781 r/wooooosh

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

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

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

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!

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

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

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.

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

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

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?

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.

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

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

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.

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

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.

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

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.

More Prof. McLaughlin! He's terrific!

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

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

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

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.

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

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

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!

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

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

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

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

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.

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.

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!

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

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.

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

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.

This is such a classic numberphile video!

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

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

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

Great voice to listen to and nice explanations!

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?

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

@jamescollier3

2 жыл бұрын

cool

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!

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

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.

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.

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

That was very refreshing episode

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.

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.

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

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.

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

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

Would love to see more from this guy!

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

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.

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

This is such a cool concept and seems almost counterintuitive.

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

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.

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.

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

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)

I like this guy

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

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!

Fascinating

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

@rhoddryice5412

2 жыл бұрын

4 is almost 5. =)

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

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

Finally, a Numberphile video that I understood completely.

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.

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.

Mind blowing !

What a great educator.

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

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.

This man is a treasure

The engineering function! Love it

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.

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

This is just amazing ☺️

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

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.

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

Also you can multiply by (1+1/12n) for more accurate estimation or exp(1/12n).

Just a fun fact for those that handle very large factorial or gamma function (e.g. calculating the t-distribution for hypothesis testing), they use log-transformed version of Stirling approximation: ln(n!) ~ n ln(n) - n + ln(2*pi*n)/2, which is useful if you want to calculate something like (3000!)/(1500!) (the use of logarithm reduces the size of number that need to be handled)

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.

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)

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

I remember seeing this approximation in Statistical Physics, where this value of N is on the order of Avogadro's number, so 10^23. I've only seen it in the form: Log(N!) ~ N•Log(N) though.

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

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!

Very good video, very informative, excellent work, very proud of you. (:

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