The big_int Type

Design

The most important anchor points of the design of the big_int type are:

  • big_int should be elastic; that is, it should grow to the necessary size required to fit the result of an arithmetic operation.

  • big_int should support custom allocators.

  • big_int should expose small-object optimization to the user.

This leads us to the following type declarations:

namespace beman::big_int {
// uint_multiprecision_t is the unsigned integer used to store each "limb"
// (machine-word digit) of the magnitude of a big_int.

#if ... // 32-bit limb platform detected
using uint_multiprecision_t = unsigned int;
#else  // 64-bit limb platform detected
using uint_multiprecision_t = unsigned long long;
#endif

} // namespace beman::big_int
// min_inplace_bits is the number of bits of statically allocated storage that
// the basic_big_int will have available for the small-object optimization.
// Limb names the limb type, and shall be uint_multiprecision_t.
template <std::size_t min_inplace_bits,
          class Limb      = uint_multiprecision_t,
          class Allocator = std::allocator<Limb>>
class basic_big_int;

// Default specialization with a stateless allocator.
using big_int = basic_big_int<64, uint_multiprecision_t, std::allocator<uint_multiprecision_t>>;

namespace pmr {

// Specialization parameterized on std::pmr::polymorphic_allocator.
template <std::size_t b, class L = uint_multiprecision_t>
using basic_big_int = beman::big_int::basic_big_int<b, L, std::pmr::polymorphic_allocator<L>>;

using big_int = basic_big_int</* same in-place bits as the default big_int */>;

} // namespace pmr

} // namespace beman::big_int

A basic_big_int stores its magnitude as a little-endian sequence of uint_multiprecision_t limbs (the first limb holds the least significant bits) together with a separate sign. Values whose magnitude fits within inplace_bits bits are stored directly inside the object; larger values are stored in allocator-provided dynamic storage.

The limb type is named by the Limb template parameter rather than being fixed by the class, so that a future revision can change it without changing the signature of basic_big_int. Limb shall be uint_multiprecision_t, and Allocator::value_type shall be Limb; a program that instantiates basic_big_int with any other limb type is ill-formed.

For a practical implementation the big_int does have a maximum size available as max_size(). Any operation that would need more storage than that, or the growth required by an arithmetic, shift, bitwise, assignment, or parsing operation, etc., throws std::length_error, or in an exception free environment std::abort(). The check happens before the allocator is consulted, so no allocation is attempted for a request that cannot be represented. A request that is within the limit but cannot be served reports the allocator’s own failure (typically std::bad_alloc) instead. During constant evaluation the same condition is a compile-time error rather than an exception, since a thrown exception is not a constant expression.

Synopsis

In the synopsis below, the italicized names (arbitrary-arithmetic, arbitrary-integer, signed-or-unsigned, cv-unqualified-arithmetic, common-big-int-type, and common-big-int-type-with) are exposition-only concepts and helper aliases used to constrain the interface. common-big-int-type<L, R> denotes the basic_big_int specialization shared by L and R when one operand is a basic_big_int and the other is either the same specialization or a built-in signed or unsigned integer type.

template <std::size_t min_inplace_bits,
          class Limb      = uint_multiprecision_t,
          class Allocator = std::allocator<Limb>>
class basic_big_int {
  public:
    // member types
    using allocator_type = Allocator;
    using size_type      = std::size_t;
    using pointer        = std::allocator_traits<Allocator>::pointer;
    using const_pointer  = std::allocator_traits<Allocator>::const_pointer;

    // member constants
    static constexpr size_type inplace_capacity = /* number of in-place limbs */;
    static constexpr size_type inplace_bits =
        inplace_capacity * std::numeric_limits<Limb>::digits;

    // [big.int.cons], construct/copy/destroy
    constexpr basic_big_int() noexcept(noexcept(Allocator()));
    constexpr explicit basic_big_int(const Allocator& a) noexcept;
    constexpr basic_big_int(const basic_big_int& x);
    constexpr basic_big_int(basic_big_int&& x) noexcept;
    constexpr basic_big_int(const basic_big_int& x, const std::type_identity_t<Allocator>& a);
    constexpr basic_big_int(basic_big_int&& x, const std::type_identity_t<Allocator>& a);
    template <_arbitrary-arithmetic_ T>
        requires(!std::same_as<std::remove_cvref_t<T>, basic_big_int>)
    constexpr explicit(/* see below */) basic_big_int(T&& value) noexcept(/* see below */);
    template <_arbitrary-arithmetic_ T>
    constexpr basic_big_int(const T& value, const allocator_type& a) noexcept(/* see below */);
    template <std::input_iterator I, std::sentinel_for<I> S>
        requires _signed-or-unsigned_<std::iter_value_t<I>>
    constexpr basic_big_int(I begin, S end, const allocator_type& a = allocator_type());
    template <std::ranges::input_range R>
        requires _signed-or-unsigned_<std::ranges::range_value_t<R>>
    constexpr basic_big_int(std::from_range_t, R&& r, const allocator_type& a = allocator_type());
    constexpr ~basic_big_int();

    // [big.int.modifiers], assignment
    constexpr basic_big_int& operator=(const basic_big_int& x);
    constexpr basic_big_int& operator=(basic_big_int&& x) noexcept;
    template <_arbitrary-integer_ T>
        requires(!std::same_as<std::remove_cvref_t<T>, basic_big_int>)
    constexpr basic_big_int& operator=(T&& x) noexcept(/* see below */);

    template <class T> constexpr basic_big_int& operator+=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator-=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator*=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator/=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator%=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator&=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator|=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <class T> constexpr basic_big_int& operator^=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
    template <_signed-or-unsigned_ S> constexpr basic_big_int& operator<<=(S s);
    template <_signed-or-unsigned_ S> constexpr basic_big_int& operator>>=(S s);

    // [big.int.modifiers], swap
    constexpr void swap(basic_big_int& x) noexcept(
        std::allocator_traits<allocator_type>::propagate_on_container_swap::value ||
        std::allocator_traits<allocator_type>::is_always_equal::value);

    // [big.int.ops], observers
    constexpr std::span<const uint_multiprecision_t> representation() const noexcept;
    constexpr size_type                              representation_size() const noexcept;
    constexpr allocator_type                         get_allocator() const noexcept;
    constexpr size_type                              size() const noexcept;
    constexpr size_type                              max_size() const noexcept;
    constexpr size_type                              max_representation_size() const noexcept;
    constexpr void                                   reserve(size_type n);
    constexpr void                                   reserve_representation(size_type n);
    constexpr size_type                              capacity() const noexcept;
    constexpr size_type                              representation_capacity() const noexcept;
    constexpr void                                   shrink_to_fit();

    // [big.int.unary], unary operators
    constexpr basic_big_int  operator+() const&;
    constexpr basic_big_int  operator+() && noexcept;
    constexpr basic_big_int  operator-() const&;
    constexpr basic_big_int  operator-() && noexcept;
    constexpr basic_big_int  operator~() const&;
    constexpr basic_big_int  operator~() &&;
    constexpr basic_big_int& operator++();
    constexpr basic_big_int  operator++(int);
    constexpr basic_big_int& operator--();
    constexpr basic_big_int  operator--(int);

    // [big.int.conv], conversion
    template <_cv-unqualified-arithmetic_ T>
    constexpr explicit operator T() const noexcept;
};

// [big.int.special], specialized algorithms
template <std::size_t b, class L, class A>
constexpr void swap(basic_big_int<b, L, A>& x, basic_big_int<b, L, A>& y)
    noexcept(noexcept(x.swap(y)));

// [big.int.cmp], comparison operators
template <class L, _common-big-int-type-with_<L> R>
constexpr bool operator==(const L& lhs, const R& rhs) noexcept;
template <class L, _common-big-int-type-with_<L> R>
constexpr std::strong_ordering operator<=>(const L& lhs, const R& rhs) noexcept;

// [big.int.binary], binary operators
template <class L, class R> constexpr _common-big-int-type_<L, R> operator+(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator-(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator*(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator/(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator%(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator&(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator|(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator^(L&& x, R&& y);
template <class T, _signed-or-unsigned_ S>
    requires /* remove_cvref_t<T> is a basic_big_int specialization */
constexpr std::remove_cvref_t<T> operator<<(T&& x, S s);
template <class T, _signed-or-unsigned_ S>
    requires /* remove_cvref_t<T> is a basic_big_int specialization */
constexpr std::remove_cvref_t<T> operator>>(T&& x, S s);

// [big.int.hash], hash support
template <std::size_t b, class L, class A>
struct std::hash<beman::big_int::basic_big_int<b, L, A>>;

Member types and constants

Name Description

allocator_type

The allocator type Allocator.

size_type

std::size_t.

pointer

std::allocator_traits<Allocator>::pointer.

const_pointer

std::allocator_traits<Allocator>::const_pointer.

inplace_capacity

The number of Limb limbs available in the in-place (small-object) storage. It is at least large enough to hold min_inplace_bits bits, and never smaller than what fits in the object’s pointer footprint.

inplace_bits

inplace_capacity * std::numeric_limits<Limb>::digits; the number of bits of in-place storage. A value whose magnitude fits in inplace_bits bits is stored without allocating.

Constructors and destructor

Default constructor

constexpr basic_big_int() noexcept(noexcept(Allocator()));

Initializes the integer value to zero and default-constructs the allocator.

  • Preconditions: None.

  • Postconditions: None.

Allocator constructor

constexpr explicit basic_big_int(const Allocator& a) noexcept;

Initializes the integer value to zero and initializes the allocator to a.

  • Preconditions: None.

  • Postconditions: None.

Copy constructor

constexpr basic_big_int(const basic_big_int& x);

Initializes the integer value to that of x and initializes the allocator to allocator_traits<Allocator>::select_on_container_copy_construction(x.get_allocator()).

  • Preconditions: None.

  • Postconditions: None.

  • Throws: Nothing if the effective width of the integer value of x is less than or equal to inplace_bits; otherwise, any exception thrown during allocation.

Move constructor

constexpr basic_big_int(basic_big_int&& x) noexcept;

Initializes the integer value to that of x and initializes the allocator by moving from x.get_allocator().

  • Preconditions: None.

  • Postconditions: x is left in a valid state with an unspecified value.

Allocator-extended copy constructor

constexpr basic_big_int(const basic_big_int& x, const std::type_identity_t<Allocator>& a);

Initializes the integer value to that of x and initializes the allocator to a. Unlike the copy constructor, select_on_container_copy_construction is not consulted, so this is how a copy is placed on a chosen allocator, such as the source’s own: basic_big_int y(x, x.get_allocator());.

  • Preconditions: None.

  • Postconditions: None.

  • Throws: Nothing if the effective width of the integer value of x is less than or equal to inplace_bits; otherwise, any exception thrown during allocation.

Allocator-extended move constructor

constexpr basic_big_int(basic_big_int&& x, const std::type_identity_t<Allocator>& a);

Initializes the integer value to that of x and initializes the allocator to a. If allocator_traits<Allocator>::is_always_equal::value is true or a == x.get_allocator(), the storage of x is taken over as by the move constructor. Otherwise a cannot deallocate that storage, so the value is copied into storage obtained from a, as by the allocator-extended copy constructor.

  • Preconditions: None.

  • Postconditions: x is left in a valid state with an unspecified value.

  • Throws: Nothing if the storage of x is taken over or the effective width of the integer value of x is less than or equal to inplace_bits; otherwise, any exception thrown during allocation. If an exception is thrown, x is unchanged.

Uses-allocator construction calls these two constructors, so an allocator-aware container such as std::pmr::vector copies or moves each basic_big_int element onto its own allocator. When the element already uses that allocator, as it does when the container reallocates, the move takes over the element’s storage instead of allocating. Because the allocator parameter is a non-deduced context, class template argument deduction takes the type from x alone, and a may be anything convertible to Allocator: basic_big_int y(x, &resource) deduces the same pmr::basic_big_int as x.

Converting constructor from an arithmetic type

template <_arbitrary-arithmetic_ T>
    requires(!std::same_as<std::remove_cvref_t<T>, basic_big_int>)
constexpr explicit(/* see below */) basic_big_int(T&& value) noexcept(/* see below */);

Initializes the integer value from value. If std::remove_cvref_t<T> is an integral type or a basic_big_int specialization, the integer value is that of value. If it is a floating-point type, the integer value is that obtained by discarding the fractional part of value (truncation toward zero).

  • Constraints: std::remove_cvref_t<T> is not basic_big_int, and is a built-in integer type, a floating-point type, or a basic_big_int specialization.

  • Preconditions: If std::remove_cvref_t<T> is a floating-point type, value is finite.

  • Postconditions: None.

  • Throws: Nothing if the effective width of the resulting value is less than or equal to inplace_bits; otherwise, any exception thrown during allocation.

  • Remarks: The constructor is explicit unless std::remove_cvref_t<T> is a built-in signed or unsigned integer type or the same basic_big_int specialization. The expression inside noexcept is true when value is an integral type whose width does not exceed inplace_bits.

Converting constructor from an arithmetic type with an allocator

template <_arbitrary-arithmetic_ T>
constexpr basic_big_int(const T& value, const allocator_type& a) noexcept(/* see below */);

Equivalent to the converting constructor above, but initializes the allocator to a.

  • Preconditions: If std::remove_cvref_t<T> is a floating-point type, value is finite.

  • Postconditions: None.

  • Throws: Nothing if the effective width of the resulting value is less than or equal to inplace_bits; otherwise, any exception thrown during allocation.

Iterator-pair constructor

template <std::input_iterator I, std::sentinel_for<I> S>
    requires _signed-or-unsigned_<std::iter_value_t<I>>
constexpr basic_big_int(I begin, S end, const allocator_type& a = allocator_type());

Initializes the integer value by concatenating the base-2 representation of each element in [begin, end), where the first element holds the least significant limb. If the iterator’s value type is signed, the combined representation is interpreted as a signed integer; otherwise it is interpreted as an unsigned integer. Initializes the allocator to a.

  • Preconditions: [begin, end) is a valid range.

  • Postconditions: None.

from_range constructor

template <std::ranges::input_range R>
    requires _signed-or-unsigned_<std::ranges::range_value_t<R>>
constexpr basic_big_int(std::from_range_t, R&& r, const allocator_type& a = allocator_type());

Initializes the integer value by concatenating the base-2 representation of each element in r, where the first element holds the least significant limb. If the range’s value type is signed, the combined representation is interpreted as a signed integer; otherwise it is interpreted as an unsigned integer. Initializes the allocator to a.

  • Preconditions: None.

  • Postconditions: None.

This constructor is available when the standard library provides <ranges> container support (the __cpp_lib_containers_ranges feature-test macro).

Destructor

constexpr ~basic_big_int();

Releases any dynamically-allocated storage owned by the object.

  • Preconditions: None.

  • Postconditions: None.

Assignment

Copy assignment

constexpr basic_big_int& operator=(const basic_big_int& x);

Sets the integer value to that of x and returns *this.

  • Preconditions: None.

  • Postconditions: None.

Move assignment

constexpr basic_big_int& operator=(basic_big_int&& x) noexcept;

Sets the integer value to that of x and returns *this.

  • Preconditions: None.

  • Postconditions: x is left in a valid state with an unspecified value.

Assignment from an integer type

template <_arbitrary-integer_ T>
    requires(!std::same_as<std::remove_cvref_t<T>, basic_big_int>)
constexpr basic_big_int& operator=(T&& x) noexcept(/* see below */);

Sets the integer value to that of x and returns *this. Note that, unlike the converting constructor, this operator does not accept floating-point operands.

  • Constraints: std::remove_cvref_t<T> is not basic_big_int, and is a built-in integer type or a basic_big_int specialization.

  • Preconditions: None.

  • Postconditions: None.

  • Remarks: The expression inside noexcept is true when x is an integral type whose width does not exceed inplace_bits.

Compound assignment operators

Arithmetic and bitwise compound assignment

template <class T> constexpr basic_big_int& operator+=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator-=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator*=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator&=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator|=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator^=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;

Each operator @= is equivalent to *this = std::move(*this) @ std::forward<T>(rhs) and returns *this, where @ is the corresponding binary operator.

  • Preconditions: None.

  • Postconditions: None.

  • Throws: std::length_error if the result would occupy more than max_size() bits; otherwise, any exception thrown during allocation.

Division and remainder compound assignment

template <class T> constexpr basic_big_int& operator/=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;
template <class T> constexpr basic_big_int& operator%=(T&& rhs) requires _common-big-int-type-with_<T, basic_big_int>;

operator/= sets *this to the quotient and operator%= sets *this to the remainder of dividing *this by rhs, truncating toward zero, and returns *this.

  • Preconditions: The integer value of rhs is nonzero.

  • Postconditions: None.

Shift compound assignment

template <_signed-or-unsigned_ S> constexpr basic_big_int& operator<<=(S s);
template <_signed-or-unsigned_ S> constexpr basic_big_int& operator>>=(S s);

operator<⇐ is equivalent to *this = std::move(*this) << s (multiplication by 2^s); operator>>= is equivalent to *this = std::move(*this) >> s (division by 2^s, rounded toward negative infinity). Each returns *this.

  • Preconditions: s >= 0, and s does not exceed the maximum shift max_size().

  • Postconditions: None.

  • Throws: std::length_error if the result would occupy more than max_size() bits; otherwise, any exception thrown during allocation.

Swap

Member swap

constexpr void swap(basic_big_int& x) noexcept(
    std::allocator_traits<allocator_type>::propagate_on_container_swap::value ||
    std::allocator_traits<allocator_type>::is_always_equal::value);

Exchanges the integer values of *this and x. Any dynamically-allocated storage is exchanged directly rather than reallocated, so the operation neither allocates nor deallocates. If std::allocator_traits<allocator_type>::propagate_on_container_swap::value is true, the allocators are also exchanged using an unqualified call to swap; otherwise they are left unchanged.

  • Preconditions: std::allocator_traits<allocator_type>::propagate_on_container_swap::value is true, or get_allocator() == x.get_allocator().

  • Postconditions: *this holds the integer value that x held before the call, and x holds the integer value that *this held before the call. The allocators are exchanged if and only if std::allocator_traits<allocator_type>::propagate_on_container_swap::value is true.

  • Throws: Nothing.

Non-member swap

template <std::size_t b, class L, class A>
constexpr void swap(basic_big_int<b, L, A>& x, basic_big_int<b, L, A>& y)
    noexcept(noexcept(x.swap(y)));

Equivalent to x.swap(y), and so subject to the same preconditions. It lives in the beman::big_int namespace and is found by argument-dependent lookup, which makes it the overload selected both by an unqualified swap(x, y) and by the using std::swap; swap(x, y) idiom that generic code and the standard algorithms use. Selecting it in preference to std::swap matters: std::swap would exchange the two values with three moves, and would not honour std::allocator_traits<A>::propagate_on_container_swap.

Both arguments must name the same basic_big_int specialization; there is no overload that exchanges values across differing min_inplace_bits, limb types, or allocators.

  • Effects: As if by x.swap(y).

  • Preconditions: std::allocator_traits<A>::propagate_on_container_swap::value is true, or x.get_allocator() == y.get_allocator().

  • Postconditions: x holds the integer value that y held before the call, and y holds the integer value that x held before the call.

  • Throws: Nothing.

Observers

Throughout this section, a "limb" is one uint_multiprecision_t object of the magnitude’s little-endian representation.

representation

constexpr std::span<const uint_multiprecision_t> representation() const noexcept;

Returns a std::span over the limbs that make up the magnitude, whether stored in place or in dynamic storage. The first limb in the range holds the least significant bits.

  • Preconditions: None.

  • Postconditions: None.

  • Remarks: If the integer value is greater than or equal to zero, basic_big_int(std::from_range, representation(), get_allocator()) has the same integer value.

representation_size

constexpr size_type representation_size() const noexcept;

Returns the number of limbs that make up the magnitude: 1 if the integer value is zero, and otherwise ceil(size() / std::numeric_limits<uint_multiprecision_t>::digits). This is the size of the span returned by representation().

  • Preconditions: None.

  • Postconditions: None.

get_allocator

constexpr allocator_type get_allocator() const noexcept;

Returns a copy of the object’s allocator.

  • Preconditions: None.

  • Postconditions: None.

size

constexpr size_type size() const noexcept;

Returns the number of bits required to represent the magnitude of the value: 0 if the integer value is zero, and otherwise floor(log2(|v|)) + 1, where v is the integer value.

  • Preconditions: None.

  • Postconditions: None.

max_size

constexpr size_type max_size() const noexcept;

Returns the maximum number of bits that the magnitude may occupy, that is, max_representation_size() * std::numeric_limits<uint_multiprecision_t>::digits. An operation that would grow the magnitude beyond this many bits throws std::length_error; see the length limit.

This is a ceiling on the representation, not a largest value of the type, and it lies far beyond any allocation a program can make. std::numeric_limits accordingly reports basic_big_int as unbounded; see Why is_bounded is false.

  • Preconditions: None.

  • Postconditions: None.

  • Throws: Nothing.

max_representation_size

constexpr size_type max_representation_size() const noexcept;

Returns the maximum number of limbs that can be part of the representation, that is, max_size() / std::numeric_limits<uint_multiprecision_t>::digits.

  • Preconditions: None.

  • Postconditions: None.

  • Throws: Nothing.

reserve

constexpr void reserve(size_type n);

A directive, expressed as a number of bits, that informs the object of a planned increase in size so that storage can be allocated up front. The bit count is rounded up to a whole number of limbs; equivalent to reserve_representation(ceil(n / std::numeric_limits<uint_multiprecision_t>::digits)).

  • Preconditions: None.

  • Postconditions: If reallocation occurs, capacity() is greater than or equal to n; otherwise, capacity() is unchanged.

  • Throws: std::length_error if n is greater than max_size(); otherwise, any exception thrown during allocation. In either case *this is unchanged.

reserve_representation

constexpr void reserve_representation(size_type n);

A directive that informs the object of a planned increase in size, expressed as a number of limbs, so that storage can be allocated up front. Equivalent to reserve(n * std::numeric_limits<uint_multiprecision_t>::digits).

  • Preconditions: None.

  • Postconditions: If reallocation occurs, representation_capacity() is greater than or equal to n; otherwise, the capacity is unchanged.

  • Throws: std::length_error if n is greater than max_representation_size(); otherwise, any exception thrown during allocation. In either case *this is unchanged.

capacity

constexpr size_type capacity() const noexcept;

Returns the number of bits of storage currently available without reallocating, that is, representation_capacity() * std::numeric_limits<uint_multiprecision_t>::digits. While the value is held in the in-place (small-object) storage this equals inplace_bits.

  • Preconditions: None.

  • Postconditions: None.

representation_capacity

constexpr size_type representation_capacity() const noexcept;

Returns the number of limbs that can be held without allocating: the greater of inplace_capacity and the number of limbs of dynamically-allocated storage currently available. Unlike capacity(), which is expressed in bits, this is a limb count that never reports fewer than inplace_capacity limbs.

  • Preconditions: None.

  • Postconditions: None.

shrink_to_fit

constexpr void shrink_to_fit();

If the magnitude fits in the in-place storage, frees any dynamic allocation and moves the value into the in-place storage. Otherwise, this is a non-binding request to reduce the dynamic capacity to the number of limbs in use; it never increases capacity(), but may reduce it, which can cause a reallocation.

  • Preconditions: None.

  • Postconditions: None.

Unary operators

The const& overloads build their result by copy construction, so its allocator is allocator_traits<Allocator>::select_on_container_copy_construction(get_allocator()), as abs’s is. The `&& overloads take over the operand’s storage and so carry the operand’s own allocator.

operator+

constexpr basic_big_int operator+() const&;
constexpr basic_big_int operator+() && noexcept;

Equivalent to return *this; for the lvalue overload and return std::move(*this); for the rvalue overload, so each selects the corresponding constructor and the allocator behavior above follows from it. The value is unchanged.

  • Preconditions: None.

  • Postconditions: None.

operator-

constexpr basic_big_int operator-() const&;
constexpr basic_big_int operator-() && noexcept;

Returns the arithmetic negation of the value (equivalent to 0 - *this). The rvalue overload reuses the operand’s storage and only flips the sign.

  • Preconditions: None.

  • Postconditions: None.

operator~

constexpr basic_big_int operator~() const&;
constexpr basic_big_int operator~() &&;

Returns the bitwise complement of the value as if performed on an infinite-width two’s-complement representation (equivalent to -1 - *this).

  • Preconditions: None.

  • Postconditions: None.

operator++

constexpr basic_big_int& operator++();    // pre-increment
constexpr basic_big_int  operator++(int); // post-increment

Pre-increment is equivalent to *this += 1 and returns *this. Post-increment increments *this and returns a copy of the value prior to the increment. Neither is ref-qualified, so both apply to an rvalue.

  • Preconditions: None.

  • Postconditions: None.

operator--

constexpr basic_big_int& operator--();    // pre-decrement
constexpr basic_big_int  operator--(int); // post-decrement

Pre-decrement is equivalent to *this -= 1 and returns *this. Post-decrement decrements *this and returns a copy of the value prior to the decrement. Neither is ref-qualified, so both apply to an rvalue.

  • Preconditions: None.

  • Postconditions: None.

Conversion operator

template <_cv-unqualified-arithmetic_ T>
constexpr explicit operator T() const noexcept;

Converts the value to T. The result is static_cast<T>(static_cast<U>(v)), where v is the integer value and U is a hypothetical signed integer type wide enough to represent v. If T is bool, the result is true when the value is nonzero and false otherwise. If T is a floating-point type, the result is determined as if by a floating-integral conversion.

  • Constraints: T is a cv-unqualified arithmetic type.

  • Preconditions: None.

  • Postconditions: None.

Comparison operators

template <class L, _common-big-int-type-with_<L> R>
constexpr bool operator==(const L& lhs, const R& rhs) noexcept;
template <class L, _common-big-int-type-with_<L> R>
constexpr std::strong_ordering operator<=>(const L& lhs, const R& rhs) noexcept;

operator== returns true if the integer value of lhs equals the integer value of rhs. operator<⇒ returns std::strong_ordering::less, std::strong_ordering::greater, or std::strong_ordering::equal according to whether the integer value of lhs is less than, greater than, or equal to the integer value of rhs. At least one operand is a basic_big_int; the other may be the same basic_big_int specialization or a built-in signed or unsigned integer type.

  • Preconditions: None.

  • Postconditions: None.

Binary operators

Every operator in this section returns a new value, so its allocator is the basic_big_int operand’s allocator run through allocator_traits<Allocator>::select_on_container_copy_construction

Arithmetic and bitwise operators

template <class L, class R> constexpr _common-big-int-type_<L, R> operator+(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator-(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator*(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator&(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator|(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator^(L&& x, R&& y);

Each returns a basic_big_int whose integer value is T(x) @ T(y), where @ is the corresponding operator and T is a hypothetical signed integer type with infinite range. One operand is a basic_big_int and the other is the same specialization or a built-in signed or unsigned integer type.

  • Preconditions: None.

  • Postconditions: None.

  • Throws: std::length_error if the result would occupy more than max_size() bits; otherwise, any exception thrown during allocation.

  • Remarks: The bitwise operators (&, |, ^) behave as if performed on a two’s-complement representation in which non-negative numbers have infinitely many leading zero bits and negative numbers have infinitely many leading one bits.

Division and remainder operators

template <class L, class R> constexpr _common-big-int-type_<L, R> operator/(L&& x, R&& y);
template <class L, class R> constexpr _common-big-int-type_<L, R> operator%(L&& x, R&& y);

operator/ returns the quotient and operator% returns the remainder of dividing x by y, truncating toward zero (matching the behavior of the built-in integer types).

  • Preconditions: The integer value of y is nonzero.

  • Postconditions: None.

Shift operators

template <class T, _signed-or-unsigned_ S>
    requires /* remove_cvref_t<T> is a basic_big_int specialization */
constexpr std::remove_cvref_t<T> operator<<(T&& x, S s);
template <class T, _signed-or-unsigned_ S>
    requires /* remove_cvref_t<T> is a basic_big_int specialization */
constexpr std::remove_cvref_t<T> operator>>(T&& x, S s);

operator<< returns a basic_big_int whose integer value is v * 2^s, and operator>> returns one whose integer value is v / 2^s rounded toward negative infinity, where v is the integer value of x. The result’s allocator is selected as described for the binary operators above.

  • Constraints: std::remove_cvref_t<T> is a basic_big_int specialization.

  • Preconditions: s >= 0, and s does not exceed the maximum shift for the result type (max_size()).

  • Postconditions: None.

  • Throws: std::length_error if the result would occupy more than max_size() bits; otherwise, any exception thrown during allocation.

Hash support

template <std::size_t b, class L, class A>
struct std::hash<beman::big_int::basic_big_int<b, L, A>> {
    std::size_t operator()(const beman::big_int::basic_big_int<b, L, A>& x) const noexcept;
};

Returns a hash of the integer value of x.

The digest is a function of that value and of nothing else. Equal values hash equally whatever their min_inplace_bits, Limb, and Allocator arguments, and whatever the width of uint_multiprecision_t on the target: a value hashes the same where limbs are 32 bits wide as it does where they are 64 bits wide.

Where a signed bit-precise integer type can represent x and the implementation gives that type a digest, the digest is std::hash<_BitInt(N)>()(static_cast<_BitInt(N)>(x)) for the narrowest such N, so a basic_big_int key and a _BitInt(N) key of the same value hash alike and can be hashed interchangeably.

The widths tried are one per object size: a _BitInt(N) past one machine word occupies ceil(N / word_bits) words, and on an implementation that hashes a scalar by its object representation every _BitInt of a given size has one digest, so a rung at each size covers every width that shares that size. A value hashed on the 192-bit rung therefore also matches a _BitInt(160) key of the same value, and one hashed on the narrowest rung matches every _BitInt no wider than a word. The ladder runs from one word up to the widest object the implementation’s own std::hash covers, which on a 64-bit target with libc is four words, so 64, 128, 192, and 256 bits; a rung the target cannot form, or whose `std::hash` the implementation does not provide, is passed over. The reach is the `BEMAN_BIG_INT_HASH_MAX_OBJECT_WORDS` macro, counted in `std::size_t` words and defaulting to four, because libc hashes a scalar past that size with a helper it only declares, which is a hard error rather than something a concept can reject. Defining that macro to a larger value is the whole change needed to hash on wider rungs once a standard library covers them.

Where no rung is available every value takes the fallback below; that is the case on an implementation that hashes no _BitInt, and on one whose compiler has no _BitInt at all.

An implementation that hashes a scalar by its object representation gives _BitInt(64) and std::int64_t the same digest, since they share one. On such an implementation, where a machine word is 64 bits, a value in the range of std::int64_t therefore also hashes as std::hash<std::int64_t>()(static_cast<std::int64_t>(x)).

Beyond the widest available width the digest is not itself part of the interface and may change between releases. It is currently SipHash-2-4 over the little-endian byte string of the magnitude, trimmed of its most significant zero bytes. That string is size() bits rounded up to a whole number of bytes. A negative value is distinguished from its magnitude before the string is absorbed. Where std::size_t is narrower than 64 bits, the digest is folded down to its width.

  • Preconditions: None.

  • Postconditions: None.

Edit this Page