Binary Splitting Recursion Library

By Alexander Yee

 

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

 

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

 

Series Type: Hyperdescent

Series Speed: Superlinear

 

 

 

 


e - exp(-1):

 

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

 

Series Type: Hyperdescent

Series Speed: Superlinear

 

 

 

 


Pi - Chudnovsky (1989):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.367)

 

 

 

 


Pi - Ramanujan (1910):

 

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) - Wedeniwski (1998):

 

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)

 

 

 

 


Catalan - Lupas (2000):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 11.542)

 

 

 

 


Catalan - Huvent (2006):

 

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 - Guillera (2008):

 

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)

 

 

 

 


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

The series is divergent for the first n terms. Tthe 2nd error bound only holds when the series begins converging. 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:

 

 

 

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:

 

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