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