# Efficient calculation of Khinchin’s constant

2009-11-05, last updated 2014-02-27

In the previous post we (me, Sander & Sander) set upon ourselves the challenge to beat Xavier Gour­don’s 1997 record of hundred and ten thousand digits of Khinchin’s constant. This quickly diverted into a challenge of calculating the Riemann Zeta function (again, see wikipedia and mathworld for more info).

Khinchin’s constant, $K_0$ and the Zeta function $\zeta$ are related by the following identity:

$\ln K_0 = \frac{1}{\ln{2}} \sum_{[1,\infty]}^{n} \frac{\zeta(2n) -1}{n} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k}$

## Analysing bounds and limits

The inner series is an alternating harmonic series and has the following limit:

$\lim_{n \to \infty} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k} = \ln{2}$

Since we are taking two terms at a time this series it is strictly increasing and $\ln{2}$ is also an upper bound.

An upper bound for $\zeta$ can be easily seen from the series definition, $\zeta(2n) - 1 < \frac{2}{2^{2n}}$. Combing these results gives an upper bound for the terms in the outer series:

$\frac{\zeta(2n) -1}{n} \sum_{[1, 2n-1]}^{k} \frac{(-1)^{k+1}}{k} < \frac{\ln{4}}{n 4^n}$

This expression also allows us to calculate an upper bound for the cutoff error, i.e. the error we introduce by not summing to $n=\infty$ but stopping at $n=N$:

$\sum_{[N, \infty]} \frac{\ln{4}}{n 4^n} < \ln{4} \sum_{[N, \infty]} \frac{1}{4^n} = \frac{\ln{16}}{3 \cdot 4^N}$

If we now take the binary logarithm of this number we know how many fractional bits we get at least correct when summing up to $N$. In fact, since $\ln{2} \ln K_0 \approx 1$, we know the total number of bits we get correct:

$-\log_2 \left( \frac{\ln{16}}{3 \cdot 4^N} \right) = 2 N + \log_2 3 - \log_2 \ln{16}$

Or, put differently, to obtain $B$ bits of $K_0$ we must sum up to (but not including):

$N =\frac{1}{2}\left(B - \log_2 3 + \log_2 \ln{16}\right) < \left\lceil\frac{B}{2}\right\rceil + 1$

The uncertainty of the sum is the sum of the uncertainties of the terms. So if we need an accuracy of $2^{-B}$ for the sum, we can divide this accuracy evenly over the terms, giving each an accuracy of $\frac{1}{N}$ $2^{-B}$. So the precision (in bits) of the terms is:

$B_{term} = \left\lceil B + \log_2 N \right\rceil$

The $\zeta$ can be less accurate, since it will be multiplied by $\ln 2 < 1$ and divided by n, this amounts to an required accuracy of:

$B_{zeta}(n) = \left\lceil B_{term} - \log_2 n -\log_2 \ln{2} \right\rceil$

## The million digit goal

To calculate $K_0$ accurate up to a million digits we require the following:

Parameter value
$B$ 3 321 929
$N$ 1 666 966
$B_{term}$ 3 321 950
$B_{zeta}(n)$ 3 321 951 … 3 321 930

The problem can now be restated as: How does one calculate $\zeta (2) \ldots \zeta (2N)$ fast and accurate up to $B_{zeta}(n)$ bits?