Ramanujan Factorial Approximation (2012)(johndcook.com)
johndcook.com
Ramanujan Factorial Approximation (2012)
https://www.johndcook.com/blog/2012/09/25/ramanujans-factorial-approximation/
38 comments
This 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.
In 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.
I 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.
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.
Too afraid to ask : what’s a factorial approximation and why do we need it?
Do 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.
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.
Cool! Now I get it!
Nice. The plot indicates that using ln should flatten things out.
Helps avoid the (x/e)**x expression which is problematic.
the way you actually are supposed to implement that is x*x exp(-x). Otherwise you will have bad accuracy for larger numbers.
How did he come up with it?
[deleted]
I 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
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
Algebraic differential equation*
Ramanujan 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.
I think that's part of the myth of Ramanujan, that he could just see these things and pull them seemingly out of thin air, and in fact Ramanujan himself has said that math comes to him in visions from a Hindu goddess, but a closer inspection demystifies a lot of this.
What's true is that Ramanujan spent an absolute significant amount of time working on math problems of all kinds, and the vast majority of his work was simply incorrect. In fact one thing Hardy appreciated and found most extraordinary about Ramanujan was not what Ramanujan managed to get right, but the ways in which he managed to get things wrong since that kind of revealed some unique insight into how Ramanujan went about solving problems.
Of course that is never what is showcased about him, instead we get infamous stories such as how Ramanujan seemingly figured out in a matter of seconds that the number 1729 is the smallest number expressible as the sum of two cubes in two different ways. What the story leaves out is that Ramanujan did not just figure this out on the fly but had been working on trying to prove Fermat's Last Theorem for years and as part of that work he had come across the number 1729 since it's related to elliptic curves (the basis of which would eventually lead to a proof of Fermat's Last Theorem).
At any rate, none of this is intended to diminish Ramanujan in any way, on the contrary my hope is to celebrate the very hard work and dedication that Ramanujan put towards mathematics. He is not someone who just divined correct solutions to complex math problems out of thin air but instead he spent countless hours for decades on end devoted to his passion and persevered through much trial and error. The only things we see of his work are the things he got right, and to that end it may seem like his accomplishments are magic; the truth is that they were anything but.
What's true is that Ramanujan spent an absolute significant amount of time working on math problems of all kinds, and the vast majority of his work was simply incorrect. In fact one thing Hardy appreciated and found most extraordinary about Ramanujan was not what Ramanujan managed to get right, but the ways in which he managed to get things wrong since that kind of revealed some unique insight into how Ramanujan went about solving problems.
Of course that is never what is showcased about him, instead we get infamous stories such as how Ramanujan seemingly figured out in a matter of seconds that the number 1729 is the smallest number expressible as the sum of two cubes in two different ways. What the story leaves out is that Ramanujan did not just figure this out on the fly but had been working on trying to prove Fermat's Last Theorem for years and as part of that work he had come across the number 1729 since it's related to elliptic curves (the basis of which would eventually lead to a proof of Fermat's Last Theorem).
At any rate, none of this is intended to diminish Ramanujan in any way, on the contrary my hope is to celebrate the very hard work and dedication that Ramanujan put towards mathematics. He is not someone who just divined correct solutions to complex math problems out of thin air but instead he spent countless hours for decades on end devoted to his passion and persevered through much trial and error. The only things we see of his work are the things he got right, and to that end it may seem like his accomplishments are magic; the truth is that they were anything but.
> the vast majority of his work was simply incorrect
I had heard this before, and I believed it. But I got convinced that that's not true by the likes of George E. Andrews and Ken Ono. They say that most of his work is correct. All of this is still hearsay as far as I'm concerned. I'm not qualified to verify his math.
I had heard this before, and I believed it. But I got convinced that that's not true by the likes of George E. Andrews and Ken Ono. They say that most of his work is correct. All of this is still hearsay as far as I'm concerned. I'm not qualified to verify his math.
> had been working on trying to prove Fermat's Last Theorem for years and as part of that work he had come across the number 1729 since it's related to elliptic curves (the basis of which would eventually lead to a proof of Fermat's Last Theorem).
I thought it wasn't that 1729 was related to elliptic curves and the proof, but that it was a "near-miss" candidate in a search for finding a counterexample in order to disprove the theorem. And 9³ + 10³ = 12³ + 1 = 1729 was the smallest of many of these near-miss candidates that Ramanujan had found.
Was that not right?
I thought it wasn't that 1729 was related to elliptic curves and the proof, but that it was a "near-miss" candidate in a search for finding a counterexample in order to disprove the theorem. And 9³ + 10³ = 12³ + 1 = 1729 was the smallest of many of these near-miss candidates that Ramanujan had found.
Was that not right?
Thank you for one most rational explanation I have ever seen about Ramanujan's work.
> the vast majority of his work was simply incorrect
My impression is just opposite. Do you have any reference proving that vast majority of his work was simply incorrect.
My impression is just opposite. Do you have any reference proving that vast majority of his work was simply incorrect.
It seems the consensus of the Mathematical Community, is that he did very few.
"What did Ramanujan get wrong?" - https://mathoverflow.net/questions/288410/what-did-ramanujan...
"An Overview of Ramanujan's Notebooks" - https://faculty.math.illinois.edu/~berndt/articles/aachen.pd...
"What did Ramanujan get wrong?" - https://mathoverflow.net/questions/288410/what-did-ramanujan...
"An Overview of Ramanujan's Notebooks" - https://faculty.math.illinois.edu/~berndt/articles/aachen.pd...
Early 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_(boo...
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_(boo...
This is one of the big tragedies of Ramanujan. We have all these miraculous mathematics from him but we don't really know how he got there. A lot of this stuff we already knew, but he seems to have found it all out independently. No idea how though, all because he was too poor to buy paper. Jeez.
I had no idea he did all his work on a big slate. His working memory must have been astoundingly good.
Maybe thats what made him what he was - working in an ephemeral medium forcing his working memory to adapt in ways that are conducive to doing mathematics?
For a comparison on the other end our spatial memory structures in the brain have changed since widespread use of gps/mapping apps, apparently.
For a comparison on the other end our spatial memory structures in the brain have changed since widespread use of gps/mapping apps, apparently.
Short term memory is very important for problem solving. Euler continued to work and publish mathematics after becoming blind
[deleted]
There was a paper a few years ago in the American Mathematical Monthly ( sorry... can't remember the author, I think it was a Russian mathematician ) that gave some interesting heuristics for why this form is natural to consider, where the 1/30 comes from ( and considerations of a couple of alternatives to the "30" ), and the kind of intuition/thinking that Ramanujan may have used. When you only see the final form of the equation like this, it looks very mysterious and impossible that someone could find it ( and to be fair, there are other results from Ramanujan that are definitely in that class! ). Probably a google search could find the paper, it was delightful to read.
> 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
I hate functions that randomly decides to return a different type too.
Why not just use
fact = math.floor(fact)
I hate functions that randomly decides to return a different type too.
To 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.
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.
[deleted]
I'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.
> I'm a simple man; I see a post for John Cook, I upvote!
Doubly so for anything Ramanujan.
Doubly so for anything Ramanujan.
What'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! ?
No, 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))
You compute n^n the same way you compute a^n which is to say that a^n = e^(n x log(a))
There 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.
To be fair, I’m not sure whether similar optimizations exist for computing the factorial, but I don’t think so.
there aren't similar tricks for factorials.
A 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-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.)
Permutation facts:
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.)
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.