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;
    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 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.

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.

  • 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

operator+

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

Returns a copy of *this (for the lvalue overload) or std::move(*this) (for the rvalue overload). 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.

  • 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.

  • 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

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 uses the allocator of x.

  • 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