Binary Splitting Recursion Library

By Alexander Yee

 

(Last updated: August 31, 2018)

 

 

 

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
  • Ramanujan


• ArcCoth(x):
  • Taylor Series


• Zeta(3) - Apery's Constant:
  • Amdeberhan-Zeilberger Formula (long)
  • Amdeberhan-Zeilberger Formula (short)


• Catalan's Constant:
  • Lupas
  • Huvent
  • Lima-Guillera
  • Pilehrood (short)
  • Pilehrood (long)


• ArcSinlemn(x/y):
  • Series


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

 

---

e - exp(1):

 

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

 

Series Type: Specialized

Series Speed: Superlinear

 

 

 

 

---

e - exp(-1):

 

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

 

Series Type: Specialized

Series Speed: Superlinear

 

 

 

 

---

Pi - Chudnovsky:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 0.367)

 

 

 

 

---

Pi - Ramanujan:

 

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) - Amdeberhan-Zeilberger Formula (long):

 

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

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 2.885)

 

 

 

 

---

Catalan - Lupas:

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 11.542)

 

 

 

 

---

Catalan - Huvent:

 

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 - Lima-Guillera:

 

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

 

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

 

Series Type: CommonP2B3

Series Speed: Linearly Convergent (cost = 3.074)

 

 

 

 

---

Catalan - Pilehrood (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 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.

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:

• 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.