Document number: | N3375 = 12-0065 |
Date: | 2012-02-24 |
Project: | Programming Language C++ |
Reference: | ISO/IEC IS 14882:2011(E) |
Reply to: | Pete Becker |
Roundhouse Consulting, Ltd. | |
pete@versatilecoding.com |
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.
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).
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.
unsigned_integer
value from a smaller value doesn’t have any specified semanticas in ths paper. This should probably throw an
exception.unsigned_integer
object from a negative value doesn’t have
any specified semantics in this paper. This should probably throw an
exception.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?<seminumeric>
synopsisnamespace 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&);
// randomness and primality
template <class Engine>
unsigned_integer random(unsigned, Engine);
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 */
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;
// observers
bool is_odd() const;
std::string to_string(int base = 10) const;
};
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.
invmodinteger 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
.
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.
modinteger 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
.
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
.