8 ms·
Get Billions of Correct Digits of Pi from a Wrong Formula (1999) [pdf]
- xamuel 8y agoThe formula involves a parameter c=10^10 and initially seems unbelievable because one's initial inclination is to assume that the 10^10 is particularly important, like it has to be that particular value in order for the formula to work. The "trick" is that higher values of c, like c=10^19, give even more accuracy. Obviously c=10^10 was chosen to optimize the formula's aesthetic beauty.
- madcaptenor 8y agoEven c = 2 works. > n = seq(-1000, 1000); #assume 1000 is big enough to be infinity > sum(exp(-n^2/2))^2 / 2 [1] 3.141593
- miduil 8y agoWhich programming language is that? Edit: Ah, it's "R".
- madcaptenor 8y agoYes, it's R. Not necessarily the ideal language for this but I had an RStudio window open.
- xyzzyz 8y agoSeems like the formula is simply a fine enough Riemann sum for calculating Gaussian integral int_-inf^inf e^(-x^2) dx = sqrt(pi). It makes it much less surprising, though the exact estimation of error is still quite ingenious and worth following.
- madcaptenor 8y agoThat "wrong formula" approximates pi by an integral: more precisely, exp(-x^2) integrated over the real line integrates to sqrt(pi). So the question is, in some sense, why is that such a good approximation? (My Fourier analysis is rusty, so I can't answer that question.)
- hammock 8y agohttps://en.wikipedia.org/wiki/Gaussian_integral https://en.wikipedia.org/wiki/Gaussian_integral
- madcaptenor 8y agoI'm familiar with the integral. But why is that sum a particularly good approximation to the integral? It seems better than one has a right to expect, although it's been a while since I did any numerical analysis.
- messe 8y agoRiemann sums. EDIT: The short answer is that it's a good approximation because e^(-n^2/c) drops off very vast as n approaches zero, meaning most of the contributions will come from small (on the order of sqrt(c)). Other than that, it's just a Riemann sum presented in an aesthetically pleasing manner.
- TimonKnigge 8y agoDo you mean 'approaches infinity'? Because at n=0 the expression is maximal :-) But the point is not to drop small terms at the extremes - it is still an infinite sum. The point is to approximate sections of the function by rectangles, and those rectangles are a bad approximation around 0 too.
- madcaptenor 8y agoReplying to my own comment. See (4.4) in the article and the discussion after it. The error in this approximation is like exp(-pi^2 c). (4.10) in the article translates this to that we should expect about 4.2c digits of accuracy, since log_10 exp(-pi^2) is about 4.2. This falls out of Poisson's summation formula, according to the OP. Generally I'd expect a numerical integration scheme to have an error like h^k for some constant k - for example for Riemann sums the error goes like h^2 and for Simpson's rule like h^5. h is the distance between the sampling points and so is analogous to 1/c. So this doesn't just follow from Riemann summation.
- Kenji 8y agoAm I the only one who is not surprised at all that this exists?
- messe 8y agoSpoiler alert: It's just a Riemann sum. This is like being surprised that (1+10^-100)^(10^100) approximates e astonishingly accurately.
- saagarjha 8y agoInterestingly, it seems that Wolfram|Alpha cannot figure out that there's a difference: http://www.wolframalpha.com/input/?i=N%5B((1%2B10%5E-100)%5E(10%5E100))%2Fe,+100%5D http://www.wolframalpha.com/input/?i=N%5B((1%2B10%5E-100)%5E...
- messe 8y agoIt's accurate to about a 100 digits, admittedly not quite as good as the expression in the OP, but it's the same principle. It's taking a fairly standard approximation, in the OP's case a Riemann sum, and inserting concrete but aesthetically pleasing numbers and acting as if something is incredible about it.
- saagarjha 8y agoYes, I get that. It seems like Wolfram|Alpha thinks 10^100 is too large of a number for it to have to care about, and is rounding it to infinity internally somewhere, hoping it doesn't change the final result. But, of course, it does matter in this case.
- kidme5 8y agoYou asked WA for the result with 100 digits of precision. It probably is 1 to that precision.
- saagarjha 8y agoI don't think it is. Try N[((1+10^-n)^(10^n))/e, n] for smaller values of n. At first it approaches e faster than the precision can "catch up", and up until around n=50 it will result in 1. But at 10^60 and above it will return 1.0000000…
- amelius 8y agoThere's still the hypothesis that any finite sequence of digits appears somewhere in pi.
- saagarjha 8y agoAh, the normality hypothesis. It seems like it should be true, but apparently this is something that's really hard to prove.
- mamon 8y agoI might be ignorant here, but wouldn't it suffice to prove that digits of Pi are random? Just check whether the distribution is uniform, the same way you would validate pseudorandom sequence generator for a programming language. Once you proved that Pi digits are random the normality hypotesis becomes trivial: as number of known Pi digits approaches infinity the probablity of any finite sequence to appear approaches 1.
- amelius 8y agoThat's sort of the whole point of normal numbers, and pi is not known to belong to this class. https://en.wikipedia.org/wiki/Normal_number https://en.wikipedia.org/wiki/Normal_number Quoting: > It is widely believed that the (computable) numbers √2, π, and e are normal, but a proof remains elusive.
- mikeash 8y agoYou can’t just check all the digits. There are an infinite number of them and you don’t know if they stop looking random at some point after you stop checking.
- arayh 8y agoHere's a brief look into the distribution of the digits of pi if you're interested: https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.html https://blogs.sas.com/content/iml/2015/03/12/digits-of-pi.ht... Summary: It's "seems" quite random, but has yet to proven as such.
- preparedzebra 8y agoFor any pattern, constant, irrational, etc, in math, there exists a set of formulas that models it up until n. It still is a cool little Riemann sum in this paper
- dajohnson89 8y agoWouldn't a better title be, "An accurate approximation of pi"? Not as clickbaity though....
- jack6e 8y ago> "Not as clickbaity though...." Not as accurate, either, given that the title of the paper is "Get Billions and Billions of Correct Digits of pi from a Wrong Formula," and it was published before "click-bait" was a thing.
- xamuel 8y agoIt's not clickbait. The article is genuinely interesting, and the title is quite relevant to why it's interesting.
- gesman 8y agoThis formula is worthy to be printed on T-shirt :)
- deleted 8y ago[deleted]
- man-and-laptop 8y agoSketch of an alternative proof, more DSP: Use the fact that the approximation in the paper is equal to the inner product of e^{-x^2} with a Dirac comb [1]. The amazing thing about the Gaussian function and the Dirac comb is that they're both preserved by the Fourier transform. So apply the Fourier transform to both of them, observe that the Fourier transform is unitary (essentially a rotation), and therefore doesn't affect the inner product; then expand the inner product of the Fourier transforms. Essentially, it's the same proof, but not in the language of Theta functions. In fact, I'd argue it's a better proof, because it generalises. Generalisation: This technique applies to all Riemann sums, as long as you can compute the Fourier transform of the function. The thinner the tails of the function's Fourier transform, the faster its Riemann sums will converge. [1] - https://en.wikipedia.org/wiki/Dirac_comb https://en.wikipedia.org/wiki/Dirac_comb
- abenedic 8y agoMyself, I would say this is 80% correct. The bigger deal is the spectral convergence of the trapezoidal sum for periodic entire functions.
- man-and-laptop 8y agoI gave my generalisation in terms of frequency, and not in terms of "number of rectangles" in the Riemann sum, which I conveniently assumed to be infinite. A better generalisation: if a function is thin-tailed, and its Fourier transform is thin-tailed, then it's Riemann sums converge to its integral at an exponential rate. In particular, this applies to the Gaussian function. I'll check out what you said.
- anonytrary 8y agoInteresting article, but I found the title a bit funny. I'd like to see an article about Newton's laws titled "Getting to the Moon from a Wrong Formula".