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

Yee, Alexander; Kondo, Shigeru

Permalink

https://hdl.handle.net/2142/28348 Copy

Description

Title

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

Author(s)

• Yee, Alexander
• Kondo, Shigeru

Issue Date

2011-11-11

Keyword(s)

• Hypergeometric Series
• Pi
• Multicore
• Parallel Computing
• Arbitrary Precision Arithmetic

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.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/28348

Owning Collections