Binary Splitting Recursion Library

By Alexander Yee

 

(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 - exp(1):

 

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

 

Series Type: Specialized

Series Speed: Superlinear

 

 

 

 


e - exp(-1):

 

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

 

Series Type: Specialized

Series Speed: Superlinear

 

 

 

 


Pi - Chudnovsky:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.367)

 

 

 

 


Pi - Ramanujan:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.653)

 

 

 

 


ArcCoth(x) - Taylor Series:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 4 / log(x2))

 

 

 

 


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)

 

 

 

 


Catalan - Lupas:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 11.542)

 

 

 

 


Catalan - Huvent:

 

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)

 


Catalan - Lima-Guillera:

 

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

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 3.074)

 

 

 

 


Catalan - Pilehrood (long):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 4.617)

 

 

 

 


ArcSinlemn(x/y) - Series:

 

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 n determines how good the approximation is. To compute N digits, you must pick a suitably large n such that the approximation is sufficient.

 

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

 

Series Type: Specialized

Series Speed: Superlinear for a fixed n

 

 

 

 

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

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 least n terms.

 

If n has been chosen carefully to reach exactly the desired precision, then the number of terms i to be summed should be chosen such that the second error bound reaches the same desired precision. This can be done by setting i as 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: