Arbitrary Precision - Easy-to-use C++ Library for Long Integer Arithmetic

About the Library

Arbitrary Precision (AP) is available on GitHub: https://github.com/arbitrary-precision/ap. Its philosophy is intuitiveness. The library must be easy to add to a project, easy to use, and easy to have as a dependency.

Core traits of the library are:

• Header-only by default. Source compilation is an optional feature.
• Cross-platform (build verified for MSVC and GCC).
• Supports multiple standards (C++11, C++14, C++17).
• No warnings during compilation.
• Thoroughly tested.

Version 1.2.0 offers two types - signed and unsigned fixed-size long integer. Both have the following interface:

• Copy and move constructors. Both are cross-class - it is possible to copy or move integer of any size and signedness to any other integer.
• Constructors, methods, and operators for std::string and const char*. The verified supported base range is [2, 16].
• Arithmetic, bitwise, and comparison operators are overloaded to work with long integers of different sizes or signedness.
• Exception from the above: bit shift operators accept only unsigned long long as a right operand (temporarily).
• All operators and constructors for the basic integer types are overloaded.
• istream/ostream overloads, with srd::ios_base::fmtflags detection for base.

Using the Code

Library integration is simple. It is needed to clone the repository and include "ap.hpp" header.
In the global scope, two templates are available: ap_int<size_t> and ap_uint<size_t>. Template parameter is a type size in bits.

There is no need to describe and demonstrate the behavior in detail since the types behave like int. Short example:

#include <iostream>
#include <ap/ap.hpp>

ap_int<256> fact(ap_uint<256> val)
{
    ap_int<256> result = 1; // copy-initialization.
    for (ap_int<128> i = 1; i <= val; ++i) // Increment, comparison of different types.
    {
        result *= i; // Multiplication of different types.
    }
    return result;
}

int main()
{
    std::cout << fact(30) << std::endl; // Implicit construction from any basic type.
    std::cout << fact(ap_int<128>(30)) << std::endl;     // Implicit, size is less.
    std::cout << fact(ap_uint<256>(30)) << std::endl;    // Same type.
    std::cout << fact(ap_int<256>(30)) << std::endl;     // Implicit int to uint 
                                                         // (uint to int is explicit).
    // std::cout << fact(ap_uint<512>(30)) << std::endl; // Must be explicit, size is greater.
    return 0;
}

What to remember when using AP integers:

• Signed integers behave as if they have two's complement representation. There is no extra sign bit.
• Division by zero triggers the native behavior of a platform.
• Bit shifts are arithmetic. If a shift value exceeds the size of an integer, the result is 0. Exception: if it is a right shift and the integer is negative, the result is -1 (sign-fill).
• Size in bits must be greater than the size of unsigned long long.
• Size in bits should be a multiple of 64. it is not mandatory, but there is no need to play with fire.

Long integer types also offer flexible string conversion interface. The most flexible method to convert from any string is "set":

integer& set(const char* str, 
index_t size = 0, index_t base = 0, const char* digits = AP_DEFAULT_STR);
// str    - string which represent the value.
// size   - string size. By default retrieved using strlen().
// base   - base used in string. By default determined automatically.
// digits - symbols to represent digits. By default "01234567890ABCDEF".

There are overloads available, which call this method:

// set() for std::string.
integer& set(const std::string& str, index_t base = 0, const char* digits = AP_DEFAULT_STR)

// Constructors.
explicit integer(const std::string& str, index_t base = 0, 
                 const char* digits = AP_DEFAULT_STR)
explicit integer(const char* str, index_t size = 0, index_t base = 0, 
                 const char* digits = AP_DEFAULT_STR);

// Assignments.
integer& operator=(const std::string& str)
integer& operator=(const char* str)

There are two methods to convert to std::string:

// Flexible approach.
std::string str(index_t base = AP_DEFAULT_STR_BASE, 
                const char* digits = AP_DEFAULT_STR) const;
// base   - base to convert to. By default 10.
// digits - symbols to represent digits. By default "0123456789ABCDEF".

// Converts to decimal.
explicit operator std::string() const;

Example:

#include <iostream>
#include "ap/ap.hpp"

int main()
{
    ap_int<128> a{"0b1"};          // Trivial case, everything is determined automatically. 
    ap_int<128> b{std::string("-Z"), 3, "XYZ"}; // Custom symbols.
    ap_int<128> c;
    c = "3";                       // Assignment.
    ap_int<128> d; 
    d.set("-1009736", 4, 2);       // Explicitly set string size to 4 and base to 2. 
                                   // Value is "-100", or -4.
    
    // Decimal view: 1 -2 3 -4:
    std::cout << std::string(a) << ' ' << std::string(b) 
    << ' ' << std::string(c) << ' ' << std::string(d) << '\n';

    // Binary view: 0b1 -0b10 0b11 -0b100:
    std::cout << a.str(2) << ' ' << b.str(2) 
    << ' ' << c.str(2) << ' ' << d.str(2) << '\n';

    // Custom ternary view: Y -Z YX -YY:
    std::cout << a.str(3, "XYZ") << ' ' << b.str(3, "XYZ") 
    << ' ' << c.str(3, "XYZ") << ' ' << d.str(3, "XYZ") << '\n';
}

Things to remember:

• Regardless of the base, the resulting string has "sign and magnitude" representation.
• If the base is binary, octal, or hexadecimal, the corresponding prefix is always appended.

I/O: iostream operators are available
Input: reads std::string from an input stream and converts it to a long integer
Output: converts to the base, specified by format flags, and then writes to an output stream

Source Compilation Mode

If macro AP_USE_SOURCES is defined, then .cpp files must be added to build and compiled. If you prefer the classical way of source code organization, this option is for you. Note that if .cpp files are added to build, but AP_USE_SOURCES is not defined, compile guard will handle this. Consider pair of sources: asm.hpp with declarations and asm.cpp with definitions:

// asm.hpp
#ifndef DEOHAYER_AP_ASM_HPP
#define DEOHAYER_AP_ASM_HPP

// ...
// Declarations.
// ...

// If .cpp shall not be compiled - include it in .hpp.
#ifndef AP_USE_SOURCES
#define DEOHAYER_AP_ASM_CPP 0 // For compile guard compatibility.
#include "asm.cpp"
#endif

#endif

// asm.cpp
#ifndef DEOHAYER_AP_ASM_CPP
#define DEOHAYER_AP_ASM_CPP 1 // Source compilation case.
#endif

// Code will not be "preprocessed away" only if the "#if" expression below is true.
// .hpp: sets macro to 0. The code will be actually present in .hpp file only if
//       AP_USE_SOURCES is not defined.
// .cpp: sets macro to 1, if AP_USE_SOURCES is not defined, expression will be 1 == 0.
#if (DEOHAYER_AP_ASM_CPP == 1) == defined(AP_USE_SOURCES)

// ...
// Definitions.
// ...

#endif

Performance

Measurement is straightforward. For the given bit size of an integer:

• Generate the left operand, filled by 25%-50%. In other words, any bits beyond the lower half will be 0.
• Generate the right operand, filled by 12-25%.
• Perform the operation, measure time in nanoseconds.
• Steps above repeated 10000 times, total time is a KPI.

This approach does trigger long division and guarantees that multiplication of the size fits into the type (complete multiplication will be done). The table shows the ratio "AP/Boost" for the given integer bit size and operation:

Bit size

<<

>>

1.74487

2.23426

2.43082

6.32478

5.87538

2.17034

1.6978

1.23195

1.43016

1.16948

0.862215

0.96964

1.43523

1.63936

0.960102

1.12024

0.980719

0.444539

0.487134

1.21475

1.38079

10240

1.41084

1.23715

0.933805

0.380653

0.408858

1.32783

1.36085

Compiled with GCC version: Ubuntu 7.5.0-3ubuntu1~18.04.

AP is considerably slower only on 128-bit values because it is not optimized for such cases.
In all other cases, AP is on par with Boost. Linear functions are slightly slower. Non-linear ones are faster.

Note: https://github.com/arbitrary-precision/ws/blob/master/src/measure/measure.cpp was used for the measurements. But because Boost uses __int128 internally, I had to switch AP to this type too (in root CMakeLists.txt):

add_executable(measure ${MEASURE_SRC_FILES})
target_compile_options(measure PUBLIC
  -DAP_WORD=unsigned\ long\ long
  -DAP_DWORD=unsigned\ __int128
) 

__int128 is not fully supported yet - it breaks interaction with the basic types. However, it has no negative impact in other cases, therefore suitable for the measurement.

Implementation

Arbitrary Precision has three fundamental types:

• word_t - an array of word_t represents a long integer value. Type can be set via AP_WORD macro.
• dword_t - holds a result of an operation on two word_t-s. It allows tracking carry, borrow, etc. Type can be set via AP_DWORD macro.
• index_t - same as size_t.

There are five core concepts:

• dregister<T> (core.hpp) - POD struct, a lightweight sign and magnitude representation of the long integer. Consists of: words - pointer to an array of word_t; capacity - array size; size - number of digits which represent the current value; sign - indicates whether the value is negative. T is a type of the pointer. Either const word_t* or word_t*.
• integer<size_t, bool> (integer.hpp) - container that owns an array of words. ap_int<> and ap_uint<> are partial specializations of this template.
• Algorithm functions (asm.*) - pure algorithms. They put strict constraints on their dregister<> operands, work only with non-negative values. Responsibility: perform actual operation word-wise.
• Internal functions (integer_api.*) - two sets of functions. Each set treats all dregister<> operands either as signed or unsigned. No constraints on operands. Responsibility - adjust operands, call algorithm, perform normalization afterwards.
• External functions (integer.hpp) - methods and operators of the integer<> class. Responsibility - grant cross-type interaction and call internal functions.

Normalization is a process, which ensures that dregister<>, represents the value correctly (is normalized):

• size must be set in a way, that words[size - 1] is not 0. Size 0 means that integer represents value 0.
• sign must be 0 if size is 0.
• (signed only) Value represented by dregister<> must be in range [-2n, 2n - 1], where n - capacity of the dregister<> in bits. It means granting two's complement behavior for the library user.

Testing

The problem is how to cover all the possible scenarios and still have a transparent, reproducible approach. The solution is to use all possible parameter combinations:

• capacity. 2 cases: large (512 bits) or small (256 bits), for 3 operands (left, right, out). 8 combinations. This is the only parameter where the output dregister<> is considered. The output might be too small to hold the value - wrapping behavior is tested too.
• size. 5 cases: 1 word, 25%, 50%, 75%, 100% of the total capacity is used. 25 combinations for the two operands.
• signedness (not sign). 2 cases: signed and unsigned. 4 combinations for the two operands.
• Bit pattern. 10 cases, shown in the table. 100 combinations for the two operands.

Name Pattern All zeros 00000000 00000000 ... 00000000 00000000 All ones 11111111 11111111 ... 11111111 11111111 Small chess 0 01010101 01010101 ... 01010101 01010101 Small chess 1 10101010 10101010 ... 10101010 10101010 Large chess 0 00000000 11111111 ... 00000000 11111111 Large chess 1 11111111 00000000 ... 11111111 00000000 Only LSB 00000000 00000000 ... 00000000 00000001 Only MSB 10000000 00000000 ... 00000000 00000000 Missing LSB 11111111 11111111 ... 11111111 11111110 Missing MSB 01111111 11111111 ... 11111111 11111111

The total number of cases for a single binary operation is 80000. Testing is performed under valgrind on internal and external functions. All tests pass without any complaints from valgrind.

Future Improvements

• C++20 compliance
• Support of implementation-specific integer types (__int128)
• Optimization of different routines
• Documentation
• More functions (sqrt, lcm, gcd, pow, etc.)
• Floating-point type
• Assembly optimization

History

• 13th December, 2021: Initial version