5 ms·
To approximate 52! by hand, compute 54! and divide by 3000
- mrpopo 10y agoThe real value being : 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 that is, the approximation was about 80% of the real value. Half of the approximation was in Stirling's formula, and another half in approximating 2^50. Edit: nevermind. Stirling's formula is surprisingly accurate. https://www.google.co.uk/#safe=off&q=%2854%2Fe%29^54*sqrt%282*pi*54%29+%2F+53+%2F+54 https://www.google.co.uk/#safe=off&q=%2854%2Fe%29^54*sqrt%28...
- ColinWright 10y agoThere are two major sources of error. One is in using 2.7 as the value for e. That's wrong by about 0.677%, and then that's raised to the power of 54. That makes the result too big by about 44%. Then it approximates 2^10 by 10^3, which is wrong by 2.4%. That's raised to the power of 5, and the result is too small by 12.6%. So we divide by 1.44 and multiply by 1.28 to get the corrected answer of 7.8 * 10^67, which is extremely close to the actual answer of 8.066 * 10^67. Finally, I used sqrt(2.pi.54) as 18, whereas it's closer to 18.42, another 2.3%. We should then get 7.8125 * 18.42/18 which is about 7.99474. Nailed it. Those corrections can (mostly) also be done (or at least approximated) by hand - maybe I should write a follow-up.
- etendue 10y agoHow does the 2^10 to 10^3 approximation come about? All of the others made sense to me, but I couldn't figure that one out.
- ColinWright 10y agoCompare 1000 with 1024. As I say above, 2^10 is bigger than 10^3 by 2.4%. When we raise it to the power of 5 we are wrong by 12.6%.
- hyperpape 10y ago2 ^ 10 = 1024. That's one of those "shout it from the rooftops" approximations for programmers. I use it constantly.
- Sharlin 10y agoAnd this is why base-ten and base-two file and memory sizes are roughly equivalent (which is somewhat useful but also causes a lot of confusion): 2^10 bytes = 1 kiB ≈ 1 kB = 10^3 bytes 2^20 bytes = 1 MiB ≈ 1 MB = 10^6 bytes 2^30 bytes = 1 GiB ≈ 1 GB = 10^9 bytes 2^40 bytes = 1 TiB ≈ 1 TB = 10^12 bytes and so on. The relative error does grow as you move to larger and larger powers, though.
- deleted 10y ago[deleted]
- impendia 10y agoAs the other answers point out, it follows from explicit computation. Let me add that there's no particularly good a priori reason to expect this particular coincidence. It just happens.
- kijin 10y agoIs there a shorthand for calculating how much X% of error will become when raised to the power of Y? For relatively small powers, simple multiplication seems to give results that are close enough, e.g. 0.677% * 54 = 36.6%, and 2.4% * 5 = 12%. But this is obviously not going to work once you start raising numbers to even higher powers.
- ColinWright 10y agoShort answer: yes. Slightly longer answer ... For very small errors, multiplying by the power is right. You can see that because of the standard expansion: (1+e)^n ~ 1 + ne + n(n-1)e^2/2 + ... When e is small enough, e^2 is very small, so we can ignore everything that follows. When e is slightly larger we can use more terms in the expansion, and that works nicely. That happens in the post about the birthday problem, where an extra term is used from the expansion for log(n). So you don't get it for free, but it's not a lot of extra work. In the case of 1.024^5, which is in the post, we get: e=0.024 n=5 print n * e -> 0.12 So the first approximation of the error is 12% print n*e + n*(n-1)/2*e**2 -> 0.12575999999999998 So the extended approximation is 12.576%. We can compare that with the actual error: print (1+e)**5 -> 1.125899906842624 Pretty close. Even longer answer: Binomial Theorem.
- deleted 10y ago[deleted]
- psi-squared 10y agoSo, let's call the correct value of whatever 'A'. Then "Off by X%" really means that the number you used is (1 + X/100) * A. (note: if you underestimated you need to make X negative for this to work) When you raise that to the power Y, you get (1 + X/100)^Y * A^Y, when the correct result is just A^Y. So you get (1 + X/100)^Y times what you should've gotten. You can convert that back into a percentage directly if you want, but if X is small (ie, if the original value is "close enough"), you can use the binomial expansion [1] and just keep the first few terms. If you do that, you eventually end up with: Percentage the final result is out = Y * X + (1/200) * Y(Y-1) * X^2 + ... [1]: https://en.wikipedia.org/wiki/Binomial_theorem https://en.wikipedia.org/wiki/Binomial_theorem
- 10y ago
- danbruc 10y agoNo discussion of 52! is complete without [1]. A somewhat condensed version of one of the illustrations from the site. 52! is the number of different ways you can arrange a single deck of cards. Let's try to wrap our puny human brains around the magnitude of this number with a fun little theoretical exercise. Start a timer that will count down the number of seconds from 52! to 0. We're going to see how much fun we can have before the timer counts down all the way. Start by picking your favorite spot on the equator. You're going to walk around the world along the equator, but take a very leisurely pace of one step every billion years. Make sure to pack a deck of playing cards, so you can get in a few trillion hands of solitaire between steps. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. Continue until the ocean is empty. When it is, take one sheet of paper and place it flat on the ground. Now, fill the ocean back up and start the entire process all over again, adding a sheet of paper to the stack each time you’ve emptied the ocean. Do this until the stack of paper reaches from the Earth to the Sun. Take a glance at the timer, you will see that the three left-most digits haven’t even changed. You still have 8.063 × 10⁶⁷ more seconds to go. So, take the stack of papers down and do it all over again. One thousand times more. Unfortunately, that still won’t do it. There are still more than 5.385 × 10⁶⁷ seconds remaining. You’re just about a third of the way done. [1] http://czep.net/weblog/52cards.html http://czep.net/weblog/52cards.html
- iopq 10y agoPfft, it's much smaller than the number of atoms in the universe. Then again, after I read how to calculate Graham's number, I'm not impressed by much.
- sowbug 10y agoI once met a guy who said he could count anything instantly. I had to test his claim. "This is my ranch, and over there's my cattle. How many are there?" He looked over, paused for the briefest moment, and then said, "I see 742 cows." Astonished, I exclaimed, "That's exactly right! Mind sharing your secret?" He leaned in a bit and proudly explained. "It's simple, really. I count the number of legs and divide by four."
- rexreed 10y agoI don't get it - is counting the # of legs less work than counting the # of cows? It would seem to be 4x the work, or am I being dense?
- ColinWright 10y agoIt's a well-known "joke", and it clearly plays off the idea of this article wherein calculating 52! is, genuinely, done by calculating 54! then dividing by a correction factor.
- deleted 10y ago[deleted]
- a_c_s 10y agoThat's exactly the joke - that he's doing something that's 4x more work than just counting the cows directly.
- ipsin 10y agoI do wish my high school combinatorics had included Stirling's approximation. It allows great approximations for problems that are really asking for it. If there are 200 white and 200 black balls in an urn, there's no sense asking for some expected value as an exact rational number.
- bitwize 10y agoNext up on Square One TV: Here 's a quick way to find the square root of four. √4 = √(2•2) = √2•√2. So just find the square root of 2, multiply it by itself and you have the square root of 4!
- ecesena 10y agoThe beauty about maths are properties. What you said is perfect - now note that sqrt is the inverse of sqr, so you can "cancel" them, and you got the result: 2.
- iheredia 10y agoAnd if you dont know how to compute 54!, just approximate it by computing 52! * 3000
- gweinberg 10y agoAt the risk of appearing humorless, he's not calculating 54! and dividing by 3000, he's approximating 54! and dividing by 3000.
- ecesena 10y agoAnd more precisely he's dividing by 2880, which is btw closer to 54*53 than 3000.
- vinchuco 10y agoI was tempted to just plug in 52 into Stirling's formula n!~~((n/e)^n)sqrt(2pi*n) but the result isn't as 'nice'. What makes 54 special and how would you know to try it instead? What makes a number computationally 'nice' for humans? Is it just less computation steps under relaxed precision? Is there a collection of heuristics for approximation?(This might be just Numerical Analysis) Or better yet, ome sort of approximate calculator software that gives error bounds? I've heard this book is good (from HN) but haven't gotten to reading it: Street-fighting mathematics. https://mitpress.mit.edu/sites/default/files/titles/free_download/9780262514293_Street_Fighting_Mathematics.pdf https://mitpress.mit.edu/sites/default/files/titles/free_dow...
- ColinWright 10y agoIt's nice because 2.7 is close to e, and 2.7 is a nice factor of 54, which is close to 52. It's worth starting from the fact that e^3 ~ 20 and see if you can make that work. I'd suggest calculating 50! using e^3 ~ 20 (somehow!) - that's the next version I'll be doing. It's an interesting exercise.
- nayuki 10y agoThis is a fantastic example of a back-of-the-envelope calculation!
- justsaysmthng 10y agoThere's an even easier way. Start calculator on your iPhone, rotate it to landscape to switch to scientific calculator, type 5, 2, x! and observe result: 8.06 * 10^67 Yeah, really ingenious, I know... but still.. Just a couple of hours ago, we were playing this math game with my 6-year old daughter and it involved making mental additions and substations to reach a certain number ... After some time she kind of started liquefying in the chair, becoming frustrated and bored with the effort of the mental math... But then I offered her the calculator and she immediately loved it - she could outsource the hard computations to the device and just enjoy the "game" part of the game. At first I went - "oh no, she won't learn how to do arithmetic with her head if she uses the calculator - that's terrible !", but then I noticed that she actually did the easy parts in her head and only used the calculator for 'hard' subtractions. In the end, the fact that we went on and enjoyed the game with the help of the calculator, generated a lot more mental math than if we'd have stopped playing the game. Anyway, not sure what my point is - I guess that sometimes a calculator is even more convenient than clever math tricks - unless your game is the math tricks themselves...
- ColinWright 10y agoThe point here is that these sorts of "math tricks" are the next stage equivalent of what you've called "the easy parts." After a while you no longer have to stop to use the calculator, you can get into flow and get ahead with the stuff that really matters. It's simply the next step along a long road that not everyone travels. And by the way - I absolutely use the tools available - calculators, symbolic algebra packages, GeoGebra, and more. It's just that not having to stop as often is a huge plus.
- naveen99 10y agoInterestingly, there is a lot of approximation / asymptotic analysis in mathematical physics: http://m.youtube.com/watch?v=LYNOGk3ZjFM http://m.youtube.com/watch?v=LYNOGk3ZjFM