The million digit attempt

Remco Bloemen

2009-12-02, last updated 2014-02-27

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!

Algorithm Digits Wall time Processor time Result
Gourdon’s⁴ 110 028 22.4 hours 22.4 hours¹ [ K0](K0-Gourdon-1k1.txt)
SCP 110 004 12.5 min 12.0 min³ K0
BernMM 110 004 33.5 min 76.2 min² K0
SCP 1 010 025 3.8 days 3.8 days³ K0
BernMM 1 000 023 4.5 days 11.2 days² K0
SCP 1 100 026 3.4 days 3.4 days² K0
BernMM 1 100 025 5.7 days 14.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:

Gourdon’s SCP BernMM
Gourdons 110 028 110 000 110 000
SCP 110 000 110 004 110 004
BernMM 110 000 110 004 110 004

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

Million digit consistency:

BernMM 1M BernMM 1M1 SCP 1M SCP 1M1
BernMM 1M 1 000 023 540 634 863 449 453 476
BernMM 1M1 540 634 1 100 025 540 634 453 476
SCP 1M 863 449 540 634 1 010 025 453 476
SCP 1M1 453 476 453 476 453 476 1 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 accutally 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!