C++ compile-time bignum library [closed]

Question

Is there any compile-time library (template metaprogramming) for arbitrary-precision arithmetic in C++?

I need this to help with fixed-point arithmetic and binary scaling in my program for AVR microcontrollers. For example, when two numbers each with their own bounds are multiplied, the bignums would be used to compute the bounds of the result, and move the fraction point in the inputs and/or outputs as appropriate. But the bounds of the result may not be representable in the standard integer types.

Inhaler

What do you mean by "template metaprogramming"? "BigInteger" type libraries practically always use dynamic memory allocation. Otherwise, you can just utilize a larger type (i.e. signed int64 for multiplying two signed int32's) – Bechuanaland

@Bechuanaland I mean, well, template metaprogramming. This link should give you some idea how bignums could be implemented at compile time: alpmestan.wordpress.com/2009/12/03/… . In essence, a compile-time bignum would be a (recursive) type, and the compiler would deal with memory allocation. – Inhaler

@Bechuanaland A large integer type is not sufficient - my problem is about dealing with the bounds of types at compile time, and I need to have compile-time checks something along the lines of "A + B < INT64_MAX && A + B > INT64_MIN". Compile-time bignums would allow these to be written "directly" without having to worry about integer overflows. – Inhaler

Answer 1

Since dynamic allocation is not allowed during compile-time, you can only have a type that's arbitrarily long at run-time. That's why standard types like std::string or std::vector doesn't have any constexpr constructors. The same applies to arbitrary-precision math. A workaround is to declare the variable as static so that it's computed only once at startup

However if you know the range of your values then you can use ctbignum which is a Library for Multiprecision Compile-Time and Run-Time Arithmetic (including Modular Arithmetic)

Constexpr C++17 Big-Integer / Finite-Field library

This is a header-only template library for fixed-width "small big-integer" computations, for use during run-time as well as compile-time. By "small big integers", we mean numbers with a few limbs (in other words, a few hundred bits), typically occurring in cryptographic applications.

Boost.MPL may be another choice in when the limits are known

In C++20 some kind of dynamic allocation in constexpr functions is allowed, so there may be a real compile-time bignum library then

But I don't think arbitrary-precision would be the solution for solving fixed-point arithmetic. That completely defeats the purpose and you can simply use a floating-point right from the beginning. So this is likely an XY problem and you should ask how to do those fixed-point operations instead

Chondro

Answer 2

Possibly Boost.Multiprecision is what you're looking for.

Bechuanaland

The documentation specifies "However, you will not be able to perform compile-time arithmetic on such types." – Dittman

Answer 3

[disclaimer : I'm the main developer and maintainer of the aerobus library]

In a development branch of aerobus, you can find a c++11 implementation of big integers. All is done via variadic templates. So far, only addition and substractions are supported but division may be added soon (and therefore, big ratios and polynomials).

Bigint are in base 2^32 (32bits words), and you can write code like that :

// 100 - 99 = 1
using b = bigint_pos<UINT32_MAX, UINT32_MAX>;
using c = bigint_pos<1, 0, 0>;
using d = bigint::sub_t<c, b>;
if(!bigint::eq_v<bigint::one, d>) {
    return 1;
}

That may (or not) suit your needs. Feel free to open issues or to contribute directly.

Booma