×

Parallel implementation of multiple-precision arithmetic and 2,576,980,370,000 decimal digits of \(\pi \) calculation. (English) Zbl 1204.68011

Summary: We present efficient parallel algorithms for multiple-precision arithmetic operations of more than several million decimal digits on distributed-memory parallel computers. A parallel implementation of floating-point real FFT-based multiplication is used, since the key operation for fast multiple-precision arithmetic is multiplication. The operation for releasing propagated carries and borrows in multiple-precision addition, subtraction and multiplication was also parallelized. More than 2.576 trillion decimal digits of \(\pi \) were computed on 640 nodes of Appro Xtreme-X3 (648 nodes, 147.2 GFlops/node, 95.4 TFlops peak performance) with a computing elapsed time of 73 h 36 min which includes the time required for verification.

MSC:

68M07 Mathematical problems of computer architecture
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Smith, D. M.: Algorithm 693: a Fortran package for floating-point multiple-precision arithmetic, ACM trans. Math. softw. 17, 273-283 (1991) · Zbl 0900.65037
[2] Bailey, D. H.: Algorithm 719: multiprecision translation and execution of Fortran programs, ACM trans. Math. softw. 19, 288-319 (1993) · Zbl 0889.68015
[3] The GNU MP Bignum Library, <http://gmplib.org/>.
[4] The MPFR Library, <http://www.mpfr.org/>.
[5] F. Bellard, Computation of 2700 billion decimal digits of pi using a desktop computer, 2010.
[6] Karatsuba, A.; Ofman, Y.: Multiplication of multidigit numbers on automata, Doklady akad. Nauk SSSR 145, 293-294 (1962)
[7] Knuth, D. E.: The art of computer programming, Seminumerical algorithms 2 (1997) · Zbl 0895.68055
[8] Cesari, G.; Maeder, R.: Performance analysis of the parallel karatsuba multiplication algorithm for distributed memory architectures, J. symbolic comput. 21, 467-473 (1996) · Zbl 0863.68072
[9] Schönhage, A.; Strassen, V.: Schnelle multiplikation grosser zahlen, Comput. (Arch. Elektron. rechnen) 7, 281-292 (1971) · Zbl 0223.68007
[10] Fagin, B. S.: Large integer multiplication on hypercubes, J. parallel distributed comput. 14, 426-430 (1992) · Zbl 0757.65152
[11] B. Char, J. Johnson, D. Saunders, A.P. Wack, Some experiments with parallel bignum arithmetic, in: Proceeding of the 1st International Symposium on Parallel Symbolic Computation, 1994, pp. 94 – 103.
[12] Lehman, M.; Burla, N.: Skip techniques for high-speed carry propagation in binary arithmetic units, IRE trans. Electr. comput. 10, 691-698 (1961)
[13] R.P. Brent, P. Zimmermann, Modern Computer Arithmetic, 2010, version 0.5.1.
[14] Crandall, R.; Fagin, B.: Discrete weighted transforms and large-integer arithmetic, Math. comput. 62, 305-324 (1994) · Zbl 0839.11065
[15] Takahashi, D.; Boku, T.; Sato, M.: A blocking algorithm for parallel 1-D FFT on clusters of pcs, Lecture notes in computer science 2400, 691-700 (2002) · Zbl 1068.65507
[16] Bailey, D. H.: Ffts in external or hierarchical memory, J. supercomput. 4, 23-35 (1990)
[17] Karp, A. H.; Markstein, P.: High-precision division and square root, ACM trans. Math. softw. 23, 561-589 (1997) · Zbl 0912.65038
[18] D. Takahashi, Implementation of multiple-precision parallel division and square root on distributed-memory parallel computers, in: Proceedings of the 2000 International Conference on Parallel Processing (ICPP-2000) Workshops, 2000, pp. 229 – 235.
[19] OpenMPI: Open Source High Performance Computing, <http://www.open-mpi.org/>.
[20] , Pi: A source book (2004) · Zbl 1054.11001
[21] Kanada Laboratory home page, <http://www.super-computing.org/>.
[22] Brent, R. P.: Fast multiple-precision evaluation of elementary functions, J. ACM 23, 242-251 (1976) · Zbl 0324.65018
[23] Salamin, E.: Computation of \(\pi \) using arithmetic – geometric mean, Math. comput. 30, 565-570 (1976) · Zbl 0345.10003
[24] Borwein, J. M.; Borwein, P. B.: Pi and the AGM — A study in analytic number theory and computational complexity, (1987) · Zbl 0611.10001
[25] Ooura, T.: Improvement of the \(\pi \) calculation algorithm and implementation of fast multiple-precision computation, Trans. jpn. Soc. indust. Appl. math. 9, 165-172 (1999)
[26] FFTE: A Fast Fourier Transform Package, <http://www.ffte.jp/>.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.