(Last updated: January 17, 2023)
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:
Run-Time Complexity for N digits: O( N log(N)2 )
Series Type: Hyperdescent
Series Speed: Superlinear
Run-Time Complexity for N digits: O( N log(N)2 )
Series Type: Hyperdescent
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(x2))
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)
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 = 4.189)
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)
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 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).