Aarith: An Arbitrary Precision Number Library

Aarith is a header-only, arbitrary precision number library for C++. It is intended to be used as a drop-in replacement of the native data types.

Aarith currently supports

IEEE 754 like floating-point numbers of arbitrary bit-width for both, the exponent and the mantissa
Two’s complement integers of arbitrary bit-width (signed and unsigned)

Installation

Copy the contents of this repository into a <destination> folder and include Aarith in your CMake build using:

add_subdirectory(<destination>)

You can then link your target <targetname> against Aarith with:

target_link_libraries(<targetname> PUBLIC aarith::Library)

Requirements/Dependencies

Aarith is intended to be used without introducing further dependencies. You can use it immediately without having to further software.

Tests

If you want to run the tests, you need catch2, the Google benchmark library.

If you want to run the tests against other number libraries, you need to install MPFR and MPIR.

Documentation

The documentation is [available online](add link!). If you want to build it locally, you need Python, Sphinx, the readthedocs Theme, breathe and Doxygen.

Quick Start

Aarith is intended to be used as a drop-in replacement for the native data types. You only need to include the headers and can start using Aarith immediately:

#include <aarith/float.hpp>
#include <aarith/integer.hpp>

int main()
{
    using namespace aarith;
    uint64_t a = 10, b = 20;
    uinteger<64> a_ = 10, b_ = 20;
    std::cout << "a + b = " << (a + b) << "\n";
    std::cout << "a_+ b_ = " << (a_ + b_) << "\n";

    float x=3.0F, y=2.5F;
    floating_point<8,23> x_{3.0F}, y_{2.5F};
    std::cout << "x + y = " << (x * y) << "\n";
    std::cout << "x_+ y_ = " << (x_ * y_) << "\n";
}

This gives the expected output of

$ ./arithmetic_example
a + b = 30
a_+ b_ = 30
x * y = 7.5
x_* y_ = 7.5

Hint

To make usage of Aarith more convenient, the following type aliases are shipped with Aarith:

using half_precision = floating_point<5, 10, uint64_t>;
using single_precision = floating_point<8, 23, uint64_t>;
using double_precison = floating_point<11, 52, uint64_t>;
using quadruple_precision = floating_point<15, 112, uint64_t>;
using bfloat16 = floating_point<8, 7, uint64_t>;
using tensorfloat32 = floating_point<8, 10, uint64_t>;

Further examples for how to use aarith can be found at the Uses Cases and in the examples and experiments source code folders (the tests can also give a good idea of how to use aarith).

We also refer the interested user to [Keszocze2021].

Use Cases

In the following, use cases for Aarith will be shown. (So far, we only present one)

The FAU Adder

The FAU Adder (see [Echavarria2016]) splits the operands into a most-significant part (MSP) and least-significant part (LSP) and cuts the carry chain in between these parts. To reduce the error, some bits of the LSP (shared_bits in total) are used the predict the carry.

The following code implements the FAU adder. This piece of code is intended to show how easily individual bits ca be accessed when designing hardware units.

template <size_t width, size_t lsp_width, size_t shared_bits = 0>
uinteger<width + 1> FAUadder(const uinteger<width>& a, const uinteger<width>& b)
{

    // make sure that the parameters
    static_assert(shared_bits <= lsp_width);
    static_assert(lsp_width < width);
    static_assert(lsp_width > 0);

    //***********************
    // Extract MSP and LSP
    // can't use structured binding (i.e. `` auto [msp, lsp] = split<lsp_index>(a)``) as msp and lsp need
    // not bee of same width
    constexpr size_t lsp_index = lsp_width - 1;
    const auto a_split = split<lsp_index>(a);
    const auto b_split = split<lsp_index>(b);

    const uinteger<lsp_width> a_lsp = a_split.second;
    const uinteger<lsp_width> b_lsp = b_split.second;

    constexpr size_t msp_width = width - lsp_width;
    const uinteger<msp_width> a_msp = a_split.first;
    const uinteger<msp_width> b_msp = b_split.first;
    //***********************

    // sum up LSP including the computation of the carry
    uinteger<lsp_width + 1> lsp_sum = expanding_add(a_lsp, b_lsp);

    // remove the carry for later use
    uinteger<lsp_width> lsp = width_cast<lsp_width>(lsp_sum);

    bool predicted_carry = false;
    // conditionally perform carry prediction
    if constexpr (shared_bits > 0)
    {
        // extract the shared bit of both operands
        uinteger<shared_bits> a_shared = bit_range<lsp_index, lsp_index - (shared_bits - 1)>(a);
        uinteger<shared_bits> b_shared = bit_range<lsp_index, lsp_index - (shared_bits - 1)>(b);

        // compute the carry
        uinteger<shared_bits + 1> shared_sum = expanding_add(a_shared, b_shared);

        predicted_carry = shared_sum.msb();
    }

    // if there was a carry but we did not predict one (i.e. it wasn't used in the MSP)
    // we need to perform an all1 error correction
    if (lsp_sum.msb() && !predicted_carry)
    {
        lsp = lsp.all_ones();
    }

    // finally put MSP and LSP together
    const uinteger<msp_width + 1> msp = expanding_add(a_msp, b_msp, predicted_carry);

    uinteger<width + 1> result{lsp};

    const auto extended_msp = width_cast<width + 1>(msp);
    result = add(result, extended_msp << lsp_width);
    return result;
}

Aarith’s Philosophy

Aarith is build with the following points in mind:

Aarith is should easy to use:
- e.g. no functions such as u_add_32(num_a, num_b), just plain num_a + num_b
- easily define new number formats, e.g. using bfloat16 = floating_point<8, 7, uint64_t>; (see [Burgess2019])
Aarith should allow for easy access to the individual bits of the stored number:
- for the design of new hardware units (e.g., implementing arithmetic units such as the FAU Adder [Echavarria2016], see example
- for debugging unexpected results
Aarith should be publicly available

Easy to use

We want Aarith to blend in with C++. That is, we want it to provide the usual operations, such as + or <<.

The following program computes the sum of 1.0 and 2.0 using 200 digits using the MPFR library.

#include <stdio.h>

#include <gmp.h>
#include <mpfr.h>

int main (void)
{
  unsigned int i;
  mpfr_t s, t, u;

  mpfr_init2 (t, 200);
  mpfr_set_d (t, 1.0, GMP_RNDD);
  mpfr_init2 (s, 200);
  mpfr_set_d (s, 2.0, GMP_RNDD);
  mpfr_init2 (u, 200);
  mpfr_add (s, s, u, GMP_RNDD);
  printf ("Sum is ");
  mpfr_out_str (stdout, 10, 0, s, GMP_RNDD);
  putchar ('\n');
  mpfr_clear (s);
  mpfr_clear (t);
  mpfr_clear (u);
  return 0;
}

The equivalent program using Aarith looks like this (the parameters for the exponent and mantissa width, i.e. E and M, need to be chosen large enough to fit a 200 digits number):

#include <aarith/float.hpp>
#include <aarith/integer.hpp>

int main()
{
    floating_point<E,M> x_{1.0F}, y_{2.0F};
    std::cout << "Sum is " << (x + y) << "\n";

}

No Surprises!

Aarith performs very little implicit type conversions. Most of the constructors are explicit. Especially, Aarith does not use typedef’s involving native data types. This is motivated by the following situation. Consider the following program:

uint8_t u8 = 42; uinteger<8> aarith_u8{u8};
std::cout << "uint8_t=" << u8
    << " (as int=" << int{u8} << ")"
    << " aarith::uinteger<8>="
    << aarith_u8 << "\n";

Running this program gives the following output:

$ ./output_example
uint8_t=* (as int=42) aarith::uinteger<8>=42

The asterisk * most likely was not was the user was expecting to see. Such a conversion is never carried out by Aarith.

Speed

Aarith is not extensively optimized for speed! There are other libraries for that. If raw speed is your goal, try MPFR and MPIR.

Literature

Keszocze2021

If you use Aarith (e.g., in your publication), please cite

Oliver Keszocze, Marcel Brand, Christian Heidorn, and Jürgen Teich. „Aarith: An Arbitrary Precision Number Library“, In: ACM/SIGAPP Symposium On Applied Computing (SAC’21). March 2021.

Bibtex:

@inproceedings{Keszocze2021,
  title = {Aarith: {{An Arbitrary Precision Number Library}}},
  booktitle = {ACM/SIGAPP Symposium On Applied Computing},
  author = {Keszocze, Oliver and Brand, Marcel and Heidorn, Christian and Teich, Jürgen},
  date = {2021-03},
  location = {{Virtual Event, South Korea}},
  series = {{{SAC}}'21}
}

Brand2020

Brand, M., Witterauf, M., Bosio, A., & Teich, J. (2020, July). Anytime Floating-Point Addition and Multiplication-Concepts and Implementations. In 2020 IEEE 31st International Conference on Application-specific Systems, Architectures and Processors (ASAP) (pp. 157-164). IEEE.

Brand2019

Brand, M., Witterauf, M., Hannig, F., & Teich, J. (2019, April). Anytime instructions for programmable accuracy floating-point arithmetic. In Proceedings of the 16th ACM International Conference on Computing Frontiers (pp. 215-219).

Burgess2019

Burgess, N., Milanovic, J., Stephens, N., Monachopoulos, K., & Mansell, D. (2019, June). Bfloat16 processing for neural networks. In 2019 IEEE 26th Symposium on Computer Arithmetic (ARITH) (pp. 88-91). IEEE.

IEEE754

754-2019 - IEEE Standard for Floating-Point Arithmetic

Echavarria2016

Echavarria, J., Wildermann, S., Becher, A., Teich, J., & Ziener, D. (2016, December). Fau: Fast and error-optimized approximate adder units on lut-based fpgas. In 2016 International Conference on Field-Programmable Technology (FPT) (pp. 213-216). IEEE.

Changelog

v1.0.1 – 27.02.2022

Added:

Add specializations for std::numeric_limits for the aarith::floating_point numbers
Add a constructor for aarith::word_array that takes a bit string as a parameter
Add a constructor for aarith::floating_point that takes a bit string as a parameter
Switched to Apache 2 license

Changed:

Update to Catch2 v2.13.18

Removed:

Fixed:

v1.0.0 – 15.03.2021

First public release of Aarith containing

Signed and unsigned arbitrary precision Two’s Complement integers
Arbitrary precision (for the exponent and mantissa) IEEE 754 floating-point like floating-point numbers

Two’s Complement Integers

Header aarith/integer/integers.hpp

The template classes integer and uinteger represent signed and unsigned integers of arbitrary, but compile-time static, precision stored in two’s complement format

The aarith integers exhibit the usual overflow/underflow behavior (i.e. modulo 2^n) which is not undefined behavior!

template<size_t Width, class WordType = uint64_t> class aarith::uinteger : public aarith::word_array<Width, WordType>

Public Functions

inline bool constexpr is_negative() const

Returns whether the number is negative.

Returns: Always returns false

inline explicit constexpr operator uint8_t() const

Converts to an uint8_t.