7 ms·
Ramanujan Factorial Approximation (2012)
- mjcohen 4y agoI added this comment there: You can remove the overflow problems by modifying the code so that it computes ln(x!) as lnfact = .5ln(math.pi)+x(ln(x)-1) lnfact += ln(((8x + 4)x + 1)*x + 1/30.)/6.
- waynecochran 4y agoNice. The plot indicates that using ln should flatten things out. Helps avoid the (x/e)**x expression which is problematic.
- adgjlsfhk1 4y agothe way you actually are supposed to implement that is x*x exp(-x). Otherwise you will have bad accuracy for larger numbers.
- prox 4y agoToo afraid to ask : what’s a factorial approximation and why do we need it?
- czzr 4y agoDo you know what a factorial is? 3 factorial is written as 3! and is defined as 3! = 3x2x1. So three factorial equals 6. That’s easy. What about 100! Or 124! Obviously you could calculate that by multiplying all the numbers but that’s slow. A quicker way is to use Ramanujan’s formula which will give you an answer with much less calculation. The catch is that the answer may not be exactly correct, just a very good approximation. For many applications this is not an issue, and a faster calculation is more useful than a slightly more accurate answer.
- prox 4y agoCool! Now I get it!
- personjerry 4y agoHow did he come up with it?
- deleted 4y ago[deleted]
- version_five 4y agoI don't know, other than he was very smart. But a potential way that the article hints at is that the factorial is related to the gamma function which I believe is the solution to a differential equation... and so there may be some insight to be had in looking at the relevant differential equation and trying to approximate its solution. Edit after googling: the gamma function not the solution to a differential equation, in fact there is a proof that it cant be [*] but it's formulated as an integral, whose approximation could lead to odd looking equations like the one in the article https://en.m.wikipedia.org/wiki/H%C3%B6lder%27s_theorem https://en.m.wikipedia.org/wiki/H%C3%B6lder%27s_theorem
- rq1 4y agoAlgebraic differential equation*
- vouaobrasil 4y agoRamanujan had a miraculous facility for just seeing expressions without much formal derivation. He worked with the British mathematician G.H. Hardy and it is clear from Hardy's description and Ramanujan's biography that Ramanujan did not have much insight into his own process or following clearly defined steps. He must have thus had a very natural insight into number theory that was mostly instinctual.
- steppi 4y agoEarly the following year, K. S. Srinivasan, a student at Madras Christian College who'd known Ramanujan back in Kumbakonam, dropped by to see him at Summer House. "Ramanujan," he said, "they call you a genius." Hardly a genius, replied Ramanujan, "Look at my elbow. That will tell you the story." It was rough, dirty, and black. Working from his large slate, he found the quick flip between writing hand and erasing elbow a lot faster, when he was caught up in the throes of his work, than reaching for a rag. "My elbow is making a genius of me," he said. Why, Srinivasan asked, didn't he just use paper? Can't afford it, replied Ramanujan. He was getting money from Ramachandra Rao. But that only went so far. Paper? He'd need four reams of it a month. From Robert Kanigel's The Man Who Knew Infinity [0]. My understanding is that Ramanujan did most of his derivations on slate and tended to preserve only the results on paper. His insight was tremendous, but it was backed up by a tremendous amount of elbow work. [0] https://en.wikipedia.org/wiki/The_Man_Who_Knew_Infinity_(book) https://en.wikipedia.org/wiki/The_Man_Who_Knew_Infinity_(boo...
- jihadjihad 4y agoI'm a simple man; I see a post for John Cook, I upvote! One of the several interesting things about Stirling's approximation is that De Moivre was able to use a less generalized version of it to help prove the central limit theorem.
- huhtenberg 4y ago> I'm a simple man; I see a post for John Cook, I upvote! Doubly so for anything Ramanujan.
- kccqzy 4y ago> The downside of this trick is that now, for example, ramanujan2(5) and ramanujan2(5.0) give different results. In some contexts, the improved accuracy may not be worth the inconsistency. Why not just use fact = math.floor(fact) instead of int()? I hate functions that randomly decides to return a different type too.
- lifthrasiir 4y agoTo be fair functions like `abs(x)` are expected to return int when x is int and float when x is float. Factorial acts same with respect to types so it is not that unreasonable. The real problem is that `fact` is not the actual factorial but its approximation (doubly so because it goes through float anyway). So all extra precision provided by bigint is useless.
- hgsgm 4y ago
- deleted 4y ago[deleted]
- vram22 4y agoA while back I got to know that there are many kind of factorials, and had written this fun blog post on the topic: Permutation facts: https://jugad2.blogspot.com/2016/10/by-vasudev-ram-nicomachus-theorem-3d.html https://jugad2.blogspot.com/2016/10/by-vasudev-ram-nicomachu... (The post URL does not match the post title, due to some error by me, which I forget. But the URL is the right one for the post.)
- ocfnash 4y agoWeirdly, I was just sent this same blog post a few days ago. I guess it’s doing the rounds. I’ll repeat what I said to my friend who sent it. Ramanujan was of course an extremely talented mathematician but IMHO, there is an unnecessary cult of mystery about him. In particular, there is no mystery as to where this formula comes from: it is obtained from applying a standard technique to a standard formula. Also, it is just one instance, I’ll call it the “k = 6” instance, of a family of such formulae and I’m near-certain the “k = 2” case was known before Ramanujan (on phone or would double check). In any case, the standard formula is just the series expansion for: n! / sqrt{2πn} (n/e)^n and the standard technique is to raise both sides of a series expansion to some power, k say, multiply out one side, and then take k-th roots again. In this case we just need to calculate: (1 + 1/12n + 1/288n^2 - 139/51840n^3 + O(1/n^4))^6 = 1 + 1/2n + 1/8n^2 + 1/240n^3 + O(1/n^4) After taking the 6th root again we multiply inside by 8n^3 (from the LHS) and you get Ramanujan’s formula.
- pfortuny 4y agoIn this case it looks a bit obvious: Stirling is to degree 1 in the square root, “Ramanujan”’s to degree 4. Nothing to see here.
- sanjayio 4y agoThis might be obvious with a modern mathematical education but keep in mind he was born in 1887 and died at the age of 32. Theorems are a little like magic tricks, they become very apparent once someone tells you the trick.
- marhee 4y agoWhat's the advantage of this approximation in python/code? I can see it being useful analytically, but what's the advantage in code? The formula has an ^n in it, so doesn't it have the same complexity as n! ?
- warinukraine 4y agoNo, because you don't compute n^n by multiplying n by n, n times. Your also don't compute a x b by summing b, a times, do you? You compute n^n the same way you compute a^n which is to say that a^n = e^(n x log(a))
- jasamer 4y agoThere are efficient ways to compute x^n. Eg. you want to compute x^8. Instead of multiplying x eight times by itself, you can do ((x^2)^2)^2, which is just three multiplications. To be fair, I’m not sure whether similar optimizations exist for computing the factorial, but I don’t think so.
- adgjlsfhk1 4y agothere aren't similar tricks for factorials.