(Last updated: October 22, 2018)

**Back To:**

This is a dump of Binary Splitting recursions for various series and constants. For the most part, these are what y-cruncher uses.

All run-time complexities shown assume that large multiplication is * O( N log(N) )*.

**Index:**

**e:****Pi:****ArcCoth(x):****Zeta(3) - Apery's Constant:****Catalan's Constant:****ArcSinlemn(x/y):****Euler-Mascheroni Constant:**

Run-Time Complexity for N digits:O( N log(N)^{2})

Series Type:Hyperdescent

Series Speed:Superlinear

Run-Time Complexity for N digits:O( N log(N)^{2})

Series Type:Hyperdescent

Series Speed:Superlinear

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)0.367

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)0.653

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)4 / log(x^{2})

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)2.755

**Zeta(3) - Amdeberhan-Zeilberger (1997):**

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)2.885

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)11.542

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:BinaryBBP

Series Speed:Linearly Convergent (cost =)17.312

Huvent's formula can be rearranged as follows:

Series Type:BinaryBBP

Series Speed:Linearly Convergent (cost =)12.984

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)11.542

A trivial rearrangement of the formula leads to a much faster series:

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)5.771

**Catalan - Pilehrood (2010-short):**

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)3.074

**Catalan - Pilehrood (2010-long):**

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)4.617

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)2 / log(y/x)

**Euler-Mascheroni Constant - Brent-McMillan (1980) Series A and B:**

The Brent-McMillan formula is an approximation to the Euler-Mascheroni Constant.

The parameter

ndetermines how good the approximation is. To computeNdigits, you must pick a suitably largensuch that the approximation is sufficient.

Run-Time Complexity for N digits:O( N log(N)^{3})

Series Type:Specialized

Series Speed:Superlinear for a fixedn

Note that there are two error bounds in this final formula:

- The 1st one,
O(eis from the series being an approximation rather than an equality.^{-4n})- The 2nd one is from the number of terms that have been summed up.
The series is divergent for the first

nterms. Tthe 2nd error bound only holds when the series begins converging. Therefore you must sum at leastnterms.

If

nhas been chosen carefully to reach exactly the desired precision, then the number of termsito be summed should be chosen such that the second error bound reaches the same desired precision. This can be done by settingias follows:

where the 3.59112... is the solution to the following equation:

This 7-variable recursion shown above is freshly derived and unoptimized. The one that y-cruncher uses is optimized down to 4 variables.

But to break it down a bit:

PandQare the harmonic numbers summed up using the BinaryBBP recursion withr = 0.R,S, andTis series B using the CommonP2B3 recursion.UandV, puts the two together to construct series A.

The Brent-McMillan formula is by far the most difficult and complicated to implement among the mainstream constants:

- The 7-variable Binary Splitting recursion is significantly more complicated and difficult to derive than most other recursions.
- The formula is an approximation which leads to multiple error-bounds that need to be dealt with.
- The initially divergent behavior followed by non-linear convergence can cause lead to difficulties not present with other (better behaved) algorithms.
- While not shown here, the refinement term is a divergent asympotic series with the opposite convergence behavior as the above.
- Hardly worth mentioning, but the formula does require an implementation of log(n).