Formulas and Algorithms

By Alexander Yee

 

(Last updated: January 29, 2017)

 

Back To:

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

 

y-cruncher has two algorithms for each major constant that it can compute - one for computation, and one for verification.

 

All complexities shown assume multiplication to be O(n log(n)). It is slightly higher than that, but for all practical purposes, O(n log(n)) is close enough.

 

---

Square Root of n and Golden Ratio

1st order Newton's Method - Runtime Complexity: O(n log(n))
Note that the final radix conversion from binary to decimal has a complexity of O(n log(n)²).

 

There are no secondary formulas for either sqrt(n) or the Golden Ratio. Verification can be trivially done as:

• sqrt(2) and sqrt(200) are the same but the digits shifted over by 1.
• Golden Ratio and sqrt(125) are also essentially the same.

 

---

e

Taylor Series of exp(1): O(n log(n)²)

Taylor Series of exp(-1): O(n log(n)²)

 

---

Pi

Chudnovsky Formula: O(n log(n)³)

Ramanujan's Formula: O(n log(n)³)

 

---

Log(n)

Machin-Like Formulas: O(n log(n)³)

Starting from v0.6.1, y-cruncher is able to generate and utilize machin-like formulas for the log of any small integer.

Generation of machin-like formulas for log(n) is done using table-lookup along with a branch-and-bound search on several argument reduction formulas.

 

---

Zeta(3) - Apery's Constant

Amdeberhan-Zeilberger Formula 2: O(n log(n)³)

Amdeberhan-Zeilberger Formula 1: O(n log(n)³)

 

---

Lemniscate

Gauss Formula: O(n log(n)³)

Sebah's Formula: O(n log(n)³)

 

Both of these formulas were pulled from: http://numbers.computation.free.fr/Constants/PiProgram/userconstants.html

 

Note that the AGM-based algorithms are probably faster. But y-cruncher currently uses these series-based formulas because:

1. It lacks an implementation of sqrt(N) for arbitrary N. It only supports N being a small integer.
2. There already is a series summation framework that can be easily applied to the ArcSinlemn() function.

 

---

Catalan's Constant

Lupas Formula: O(n log(n)³)

 

 

Huvent's Formula: O(n log(n)³)



y-cruncher uses the following rearrangement of Huvent's formula:

 

---

Euler-Mascheroni Constant

Brent-McMillan (alone): O(n log(n)³)



                

 

 

Brent-McMillan with Refinement: O(n log(n)³)



                          

Note that both of these formulas are essentially the same.
Therefore, in order for two computations to be independent enough to qualify as a verified record, they MUST be done using different n.

For simplicity of implementation, y-cruncher only uses n that are powers of two - which serves a dual purpose of allowing the use of (the easily computed) Log(2), as well as lending itself to shift optimizations.

 

---

Series Summation:

 

Most of the formulas above involve an infinite series of some sort. These are done using standard Binary Splitting techniques with the following catches:

• Precision is tightly controlled to keep operands from becoming unnecessarily large.
• The cutting points for the binary splitting recursions are usually significantly skewed in order to reduce memory usage and improve load-balance.
• Series summation is partially done backwards. The lowest terms (terms with the largest index) are summed first. The motivation and details for this is quite intricate and goes hand-and-hand with the skewing. So I won't go into that.

This series summation scheme (including the skewed splitting and backwards summing) has been the same in all versions of y-cruncher to date. All of this is expected to change when GCD factorization is to be incorporated.