The million digit attempt

This post summarises a few runs that where made to compute many digits of Khinchin’s constant. We succeeded at repeating the previous record of a hundred thousand, in much less time, but failed at the million digit attempt.

Algorithms: (with source!)

BernMM: This implementation calculates the first zeta’s using David Harvey’s multi-modular Bernoulli algorithm. It switches to the power table method as soon as this becomes feasible. It is described in more detail in this post. Source: khinchin.bernmm.cpp. Requires GMP, MPFR, BernMM and NTL.

SCP: This implementation also employs the power table method for the first terms using the von Staudt-Clausen theorem and other trickery described in this post. Source: khinchin.SCP.cpp. Requires GMP and MPFR. And an unnecessary dependency on Boost.

All sources were compiled using g++ -ggdb -O3 -lrt -lpthreat.

Running time of various attempts:

These two algorithms were run at various levels of precision to evaluate their accuracy and performance. Timings were made using the time command. Gourdons attempt is included for completeness, but beware of the different (ten years older) hardware!

AlgorithmDigitsWall timeProcessor timeResult
Gourdon’s⁴110 02822.4 hours22.4 hours¹K0
SCP110 00412.5 min12.0 min³K0
BernMM110 00433.5 min76.2 min²K0
SCP1 010 0253.8 days3.8 days³K0
BernMM1 000 0234.5 days11.2 days²K0
SCP1 100 0263.4 days3.4 days²K0
BernMM1 100 0255.7 days14.4 days²K0

¹ On an SGI R10000 (64 bit architecture) with 256 Mb of memory.

² On the Qubis server, with few other processes running. Amd Phe­nom II X4 940, 64 bit 3 GHz quad core processor with 4 GB DDR2 RAM.

³ On my desktop system, with many other processes running. Same hardware as the server.

⁴ http://pi.lacim.uqam.ca/piDATA/khintchine.txt

Numerical consistency between attempts:

110 000 digit consistency:

vsGourdon’sSCPBernMM
Gourdons110 028110 000110 000
SCP110 000110 004110 004
BernMM110 000110 004110 004

Everything checks out, we can successfully calculate a hundred thousand digits of $K_0$ in twelve minutes.

Million digit consistency:

vsBernMM 1MBernMM 1M1SCP 1MSCP 1M1
BernMM 1M1 000 023540 634863 449453 476
BernMM 1M1540 6341 100 025540 634453 476
SCP 1M863 449540 6341 010 025453 476
SCP 1M1453 476453 476453 4761 100 026

This table show that there is something terribly wrong! Both algorithms are inconsistent with themselves and each other! From the table one can deduce that BernMM is accurate to 540 634 decimals and SCP to 453 476. But it seems that that SCP-1M1 is actually less precise than SCP-1M! This means there is some sort of error accumulating in the algorithm, and this could potentially undermine the consistency check, so I’ll have to fix this.

However, 540 634 is still a world record!

Remco Bloemen
Math & Engineering
https://2π.com