pi_spigot

Build Status codecov Boost Software License 1.0 GitHub code size in bytes

The pi_spigot repository implements a spigot-type algorithm in modern C++ template code. It calculates many decimal digits of the mathematical constant pi.

The spigot-type algorithm used here has rather slow quadratic order N2 computational complexity. So you won’t break any digit or speed records with this implementation. It is, however, capable of readily computing many thousands of digits (up to a 100,000 decimal digits or more) of pi — right out of the box and with just a few lines of computational code.

The default setting of the tests computes hundredthousand decimal digits of pi.

Mathematical details

Spigot-type algorithms are known for various mathematical constants including logarithms and pi.

The basic spigot algorithm for computing digits of pi in base-10 is given by (Eq. 6.1, Sect. 6.1, page 78 of Arndt and Haenel [2]):

spigotalgo

In the code, this equation is primarily implemented in the calculate() method of the pi_spigot_single template class which resides in namespace math::constants.

Using the pi_spigot_single template class

The signature of the pi_spigot_single template class is shown below.

namespace math::constants {

template<const std::uint32_t ResultDigit,
         const std::uint32_t LoopDigit>
class pi_spigot_single;

}

The template parameters ResultDigit and LoopDigit can be used to vary the size and granularity of the calculation (within certain limits).

In order to compute, let’s say, tenthousand decimal digits of pi, the result of ResultDigit should be set to 10001.

The LoopDigit parameter controls the number of decimal digits calculated within each successive iterative loop of the program. In the classic literature, this parameter is often set to 4 and can not be varied. in this repository, LoopDigit parameter can be set to a variable number of digits ranging from about 4 through 9, where the best performance is obtained for 9.

The internal mathematical code requires multiplication within the running iteration. This code uses uint64_t for internal result storage. For this reason, the maximum value of LoopDigit is 9 so that when it is multiplied, the result has about 18 decimal digits, which still fits inside uint64_t without overflow.

A C++ alias can be used to conveniently set the digit characteristics used in the spigot calculation.

using pi_spigot_type = math::constants::pi_spigot_single<100001U, 9U>;

The default configuration in the pi_spigot repository uses 100001 decimal digits with digit granularity of 9, as shown. The exact template instantiation is actually done in two steps in the code (via secondary subroutine). The instantiation actually takes place with named parameters in the test_pi_spigot_single() template subroutine.

Timing and memory consumption

Timing and memory consumption are provided in closed form equations in [3]. In that work, we find empirically that the memory grows linearly with input size while the computational complexity grows quadratically.

The table below lists memory consumption and computation time on a PC platform running GCC 9 with instamntiation of pi_spigot_single<N, 9U>, where N varies.

N (digits) Memory Consumption Operation Count Time (s)
10,001 137,788 19,155,868 0.23
50,001 688,900 478,496,610 5.2
100,001 1,377,788 1,913,780,868 21

Testing, continuous integration and quality

Testing and continuous integration runs on GitHub Actions. Various OS/compiler combinations are used including GCC/clang/MSVC.

Code coverage uses GCC/gcov/lcov and has a quality-gate with comparison/baseline-check provided by third-party Codecov. Codecov.

TBD Provide use linters and describe them.

Possible extensions

The pi-spigot algorithm in this repository can successfully compute up to a million digits of pi. It is, however, very slow with computational complexity growing quadratically in proportion to digit size.

Looking at the implementation of the algorithm, however, it might be possible to parallelize some or part of the algorithmic loops. If this is possible, a modern GPU massive parallelization would reduce the calculation time dramatically.

At the moment, the LoopDigit parameter is limited to 9 decimal digits due to the size of multiplication which needs to remain bounded within uint64_t. Possible extension to 128-bit or multiple-precision integral types would allow for much larger digit counts per iteration, however, at the cost of higher time for the individual operations.

References

The original publication of the description of the spigot algorithm can be found in [1]. The expression of this algorithm (as used in this repository) has been further influenced by descriptions in [2]. The pi_spigot implementation in C++ code in this repository has been inspired by Section 10.8 of [3].

[1] S. Rabinowitz and S. Wagon: A Spigot Algorithm for the Digits of Pi, American Mathematical Monthly 102: 195–203, 1995

[2] J. Arndt and C. Haenel: pi Unleashed (Springer Verlag, Heidelberg, 2001)

[3] C.M. Kormanyos: Real-Time C++: Efficient Object-Oriented and Template Microcontroller Programming, 4th Edition (Springer, Heidelberg, 2021). ISBN 9783662629956.

GitHub

View Github