Previous submissions:
https://news.ycombinator.com/item?id=4796586
https://news.ycombinator.com/item?id=4915328
Also:
Refuting “The Mathematical Hacker”: https://news.ycombinator.com/item?id=4921953
https://news.ycombinator.com/item?id=4796586
https://news.ycombinator.com/item?id=4915328
Also:
Refuting “The Mathematical Hacker”: https://news.ycombinator.com/item?id=4921953
I look forward to any additional comments and contributions people may choose to make here.
It makes, in my opinion, a much more lucid argument than this article as to why a firm background in math, particularly theoretical math, is important for programmers of all sorts. It's definitely something I'd read if you're thinking about the role of math in computer science and programming as fields.
The article is here: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EW...
There have been numerous submissions of it to HN, of varying popularity. The ones I could find with the most comments are: http://news.ycombinator.com/item?id=6838434 (three weeks ago) http://news.ycombinator.com/item?id=3553983 (one year ago) http://news.ycombinator.com/item?id=1666445 (three years ago)
(Part of my curiosity on your take comes from the fact that you commented on a similarly themed essay I wrote some time back.)
> >>> int(math.exp(math.lgamma(41)))
> 815915283247882431423526575245034982027017846784L
> [...]
> Prelude> fac 40
> 815915283247897734345611269596115894272000000000
Another problem is that lgamma runs in constant time but it’s accurate only in a finite range. To extend the range the polynomial must have more terms, so the “accurate” version doesn’t run in constant time. And for enough precision, you must use the “long” version of the floating point numbers. The complete analysis is complex and I don’t have enough time to do it.
The recursive functions runs in linear time only for small numbers. It uses only integer arithmetic that is faster. But if the number are big enough you must use “long” integers, and the time is probably quadratic. So it’s not clear which version is better, neither for small numbers nor for big numbers and asymptotic behavior.
[1]: http://www.johndcook.com/blog/2012/07/14/log-gamma-differenc...
[2]: http://www.johndcook.com/blog/2010/08/16/how-to-compute-log-...
[3]: http://www.johndcook.com/blog/2008/04/24/how-to-calculate-bi...
In general, it's application-dependent. But often, in applications, the factorial enters multiplicatively, and they are in products with other stuff; the whole thing can easily underflow or overflow.
So what you often really want is the log of the factorial. (If someone gave you the exact integer factorial for free, the first thing you'd do is take its log.) That's why they implemented lgamma(). The error guarantees it gives are in the log domain, which is (often, not always) what you want, anyway.