2009-12-02 (updated 2014-02-27)

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!

Algorithm	Digits	Wall time	Processor time	Result
Gourdon’s⁴	110 028	22.4 hours	22.4 hours¹	K0
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 Phenom 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:

vs	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 $K_0$ in twelve minutes.

Million digit consistency:

vs	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 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!