(Last updated: August 31, 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:Specialized

Series Speed:Superlinear

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

Series Type:Specialized

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})

**Zeta(3) - Amdeberhan-Zeilberger Formula (long):**

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 Formula (short):**

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

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

Series Type:CommonP2B3

Series Speed:Linearly Convergent (cost =)3.074

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 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.
Due to the initially divergent behavior of series A and B, the 2nd error bound only holds when

i > n. 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:

Just to be clear, this 7-variable recursion shown above is "freshly derived". There is a lot of room to optimize it. So it is not the one that y-cruncher uses.

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.