Efficient calculation of Khinchin’s constant

Remco Bloemen

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, K0K_0 and the Zeta function ζ\zeta are related by the following identity:

lnK0=1ln2[1,]nζ(2n)1n[1,2n1]k(1)k+1k \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:

limn[1,2n1]k(1)k+1k=ln2 \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 ln2\ln{2} is also an upper bound.

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

ζ(2n)1n[1,2n1]k(1)k+1k<ln4n4n \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=n=\infty but stopping at n=Nn=N:

[N,]ln4n4n<ln4[N,]14n=ln1634N \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 NN. In fact, since ln2lnK01\ln{2} \ln K_0 \approx 1, we know the total number of bits we get correct:

log2(ln1634N)=2N+log23log2ln16 -\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 BB bits of K0K_0 we must sum up to (but not including):

N=12(Blog23+log2ln16)<B2+1 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 2B2^{-B} for the sum, we can divide this accuracy evenly over the terms, giving each an accuracy of 1N\frac{1}{N} 2B2^{-B}. So the precision (in bits) of the terms is:

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

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

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

The million digit goal

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

Parameter value
BB 3 321 929
NN 1 666 966
BtermB_{term} 3 321 950
Bzeta(n)B_{zeta}(n) 3 321 951 … 3 321 930

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