y-cruncher - Language and Algorithms

By Alexander J. Yee

 

(Last updated: December 31, 2013)

 

 

Back To:

Implementation (as of v0.6.3):

 

General Information:

Libraries and Dependencies:

Compilers:

Other Internal Requirements:

Overall Design:

y-cruncher's design is split into 3 major layers.

 

Formulas:

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)2).
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.
 
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:

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


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



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

 
Euler-Mascheroni Constant

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



                          


Brent-McMillan (alone): 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 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.

 

Arithmetic Algorithms:

 

Multiplication:

Like most bignum programs, y-cruncher uses different multiplication algorithms for different sizes:

 

As of v0.6.3, y-cruncher uses:

*Standard libraries like GMP avoid the use of floating-point FFTs due to the difficulty of proving bounds on round-off error. But with modern SIMD, the performance of floating-point is through the roof. So rather than throwing all this computational power away, y-cruncher utilizes it to the maximum extent.

 

y-cruncher fully exploits floating-point algorithms and ensures their accuracy by means of conservative parameter selection and algorithmic error-detection. Although this is not proven to be correct for all inputs, the probability that y-cruncher's multiplication returns an undetected incorrect value is less than the probability of a silent hardware error. So in that sense, y-cruncher is arguably more reliable than other implementations that lack algorithmic error-detection.

 

**The last two of these algorithms (Hybrid NTT and VST) are homebrew algorithms that were developed between 2008 - 2012. Both of them are currently unpublished.

 

 

The following popular algorithms are currently not used by y-cruncher:

With modern SIMD, the floating-point FFT asserts complete dominance over everything from 500 decimal digits up to the point where it no longer fits in CPU cache.

This completely displaces 3-way Toom-Cook as well as a good portion of the sizes that are normally covered by SSA.

 

Of the three of these, the NTT over primes algorithm is the only one that y-cruncher may conceivably pick up in the near future.

 

 

 

Inverse and Roots:

Reciprocals, division, and square roots are all done using 1st order Newton's Method.

 

Log(n):

Prior to v0.6.1, only log(2) and log(10) were supported using hard-coded machin-like formulas. A generic log(n) was needed for Ramanujan's formula for Catalan's constant. That was implemented using Arithmetic-Geometric Mean (AGM).

 

In v0.6.1, Ramanujan's formula for Catalan's constant was removed - thereby removing the need for a generic log(n). Instead, v0.6.1 supports the computation of log(n) for any small integer n. This is done using a formula generator that generates (at run-time) machin-like formulas for arbitrary small integer n.

 

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.

 

 

Radix Conversion:

 

Series Summation:

Series summation is done using standard Binary Splitting techniques with the following catches:

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.