pi_spigot
The pi_spigot repository implements
a spigot-type algorithm in modern C++ template code.
It calculates many decimal
digits of the mathematical constant
.
The spigot-type algorithm used here has rather slow quadratic
order
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
— right out of the box and with just a few lines
of computational code.
The default setting of the tests computes
decimal digits of
.
Mathematical details
Spigot-type algorithms are known for various mathematical constants
including logarithms and
.
The basic spigot algorithm for computing digits of
in base-10 is given by
(Eq. 6.1, Sect. 6.1, page 78 of Arndt and Haenel [2]):
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,
decimal digits of
,
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 .
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:
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.
