(Last updated: July 11, 2015)

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,

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)^{2})

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)^{2})

Taylor Series of exp(-1):

O(n log(n)^{2})

Pi

Chudnovsky Formula:

O(n log(n)^{3})

Ramanujan's Formula:

O(n log(n)^{3})

Log(n)

Machin-Like Formulas:

O(n log(n)^{3})

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)^{3})

Amdeberhan-Zeilberger Formula 1:

O(n log(n)^{3})

Lemniscate

Gauss Formula:

O(n log(n)^{3})

Sebah's Formula:

O(n log(n)^{3})

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:

- It lacks an implementation of sqrt(N) for arbitrary N. It only supports N being a small integer.
- 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)^{3})

Huvent's Formula:

O(n log(n)^{3})

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

Euler-Mascheroni Constant

Brent-McMillan (alone):

O(n log(n)^{3})

Brent-McMillan with Refinement:

O(n log(n)^{3})

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

For simplicity of implementation, y-cruncher only usesnthat 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.