Proposal for Unbounded-Precision Integer Types

What’s New in this Revision

Several people sent me extensive comments on N3375. For personal reasons, I had very little time to spend on this proposal through the summer, so I have not been able to give those comments more than superficial consideration. I have incorporated most of those comments as new issues in Open issues; they’re marked [new in N3417].

Overview

Programmers sometimes need to manipulate integer values that are too large to repesent with C++’s standard integer types. Doing a Google search for terms that describe large integers produces many hits for libraries that handle large integers. These libraries vary in quality, from hacks by beginners to sophisticated, professional implementations. Also, Java has unbounded precision integers as part of its standard class library.

One important use for unbounded-precision integers is cryptography. Cryptographic applications typically manipulate integer values of several hundred digits. If the C++ standard library provides facilities for such values it will make cryptographic applications easier to write and to port.

There have been two Committee papers proposing unbounded-precision integer libraries for C++: N1718 (2004) and N2143 (2007), both by M.J. Kronenburg. Nothing was done with these papers, in part because there was too much else going on in the Library Working Group at the time. Now that the Committee is looking to greatly expand the scope of the standard library, it’s time to reconsider unbounded-precision integers.

Design considerations

An unbounded-precision integer type is an integer type that does not impose pre-defined limits on the precision of the values that it can represent. Of course, in practice, unbounded precision can’t be achieved; sooner or later the system runs out of resources. So unbounded in this context means bounded only by the availability of system resources; there is no hard-coded limit to the number of digits in the value that an unbounded-precision integer type an represent.

Unbounded-precision integer types should interoperate with C++’s built-in integer types. Applying arithmetic operations to a mix of standard integer types and unbounded-precision integer types should just work. And to the extent possible, operations that can be applied to standard integer types should also be applicable, using the same syntax, to unbounded-precision integer types.

Unbounded-precision integer types should also provide operations that facilitate their application in the areas that demand such types. In particular, to support cryptographic applications, an unbounded-precision integer type must provide facilities for generating random values (with a user-specified source of randomness) and for determining whether any particular value is a prime number (subject to the limitations of number theory; for large values, primality can only be determined to a degree of certainty in a reasonable amount of time).

Design overview

This paper proposes two unbounded-precision integer types. The type unsigned_integer represents unsigned integer values; the type integer represents signed integer values. In addition to the basic arithmetic operations, unsigned_integer supports manipulation of individual bits. It also provides a function for generating random values, a function for determining whether a value is prime (within a specified degree of certainty), and a function for generating prime numbers (again, within a specified degree of certainty). The type integer is more of a pure arithmetic type. It does not provide the additional operations that unsigned_integer provides.

To support interoperability, objects of either types can be constructed from values of any of the standard integer types. So code like this just works:

    integer i = 30000;
    integer j = 1000 * i;

As currently specified, neither unsigned_integer nor integer provides overloaded operators that take standard integer types. When an operation is applied to a standard integer type and an unsigned_integer or an integer, the standard integer operand is converted to the appropriate unbounded-precision integer type and the operation is applied to the result. It is assumed that implementations will make this kind of mixed operation efficient by implementing a small-integer optimization, storing small values directly in the unsigned_integer or integer object, and using heap storage when needed for larger values. This greatly simplifies the interface specification.

Objects of these types can also be constructed from values of floating-point types. Conversions from floating-point to integer are inherently lossy, so these constructors are marked explicit.

Objects of these types can also be constructed from string representations (with the usual range of possible bases) and from an initializer list that holds unsigned 32-bit values.

Values of type unsigned_integer can be freely converted to integer through copy construction and assignment. Values of type integer cannot be assigned directly to values of type unsigned_integer, nor can a value of type unsigned_integer be constructed implicitly from a value of type integer; this prevents accidentally attempting to convert a negative value to a positive one. The C and C++ rule that in such assignments the result is reduced modulo 2n should not be applied to unbounded-precision integer types, because n is rather large.

Bit manipulations on unsigned_integer values treat the value as having an unbounded number of zero bits above the highest non-zero bit in the value. As a result, the usual bit operations, &, |, and ^, can be applied to values of different sizes. Further, unsigned_integer can be used as a replacement for std::bitset (although with a less thorough interface) when limiting the object to a fixed number of bits is undesirable.

Open issues

1. Allocators -- unbounded-precision integer types need to manage memory on the free store to hold their data. This suggests that users should be able to specify an allocator. But templatizing these types on an allocator would require that all of the arithmetic operations provide overloads for all of the standard integer types, because function template instantiation requires exact type matches, without conversions.
2. Policy for out-of-bounds subtraction -- subtracting an unsigned_integer value from a smaller value doesn’t have any specified semantics in this paper. This should probably throw an exception.
3. Policy for out-of-bounds constructor arguments -- constructing an unsigned_integer object from a negative value doesn’t have any specified semantics in this paper. This should probably throw an exception.
4. Policy for lossy conversions -- converting an unsigned_integer or integer object to an integral type that cannot represent its value doesn’t have any specified semantics in this paper. Should this throw an exception?
5. [new in N3417] Rvalue overloads for arithmetic operations (Joe Gottman) -- many of the operations on the unbounded-precision types can be made more efficient by providing overloaded versions that take rvalue references. For example:

   integer operator+(integer&& lhs, const integer& rhs) {
       return std::move(lsh += rhs);
   }

6. [new in N3417] Functions for controlling when and how allocations occur (Joe Gottman) -- just as with std::string, many operations can be made faster by pre-allocating enough memory to hold the expected result. In some cases the desired capacity is best expressed in bits and in some cases in decimal digits, so the suggestion is to offer both:

   size_t capacity_in_bits() const;   // The number of bits the object can hold without reallocation.
   size_t capacity_in_digits() const; // The largest number n such that the object can hold n decimal
                                      // digits without reallocation.
   void reserve_bits(size_t n);       // Postcondition: capacity_in_bits() >= n.
   void reserve_digits(size_t n);     // Postcondition: capacity_in_digits() >= n.
   void shrink_to_fit()();            // A non-binding request to reduce memory usage.

7. [new in N3417] Support user-defined literals (Alisdair Meredith, Marc Glisse) -- obviously useful, but users might expect them to be constexpr, which they cannot, in general, be, because they need to allocate memory.
8. [new in N3417] Add noexcept specifications as appropriate (Alisdair Meredith) -- there are several that are obvious. In addition, if we require the small-object optimization, some or all of the constructors that take integral types can be noexcept.
9. [new in N3417] Add constexpr specifications as appropriate (Alisdair Meredith) -- although most functions can allocate memory, there are a few that could be marked constexpr. It’s not clear how useful this would be.
10. [new in N3417] Why do the bitshift operators take an int argument? (Alisdiar Meredith, Marc Glisse) -- this may be limiting, for example, on a 64-bit OS with a 32-bit int type. size_t or ptrdiff_t may be a better choice.
11. [new in N3417] Why just one string type for string conversions? (Alisdair Meredith) -- there are four standard basic_string typedefs.
12. [new in N3417] Converting to a string could use a mechanism for providing an allocator (Alisdair Meredith) -- for example,

    template<class charT, class Traits, class Alloc>
    void unsigned_integer::load(basic_string<charT, Traits, Alloc>&);

13. [new in N3417] Consider extending interface to more fully support dynamic bitsets (Alisdair Meredith) -- or maybe that should be a separate class, with shared implementation.
14. [new in N3417] powmod should be specified to run in constant time with identical cache access patterns for arguments of the same size (Jack Lloyd) -- this is important for cryptographic purposes, to avoid side-channel attacks.
15. [new in N3417] Need functions to interconvert with byte arrays (Jack Lloyd) -- quite a common need in cryptographic operations.
16. [new in N3417] Add a typedef that gives the underlying representation type and an accessor that provides a pointer to the internal representation. (Jack Lloyd) -- some common cryptographic algorithms can’t be implemented with the interface in the proposal; adding these accessors makes it possible to implement them.
17. [new in N3417] Is the unsigned_integer type necessary? (Marc Glisse) -- if this is there to support bit manipulation, why not just specify those operations as undefined for negative numbers.
18. [new in N3417] Rounding of divisions and right shifts needs to be specified. (Marc Glisse) -- even if it’s obvious. Also, does mod return negative values?
19. [new in N3417] The constructor that takes a string should be explicit. (Marc Glisse)
20. [new in N3417] Consider making to_string() a non-member function. (Daniel Krügler) -- this would be a good match with the existing to_string functions.
21. [new in N3417] Consider removing explicit operator std::string() const. (Daniel Krügler, Jens Maurer) -- to_string() is sufficient.

Header <seminumeric> synopsis

namespace std {
namespace seminumeric {

/* class unsigned_integer */

    class unsigned_integer;
    template <> class numeric_limits<unsigned_integer>;
    
    void swap(unsigned_integer&, unsigned_integer&);

    // arithmetic operations
    unsigned_integer operator+(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator-(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator*(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator/(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator%(const unsigned_integer&, const unsigned_integer&);
    std::pair<unsigned_integer, unsigned_integer> div(const unsigned_integer&, const unsigned_integer&);

    unsigned_integer operator<<(const unsigned_integer&, int);
    unsigned_integer operator>>(const unsigned_integer&, int);

    // logical operations
    unsigned_integer operator&(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator|(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer operator^(const unsigned_integer&, const unsigned_integer&);

    // comparisons
    bool operator==(const unsigned_integer&, const unsigned_integer&);
    bool operator!=(const unsigned_integer&, const unsigned_integer&);
    bool operator<(const unsigned_integer&, const unsigned_integer&);
    bool operator<=(const unsigned_integer&, const unsigned_integer&);
    bool operator>(const unsigned_integer&, const unsigned_integer&);
    bool operator>=(const unsigned_integer&, const unsigned_integer&);

    // numeric operations
    unsigned_integer sqr(const unsigned_integer&);
    unsigned_integer sqrt(const unsigned_integer&);
    std::pair<unsigned_integer, unsigned_integer> sqrtrem(const unsigned_integer&);

    unsigned_integer pow(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer mod(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer powmod(const unsigned_integer&, const unsigned_integer&, const unsigned_integer&);
    unsigned_integer invmod(const unsigned_integer&, const unsigned_integer&);

    unsigned_integer gcd(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer lcm(const unsigned_integer&, const unsigned_integer&);

    // primality
    template <class Engine>
        bool is_probable_prime(const unsigned_integer&, int, Engine);
    template <class Engine>
        unsigned_integer probable_prime(unsigned, int, Engine);

    // stream inserter and extractor
    template <class Elem, class Traits>
        std::basic_istream<Elem, Traits>& operator>>(std::basic_istream<Elem, Traits>&, unsigned_integer&);
    template <class Elem, class Traits>
        std::basic_ostream<Elem, Traits>& operator<<(std::basic_ostream<Elem, Traits>&, const unsigned_integer&);
    void swap(integer&, integer&);


/* class integer */

    class integer;
    template <> class numeric_limits<integer>;

    void swap(integer&, integer&);

    // arithmetic operations
    integer operator+(const integer&, const integer&);
    integer operator-(const integer&, const integer&);
    integer operator*(const integer&, const integer&);
    integer operator/(const integer&, const integer&);
    integer operator%(const integer&, const integer&);
    std::pair<integer, integer> div(const integer&, const integer&);

    integer operator<<(const integer&, int);
    integer operator>>(const integer&, int);

    // comparisons
    bool operator==(const integer&, const integer&);
    bool operator!=(const integer&, const integer&);
    bool operator<(const integer&, const integer&);
    bool operator<=(const integer&, const integer&);
    bool operator>(const integer&, const integer&);
    bool operator>=(const integer&, const integer&);

    // numeric operations
    integer sqr(const integer&);
    integer sqrt(const integer&);
    std::pair<integer, integer> sqrtrem(const integer&);

    integer pow(const integer&, const unsigned_integer&);
    integer mod(const integer&, const unsigned_integer&);
    integer powmod(const integer&, const unsigned_integer&, const unsigned_integer&);
    integer invmod(const integer&, const unsigned_integer&);

    integer gcd(const integer&, const integer&);
    integer lcm(const integer&, const integer&);

    // stream inserter and extractor
    template <class Elem, class Traits>
        std::basic_istream<Elem, Traits>& operator>>(std::basic_istream<Elem, Traits>&, integer&);
    template <class Elem, class Traits>
        std::basic_ostream<Elem, Traits>& operator<<(std::basic_ostream<Elem, Traits>&, const integer&);

}   /* namespace seminumeric */
}   /* namespace std */

Class unsigned_integer

class unsigned_integer {
public:
    // construct, copy
    unsigned_integer();
    unsigned_integer(char);
    unsigned_integer(signed char);
    unsigned_integer(unsigned char);
    unsigned_integer(short);
    unsigned_integer(unsigned short);
    unsigned_integer(int);
    unsigned_integer(unsigned int);
    unsigned_integer(long);
    unsigned_integer(unsigned long);
    unsigned_integer(long long);
    unsigned_integer(unsigned long long);
    explicit unsigned_integer(float);
    explicit unsigned_integer(double);
    explicit unsigned_integer(long double);
    unsigned_integer(const std::string&, int base = 10);
    unsigned_integer(std::initializer_list<unspecified>);

    unsigned_integer(const unsigned_integer&);
    unsigned_integer(unsigned_integer&&);
    explicit unsigned_integer(const integer&);
    explicit unsigned_integer(integer&&);

    unsigned_integer& operator=(const unsigned_integer&);
    unsigned_integer& operator=(unsigned_integer&&);

    void swap(unsigned_integer&);

    // conversions
    explicit operator int() const;
    explicit operator unsigned() const;
    explicit operator long() const;
    explicit operator unsigned long() const;
    explicit operator long long() const;
    explicit operator unsigned long long() const;
    explicit operator float() const;
    explicit operator double() const;
    explicit operator long double() const;
    explicit operator std::string() const;
    explicit operator bool() const;

    // arithmetic operations
    unsigned_integer& operator+=(const unsigned_integer&);
    unsigned_integer& operator-=(const unsigned_integer&);
    unsigned_integer& operator*=(const unsigned_integer&);
    unsigned_integer& operator/=(const unsigned_integer&);
    unsigned_integer& operator%=(const unsigned_integer&);
    std::pair<unsigned_integer, unsigned_integer> div(const unsigned_integer&) const;

    unsigned_integer& operator++();
    unsigned_integer operator++(int);
    unsigned_integer& operator--();
    unsigned_integer operator--(int);

    unsigned_integer& operator<<=(int);
    unsigned_integer& operator>>=(int);

    // logical operations
    unsigned_integer& operator&=(const unsigned_integer&);
    unsigned_integer& operator|=(const unsigned_integer&);
    unsigned_integer& operator^=(const unsigned_integer&);

    // numeric operations
    unsigned_integer& sqr();
    unsigned_integer& sqrt();
    unsigned_integer sqrtrem();

    unsigned_integer& pow(const unsigned_integer&);
    unsigned_integer& mod(const unsigned_integer&);
    unsigned_integer& powmod(const unsigned_integer&, const unsigned_integer&);
    unsigned_integer& invmod(const unsigned_integer&);

    // bit twiddling
    void set(size_t, bool val = true);
    void flip(size_t);
    bool test(size_t) const;

    int lowest_bit() const;
    int highest_bit() const;

    // randomness
    template <class Engine>
        static unsigned_integer random(unsigned, Engine&);

    // observers
    bool is_odd() const;
    std::string to_string(int base = 10) const;
};

Class integer

class integer {
public:
    // construct, copy
    integer();
    integer(char);
    integer(signed char);
    integer(unsigned char);
    integer(short);
    integer(unsigned short);
    integer(int);
    integer(unsigned int);
    integer(long);
    integer(unsigned long);
    integer(long long);
    integer(unsigned long long);
    explicit integer(float);
    explicit integer(double);
    explicit integer(long double);
    integer(const std::string&, int base = 10);
    integer(std::initializer_list<unspecified>);

    integer(const integer&);
    integer(integer&&);
    integer(const unsigned_integer&);
    integer(unsigned_integer&&);

    integer& operator=(const integer&);
    integer& operator=(integer&&);
    integer& operator=(const unsigned_integer&);
    integer& operator=(unsigned_integer&&);

    void swap(integer&);

    // conversions
    explicit operator int() const;
    explicit operator unsigned() const;
    explicit operator long() const;
    explicit operator unsigned long() const;
    explicit operator long long() const;
    explicit operator unsigned long long() const;
    explicit operator float() const;
    explicit operator double() const;
    explicit operator long double() const;
    explicit operator std::string() const;
    explicit operator bool() const;

    // arithmetic operations
    integer& operator+=(const integer&);
    integer& operator-=(const integer&);
    integer& operator*=(const integer&);
    integer& operator/=(const integer&);
    integer& operator%=(const integer&);
    std::pair<integer, integer> div(const integer&) const;

    integer& operator++();
    integer operator++(int);
    integer& operator--();
    integer operator--(int);
    
    integer operator+();
    integer operator-();
    integer& negate();

    integer& operator<<=(int);
    integer& operator>>=(int);

    // numeric operations
    integer& sqr();
    integer& sqrt();
    integer sqrtrem();

    integer& pow(const unsigned_integer&);
    integer& mod(const unsigned_integer&);
    integer& powmod(const unsigned_integer&, const unsigned_integer&);
    integer& invmod(const unsigned_integer&);

    // observers
    bool is_odd() const;
    std::string to_string(int base = 10) const;
};

std::pair<integer, integer> div(const integer& left, const integer& right);
std::pair<unsigned_integer, unsigned_integer> div(const unsigned_integer& left, const unsigned_integer& right);

std::pair<integer, integer> integer::div(const integer& right) const;
std::pair<unsigned_integer, unsigned_integer> unsigned_integer::div(const unsigned_integer& right) const;

The functions return an object that is an instantiation of std::pair; its first field holds the quotient, left / right or *this / right, and its second field holds the remainder, left % right or *this % right.

void unsigned_integer::flip(size_t pos);

The member function toggles the bit at position pos in the stored value.

integer gcd(const integer& a, const integer& b);
unsigned_integer gcd(const unsigned_integer& a, const unsigned_integer& b);

The functions return return an object whose value is the greatest common denominator of a and b.

int unsigned_integer::highest_bit() const;

The member function returns the zero-based position of the highest non-zero bit in the stored value, or -1 if there are no non-zero bits.

integer invmod(const integer& val, const unsigned_integer& m);
unsigned_integer invmod(const unsigned_integer& val, const unsigned_integer& m);

integer& integer::invmod(const unsigned_integer& m);
unsigned_integer& unsigned_integer::invmod(const unsigned_integer& m);

The non-member functions return an object whose value is val-1 mod m. The member functions set the stored value of *this to *this-1 mod m and return *this.

integer lcm(const integer& a, const integer& b);
unsigned_integer lcm(const unsigned_integer& a, const unsigned_integer& b);

The functions return an object whose value is the least common multiple of a and b.

integer::integer();

integer::integer(char val);
integer::integer(signed char val);
integer::integer(unsigned char val);
integer::integer(short val);
integer::integer(unsigned short val);
integer::integer(int val);
integer::integer(unsigned int val);
integer::integer(long val);
integer::integer(unsigned long val);
integer::integer(long long val);
integer::integer(unsigned long long val);

explicit integer::integer(float val);
explicit integer::integer(double val);
explicit integer::integer(long double val);

integer::integer(const std::string& str, int base = 10);

integer::integer(std::initializer_list<unspecified> list);

integer::integer(const integer& other);
integer::integer(integer&& other);
integer::integer(const unsigned_integer& other);
integer::integer(unsigned_integer&& other);

The default constructor constructs an object whose value is 0.

The constructors that take integral arguments construct objects whose value is val.

The constructors that take floating-point arguments construct objects whose value is an approximation to val, accurate to at least std::numeric_limits::digits.

The constructor that takes a string constructs an object whose value is the value represented by the string object. The string object shall have the form required for the string argument to the function std::strtol with a radix of base, and shall be interpreted as if by std::strtol(str.c_str(), 0, base), except that the resulting value can never be outside the range of representable values.

The constructor that takes an initializer_list constructs an object whose stored value is equal to the elements of the initializer_list treated as a series of unsigned 32-bit digits with the leftmost digit being most significant. For example, the initializer list { 0xFE, 0xF0, 0xAA, 0x31 } represents the value 0xFE * 323 + 0xF0 * 322 + 0xAA * 321 + 0x31 * 320.

The copy and move constructors construct objects with the same value as other.

bool integer::is_odd() const;
bool unsigned_integer::is_odd() const;

The member functions return true only if the stored value represents an odd number.

template <class Engine>
    bool is_probable_prime(const unsigned_integer& val, int certainty, Engine eng);

The template function returns true only if the value val can be determined to be a prime number with probability greater than 1 - 2-certainty/2. It uses eng as a source of randomness for this evaluation.

int unsigned_integer::lowest_bit() const;

The member function returns the zero-based position of the lowest non-zero bit in the stored value, or -1 if there are no non-zero bits.

integer mod(const integer& val, const unsigned_integer& m);
unsigned_integer mod(const unsigned_integer& val, const unsigned_integer& m);

integer& integer::mod(const unsigned_integer& m);
unsigned_integer& unsigned_integer::mod(const unsigned_integer& m);

The non-member functions return an object whose value is val mod m. The member functions set the stored value in *this to *this mod m and return a reference to *this.

integer& integer::negate();

The member function sets the stored value of *this to the negation of its previous vaue and returns a reference to *this.

integer operator+(const integer& left, const integer& right);
unsigned_integer operator+(const unsigned_integer& left, const unsigned_integer& right);

The operators return an object whose value is the sum of the values of left and right.

integer& integer::operator+=(const integer& right);
unsigned_integer& unsigned_integer::operator+=(const unsigned_integer& right);

The member operators set the stored value of *this to the sum of the values of *this and right and return a reference to *this.

integer& integer::operator++();
unsigned_integer& unsigned_integer::operator++();

integer integer::operator++(int);
unsigned_integer unsigned_integer::operator++(int);

The member operators set the value stored in *this to *this + 1. The first two operators return *this. The last two operators return an object whose value is the value stored in *this prior to the increment.

integer integer::operator+();

The member function returns an object whose value is equal to the value of *this.

integer operator-(const integer& left, const integer& right);
unsigned_integer operator-(const unsigned_integer& left, const unsigned_integer& right);

The operators return an object whose value is the difference between the values of left and right.

integer& integer::operator-=(const integer&);
unsigned_integer& unsigned_integer::operator-=(const unsigned_integer&);

The member operators set the stored value of *this to the difference between the values of *this and right and return a reference to *this.

integer& integer::operator--();
unsigned_integer& unsigned_integer::operator--();

integer integer::operator--(int);
unsigned_integer unsigned_integer::operator--(int);

The member operators set the value stored in *this to *this - 1. The first two operators return *this. The last two operators return an object whose value is the value stored in *this prior to the decrement.

integer integer::operator-();

The member operator returns an object whose value is the negation of the value of *this.

integer operator*(const integer& left, const integer& right);
unsigned_integer operator*(const unsigned_integer& left, const unsigned_integer& right);

The operators return an object whose value is the product of the values of left and right.

integer& integer::operator*=(const integer& right);
unsigned_integer& unsigned_integer::operator*=(const unsigned_integer& right);

The member operators set the stored value of *this to the product of the values of *this and right and return a reference to *this.

integer operator/(const integer& left, const integer& right);
unsigned_integer operator/(const unsigned_integer& left, const unsigned_integer& right);

The operators return an object whose value is the quotient of the value of left divided by the value of right, discarding any fractional part.

integer& integer::operator/=(const integer& right);
unsigned_integer& unsigned_integer::operator/=(const unsigned_integer& right);

The member operators set the stored value of *this to the quotient of the value of *this divided by the value of right, discarding any fractional part, and return a reference to *this.

integer operator%(const integer&, const integer&);
unsigned_integer operator%(const unsigned_integer&, const unsigned_integer&);

The operators return an object whose value is the remainder of the value of left divided by the value of right. The remainder is the value such that (left / right) * right + left % right is equal to left.

integer& integer::operator%=(const integer&);
unsigned_integer& unsigned_integer::operator%=(const unsigned_integer&);

The member operators set the stored value of *this to the remainder of *this divided by the value of right and return a reference to *this.

integer operator<<(const integer& val, int shift);
unsigned_integer operator<<(const unsigned_integer& val, int shift);

If the value of shift is negative, the operators returns operator>>(val, -shift). Otherwise, the operators return a new object whose value is val * 2shift.

integer& integer::operator<<=(int);
unsigned_integer& unsigned_integer::operator<<=(int shift);

If the value of shift is negative, the operators have the effect of *this >>= -shift. Otherwise, the operators set the value of *this to *this * 2shift. The operators return a reference to *this.

template <class Elem, class Traits>
    std::basic_ostream<Elem, Traits>& operator<<(std::basic_ostream<Elem, Traits>& strm, const integer& val);
template <class Elem, class Traits>
    std::basic_ostream<Elem, Traits>& operator<<(std::basic_ostream<Elem, Traits>& strm, const unsigned_integer& val);

The operators have the effect of strm << val.to_string(), and return a reference to strm.

integer operator>>(const integer& val, int shift);
unsigned_integer operator>>(const unsigned_integer& val, int shift);

If the value of shift is negative, the operators returns operator<<(val, -shift). Otherwise, the operators return a new object whose value is val / 2shift.

unsigned_integer& unsigned_integer::operator>>=(int);
integer& integer::operator>>=(int);

If the value of shift is negative, the operators have the effect of *this <<= -shift. Otherwise, the operators set the value of *this to *this / 2shift. The operators return a reference to *this.

template <class Elem, class Traits>
    std::basic_istream<Elem, Traits>& operator>>(std::basic_istream<Elem, Traits>& strm, integer& val);
template <class Elem, class Traits>
    std::basic_istream<Elem, Traits>& operator>>(std::basic_istream<Elem, Traits>& strm, unsigned_integer& val);

The operators have the effect of { std::string temp; strm >> temp; val = temp; }, and return a reference to strm.

unsigned_integer operator&(const unsigned_integer& left, const unsigned_integer& right);

The operator returns an object whose value is the bitwise AND of the values of left and right.

unsigned_integer& unsigned_integer::operator&=(const unsigned_integer& right);

The member operator sets the value of *this to the bitwise AND of the values of *this and right and returns a reference to *this.

unsigned_integer operator|(const unsigned_integer& left, const unsigned_integer& right);

The operator returns an object whose value is the bitwise inclusive OR of the values of left and right.

unsigned_integer& unsigned_integer::operator|=(const unsigned_integer& right);

The member operator sets the value of *this to the bitwise inclusive OR of the values of *this and right and returns a reference to *this.

unsigned_integer operator^(const unsigned_integer& left, const unsigned_integer& right);

The operator returns an object whose value is the bitwise exclusive OR of the values of left and right.

unsigned_integer& unsigned_integer::operator^=(const unsigned_integer& right);

The member operator sets the value of *this to the bitwise exclusive OR of the values of *this and right and returns a reference to *this.

explicit integer::operator int() const;
explicit unsigned_integer::operator int() const;
explicit integer::operator unsigned() const;
explicit unsigned_integer::operator unsigned() const;
explicit integer::operator long() const;
explicit unsigned_integer::operator long() const;
explicit integer::operator unsigned long() const;
explicit unsigned_integer::operator unsigned long() const;
explicit integer::operator long long() const;
explicit unsigned_integer::operator long long() const;
explicit integer::operator unsigned long long() const;
explicit unsigned_integer::operator unsigned long long() const;

The operators return a value equal to the stored value of *this.

explicit integer::operator float() const;
explicit unsigned_integer::operator float() const;
explicit integer::operator double() const;
explicit unsigned_integer::operator double() const;
explicit integer::operator long double() const;
explicit unsigned_integer::operator long double() const;

The operators return a value that approximates the value stored in *this.

explicit integer::operator std::string() const;
explicit unsigned_integer::operator std::string() const;

The operator return this->to_string().

explicit integer::operator bool() const;
explicit unsigned_integer::operator bool() const;

The operator returns false only if *this is equal to 0.

integer& integer::operator=(const integer& right);
integer& integer::operator=(integer&& right);
integer& integer::operator=(const unsigned_integer& right);
integer& integer::operator=(unsigned_integer&& right);

unsigned_integer& unsigned_integer::operator=(const unsigned_integer& right);
unsigned_integer& unsigned_integer::operator=(unsigned_integer&& right);

The operators store the value of right into *this.

bool operator==(const integer& left, const integer& right);
bool operator==(const unsigned_integer& left, const unsigned_integer& right);

The operators return true only if the value stored in left is equal to the value stored in right.

bool operator!=(const integer& left, const integer& right);
bool operator!=(const unsigned_integer& left, const unsigned_integer& right);

The operators return !(left == right).

bool operator<(const integer& left, const integer& right);
bool operator<(const unsigned_integer& left, const unsigned_integer& right);

The operators return true if the value stored in left is less than the value stored in right.

bool operator<=(const integer& left, const integer& right);
bool operator<=(const unsigned_integer& left, const unsigned_integer& right);

The operators return !(right < left).

bool operator>(const integer& left, const integer& right);
bool operator>(const unsigned_integer& left, const unsigned_integer& right);

The operators return right < left.

bool operator>=(const integer& left, const integer& right);
bool operator>=(const unsigned_integer& left, const unsigned_integer& right);

The operators return !(left < right).

integer pow(const integer& val, const unsigned_integer& exp);
unsigned_integer pow(const unsigned_integer& val, const unsigned_integer& exp);

integer& integer::pow(const unsigned_integer& exp);
unsigned_integer& unsigned_integer::pow(const unsigned_integer& exp);

The non-member functions return an object whose value is valexp. The member functions set the value of *this to *thisexp and return *this.

integer powmod(const integer& val, const unsigned_integer& exp, const unsigned_integer& m);
unsigned_integer powmod(const unsigned_integer& val, const unsigned_integer& exp, const unsigned_integer& m);

integer& integer::powmod(const unsigned_integer& exp, const unsigned_integer& m);
unsigned_integer& unsigned_integer::powmod(const unsigned_integer& exp, const unsigned_integer& m);

The non-member functions return an object whose value is valexp mod m. The member functions set the value of *this to *thisexp mod m and return *this.

template <class Engine>
    unsigned_integer probable_prime(unsigned length, int certainty, Engine eng);

The template function returns an object that holds a random value of length bits that is probably prime with a probability of 1 - 2-certainty/2 using eng as a source of randomness.

template <class Engine>
    unsigned_integer random(unsigned, Engine);

The template function returns an object that holds a random value of length bits using eng as a source of randomness.

void unsigned_integer::set(size_t pos, bool val = true);

The member function sets the bit at position pos in the stored value to val.

integer sqr(const integer& val);
unsigned_integer sqr(const unsigned_integer& val);

integer& integer::sqr();
unsigned_integer& unsigned_integer::sqr();

The non-member functions return an object whose value is val * val. The member functions set the value of *this to *this * *this and return a reference to *this.

integer sqrt(const integer&);
unsigned_integer sqrt(const unsigned_integer&);

integer& integer::sqrt();
unsigned_integer& unsigned_integer::sqrt();

The non-member functions return an object whose value is the square root of the value held by val, discarding any fractional part. The member functions set the value of *this to the square root of the value held by *this, discarding any fractional part, and return a reference to *this.

std::pair<integer, integer> sqrtrem(const integer& val);
std::pair<unsigned_integer, unsigned_integer> sqrtrem(const unsigned_integer& val);

integer integer::sqrtrem();
unsigned_integer unsigned_integer::sqrtrem();

The non-member functions return an instantiation of std::pair; its first field holds a value equal to the square root of val, discarding any fractional part; its second field holds the difference between val and the square of the value stored in first. The member functions set *this to the square root of *this, discarding any fractional part; the functions return an object whose value is the difference between the original value of *this and the square of the new value of *this.

void swap(integer& left, integer& right);
void swap(unsigned_integer& left, unsigned_integer& right);

void integer::swap(integer& right);
void unsigned_integer::swap(unsigned_integer& right);

The non-member functions swap the stored values of left and right. The non-member functions swap the stored values of *this and right.

bool unsigned_integer::test(size_t pos) const;

The member function returns true only if the bit at position pos in the stored value is non-zero.

std::string integer::to_string(int base = 10) const;
std::string unsigned_integer::to_string(int base = 10) const;

The member functions return a string representation of the value stored in *this, using base as the radix.

unsigned_integer::unsigned_integer();

unsigned_integer::unsigned_integer(char val);
unsigned_integer::unsigned_integer(signed char val);
unsigned_integer::unsigned_integer(unsigned char val);
unsigned_integer::unsigned_integer(short val);
unsigned_integer::unsigned_integer(unsigned short val);
unsigned_integer::unsigned_integer(int val);
unsigned_integer::unsigned_integer(unsigned int val);
unsigned_integer::unsigned_integer(long val);
unsigned_integer::unsigned_integer(unsigned long val);
unsigned_integer::unsigned_integer(long long val);
unsigned_integer::unsigned_integer(unsigned long long val);

explicit unsigned_integer::unsigned_integer(float val);
explicit unsigned_integer::unsigned_integer(double val);
explicit unsigned_integer::unsigned_integer(long double val);

unsigned_integer::unsigned_integer(const std::string& val, int base = 10);
unsigned_integer::unsigned_integer(std::initializer_list<unspecified> list);

unsigned_integer::unsigned_integer(const unsigned_integer& other);
unsigned_integer::unsigned_integer(unsigned_integer&& other);
explicit unsigned_integer::unsigned_integer(const integer& other);
explicit unsigned_integer::unsigned_integer(integer&& other);

The default constructor constructs an object whose value is 0.

The constructors that take integral arguments construct objects whose value is val.

The constructors that take floating-point arguments construct objects whose value is an approximation to val, accurate to at least std::numeric_limits::digits.

The constructor that takes a string constructs an object whose value is the value represented by the string object. The string object shall have the form required for the string argument to the function std::strtol with a radix of base, and shall be interpreted as if by std::strtol(str.c_str(), 0, base), except that the resulting value can never be outside the range of representable values.

The constructor that takes an initializer_list constructs an object whose stored value is equal to the elements of the initializer_list treated as a series of unsigned 32-bit digits with the leftmost digit being most significant. For example, the initializer list { 0xFE, 0xF0, 0xAA, 0x31 } represents the value 0xFE * 323 + 0xF0 * 322 + 0xAA * 321 + 0x31 * 320.

The copy and move constructors construct objects with the same value as other.