10 trillion digits of pi: A case study of summing hypergeometric series to high precision on multicore systems

Abstract

Hypergeometric series are powerful mathematical tools with many usages. Many mathematical functions, such as trigonometric functions, can be partly or entirely expressed in terms of them. In most cases this allows efficient evaluation of such functions, their derivatives and their integrals. They are also the most efficient way known to compute constants, such as π and e, to high precision. Binary splitting is a low complexity algorithm for summing up hypergeometric series. It is a divide-and-conquer algorithm and can therefore be parallelized. However, it requires large number arithmetic, increases memory usage, and exhibits asymmetric workload, which makes it non-trivial to parallelize. We describe a high performing parallel implementation of the binary splitting al- gorithm for summing hypergeometric series on shared-memory multicores. To evaluate the implementation we have computed π to 5 trillion digits in August 2010 and 10 trillion digits in October 2011 — both of which were new world records. Furthermore, the implementation techniques described in this paper are general, and can be used to implement applications in other domains that exhibit similar features.