std::big_int

Contents

1. Introduction

C++ currently provides no portable support for integers wider than 64 bits. This is one of the oldest and most widely recognized gaps in the language, which authors have attempted to fill several times: [N1692] (2004), [N1744] (2005), [N2143] (2007), and [N4038] (2014) all proposed a std::integer class with infinite precision. Each of these attempts failed — not because there was a lack of interest or motivation, but because the task turned out to be too great of a challenge.

std::big_int is to long long what std::string is to char[N]: sure, a fixed size is sufficient for some use cases, but it comes with a constant threat of overflow and undefined behavior, and that threat is easily eliminated at some acceptable runtime cost.

1.1. Infinite-precision integers in other languages

The runtime cost of infinite-precision integers is often acceptable to the point where the default integer in many languages is not fixed-size. Even when infinite-precision is not the default, languages often provide an infinite-precision type in their standard library, or there is a commonly used third-party library that the ecosystem uses:

Beyond that, there are also many programming languages where some third-party support is available (e.g. gmp in C or Boost.Multiprecision in C++), but there isn't as much ecosystem convergence, so these are not listed in the table.

Furthermore, even when the language doesn't provide an infinite-precision integer type, this is typically part of the compiler regardless. For example, MSVC, GCC, and LLVM all internally have an infinite-precision integer, such as llvm::APInt. Any C23 compiler also needs such a type to implement optimizations like constant folding for _BitInt(N), unless it has a small BITINT_MAXWIDTH.

Not only are infinite-precision integers available in many languages, they are also used frequently:

2. Motivation

2.1. Use cases

In terms of utility, std::big_int use cases can be classified into two buckets:

1. The use case where integers are potentially big. That is, the numbers involved are typically still small, but since no fixed-width integers are used, they might sometimes be big.
2. The use case where integers are actually big.

std::big_int has many use cases, falling into one of those buckets:

2.2. std::big_int is a vocabulary type

An important reason why std::big_int should be in the C++ standard library is that it is a vocabulary type and may appear at library boundaries.

In some sense, std::big_int is an even more important vocabulary type than std::vector and std::string because there is no convenient fallback solution. If those containers were not available, users could still communicate at library boundaries by using pointers and sizes. Strings can be passed to other libraries as a char* (and maybe size_t), so while std::string is an important container type and helps with managing allocation ownership, it is arguably gratuitous as a vocabulary type. Similarly, if std::span and std::string_view were not available, they could easily be replaced with the pointer and the size that they wrap.

By comparison to contiguous containers and views, there is no widely established convention for passing large integers between libraries in C++, other than using their string representation, which comes at significant cost. Consequently, we see a fragmented ecosystem in C++, where every logging, database, cryptography, and serialization library has its own solution to passing big integers and often its own types. std::big_int could lay the foundation for passing big integers between libraries just as easily as in other languages.

2.3. std::big_int for convenience and correctness

Another reason why std::big_int needs to be in the standard library is that users would often avoid it otherwise, even when it is the right tool for the job. For example, it could be quite plausible that a library has to handle integers with more than 64 bits in some edge cases, but if the library author needs to add a dependency on the whole of Boost.Multiprecision to replace 2-3 lines of code using std::intmax_t with boost::multiprecision::cpp_int, they may just not do it.

C++ developers don't get a fair choice between a fixed-width type for performance and an infinite-precision type for correctness; they get to choose between readily available fixed-width types and adding a heavy dependency like GMP or Boost.Multiprecision for correctness, which they may not do, especially if that dependency is transitively forced onto their library users.

2.4. std::big_int is platform-dependent and hard to implement

Another reason why std::big_int needs to be in the standard library is that it's extremely difficult to implement and optimize, in part because the implementation depends heavily on the platform's hardware capabilities, many of which are not exposed portably in the language.

In general, the intrinsics necessary to implement std::big_int efficiently vary wildly from compiler to compiler and from architecture to architecture. It also varies a lot whether those intrinsics can be used during constant evaluation, and these implementation details are subject to frequent change and added features. Our [Reference-Impl] of std::big_int is a sea of if constexpr and #ifdef checks.

Overall, it is practically impossible or at least extremely difficult for a third-party library to keep up with all these details to implement the type optimally, across all compilers and all supported architectures. Features like these should ideally live directly in the compiler or in the standard library.

2.5. std::big_int should be a compiler intrinsic for constant evaluation

While a portable implementation of std::big_int is possible, an ideal implementation for constant evaluation simply delegates to the compiler's internal infinite-precision integer type (e.g. llvm::APInt in LLVM). This is because constant evaluation is relatively expensive compared to highly optimized multiprecision code in the compiler internals. A third-party library such as Boost.Multiprecision does not have the luxury of adding new compiler intrinsics, so the implementation quality could never match the potential of std::big_int.

A closely related issue is the implementation of the user-defined literal, which has the following interface in our proposal:

The problem is that there is no other form of operator""n that enables this syntax, and the char... form requires manual parsing of the digits during constant evaluation, rather than delegating this to the compiler. It would be much better if parsing could be done in the compiler (and it already does actually) to provide a form such as:

With this form,

• digit separators would be skipped automatically,
• base prefixes like 0x would be handled by the compiler, and
• forming the limb array would be done by the compiler, which is the expensive part,
• template instantiations would be avoided completely.

That being said, this new form of operator""n" is not part of this proposal, but it does demonstrate why some compiler support is needed.

3. Design

3.1. Design strategy

The most important anchor points of the design are:

• std::big_int should be elastic; that is, it should grow to the necessary size required to fit the result of an arithmetic operation.
• std::big_int should support custom allocators.
• std::big_int should expose small object optimization to the user.
• std::big_int should grant access to the underlying representation.
• std::big_int operations should be constexpr.

This culminates in the following library declarations:

Conceptually, a basic_big_int holds:

The underlying arithmetic is then implemented to operate on limb arrays, i.e. arrays of uint_multiprecision_t objects, agnostic of whether the integer value is stored in-place or dynamically.

3.2. Layout

3.2.1. std::uint_multiprecision_t

A user-facing integer type alias introduced by this paper is std::uint_multiprecision_t, which is an unsigned integer type with the following important properties:

• std::uint_multiprecision_t has no padding bits. Padding bits in a limb type would be wasteful and make things more difficult both for users and for implementations.
• std::uint_multiprecision_t is the widest type that has arithmetic hardware support.
• std::uint_multiprecision_t has no explicit minimum width, but effectively cannot be narrower than unsigned char due to being unpadded.

In summary, it is the unsigned integer type most suitable for multiprecision. Colloquially it is the largest unsigned integer which has arithmetic instructions.

Curiously, there is no existing type with the desired properties despite the abundance of type aliases in <cstdint> and <cstddef>:

• std::uint_fast32_t is at least 32 bits wide, which means that on 16-bit architectures, the multiprecision code would have two layers: the emulation of 32-bit integers on 16-bit hardware, and then the multiprecision of std::big_int operations. This is highly questionable because the point of std::uint_multiprecision_t is to have a type whose operations correspond directly to hardware instructions. Also, std::uint_fast32_t is not consistently 64 bits wide on targets with 64-bit arithmetic support.
• std::size_t often could be used as std::uint_multiprecision_t, but on targets like WASM32, it is only 32 bits wide despite WASM32 having 64-bit arithmetic instructions for i64. It would be extremely wasteful to only use 32-bit operations when 64 bits are available.
• std::uintptr_t typically has the same problem as std::size_t.
• unsigned long is only 32 bits wide on 64-bit Windows.
• unsigned long long is always 64 bits wide, even on 32-bit targets.

3.2.2. C compatibility

While std::big_int is not really C-compatible by virtue of being a class template full of C++ features, it is still possible to provide a C-compatible interface taking uint_multiprecision_t[] and implementing its functionality in C++. This relies on the fact that the internal layout of std::big_int is specified in detail.

However, this somewhat assumes that std::uint_multiprecision_t also becomes available in C, possibly in <cstdint> / <stdint.h>. Not having the type in C means that C users would need to recreate the type choice the implementation makes or use implementation-specific definitions like a predefined __UINT_MULTIPRECISION_T__ macro.

C compatibility ambitions are not in scope for the paper right now, but are worth exploring in the future.

3.2.3. Small object optimizations

std::big_int (or generally, infinite-precision integer types) benefit from small object optimization perhaps more than any other vocabulary type. This is because with a relatively small amount of in-place storage (e.g. 8 bytes for 64-bit numbers), a lot of applications would never need to allocate dynamic storage to hold the value, or only for extreme and unusual program inputs. Furthermore, once the numbers are huge enough to require dynamic allocation, the cost of multiprecision arithmetic often hugely outweighs the small amount of overhead caused by having a few unused bytes of in-place storage.

The optimization is also necessary to prevent excessive allocations for small intermediate results. For example, even for huge inputs x and y, the difference x - y, the quotient x / y, or the remainder x % y could still be fairly small numbers (possibly zero), and it is wasteful to dynamically allocate for tiny integers.

3.2.3.1. SOO customization

Because performing this optimization for std::big_int is such a no-brainer and any reasonable implementation should have it, we propose to expose it to the user via the min_inplace_capacity template parameter. This parameter specifies the minimum integer width that std::basic_big_int must be able to represent without dynamic allocation. While std::big_int should be used in most cases and provides a reasonable default, there may be scenarios where

• on 32-bit platforms, the capacity could be lowered to 32 or raised to 64 to prefer performance,
• on platforms where allocations are particularly expensive or where dynamic storage is very limited, the capacity could be raised to 128 or even 256.

3.2.3.2. Layout in our reference implementation

3.2.4. Sign and magnitude

std::big_int uses a sign-and-magnitude representation (as opposed to e.g. two's complement), and this is exposed to the user. While it may seem like constraining implementation freedom unnecessarily, the chosen representation impacts the complexity requirements of various operations. For example, if the sign bit is separately stored, then negation can be implemented in constant time by just flipping the sign bit, whereas for two's complement, it requires linear time because bits of the magnitude need updating.

Most implementations of infinite-precision integers use sign-and-magnitude representation, as does our [Reference-Impl]. This is not only due to those beneficial complexity requirements, but also because it simplifies the implementation greatly. For example: multiplicative operators like multiplication and division can be implemented solely in terms of the magnitude, and the sign bit of the result can be computed separately.

3.2.4.1. Bitwise operations

The only major downside of sign-and-magnitude representation is that it requires emulation of two's complement for bitwise operations, but this is relatively cheap and does not require an additional pass over the data.

3.2.5. Representation endianness

There are two options for the endianness of the representation:

• Most significant limb first (big endian).
• Least significant limb first (little endian).

For some operations, there is no significant difference in performance between these two. However, these are far from equally good options in specific cases. In particular, there are many common operations that shrink or truncate, like

• &= 0xFF,
• %= 10,
• subtraction between two close values,
• etc.

Whenever these operations are performed in-place, and we are left with, say, a single limb, that limb is already in the right place; only the limb count stored in the container needs to be updated.

The key insight is that truncation of little-endian representations is much cheaper because no limbs need to be moved. Similarly, zero-extension or sign-extension moves no limbs in a little-endian representation, but requires moving all limbs in a big-endian representation.

In practice, every implementation known to us uses little-endian representation because it is strictly better for the operations that are performed on integers in practice.

3.2.6. Access to the underlying representation

As mentioned in §3.1. Design strategy, a std::big_int is conceptually a union of uint_multiprecision_t inplace_storage[N]; and uint_multiprecision_t* dynamic_storage;. This storage should be directly accessible using a function. Currently, we facilitate this using:

The obvious downside of giving the user such direct access is that it breaks encapsulation, and it constrains the small object type that the implementation could use. For example, it isn't possible to have an __int128 inplace_storage because uint_multiprecision_t cannot alias __int128.

Despite those downsides, giving the user low-level access to the storage is necessary because it enables the user to provide additional operations on std::big_int without overhead.

Crucially, we only provide read access to the representation, not write access. Providing write access would make it easily possible to put the std::big_int into a corrupt state, like having a size() that doesn't match the number of bits in the representation, or producing negative zero.

3.2.6.1. Why not provide access using a random access range?

Rather than providing a std::span to the underlying representation, it would also be possible to provide a random access range. This would grant some more flexibility in the representation, like:

• Storing an unsigned __int128 or other type rather than a uint_multiprecision_t[] for in-place storage.
• Using tagged integer representations (see §3.2.8. Why not use tagged integers?).

However, we decided against random access iterators for a number of reasons:

• If the implementation actually makes use of the added design freedom and computes the uint_multiprecision_t representation on the fly in the small case, the iterator needs to check whether the integer is small or large on every iteration. This is especially annoying when the std::big_int currently holds an allocation, which is definitely just an array of uint_multiprecision_t in memory. We are concerned about the performance overhead.
• As explained above, the benefit of providing access to the limb array is that the user can extend the type with additional operations without overhead. If representation() returns a std::span, the user can actually do that. Otherwise, there should actually be a dynamic_representation() returning a std::span for the large case. Such a function would inevitably be used by the standard library to implement its operations without overhead. Even if provided, users would now need to handle the small and large cases separately.
• Getting access to the underlying contiguous range allows for less overhead and more SIMD-friendliness.

  If the user wanted to compare std::big_int to their own std::span<const uint_multiprecision_t> (an operation we don't directly provide but might be added in the future via a std::big_int_view type), this could be done by directly loading (unaligned) from the std::span bytes and from the std::big_int representation bytes into SIMD registers, then comparing 16-64 bytes in one SIMD instruction. In fact, our implementation delegates operator<=> to std::memcmp.

  By contrast, if the user only had access to a random access iterator, they would need to repeatedly assemble N results of operator*; they could not simply call std::memcmp.

• As explained in §3.2.2. C compatibility, providing a std::span enables C interoperability. The application may internally hold a std::big_int and pass its representations to C APIs as uint_multiprecision_t[] and size_t, similar to how std::string can interface with C thanks to c_str().

It is also important to understand that the C-compatible interface has implications even beyond std::big_int.

3.2.7. Why not use reference counting?

An idea very early in the design process was to use reference counting in order to avoid the issue explained in §3.4. Optimal operator overloads. That is, if std::big_int was essentially a shared_ptr<uint_multiprecision_t[]>, it would be possible to pass it cheaply by value.

While this idea seems clever at first, there are several problems:

• The same was historically attempted for types like std::string to no success. Boost implementers gave negative feedback on this idea being pursued for std::big_int, and Boost.Multiprecision performs no reference counting either. A key problem is difficulty of implementation.
• Reference counting needs to be atomic because in the standard library, read-only access like copy constructors is generally thread-safe. Atomic operations can have significant overhead.
• Actually making use of the optimization opportunity in the example above (that is, modifying std::big_int's data in-place if it has unique ownership) requires an atomic compare exchange (CAS): if the reference counter is currently one, set it to zero, otherwise other threads might believe they have unique ownership too. That also makes the std::move in the example necessary; we need permission to mess with the original object. Even with no contention, a CAS is a relatively expensive instruction.

By comparison, a std::big_int design with unique ownership avoids a lot of problems because it is statically known that it has unique ownership; no runtime check is needed.

3.2.8. Why not use tagged integers?

A potential alternative layout can be provided using tagged integer techniques, as explained in [MSR-TR-2022-17].

The paper explores further improvements upon the technique where two least significant bits are used in the short representation, which makes the happy path even faster because it eliminates the if statement at the start, among other improvements.

Overall, such techniques provide two key benefits:

• The container size is aggressively reduced to just a single pointer. By comparison, the layout in our reference implementation is two pointers large on 64-bit.
• The happy path for small integers is faster because it avoids a branch. At the assembly level, in the improved approach described in the paper, addition compiles down to just an add instruction followed by two cheap checks and easily predictable branches.

That being said, we decided not to pursue this approach for a number of reasons:

• If one actually wants to reduce the size to just a single pointer, not every 64-bit integer can be represented anymore. Many use cases involve just that, such as
  • reinterpreting double as a 64-bit integer,
  • generating random numbers 64 bits at a time,
  • performing modular arithmetic with large 64-bit moduli,
  • using a 64-bit bit mask or bit pattern for bit manipulation,
  • computing 64-bit hashes,
  • …
• As explained in §3.2.6. Access to the underlying representation, it is crucial for us to provide direct access to the representation of the integer. The tagged pointer approach implies we cannot simply return a span<const uint_multiprecision_t> but would need to return some kind of union between an array (for small values) and a span (for large values). This is substantially more complicated and makes the happy path slower as well.
• The tagged integer approach relies heavily on assumptions about pointer representation and on the ability to reinterpret pointers as integers and vice versa. The constexpr support is hard to implement without compiler magic because we would do union type punning, which is undefined behavior in C++. The only way around that is to always hold an allocation in the constexpr case, which sacrifices the ability to hold any std::big_int values in a constexpr variable (except zero perhaps), increases the complexity of the implementation, and presumably makes constant evaluation slower.

3.2.8.1. Problems with extendability

Furthermore, it is impossible for the user to extend the set of operations without overhead because the user has no access to the lowest-level details needed. Consider that in the example above, we can implement add_tagged optimally, ending in return (z - 1); because we know exactly how the tagged integer is represented.

Similarly, multiplication and division need to keep in mind that we are essentially performing a fixed-point operation with a constant fractional digit and require some bit-shifting and adjusting to handle that. Every operation deals with the issue slightly differently.

By comparison, the proposed layout involves a uint_multiprecision_t[] directly exposed to the user,, so the std::big_int API does very little hiding and abstracting. The user could actually implement a popcount function that is not a single CPU cycle slower than a standard library implementer when only using the std::big_int public API.

3.2.9. std::big_int is not a container

When looking at the API of std::big_int, one may be tempted to think of it as a contiguous container and even to define it as such. That is, rather than having representation(), std::big_int could have begin() and end() iterators, etc.

There are a few problems with this approach:

• It would be surprising for std::big_int to simultaneously act like an integer and a container.
• Code that calls size() and other member functions would always be interacting with std::big_int at the low-level representation level, which is not what most users should do. In our design, std::big_int::size() yields the size in bits, which abstracts from the width of std::uint_multiprecision_t.
• In our design, there is always at least one limb. This is in part because with small object optimization, there is always at least one limb of in-place storage anyway. This is convenient for anyone relying on representation().front() always being valid, but makes clear() and resize() weird since it's not actually possible to downsize the container to zero limbs.
• In our design, code that iterates over the representation does so using for (auto limb : x.representation()), which makes it abundantly clear that we are not iterating over, say, each bit. This clarity would be lost if we iterated directly over x.
• If std::big_int were a sequence container, it should presumably have push_back, append, etc. However, it's inherently confusing what back refers to in this context: in English, numbers are written from most significant to least significant, so the back is the least significant digit, but in our std::big_int representation, the back is the most significant limb. By contrast, it is clear that representation().back() is the most significant limb if the user knows how the representation is structured.
• Because the sign in the representation is separate from the limbs, it doesn't neatly fit into the mental model of a container. If there was a assign function that assigns a range of limbs, it couldn't assign the sign bit, so it would be a partial assignment and should be called assign_magnitude or assign_representation. However, if we need to clarify what we're assigning, this indicates that the idea of std::big_int is simply a container is unnatural. We would also need to check whether the call to assign generated a negative zero.
• There is a difference in terminology between std::big_int and a container. For example, reducing the size of an integer is called truncating, but the container function is called resize(). Similarly, setting to zero should be spelled set_zero() or = 0, not clear().

That being said, std::big_int still has an API that is similar to a contiguous container for the purpose of familiarity. This includes functions such as shrink_to_fit(), get_allocator(), size() (in bits), reserve() (amount of bits), etc. These are mostly about allocation management, not about iterating over the representation.

3.3. constexpr support

std::big_int also provides constexpr operations, similar to std::string.

Without any dedicated compiler intrinsics, this means that std::big_int manages an allocation, similar to std::string. That allocation is transient, i.e. it cannot persist to runtime. However, performing operations on a std::big_int and freeing all memory before the end of the constant expression is fine.

There is another layer to the design here, which is that std::big_int is mandated to perform small object optimization, and this is exposed to the user in the public API, rather than just being an optional optimization like for std::string. Because of this, we can have std::big_int values persist to runtime as long as the value is small enough to require no allocation.

3.3.1. Circumventing transient allocations

One additional restriction on implementations to make this behavior reliable is that they must never represent a basic_big_int dynamically when inplace storage is sufficient. At runtime, implementations might hold onto an allocation until shrink_to_fit is called because that allocation may be immediately useful in the next operation.

However, at compile time, we require that every operation behaves as if shrink_to_fit() was called on the result, so allocations are aggressively freed if at all possible. This is necessary because the result of the subtraction in the example might be stored in a constexpr variable, and this would fail unnecessarily because of constexpr allocation restrictions.

If we didn't have that behavior, constexpr std::big_int variables might randomly fail to compile from the perspective of the user, depending on the compiler, for no good reason.

3.4. Optimal operator overloads

The design includes operator overloads that are optimal, which requires handling two cases:

• When an operand is an rvalue of type basic_big_int, its allocation can be reused for the operation.
• When an operand is of integral type, no temporary basic_big_int is created. This is important because the type may be __int128, _BitInt(1024), etc. and may not be representable as basic_big_int without an unnecessary allocation.

Each such binary operator must handle eight distinct cases, which the [Reference-Impl] classifies as follows:

// Convenience macro that describes one of eight forms of binary operation // that any binary operation for `big_int` can take. enum struct binary_op_form : unsigned char { // Both sides are movable. // Typically, the operation is performed by mutating the integer // with the most capacity. move_move, // Only the left side is movable, and its allocation is reused. // The right side is also a `basic_big_int`, but not movable. move_copy, // Only the right side is movable, and its allocation is reused. // The left side is also a `basic_big_int`, but not movable. copy_move, // Neither side is movable, so a fresh `basic_big_int` is created. copy_copy, // The left side is movable, and its allocation is reused. // The right side is a fundamental integer (of any cvref qualification). move_int, // The right side is movable, and its allocation is reused. // The left side is a fundamental integer (of any cvref qualification). int_move, // A fresh `basic_big_int` is created because the left side is not movable. // The right side is a fundamental integer (of any cvref qualification). copy_int, // A fresh `basic_big_int` is created because the right side is not movable. // The left side is a fundamental integer (of any cvref qualification). int_copy, };

The benefit of such a design is that vast amounts of user code are sped up without any effort by the user, such as:

Since (y * z) returns basic_big_int by value, operator+ can repurpose the allocation of that result. By comparison, if operator+ worked with const&, lots of allocations would be unnecessarily thrown away.

The downside of this design is that every binary operator needs to be a template accepting forwarding references, and this possibly applies to other future operations like std::gcd as well. However, this implementation complexity is not really perceived by the user. If the operators were not optimal, the user would need to avoid overhead by writing:

It's obvious that the complexity of managing allocations optimally goes somewhere. The question is just whether it should be done invisibly by the standard library, or whether the burden is off-loaded onto users. We don't see a compelling reason to off-load onto users.

3.4.1. Why not return by && from unary operators?

For unary operators, it would also be possible to return by xvalue instead of by prvalue, but this would mean that the value category of the result of operators is not always the same. The perceived benefit is that an unnecessary extra object is avoided.

It would also mean that users run danger of holding onto objects longer than they expected:

If x refers to the original object y, a data race could be introduced by working with x on one thread, and overwriting y = 0; on another thread, each of which is well-defined on its own.

Overall, this idea is making things more complicated and dangerous, with the only benefit being a micro-optimization which we don't see as sufficiently important.

3.5. Why not provide lower-level operations for arithmetic?

A common idea in the committee is that rather than providing the high-level construct of std::big_int, we could (first) provide the low-level building blocks, such as multiprecision operations. Then, any third-party library could easily build its own big_int type on top of such operations.

There is some merit to this idea; our [Reference-Impl] internally dispatches to a number of functions that operate on span<uint_multiprecision_t>, and those could be exposed directly to the user. However, we don't propose any of these low-level operations in this paper for a number of reasons:

• The low-level operations are not actually useful in isolation and not actually useful in a wide variety of domains. Unlike other numeric operations like those in <cmath>, the multiprecision span operations are basically only useful for implementing big_int.
• Fixed-width multiprecision operations should already be covered by _BitInt(N), making the span arithmetic functions even more limited in scope.
• Many of the operations require additional allocations. For example, operator/ requires additional temporary basic_big_int, unless the divisor has only one limb.
• big_int does an enormous amount of work by dispatching to the proper operation depending on
  • type of operands (one may be of integral type),
  • value category of operands (to repurpose allocations),
  • limb count (different multiplication algorithms are chosen based on operand size),
  • constant evaluation,
  • the availability of _BitInt(N) (if a sufficiently large _BitInt is available for the operation, the whole operation can be delegated to intrinsics by converting both sides to _BitInt),
  • […]
  Providing the user only with the span operation which does not have this vast amount of extra logic is not actually in their best interest. It would be like providing them with a sqrt function that doesn't handle infinities and NaNs and telling them that this sqrt is a lower-level building block. In reality, it's simply an incomplete and less useful version of std::sqrt. Analogously, in the best case, their big_int operations would end up recreating the standard library implementation verbatim. In the worst (and much more likely case), the user's big_int would end up worse than the standard library version.
• The design of these span operations is extremely complicated in itself. Among other important questions, it is unclear whether the operations should be templates that can take span with both static and dynamic extent, how allocators should be passed (if at all), etc.
• The motivation of this paper is largely based on using big_int as a vocabulary type and as a safe and dynamic alternative to fixed-width integers. None of that motivates these span operations.
• There is no urgency to add span operations as a prerequisite for std::big_int. If those low-level operations were ever added, the implementation of std::big_int could simply start using them. There is no ABI break waiting to happen by standardizing std::big_int without those span operations.
• The span operations are a pessimization for constant evaluation. At least in theory, it is possible to make std::big_int hold a std::meta::info or some other compiler internals handle type which directly references the compiler's arbitrary-precision integer type. See also §2.5. std::big_int should be a compiler intrinsic for constant evaluation. The compiler handle approach can result in much more lightweight constant evaluation, and only requires allocating when the object is transitioned from its compile-time representation to its runtime representation. By contrast, the span operations necessitate actually having a span<uint_multiprecision_t> and managing its allocations, so more work is done in the frontend.

Overall, we don't see a need for these span operations in this paper. They might be useful in spite of the problems listed above, but are an entirely separate feature with separate motivation.

The explanation above also reveals that the premise of span operations being lower-level is simply wrong, to an extent. The std::big_int level is the lowest level at which approaches such as wrapping a handle to llvm::APint is feasible. The more std::big_int is treated as a compiler intrinsic, the lower-level it conceptually becomes.

3.6. Why no std::big_int_view?

Similar to std::string_view, one might imagine a std::big_int_view (or view type with some other name). This could even be seen as an easier first step towards multiprecision arithmetic. However, we do not provide such a type for a number of reasons below.

3.6.1. Issues with std::big_int_view parameters

Remember that the point of std::string_view as a parameter type is to accept anything string-like.

std::big_int_view cannot provide similar functionality for integer literals. Consider that we want the call g(123) below to be valid:

The key problem is turning the provided int into data and size. ref binds to a temporary object with value 123 (which is good because the lifetime of that object extends beyond the constructor call), but we cannot reinterpret that as a uint_multiprecision_t[N].

We could still turn big_int_view int a std::variant-like type that can either hold a array<uint_multiprecision_t, N> or a span<uint_multiprecision_t>, but that does not solve the problem for large integers like __int128, _BitInt(1024), etc. That requires at least an additional function:

3.6.2. Issues with std::big_int_view allocation management

The allocation that std::big_int holds is actually very useful for intermediate operations.

Operations on a std::big_int_view would require the user to write more code to avoid allocations and unnecessary copies.

3.6.3. std::big_int_view is just not useful enough

The nail in the coffin is that the user cannot do much with a std::big_int_view:

• Not a lot of operations could be performed on a std::big_int_view without allocating a std::big_int. Other than equality and relational comparison, almost any useful operation on std::big_int produces another std::big_int. Similar to how there is no operator+ between two std::string_views, there shouldn't be an operator+ between two std::big_int_views. To be fair, std::big_int_view can at least provide operator- and std::abs because we use §3.2.4. Sign and magnitude for the representation, so negation only requires flipping a sign bit in the container rather than modifying the limbs. However, this alone does not justify the existence of the type. By comparison, std::string_view provides the ability to search, check prefixes and suffixes, trim trailing/leading whitespace and other characters, create substrings in general, access random code units, etc., and these are all immensely useful non-allocating operations.
• Looking at the standard library, there would be little benefit to having a std::big_int_view. Most operations we provide come with lvalue and rvalue overloads in order to repurpose the allocations of the arguments. A notable and rare exception is std::saturating_cast, which only takes a const& because the result is always a fundamental integer type.
• Third-party libraries typically do not provide a dedicated view type for big integers. There is a boost::multiprecision::cpp_int but no boost::multiprecision::cpp_int_view.

That being said, a std::big_int_view type is not entirely useless; it's just not useful enough to be included in this paper, let alone be standardized before std::big_int.

3.7. Why no std::big_uint?

We do not propose an unsigned counterpart to std::big_uint, nor any way to make std::basic_big_int unsigned.

One reason against providing std::big_uint is that doing so contradicts the goal of providing safe and infallible operations (not counting allocation failure). Operations like subtraction, remainders, etc. can produce negative values. Saturating to zero is mathematically wrong for $\mathbb{N}$ and $\mathbb{Z}$, so the most plausible way to handle the case is to throw an exception.

std::big_uint also contracts the goal of providing a vocabulary type. Some users will inevitably use it for integers that can be large in value but not negative, which bifurcates the ecosystem into std::big_int and std::big_uint.

Another observation is that unsigned integers become less motivated the larger the type is. For 8-bit integers, this allows representing up to 255 instead of 127, which is a meaningful difference. When looking at §3.2.3.2. Layout in our reference implementation, making big_int unsigned would raise the maximum bit count from 137 billion bits to 274 billion bits. Who is supposed to benefit from this?

To be fair, guaranteeing that the sign bit is always zero eliminates some runtime checks, but even that is fairly limited. For example, since std::big_int uses a sign and magnitude representation, most of the multiplication logic already ignores the sign. The sign bit can simply be computed using an XOR at the end of the operation. Overall, eliminating the sign bit is the pinnacle of micro-optimizations.

3.7.1. Burning the std::big_uint bridge

Not only is std::big_uint not part of this paper now, we also don't leave any room for integrating it into basic_big_int using the current set of template parameters. That is, we don't have a bool for configuring signedness. See also §3.8. Template parameters below.

Even if the bridge was not burned, adding std::big_uint in the form of std::basic_big_int extensions would be problematic. The status quo is that any code that uses std::basic_big_int can assume that subtraction and negation of small values is non-throwing, and that the only failure mode is producing stupidly large values (with some rare exceptions like division by zero; see also §3.15. Error handling). Making std::basic_big_int throw or abort on negative values would rug-pull these assumptions.

3.7.2. Conclusion

Providing std::big_uint would be in direct contradiction with our design goals, so it is not provided. The performance benefits are minimal.

Making std::basic_big_int possibly unsigned in the future is also problematic, so we don't provide any reserved template parameters which would enable that. A big unsigned integer type should either be provided immediately (which we do not want) or be an entirely separate std::basic_big_uint.

3.8. Template parameters

3.8.1. Order of template parameters

For std::basic_big_int, the order is generally most likely to be specified as an argument first:

The Allocator parameter needs to come after the Limb parameter so that the default argument allocator<Limb> can be spelled. This is unfortunate because the limb type cannot be configured at all (it must always be uint_multiprecision_t), but would not be so bad if it became genuinely configurable in the future. Fortunately, the only people inconvenienced are power users who use std::basic_big_int with a custom allocator, which is acceptable.

3.8.2. min_inplace_capacity

Consistently with the rest of the standard library (e.g. std::array, std::bitset, std::span), the type of min_inplace_capacity is std::size_t.

3.8.3. min_inplace_capacity restrictions

An interesting design question is whether min_inplace_capacity arguments should be disallowed if the capacity is increased internally. This might make sense because basic_big_int<7> and basic_big_int<8> are functionally equivalent, but distinct types with distinct instantiated code.

We decided not to restrict the argument because it may cause portability problems and disallows certain useful configurations.

Furthermore, it is very easy for the user to ensure no increase themselves:

3.8.4. Limb type parameter

When it comes to allowing configuration of the limb type, there is a spectrum of solutions:

• Don't allow any limb type configuration and have no template parameter. This is a simple design, but closes the door to future extensions forever because adding another template parameter would be an API break.
• Ours: Have a limb type parameter class Limb but only allow std::uint_multiprecision_t as an argument. This enables future extension.
• Allow types as arguments that are functionally equivalent to std::uint_multiprecision_t. That is, they are distinct types that have the same object and value representation, like unsigned long and unsigned long long on 64-bit Linux.
• Allow some subset of unsigned integer types, like 32-bit and 64-bit integers.
• Allow arbitrary unsigned integer types.

While we are not proposing any arguments other than std::uint_multiprecision_t in this paper, such future extension could be very reasonable for a few reasons:

• Existing code that uses either unsigned long or unsigned long long as a limb type would experience friction when working with spans of std::uint_multiprecision_t, even if those types are functionally equivalent. For example, there would be no guarantee that an existing C API yielding a const unsigned long* to the user could obtain that pointer directly from std::big_int::representation().
• Some configuration of the limb type is reasonably implementable and quite useful. For example, 64-bit code interfacing with 32-bit legacy code bases could benefit from working with a 32-bit limb type.
• Within a few decades, 128-bit arithmetic support may arrive on 64-bit platforms, similar to how WASM32 supports 64-bit arithmetic operations but has a 32-bit address space. If so, there ought to be a way to create a std::basic_big_int with 128-bit limbs, even if std::uint_multiprecision_t cannot be redefined due to ABI concerns.

Even if one doesn't find these arguments compelling, is there strong enough reason to make it impossible to ever extend basic_big_int with a different limb type? Probably not. The template parameter only mildly inconveniences implementers and power users who don't merely use std::big_int. Most users work with std::string rather than std::basic_string, and we expect a similar pattern for std::big_int vs. std::basic_big_int.

3.9. Conversions

3.9.1. Converting constructor

We provide the following constructor for implicit conversions:

This allows:

• An implicit conversion from any integer type. This makes it possible to write functions such as gcd(std::big_int, std::big_int) and call them like gcd(x, 3). The conversion should not be explicit because it would make initialization from literals too tedious, and the conversion is value-preserving anyway (not counting allocation failure).
• An explicit conversion from any floating-point type. This could be implicit, but is not value-preserving. See also §3.9.2. Explicit conversions to arithmetic types for more rationale. Similar to division by zero and analogous to converting float to int, converting non-finite values results in undefined behavior. See also §3.15. Error handling.
• An explicit conversion from any other specialization of std::basic_big_int. This makes it possible to convert between std::basic_big_int with different allocators and SOO sizes, and make it possible to convert std::big_int literals like 123n to other specializations. Similar constructors like the string-view-like constructor of basic_string are traditionally also explicit.

The no-alloc-constructible-from<T> part ensures that the constructor is noexcept if no allocation ever needs to take place to represent the value.

Since floating-point types may have non-finite values and converting those to std::big_int results in undefined behavior, conversions from floating-point types are never noexcept, consistent with the Lakos rule.

3.9.2. Explicit conversions to arithmetic types

std::big_int is generally designed to mirror the interface of fundamental integer types, though conversions are a notable exception. For example, any integer type can be implicitly converted to int, but std::big_int makes this explicit. This follows the general design direction of more explicit conversions in new C++ types, like std::float64_t → std::float32_t, non-value-preserving conversions in <simd>, etc.

Besides following an established design direction, we also consider it surprising if one could convert a dynamically sized std::big_int which potentially holds thousands of bits to an int, without ever expressing that intent in code. There would also be no way to catch such conversions with list-initialization since user-defined conversions are never narrowing.

3.9.3. Bit-precise integer interoperability

While [P3666R4] has not been merged into C++29 yet, we still need to consider how std::big_int will interoperate with _BitInt. Notably, the constructor of std::big_int may or may not reject those integers, and the user-defined conversion to integer types may or may not be valid.

We believe that this conversion should be valid in both directions because it exposes a fundamental and clearly useful bit of functionality. There is simply no good reason to prevent these conversions, other than wanting to prevent _BitInt from ever being a useful and fully supported type in the standard library.

3.10. Expression templates (or lack thereof)

One possible direction is to provide expression templates for std::big_int operations, similar to Boost.Multiprecision (unless disabled). That is, for example, operator+ would not return a std::big_int object, but rather a std::big_int_expression<op, L, R> which could be converted to a std::big_int object when needed.

Expression templates enable two things:

• Avoiding unnecessary temporaries and allocations. This was a major motivation prior to C++11, and is pretty much irrelevant thanks to move semantics.
• Performing various mathematical optimizations.

Many transformations can be performed with expression templates, such as:

For fundamental integers, the compiler typically performs these optimizations automatically, but std::big_int is too much of a black box for the compiler to reason about.

3.10.1. Technical reasons against expression templates

While it seems promising to have expression templates in order to perform these optimizations, we decided against this direction for a number of reasons:

• The design becomes substantially more complicated. Instead of every operation simply returning basic_big_int, they now return an object representing the operation.
• These simplifications are a double-edged sword: if the user doesn't spell out pow_mod(x, y, m), how can they be certain that pow(x, y) % m is equivalent? Will they remember months after having written the code that it is substantially transformed? Expression templates innately introduce complexity and uncertainty even though the user's code is simpler.
• Expression templates don't actually let the user express something new, they just transform expressions.
• Putting the burden on the compiler is not free. Instead of instantiation the operator@ templates with just basic_big_int operands, they would be instantiated with all sorts of distinct expression template types.
• Since the return type isn't actually basic_big_int, it can be problematic to pass the result into function templates or to store it in auto variables, since auto doesn't deduce to basic_big_int. This regularly forces users to cast to std::big_int or to avoid the use of auto. The interaction with auto expressions is especially weird: auto(++x) no longer increments and copies x; it copies the big_int_expression object which is just a symbolic placeholder.

3.10.2. The problem with optional expression templates

It should also be noted that expression templates are often an optional feature; Boost.Multiprecision allows users to disable them via the backend of the number type. For the C++ standard library, making them optional this way is diametrically opposed to our goals: we are trying to provide a single concrete vocabulary type in the form of std::big_int, which is in conflict with having 50% of the users use a different type based on their preference for expression templates.

On the other hand, making expression templates mandatory without an opt-out forces the aforementioned compile-time cost down everyone's throat.

If both making expression templates optional and mandatory are bad options, perhaps the only remaining option is to not have them at all.

3.10.3. Expression templates in the ISO C++ process

Even if we decided that the benefits of expression templates outweigh the costs, the ISO C++ process is not conducive to adding them. Every single mathematical operation has some kind of interesting special forms that could be transformed, so any operation on std::big_int would produce a new expression template type.

If the user actually wants to rely on these transformations, they need to be standardized instead of being left up to the implementation, which means that of the dozens of operations on std::big_int, every combination with other operations needs to be investigated for special forms, possibly leading to hundreds of these transformation rules.

If a C++ user discovers some interesting transformation, they would need to propose it to the committee, which is a perpetual maintenance burden for the committee. This also means that they won't get to use it until the next C++ standard is published and implemented, which means years of delay.

3.11. User-defined literals for std::big_int

For convenient creation of std::big_int, we provide the following user-defined literal:

The inline namespace approach is the same as for other standard library UDLs, such as std::literals::string_­view_literals::operator""sv.

3.11.1. Why 123n?

The suffix 'n' was chosen for symmetry with JavaScript, where 123n is equivalent to BigInt(123).

3.11.2. User-defined literals vs. string constructors

It is worth noting that other libraries typically don't provide a UDL. For example, Boost.Multiprecision instead has a string constructor, expecting users to write boost::multiprecision::cpp_int("123"). We opted not to match that design because

• The 123n syntax is more natural and concise than std::big_int("123").
• The "123" syntax pessimizes runtime performance. The UDL approach allows pre-computing a constexpr uint_multiprecision_t[] holding the limbs during constant evaluation. The runtime call to operator""() only needs to copy the pre-computed limb array. Such a design is only possible thanks to template<char...> giving us the literal as a constant expression.
• Third-party libraries avoid this form of UDL in part because it is very complicated to implement and requires parsing the integer literal with all features (including base prefixes, digit separators, etc.). In the standard, we can consider this to be an insignificant QoI issue. In the standard library implementation, we also have the luxury of doing the UDL parsing using a compiler intrinsic if it turns out to be too expensive to do in constant evaluation. Third-party libraries don't have this luxury.

While this new form of UDL is not proposed here, it still informs us that there is potential to improve UDLs and reduce some of their costs, without breaking existing uses of 123n. This makes UDLs a more compelling option right now.

3.11.3. Why provide UDLs or string constructors at all?

Some form of convenient construction is necessary. Otherwise, creating large constant std::big_int objects is simply too tedious.

It would also be possible using the constructor taking a span<const uint_multiprecision_t>, but this would require breaking any large constants up into individual limbs, which is very difficult to do portably considering that uint_multiprecision_t varies in size.

Another option is to rely on _BitInt, but this feature is not yet available in the C++ standard, and even if it was, the BITINT_MAXWIDTH is only guaranteed to be at least LLONG_WIDTH. In other words, _BitInts larger than 64-bit are an optional feature.

3.12. Adjacent library utilities

There are a number of standard library utilities provided for fundamental integers, such as std::abs and std::gcd. These are all useful for std::big_int and even if we didn't add the overloads in this paper, someone would do it sooner or later.

We do not add any new integer utilities such as integer exponentiation or modular arithmetic; these can always be added later, and are brand-new orthogonal features that equally make sense for fundamental integers.

3.12.1. Hash support for std::big_int

We also provide std::hash support. While the hashing algorithm is up to the implementation (there are various widely used algorithms for hashing a sequence of integers), there is an important restriction: for any basic_big_int<b, A> object, the std::hash result depends solely on the integer value (i.e. the mathematical value represented) by the object.

This makes it possible to use a different basic_big_int as a key type than the type used for lookup (assuming transparent lookup in some container).

However, the hash might not be compatible with that of fundamental types, i.e. 1 may be hashed differently than std::big_int{1}. Also note that 1 is already hashed differently from __int128, so it's not possible to have hash parity with all integer types. To maintain some degree of parity, we ensure that as available, hash<big_int>(x) equals hash<_BitInt(N)>(static_cast<_BitInt(N)>(x)) (where N is the smallest possible _BitInt width that can represent x).

3.12.2. std::numeric_limits specialization

There should be a specialization of std::numeric_limits provided for std::basic_big_int. Doing so is tradition in third-party libraries that provide their own infinite-precision integers, and it provides useful capabilities such as writing generic code that works with int, big_int, and boost::multiprecision::cpp_int, and distinguishing the infinite-precision integers via numeric_limits::is_bounded.

3.12.3. std::in_range

We provide std::in_range overloads for std::big_int as follows:

While the same functionality can be achieved using t >= numeric_limits<R>::min() && t <= numeric_limits<R>::max(), std::in_range provides a more convenient and efficient way to check if a std::big_int value can be represented in another integer type.

The other comparison functions in [utility.intcmp] are not overloaded because this is not very useful for std::big_int. The comparison operators already provide the mathematically correct result in all cases. We are also not convinced that much generic code would benefit; std::cmp_* functions are typically used when there is a known mismatch in signedness between two bounded integers.

3.12.4. std::abs

We provide std::abs overloads for std::big_int as follows:

This is an obviously useful overload that any user would expect to exist.

Header management provides a problem: we don't want <cstdlib> and <cmath> to include <big_int>, and both of these provide the overloads for other integer types. To solve this, <big_int> provides the overload as well as the rest of the overload set (not providing the rest of the overload set would risk ODR violations).

3.12.5. std::gcd, std::lcm, and std::midpoint

We provide std::gcd, std::lcm, and std::midpoint overloads for std::big_int as follows:

All of these take forwarding references to allow for optimal allocation reuse. They work the same way as the binary operators, as described in §3.4. Optimal operator overloads.

3.12.6. std::saturating_cast

We provide a std::saturating_cast overload for std::big_int as follows:

… where R is a signed or unsigned integer type.

This is partially motivated by the fact that Boost's static_cast for cpp_int behaves in a saturating instead of truncating way. While that behavior is useful, it would be surprising to C++ users who expect conversions to truncate, and it would be inconvenient in generic code that tries to handle both std::big_int and fundamental integer types. In any case, providing std::saturating_cast provides an easy upgrade path from boost::multiprecision::cpp_int to std::big_int.

3.12.7. std::to_chars and std::from_chars

We also provide std::to_chars and std::from_chars overloads for std::big_int:

These are clearly useful.

A notable quirk is that both std::to_chars and std::from_chars can potentially throw because they internally do arbitrary-precision arithmetic. This is also why std::to_chars has an rvalue overload; it allows reusing the allocation of value for intermediate calculations. However, std::to_chars should be guaranteed not to throw if base is a power of two because converting to base-two digits can be performed limb-by-limb in a single pass.

One could argue that providing std::to_chars is weird because it operates on a fixed-size buffer, while std::big_int is dynamically sized. However, most std::big_int objects in practice could easily fit into a buffer of a few hundred or thousand characters. If so, the user should not be forced to go through std::format_to to avoid an allocation.

3.12.8. Formatting support

std::big_int is also formattable out of the box, with std::format, std::print, etc. Once again, this is clearly useful and expected by users.

The same options as for any fundamental integer type should be supported, so that e.g. std::format("{:x}", x) prints a std::big_int x in hexadecimal.

3.12.9. std::to_string and std::from_string

We also provide std::to_string and std::to_wstring overloads for std::big_int:

Since these are defined in terms of std::format with a {} specifier, the specification is trivial and the same as for any fundamental integer type. In practice, an implementation would directly call std::to_chars to cut out the middle-man between std::to_string and std::to_chars.

std::to_chars has an rvalue overload so that the allocation of val can be reused for intermediate calculations. std::to_string and std::to_wstring also need such an overload to avoid pessimization.

3.12.10. No <bit> support

While bit-manipulation functions are useful for std::big_int, these are not included in the proposal because there are too many design problems that need to be resolved, and this should better be done in a follow-up paper:

• Some of the functions such as std::rotl don't really make sense for an infinite-precision integer type. It is unclear which ones to provide.
• While std::countr_zero and std::countr_one are useful, there would need to be error handling for the case of std::countr_zero(0n) and std::countr_one(-1n), since the result is infinity.
• <bit> uses int to report results such as in int std::popcount, but this seems insufficient for std::big_int. That opens the question whether to use a fixed type like long long or some implementation-defined signed integer type, and whether that type should have a spelling exposed to the user.
• It is unclear how std::bit_repeat should work for std::big_int. The function takes a T pattern and int pattern length and repeats that pattern as many times as possible. For std::big_int, that would result in an infinite amount of repetitions. Nonetheless, std::bit_repeat would be useful for std::big_int; it just needs a different design that is not yet clear.
• The <bit> header currently accepts only unsigned integers in most functions, but std::big_int is signed, seemingly contradicting the current design direction.
• While std::bit_reverse could be useful for std::big_int, it's unclear how to define it for negative numbers.

3.13. Naming

The name std::big_int was chosen because it meets user expectations and makes its design instantly clear. In languages where infinite-precision integers are not built-in, the name is virtually always some variant of big int or big integer. The name std::big_int is also immediately recognizable as supporting infinite-precision arithmetic and as growing elastically as needed.

Previous proposals used the name std::integer, but this name doesn't convey the design well, and is too similar to concept names like std::integral.

3.14. Choice of header

We propose a new <big_int> header that just provides std::big_int and its utility functions.

While std::big_int could belong in <numeric>, that header is already enormous, and std::big_int is essentially a standalone container. It could be seen as a std::vector with some operator overloads. Containers traditionally have their own headers, like <vector>.

3.15. Error handling

std::big_int has elastic operations, meaning that it grows as needed to fit the result, making many operations infallible. The allocations can still fail and throw std::bad_alloc, same as for any other container.

Fallible operations include

• operator/ and operator%, if the divisor is zero,
• conversion from numeric_limits<float>::infinity() to std::big_int, and
• operator<< and operator>> with negative shifts.

We handle this as undefined behavior. From a runtime cost perspective, this is unjustified because operator/ already cannot be minimal and entirely branchless due to the §3.2.3. Small object optimizations, even if there is no extra check for division by zero. std::big_int division is also a fairly heavy operation, so the general principle of don't harden high-performance, low-level numerics doesn't really apply here.

The reason we still have undefined behavior for these cases is that there is no clear precedent for error handling in heavy numerics in the standard library. std::bitset offers some precedent, but arguably goes too far by throwing on runtime checks even in fast and low-level operations like operator[], making the type less attractive for some high-performance use cases. The proposed undefined behavior can be thought of as a placeholder, and undefined behavior can always be filled in with something better at a later point.

4. Future direction

The initial std::big_int proposal is only the start. There are many features that could be added subsequently but which are not in this paper to keep its scope focused.

4.1. Integer numeric functions

This paper only provides std::big_int overloads for pre-existing functions, such as std::abs. However, infinite-precision libraries typically provide many more operations, such as

• modular arithmetic functions, like powmod,
• integer exponentiation (ipow),
• integer logarithm (ilog),
• integer square root (isqrt),
• factorial (fact),
• binomial coefficient (choose),
• […]

The key observation is that these functions are at least as useful for fundamental integer types, not just for std::big_int, and they should be designed for integers in general. That makes all of them separate and orthogonal features, where a std::big_int overload is just one of the design aspects.

4.2. Fixed-point interoperability

To provide interoperability with fixed-point numbers, a conversion to/from such numbers could be provided. Concretely, this would require

• a constructor taking the integer and its scale (in bits),
• a conversion function that yields the integer and its scale.

Neither is truly necessary because conversion from fixed-point could also be implemented in terms of construction from an integer followed by <<= or >>=. conversion to fixed-point could also be implemented in terms of a std::countl_zero overload for std::big_int and in terms of >>. However, more direct implementations may provide some convenience.

In any case, there is no urgent need to provide such convenience in this proposal, especially considering that there are zero-overhead workarounds using bit-shifting.

4.3. Random number generation

Adding support for std::big_int in <random> is another logical next step, but out of scope in this paper in order to limit the scope. Presumably, the approach would be to allow std::big_int in std::uniform_int_distribution and other facilities.

4.4. Making std::uint_multiprecision_t C-compatible

As mentioned in §3.2.2. C compatibility, it may be beneficial to improve C compatibility by putting std::uint_multiprecision_t in <cstdint>, and possibly by standardizing the type for C2y.

4.5. Non-transient allocations

std::big_int would benefit from non-transient constexpr allocations because it would allow constexpr variables to hold any integer value. Currently, the limit is imposed by the inplace_capacity.

However, this is a general problem, and any solution should include std::string, std::vector, etc. Recent proposals dealing with this problem include:

• [P1974R1] Persistent constexpr allocation
• [P4147R0] constexpr => runtime bridge

4.6. Constant template parameters

While std::big_int's implementation doesn't meet the requirements of a structural type, it could be declared magically structural in the standard or it could be made usable as a template parameter in some other way. Using some compiler support, the name mangling could be customized so that std::big_int becomes usable as a template parameter. That is, 123n could be mangled as W123 similar to how 123 is mangled as i123.

However, again, this is is a general problem, and other types such as std::string could benefit from being structural as well. Most recently, [P4340R0] explores solutions that would make further class types usable as template parameters.

5. Arguments against standardization

While there is strong motivation to include std::big_int in the standard, there are also some arguments against doing so, which need to be considered carefully.

5.1. Many trade-offs

std::big_int is relatively complex, and any complex design comes with a number of trade-offs. This does provide some motivation against standardization. Generally speaking, if a feature has so many trade-offs that most users will have to make their own form of a feature, this suggests that the feature is unfit for standardization.

Some concrete trade-offs for std::big_int (and our response to these) are:

In summary, the idea that std::big_int has too many domain-specific trade-offs is largely unsubstantiated. Allowing configuration of the inplace_capacity and allocator provides sufficient flexibility for virtually every use case. Any remaining trade-off in the design of std::big_int would be mildly annoying at worst.

Another way to look at this issue is to consider whether std::big_int is suitable for each of the advertised §2.1. Use cases (serialization, safety, scripting engines, statistics, scientific computing, and cryptography). For each of these, it is possible to imagine a reason to avoid std::big_int, like not being optimized with manual assembly for some architecture used in scientific computing, but std::big_int remains an acceptable default choice for most users; there is no deal breaker among the trade-offs above that would make it unsuitable for the domain.

5.2. Use of committee resources

Another concern with std::big_int is that it undoubtedly consumes committee resources both to standardize initially, and to maintain. This is naturally the case with any large feature.

However, big integer types have many millions of uses throughout various programming languages already, and standardization will likely make that number skyrocket for C++, so this is simply committee time well-spent, however much time it is.

5.3. Increased complexity of future integer features

The current design approach of std::big_int is to closely imitate the fundamental integer types. Rather than providing operations as member functions, existing standard library facilities like std::gcd and std::popcount should be extended to support std::big_int in addition to signed and/or unsigned integer types. Consequently, once a decent amount of coverage for std::big_int is provided, the expectation is that any new integer utility would also support std::big_int. This is very similar to how any new functions in <cmath> or <bit> are now expected to have std::simd overloads, for the sake of consistency.

We don't consider this permanent increase in standardization effort to detract from std::big_int because

• In a lot of cases, those new integer utilities are a useful part of big integer libraries anyway. For example, those libraries typically come with integer exponentiation functions, so std::big_int support for such a new std::ipow function would be added enthusiastically, not reluctantly. See also §4.1. Integer numeric functions.
• It is quite easy to design the function signatures for new std::big_int utilities once there are some examples in the standard library setting a precedent.
• A naive implementation is often quite easy to provide for std::big_int, by simply doing the same as for the fixed-width integers. This is very similar to how the naive implementation for simd::vec is to perform the scalar operation elementwise.

In short, the added cost to new integer utilities is either low or effectively zero (if we would have added std::big_int support anyway, it's not really an additional cost).

5.4. Use of implementer resources

Another similar criticism is that std::big_int would consume a substantial amount of implementer resources, especially when the goal is to have a high-performance implementation.

There are many factors that address this issue:

• Standardization of the type concentrates the work of third-party libraries in the standard library. Many upgrades to e.g. Boost.Multiprecision might also be backported to the standard library counterpart, and vice versa.
• Due to how ridiculously widespread big integers are in C++ already (see GitHub code search in §1. Introduction), standardization would act as an invite to outside collaborators.
• Every major compiler vendor already provides a big integer type, such as llvm::APInt. While some major refactoring would be required, vendors could end up converting these types into wrappers around std::big_int or could at least implement the numeric operations via std::big_int. For example, llvm::APIntOps::pext is the spiritual equivalent of a std::bit_compress overload for std::big_int, so why maintain both?

The biggest remaining concern is that standardization trifurcates the implementations into a libstdc++ std::big_int, a libc++ std::big_int, and an MSVC std::big_int. However, this work is already trifurcated among the vendors' existing big integer types (see above), so standardization does not create additional duplicated effort so much as relocate this existing work for the benefit of users.

5.5. Residual fragmentation

A possible criticism of std::big_int is that everyone already has their own big integer. Or more precisely, the ecosystem is already full of solutions such as GMP, Boost.Multiprecision, etc. or various internal implementations of multiprecision used in cryptographic libraries. Even if std::big_int was standardized, the ecosystem wouldn't simply drop their own solutions overnight.

While that is true, these arguments shouldn't stop any proposal on their own. Any new feature takes time to adopt, and even if it provides a better or more convenient solution to a problem, it's unrealistic for everyone to rewrite their existing solutions. Similarly, the addition of C++17 std::string_view does not mean that everyone would instantly move away from existing solutions like gsl::string_view, but that doesn't make C++17's new type worthless.

5.5.1. N-to-N conversion problem

Furthermore, there is an N-to-N conversion problem between all these existing solutions. How does one convert boost::multiprecision::cpp_int to e.g. OpenSSL's BIGNUM? The most universal form of conversion is to convert to a string and parse as another type, but this is comically expensive and involves multiprecision division operations.

std::big_int provides at least an intermediate representation that turns this into a 1-to-N conversion problem. That is, any existing big integer type can be extended with a constructor taking const std::big_int& or std::span<const std::uint_multiprecision_t> to facilitate conversions, and any library with some existing internal integer type can at least provide new functions taking such parameters in its top-level API.

5.6. Inability to change ABI

Since the standard library is typically kept in an ABI-stable state, standardizing std::big_int has the downside of losing some potential flexibility compared to third-party libraries. A crucial question is thus whether frequent changes to the representation of std::big_int are plausible and desirable, i.e. whether we forfeit much in this regard.

We believe this is either not the case or can be mitigated with our design, for the following reasons:

• The SOO size can be customized with the min_inplace_capacity parameter, so even if a user realizes that the std::big_int layout is not suitable for them, they can choose another std::basic_big_int.
• The overall sign-and-magnitude layout is an industry standard that has not seen meaningful change in the last decades. Most big integer implementations use this layout.
• Even more fundamentally, the approach of performing multi-precision operations using limb arrays is an eternal standard. For over 50 years, CPU instructions like adc have been specifically designed around performing multi-precision operations word-by-word, and arranging words in an array has always been the obvious layout to make this seamless.
• The layout of Boost.Multiprecision's boost::multiprecision::cpp_int has seen little change historically.
• For really large integers (multi-limb case), the underlying operations work with span<uint_multiprecision_t>, and the details of how those limbs are laid out in the container are somewhat irrelevant.

In conclusion, while the ABI freeze is a real concern with std::big_int, the ABI is fairly stable in practice, for various innate reasons. However, it is plausible that some details of how §3.2.3. Small object optimizations are implemented may be imperfect at first, and tweaking those details would be difficult in the standard library.

5.7. Header bloat

The design strategy for std::big_int is to provide supporting utilities as overloads of existing standard library functions. That is, std::to_chars, std::gcd, etc. receive new overloads accepting std::big_int. An unfortunate consequence is that this bloats any and all integer utilities with std::big_int support, including formerly lightweight headers like <charconv>.

To be fair:

• We have never really kept our headers minimal, with some extreme example like including <memory> for std::to_address and getting all of std::atomic, std::shared_ptr, and uninitialized_* algorithms.
• None of this is a problem with import std;.
• <big_int> is still relatively lightweight. It manages its representation similar to std::vector, and the really complicated numeric parts like Toom-Cook multiplications live in the runtime library anyway. The constexpr paths use a much smaller implementation.

6. Implementation experience

Our reference implementation can be found at [Reference-Impl].

6.1. Deployment experience

This reference implementation is still very recent and has no real-world deployment experience. That being said, std::big_int is heavily modeled after Boost.Multiprecision and boost::multiprecision::cpp_int has decades of deployment experience across hundreds and thousands of projects.

6.2. Benchmarks

See https://eisenwave.github.io/std-big-int/benchmarks.html. Overall, our std::big_int implementation is typically a bit slower than gmp_int (Boost wrapper around GMP) and on par with boost::multiprecision::cpp_int on identical generic driver code (that is, templates that perform computation for any of these integer types). These benchmarks are unsurprising: GMP uses hand-written assembly optimized over many years and represents somewhat of a theoretical optimum, and our top-level API and implementation internals are so similar to those of Boost, not much should be gained or lost in terms of performance.

7. Wording

The changes are relative to [N5032].

[headers]

In [headers], add a new element to C++ library headers table:

[version.syn]

Add a feature-test macro to [version.syn] as follows:

[numeric.limits]

[numeric.limits.general]

Change [numeric.limits.general] paragraph 5 as follows:

[numeric.special]

Insert a new paragraph at the end of [numeric.special] as follows:

[utility]

[utility.syn]

Change the synopsis [utility.syn] as follows:

[utility.intcmp]

Change [utility.intcmp] as follows:

[numeric.ops.overview]

Change the synopsis [numeric.ops.overview] as follows:

[numeric.ops.gcd]

Append a new item to [numeric.ops.gcd] as follows:

[numeric.ops.lcm]

Append a new item to [numeric.ops.lcm] as follows:

[numeric.ops.midpoint]

Append a new item to [numeric.ops.midpoint] as follows:

[numeric.sat.cast]

Change [numeric.sat.cast] as follows:

template<class R, class T> constexpr R saturating_cast(T x) noexcept;

1 Constraints: R and T are signed or unsigned integer types ([basic.fundamental]).

2 Returns: If x is representable as a value of type R, x; otherwise, either the largest or smallest representable value of type R, whichever is closer to the value of x.

[numeric.int.div]