The mil­lion di­git attempt

This post sum­mar­ises a few runs that where made to com­pute many di­gits of Khinchin’s con­stant. We suc­ceeded at re­peat­ing the pre­vi­ous re­cord of a hun­dred thou­sand, in much less time, but failed at the mil­lion di­git attempt.

Al­gorithms: (with source!)

BernMM: This im­ple­ment­a­tion cal­cu­lates the first zeta’s us­ing David Har­vey’s multi-mod­u­lar Bernoulli al­gorithm. It switches to the power table method as soon as this be­comes feas­ible. It is de­scribed in more de­tail in this post. Source: khinchin.​bernmm.​cpp. Re­quires GMP, MPFR, BernMM and NTL.

SCP: This im­ple­ment­a­tion also em­ploys the power table method for the first terms us­ing the von Staudt-Clausen the­orem and other trick­ery de­scribed in this post. Source: khinchin.​SCP.​cpp. Re­quires GMP and MPFR. And an un­ne­ces­sary de­pend­ency on Boost.

All sources were com­piled us­ing g++ -ggdb -O3 -lrt -lpthreat.

Run­ning time of vari­ous attempts:

These two al­gorithms were run at vari­ous levels of pre­ci­sion to eval­u­ate their ac­cur­acy and per­form­ance. Tim­ings were made us­ing the <code>time</code> com­mand. Gour­dons at­tempt is in­cluded for com­plete­ness, but be­ware of the dif­fer­ent (ten years older) hardware!

Al­gorithm Di­gits Wall clock time Pr­cessor time Res­ult
Gour­don’s110 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

Nu­mer­ical con­sist­ency between attempts:

Table 1. 110 000 digit consistency
Gour­don’sSCPBernMM
Gour­dons110 028110 000110 000
SCP110 000110 004110 004
BernMM110 000110 004110 004

Everything checks out, we can suc­cess­fully cal­cu­late a hun­dred thou­sand di­gits of in twelve minutes.

Table 2. Million digit consistency
BernMM 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 ter­ribly wrong! Both al­gorithms are in­con­sist­ent with them­selves and each other! From the table one can de­duce that BernMM is ac­cur­ate to 540 634 decim­als and SCP to 453 476. But it seems that that SCP-1M1 is ac­cutally less pre­cise than SCP-1M! This means there is some sort of er­ror ac­cu­mu­lat­ing in the al­gorithm, and this could po­ten­tially un­der­mine the con­sist­ency check, so I’ll have to fix this.

However, 540 634 is still a world record!

(Ori­gin­ally pos­ted on 2009-12-02)

Add comment