y-cruncher - Language and Algorithms

By Alexander J. Yee

 

(Last updated: April 14, 2015)

 

 

Back To:

 

Expanded Articles:

 

General:

 

Large Number Arithmetic:

 

Implementation (as of v0.6.8):

 

General Information:

 

Libraries and Dependencies:

y-cruncher has no other non-system dependencies. No Boost. No GMP. Pretty much everything that isn't provided by C++ is built from ground up.

 

 

Compilers:

 

Other Internal Requirements:

 

Code Organization:

 

y-cruncher used have a layered design where each layer is built upon the layer below it. Now it's mostly a collection modules:

Module Files Lines of Code Description
Public 48 4,872

The common support library. It provides a common interface for stuff like time, file I/O, and colored console output.

Digit Viewer 71 9,811

The bundled Digit Viewer.

BBPv2 33 4,255

The bundled BBP digit extraction app for Pi.

Launcher 8 564

The CPU dispatcher that picks the optimal binary to run.

It's module that builds the y-cruncher.exe and y-cruncher.out files.

y-cruncher 197 36,571

y-cruncher itself. This has most of the console UI, the implementations for all the constants, and the supporting math functions.

Objects 39 6,891

The bignum library. It provides the large number objects that are used by y-cruncher.

Modules 1,037 180,205

All the low-level arbitrary-precision arithmetic. It also has all the y-cruncher-specific support libraries such as the parallel computing framework and the multi-layer raid file.

Misc. 7 998

Stupid stuff like global settings, and version numbers/names.

Total: 1,401 244,167  

At one point, y-cruncher had almost 300,000 lines of code. But it has steadily gotten smaller as more and more of the program is migrated to C++.

 

 

Limits:

 

Like most other programs, there are theoretical limits to y-cruncher. Most of these limits are enforced by the program.

  32-bit 64-bit Comments

Ram Usage

~1.8 GiB ~ 1 EiB (1018 bytes)

Limited by memory address space.

Disk Usage

~ 1 EiB

Limited by 64-bit address space.

Task Decomposition

256

Arbitrary limit. Will be increased in the future.

RAID - Level 1

8 paths

 

RAID - Level 2

64 x Level 1 RAID groups

Limited by the # of bits in largest integer.

Will likely be increased in the future.

Largest Multiplication

(2.02 * 1018) x (2.02 * 1018) bits
(6.7 * 1017) x (6.7 * 1017)
decimal digits

Small Primes Number-Theoretic Transform:

  • 5 x 63-bit primes
  • Transform Length: 7 * 252

Convolution Length

4.03 * 1018 bits
1.34 * 1018 decimal digits

Computation Size

(for all constants)

1015 decimal digits

Limited by double-precision floating-point.*

BBP Hexadecimal Offset

246 - 1

Implementation-specific limitation.

*y-cruncher uses double-precision floating-point for things such as:

The result of these calculations are generally rounded to integers and must be accurate to +/- 1 for the program to operate correctly. The problem is that double-precision floating-point only has 53 bits of precision which will run out at around 9 * 1015. Since there is round-off error, the limit will certainly be lower. The exact limit is unknown and will vary with the different constants. Therefore y-cruncher arbitrarily caps it to 1015 decimal digits. Colloquially, I call this the "float-indexing limit".

 

There are currently no plans to raise this limit since it is already well beyond the capability of current hardware (as of 2015).

 

It is worth mentioning that the float-indexing limit is the only thing left that prevents y-cruncher from going all the way up to the 64-bit limit. Without it, it should be possible to reach 6.7 * 1017 decimal digits (the limit of the Small Primes NTT).

 

Getting rid of the float-indexing limit will require a floating-point type with at least a 64-bit mantissa. A viable option is to use 80-bit extended-precision via the x87 FPU although some compilers don't support it. But since "float indexing" isn't exactly a performance bottleneck, any sort of software emulation will probably work as well.