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