# 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.

View Github