|
What it the fastest algorithm for estimating Euler's Constant $\gamma \approx0.57721$? Using the definition: $$\lim_{n\rightarrow\infty} \sum_{x=1}^{n}\frac{1}{x}-\log n=\gamma$$ I finally get 2 decimal places accuracy when $n\geq180$. The third correct decimal place only comes when $n \geq638$. Clearly this method is not very efficient (it may can be expensive to compute $\log$). What is the best method to use to efficiently numerically estimate $\gamma$? |
||||
|
|
|
The paper "On the computation of the Euler constant $\gamma$" by Ekatharine A. Karatsuba, in Numerical Algorithms 24(2000) 83-97, has a lot to say about this. This link might work for you. In particular, the author shows that for $k\ge 1$, $$ \gamma= 1-\log k \sum_{r=1}^{12k+1} \frac{ (-1)^{r-1} k^{r+1}}{(r-1)!(r+1)} + \sum_{r=1}^{12k+1} \frac{ (-1)^{r-1} k^{r+1} }{(r-1)! (r+1)^2}+\mbox{O}(2^{-k})$$ and more explicitly $$\begin{align*} -\frac{2}{(12k)!} - 2k^2 e^{-k} \le \gamma -1+&\log k \sum_{r=1}^{12k+1} \frac{ (-1)^{r-1} k^{r+1}}{(r-1)!(r+1)} - \sum_{r=1}^{12k+1} \frac{ (-1)^{r-1} k^{r+1} }{(r-1)! (r+1)^2}\\ &\le \frac{2}{(12k)!} + 2k^2 e^{-k}\end{align*}$$ for $k\ge 1$. Since the series has fast convergence, you can use these to get good approximations to $\gamma$ fairly quickly. |
|||||||||||||||
|
|
I like $$ \gamma = \lim_{n \rightarrow \infty} \; \; \left( \; \; 1 + \frac{1}{2} + \cdots + \frac{1}{n} - \frac{1}{n + 1 } - \cdots - \frac{1}{n^2 } - \frac{1}{n^2 + 1 } - \cdots - \frac{1}{n^2 + n} \; \; \right) $$ because it needs no logarithm and the error is comparable to the final term used. I found this formula on page 82, the January 2012 issue (volume 119, number 1) of the M. A. A. American Mathematical Monthly. It was sent in by someone named Jouzas Juvencijus Macys, possibly for the Problems and Solutions section. He stopped the sum at $-1/n^2.$ I noticed that the error would be minimized by continuing the sum to $-1/(n^2 + n).$ If you want, you can add a single term $1/(6 n^2)$ to get the error down to $n^{-3}.$ $$ \gamma = \lim_{n \rightarrow \infty} \; \; \frac{1}{6n^2} + \left( \; \; 1 + \frac{1}{2} + \cdots + \frac{1}{n} - \frac{1}{n + 1 } - \cdots - \frac{1}{n^2 } - \frac{1}{n^2 + 1 } - \cdots - \frac{1}{n^2 + n} \; \; \right) $$ |
||||
|
|
A good place for fast evaluation of constants is Gourdon and Sebah's 'Numbers, constants and computation'. They got $108\cdot 10^6$ digits for $\gamma$ in 1999 (see the end of their 2004 article 'The Euler constant') and propose a free program for high precision evaluation of various constants 'PiFast'. On his page of constants Simon Plouffe has Euler's constants to 10^6 digits (the file looks much smaller sorry...) using Brent's splitting algorithm (see the 1980 paper of Brent 'Some new algorithms for high-precision computation of Euler’s constant' or more recently 3.1 in Haible and Papanikolaou's 'Fast multiprecision evaluation of series of rational numbers'). It seems that the 1999 record was broken in 2009 by A. Yee & R. Chan with 29,844,489,545 digits 'Mathematical Constants - Billions of Digits' (warning: the torrent file proposed there is more than 11Gb large! An earlier 52Mb file of 'only' 116 million digits is available here using the method proposed by Gourdon and Sebah). |
||||
|
|
|
Finch's Mathematical Constants mentions these papers:
|
|||
|
|
|
(N.B. The previous version of this answer featured both the Brent-McMillan algorithm and the acceleration of Macys's series; I have decided to move the Brent-McMillan material into a new answer in the interest of having only one method per answer.) The convergence properties of Macys's series in Will's answer can be improved a fair bit, if you're willing to devote some amount of computational effort; due to the $n^{-2}$ behavior of the error, one obvious choice for a convergence acceleration method is Richardson extrapolation. Skipping some hairy details (which I might include later if I find time, but see Marchuk/Shaidurov if you must), the working formula is $$\gamma=\lim_{n\to\infty} G_n=2\lim_{n\to\infty} \sum_{i=1}^{n+1} \frac{(-1)^{n-i} i^{2n+2}}{(n+i+1)!(n-i+1)!}\left(\sum_{k=i+1}^{i(i+1)} \frac1{k}-\sum_{k=1}^i \frac1{k}\right)$$ Here are some sample results: $$\begin{array}{ccc}n&G_n&\gamma-G_n\\10&0.577210083083&5.581818\times10^{-6}\\50&0.577215659731&5.170456\times10^{-9}\\100&0.577215664665&2.362333\times10^{-10}\\200&0.577215664891&1.061648\times10^{-11}\\250&0.577215664898&3.902515\times10^{-12}\\300&0.577215664900&1.721878\times10^{-12}\\350&0.577215664901&8.618620\times10^{-13}\end{array}$$ For higher precision, there isn't much of an improvement; I would still recommend Brent-McMillan if one needs many digits of $\gamma$. |
|||||||||
|
|
As it turns out, the convergence of the Karatsuba series presented in Matthew's answer can be improved. This time, the geometric behavior of the error (as can be ascertained from the bounds presented) can be exploited through the use of the Shanks transformation. (Richardson can be made to work here as well, but the results are not as spectacular.) Letting $$\varepsilon_0^{(k)}=1-\log(k+1) \sum_{r=1}^{12k+13} \frac{ (-k)^{r+1}}{(r-1)!(r+1)} + \sum_{r=1}^{12k+13} \frac{ (-k)^{r+1} }{(r-1)!(r+1)^2}$$ Wynn's version of the Shanks transformation uses the recursion $$\varepsilon_{k+1}^{(n)}=\varepsilon_{k-1}^{(n+1)}+\frac1{\varepsilon_{k}^{(n+1)}-\varepsilon_k^{(n)}}$$ It would seem that a two-dimensional array would be required for implementation, but one can arrange things such that only a one-dimensional array is required, through clever overwriting. Here is a Mathematica routine to demonstrate: (actually the same as the routine presented in this answer). Here's a comparison of Karatsuba's series, with and without Shanks transformation: Not too shabby, in my humble opinion... |
|||
|
|
|
I do not know about the best method, however numerically evaluating the integral $$\gamma = - \int_0^1\!dx\,\ln \ln x^{-1}$$ seems to be pretty efficient. |
|||||||||||||||
|
|
Hmm, I don't know whether is is actually competing. The Euler-gamma can also be seen as the "regularized" sum of all zeta's at the nonpositive integer arguments (mostly expressed in a sum-formula using the Bernoulli-numbers). If I do a convergence-acceleration-method, (in the sense of a Nörlund-matrix-summation) I get the following approximations, where the partial sums are documented in steps of 5. Well, this might not compete because of the computation effort for the coefficients of the Noerlund summation and also it seems, as if the rate/quality of convergence decreases with the increasing steps, so this should possibly be seen only as a sidenote. (Reminder as to how to reproduce the behaviour: |
|||
|
|
|
There is another interesting formula
$$\small \gamma = \sum_{k=2}^\infty {\zeta(k)-1\over k}$$
found in mathworld (see eq 123) . then we can write an approximation-formula for the Euler $\small \gamma$ $$\small \gamma_{r,c} = \sum_{k=2}^c {\zeta_r(k)-1\over k}$$ which depends on the number of rows r and the number of columns c . Now to reduce the number of coefficients needed to arrive at a good approximation
If we use all three accelerations, we get a double sum $$\small \gamma_{r,c} = \sum_{k=2}^c \sum_{j=1}^r a_{j,k}{ 1 \over j^k}$$ where the $\small a_{j,k} $ contain the factors due to the denominator in the $\small \gamma$-formula and due to the threefold convergence-acceleration. I did actually implement this in Pari/GP and the surprising result was, that the best approximations were (using order 0.5 in the Eulersummation for the columns and -0.25 for the Eulersummation of the approximated zetas), if roughly r=c . Then the number of correct digits were about r/2; so with r=64 and c=64 we get $\small \gamma$ to 31 digits accuracy. The cost of computation of the complete array of zeta-terms is thus in principle quadratic in d (the required number of correct digits); for the Euler-sums a vector for the column-acceleration and another vector for the row-acceleration is required whose values can recursively be computed and are thus linear with the number of rows resp the number of columns and thus also linear with d. (The convergence-acceleration (1.) by using the alternating sums costs nearly nothing) |
|||||
|
|
I quite like the Brent-McMillan algorithm myself (which is based on the relationships between the Euler-Mascheroni constant and modified Bessel functions): $$\gamma=\lim_{n\to\infty}\mathscr{G}_n=\lim_{n\to\infty}\frac{\sum\limits_{k=0}^\infty \left(\frac{n^k}{k!}\right)^2 (H_k-\log\,n)}{\sum\limits_{k=0}^\infty \left(\frac{n^k}{k!}\right)^2}$$ where $H_k=\sum\limits_{j=1}^k \frac1{j}$ is a harmonic number. It requires the use of a logarithm, but the algorithm is quite simple and reasonably efficient (in particular, we have the inequality $0 < \mathscr{G}_n-\gamma < \pi\exp(-4n)$). Here's some Mathematica code for the Brent-McMillan algorithm (which should be easily translatable to your language of choice): The integer parameter The Brent-McMillan paper also presents more elaborate schemes for computing $\gamma$, such as $$\gamma=\lim_{n\to\infty}\frac{\sum\limits_{k=0}^\infty \left(\frac{n^k}{k!}\right)^2 (H_k-\log\,n)}{\sum\limits_{k=0}^\infty \left(\frac{n^k}{k!}\right)^2}-\frac{\frac1{4n}\sum\limits_{k=0}^\infty \frac{(2k)!^3}{k!^4 (16n)^{2k}}}{\left(\sum\limits_{k=0}^\infty \left(\frac{n^k}{k!}\right)^2\right)^2}$$ but I have no experience in using them. |
|||||
|
