Binary Splitting Recursion Library

By Alexander Yee

 

(Last updated: February 22, 2019)

 

 

 

Back To:

• Numberworld Home
• y-cruncher Home
• Algorithms and Internals

 

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


• Pi:
  • Chudnovsky (1989)
  • Ramanujan (1910)


• ArcCoth(x):
  • Taylor Series


• Zeta(3) - Apery's Constant:
  • Wedeniwski (1998)
  • Amdeberhan-Zeilberger (1997)


• Catalan's Constant:
  • Lupas (2000)
  • Huvent (2006)
  • Guillera (2008)
  • Pilehrood (2010-short)
  • Pilehrood (2010-long)


• ArcSinlemn(x/y):
  • Series


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

 

---

e - exp(1):

 

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

 

Series Type: Hyperdescent

Series Speed: Superlinear

 

 

 

 

---

e - exp(-1):

 

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

 

Series Type: Hyperdescent

Series Speed: Superlinear

 

 

 

 

---

Pi - Chudnovsky (1988):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.367)

 

 

 

 

---

Pi - Ramanujan (1910):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.653)

 

 

 

 

---

ArcCoth(x) - Taylor Series:

 

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

 

Series Type: CommonP2B3

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

 

 

 

 

---

Zeta(3) - Wedeniwski (1998):

 

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

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 2.885)

 

 

 

 

---

Catalan - Lupas (2000):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 11.542)

 

 

 

 

---

Catalan - Huvent (2006):

 

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

 

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

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 3.074)

 

 

 

 

---

Catalan - Pilehrood (2010-long):

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 4.617)

 

 

 

 

---

ArcSinlemn(x/y) - Series:

 

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

 

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

 

Series Type: Specialized

Series Speed: Superlinear for a fixed n

 

 

 

 

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

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

The series is divergent for the first n terms. The 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:

• P and Q are the harmonic numbers summed up using the BinaryBBP recursion with r = 0.
• R, S, and T is series B using the CommonP2B3 recursion.
• U and V, 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).