y-cruncher Multi-Precision Library

A Multi-threaded Multi-Precision Arithmetic Library

(Powered by y-cruncher)

(Last updated: March 3, 2016)

 

Shortcuts:

YMP Library:

Large Number Objects:

Low-Level Programming:

Objects Library

 

The YMP library exposes two of the five large number types in y-cruncher:

Beyond these, there is also BasicInt, ExactFloat, and SwapFloat. But at this time, they are not part of the public interface.

 

All classes are templated to the word size. Currently only 32-bit and 64-bit word sizes are supported. Both sizes are supported on all architectures regardless of the native word size of the hardware. Needless to say, the word sizes that matches the native word size is usually the more efficient one.

 

More on Object Types.

 

 

Ease-of-use vs. Performance:

 

When designing bignum classes, there are conflicting goals between safety/ease-of-use and flexibility/performance.

 

A strictly OOP design with full encapsulation is easy and safe to use. But the constant memory allocation and page-commit overhead comes with a tremendous performance hit. At the other extreme, going bare metal gives the user full control of everything (including the ability to reuse memory). But it becomes extremely difficult and error-prone to do anything.

 

One of the greatest barriers to exposing a public interface for y-cruncher's internals is that these internal objects are on the "wrong end" of the trade-off. Anyone who uses y-cruncher enough will notice that it allocates all the memory it needs at the start of a computation and frees all of it at the end. The result is a flat memory usage curve. How is this possible? Bare metal programming. Yes, it's difficult to do. But if pulled off correctly, it can be very efficient.

 

 

Class Hierarchy:

 

To satisfy both uses cases, YMP provides interfaces for both.

 

For each of the object types in YMP, there are 3 classes:

If none of these are suitable, you can build your own on top of the low-level functions.

 

 

The base classes:

 

The base class holds all the metadata about the bignum as well as one or more pointers to a buffer. The base class maintains a concept of an "allocated" size and an "actual" size much like std::vector. The internal buffer is the allocated size which the object is allowed to use. The actual array of 32-bit or 64-bit words that makes up the bignum is stored entirely inside the buffer and does not necessarily start from the beginning of the buffer.

 

The base class is abstract. Ownership of the buffer is left to the sub-classes. The only public methods in the base class are const-getters.

 

To allow for inter-compatibility between the subclasses, all functions and methods for all classes that take a const-input will take a reference to the base class. This allows instances of either subclass (raw or owner) to be used as inputs into each other's functions and methods.

 

 

"Owner" classes with RAII:

 

The "owner" subclass is a standard C++ object with RAII and full encapsulation. This class is the easiest to use. All the memory allocation is completely hidden away. However, "owner" classes are less performant due to memory allocation overhead.

 

Some of methods have alternate versions that provide greater control over parameters like scratch memory and lookup tables. But full control over all memory allocation can only be done with the "raw" subclass.

 

Internally, the owner subclass extends the base class with a smart pointer that owns the buffer pointed to by the base class. Small number optimization may be used to eliminate small memory allocations. Most of the methods in owner classes are merely thin wrappers over those of the "raw" subclass.

 

 

Bare Metal "raw" classes:

 

The "raw" subclass is the bare-metal class. It is a POD type that maintains only metadata and a pointer to the large number in memory. Since it has no concept of resource ownership, multiple "raw" classes may point to the same buffer.

 

"Raw" classes do no memory allocation or resource management. The user is given full control of almost everything. Output buffers need to be specified by the user. Large multiplication functions take a struct containing more parameters. y-cruncher exclusively uses raw classes.

 

Raw objects have 3 states. These states are not enforced and the user must manually keep track of them.

  1. Completely invalid.
  2. Valid buffer, invalid value.
  3. Valid buffer, valid value.

State 1 is when every single field is uninitialized. Any attempt to read the object or write to its buffers is undefined behavior. Since all constructors leave the object in at minimum state 2, this state is not possible without doing something like a malloc + cast.

 

State 2 is an object that has a valid buffer range, but an uninitialized value. Any attempt to read the object's value is undefined behavior. Objects in this state can be used as output operands. Functions will write the output of an operation into the object utilizing its buffer. If the buffer isn't large enough, an exception will be thrown.

 

State 3 is when the object is completely valid. It can be read from and written to. Objects in this state can be used as both input and output operands. When used as an output operand, the object will be overwritten and the new value written into the buffer. If the buffer isn't large enough, an exception will be thrown.

 

Use common sense when dealing with multiple raw objects that have overlapping buffers. If object A modifies its buffer that's shared with object B, object B's value becomes invalidated and therefore goes to state 2.

 

 

Object Types:

 

BigInt:

BigInt is a large integer type.

BigFloat:

BigFloat is a large floating-point type.

 

General Rules:

 

There are a number of usage rules that apply equally to all objects.