|
| mp_integer ()=default |
| Default constructor. More...
|
|
| mp_integer (const mp_integer &other)=default |
| Copy constructor. More...
|
|
| mp_integer (mp_integer &&other)=default |
| Move constructor. More...
|
|
template<typename T , generic_ctor_enabler< T > = 0> |
| mp_integer (T x) |
| Generic constructor. More...
|
|
| mp_integer (const char *s, int base=10) |
| Constructor from C string. More...
|
|
| mp_integer (const std::string &s, int base=10) |
| Constructor from C++ string (equivalent to the constructor from C string). More...
|
|
| mp_integer (const ::mpz_t n) |
| Constructor from mpz_t . More...
|
|
mp_integer & | operator= (const mp_integer &other)=default |
| Copy assignment operator. More...
|
|
mp_integer & | operator= (mp_integer &&other)=default |
| Move assignment operator. More...
|
|
template<typename T , generic_assignment_enabler< T > = 0> |
mp_integer & | operator= (const T &x) |
| Generic assignment operator. More...
|
|
bool | is_static () const |
| Test for static storage. More...
|
|
bool | is_dynamic () const |
| Check for dynamic storage. More...
|
|
std::string | to_string (int base=10) const |
| Conversion to string. More...
|
|
template<typename T , generic_conversion_enabler< T > = 0> |
| operator T () const |
| Generic conversion operator. More...
|
|
bool | promote () |
| Promote to dynamic storage. More...
|
|
bool | demote () |
| Demote to static storage. More...
|
|
std::size_t | nbits () const |
| Size in bits. More...
|
|
std::size_t | size () const |
| Size in limbs. More...
|
|
int | sgn () const |
| Sign. More...
|
|
mpz_view | get_mpz_view () const |
| Get an mpz_t view. More...
|
|
mp_integer & | neg () |
| Negate in-place. More...
|
|
mp_integer | operator+ () const |
| Identity operator. More...
|
|
template<typename T , in_place_enabler< T > = 0> |
mp_integer & | operator+= (const T &op) |
| In-place addition operator. More...
|
|
mp_integer & | operator++ () |
| Prefix increment. More...
|
|
mp_integer | operator++ (int) |
| Suffix increment. More...
|
|
mp_integer | operator- () const |
| Negated copy. More...
|
|
template<typename T , in_place_enabler< T > = 0> |
mp_integer & | operator-= (const T &op) |
| In-place subtraction operator. More...
|
|
mp_integer & | operator-- () |
| Prefix decrement. More...
|
|
mp_integer | operator-- (int) |
| Suffix decrement. More...
|
|
template<typename T , in_place_enabler< T > = 0> |
mp_integer & | operator*= (const T &op) |
| In-place multiplication operator. More...
|
|
template<typename T , in_place_enabler< T > = 0> |
mp_integer & | operator/= (const T &d) |
| In-place division operator. More...
|
|
template<typename T , in_place_mod_enabler< T > = 0> |
mp_integer & | operator%= (const T &d) |
| In-place modulo operator. More...
|
|
template<typename T , shift_op_enabler< T > = 0> |
mp_integer & | operator<<= (T s) |
| In-place left shift operator. More...
|
|
template<typename T , shift_op_enabler< T > = 0> |
mp_integer & | operator>>= (T s) |
| In-place right shift operator. More...
|
|
mp_integer & | abs () |
| In-place absolute value. More...
|
|
mp_integer & | nextprime () |
| Compute next prime number (in-place version). More...
|
|
int | probab_prime_p (int reps=25) const |
| Test primality. More...
|
|
mp_integer & | sqrt () |
| Integer square root (in-place version). More...
|
|
bool | odd_p () const |
| Test if value is odd. More...
|
|
bool | even_p () const |
| Test if value is even. More...
|
|
mppp_impl::integer_union< SSize > & | _get_union () |
| Return a reference to the internal union. More...
|
|
const mppp_impl::integer_union< SSize > & | _get_union () const |
| Return a const reference to the internal union. More...
|
|
std::remove_extent<::mpz_t >::type * | get_mpz_t () |
| Get a pointer to the dynamic storage. More...
|
|
bool | is_zero () const |
| Test if the value is zero. More...
|
|
bool | is_one () const |
| Test if the value is equal to one. More...
|
|
bool | is_negative_one () const |
| Test if the value is equal to minus one. More...
|
|
|
std::ostream & | operator<< (std::ostream &os, const mp_integer &n) |
| Output stream operator for mp_integer. More...
|
|
std::istream & | operator>> (std::istream &is, mp_integer &n) |
| Input stream operator for mp_integer. More...
|
|
int | sgn (const mp_integer &n) |
| Sign function. More...
|
|
void | neg (mp_integer &rop, const mp_integer &n) |
| Binary negation. More...
|
|
mp_integer | neg (const mp_integer &n) |
| Unary negation. More...
|
|
void | add (mp_integer &rop, const mp_integer &op1, const mp_integer &op2) |
| Ternary add. More...
|
|
template<typename T , typename U > |
common_t< T, U > | operator+ (const T &op1, const U &op2) |
| Binary addition operator. More...
|
|
template<typename T , in_place_lenabler< T > = 0> |
T & | operator+= (T &x, const mp_integer &n) |
| In-place addition for interoperable types. More...
|
|
void | sub (mp_integer &rop, const mp_integer &op1, const mp_integer &op2) |
| Ternary subtraction. More...
|
|
template<typename T , typename U > |
common_t< T, U > | operator- (const T &op1, const U &op2) |
| Binary subtraction operator. More...
|
|
template<typename T , in_place_lenabler< T > = 0> |
T & | operator-= (T &x, const mp_integer &n) |
| In-place subtraction for interoperable types. More...
|
|
void | add_ui (mp_integer &rop, const mp_integer &op1, unsigned long op2) |
| Ternary add with unsigned long . More...
|
|
void | mul (mp_integer &rop, const mp_integer &op1, const mp_integer &op2) |
| Ternary multiplication. More...
|
|
template<typename T , typename U > |
common_t< T, U > | operator* (const T &op1, const U &op2) |
| Binary multiplication operator. More...
|
|
template<typename T , in_place_lenabler< T > = 0> |
T & | operator*= (T &x, const mp_integer &n) |
| In-place multiplication for interoperable types. More...
|
|
void | addmul (mp_integer &rop, const mp_integer &op1, const mp_integer &op2) |
| Ternary multiply–accumulate. More...
|
|
void | tdiv_qr (mp_integer &q, mp_integer &r, const mp_integer &n, const mp_integer &d) |
| Ternary truncated division. More...
|
|
template<typename T , typename U > |
common_t< T, U > | operator/ (const T &n, const U &d) |
| Binary division operator. More...
|
|
template<typename T , in_place_lenabler< T > = 0> |
T & | operator/= (T &x, const mp_integer &n) |
| In-place division for interoperable types. More...
|
|
template<typename T , typename U > |
common_mod_t< T, U > | operator% (const T &n, const U &d) |
| Binary modulo operator. More...
|
|
void | mul_2exp (mp_integer &rop, const mp_integer &n, ::mp_bitcnt_t s) |
| Ternary left shift. More...
|
|
template<typename T , shift_op_enabler< T > = 0> |
mp_integer | operator<< (const mp_integer &n, T s) |
| Left shift operator. More...
|
|
void | tdiv_q_2exp (mp_integer &rop, const mp_integer &n, ::mp_bitcnt_t s) |
| Ternary right shift. More...
|
|
template<typename T , shift_op_enabler< T > = 0> |
mp_integer | operator>> (const mp_integer &n, T s) |
| Right shift operator. More...
|
|
int | cmp (const mp_integer &op1, const mp_integer &op2) |
| Comparison function for mp_integer. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator== (const T &op1, const U &op2) |
| Equality operator. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator!= (const T &op1, const U &op2) |
| Inequality operator. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator< (const T &op1, const U &op2) |
| Less-than operator. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator>= (const T &op1, const U &op2) |
| Greater-than or equal operator. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator> (const T &op1, const U &op2) |
| Greater-than operator. More...
|
|
template<typename T , typename U , rel_enabler< T, U > = 0> |
bool | operator<= (const T &op1, const U &op2) |
| Less-than or equal operator. More...
|
|
void | pow_ui (mp_integer &rop, const mp_integer &base, unsigned long exp) |
| Ternary exponentiation. More...
|
|
mp_integer | pow_ui (const mp_integer &base, unsigned long exp) |
| Binary exponentiation. More...
|
|
template<typename T , typename U > |
common_t< T, U > | pow (const T &base, const U &exp) |
| Generic binary exponentiation. More...
|
|
void | abs (mp_integer &rop, const mp_integer &n) |
| Binary absolute value. More...
|
|
mp_integer | abs (const mp_integer &n) |
| Unary absolute value. More...
|
|
std::size_t | hash (const mp_integer &n) |
| Hash value. More...
|
|
void | nextprime (mp_integer &rop, const mp_integer &n) |
| Compute next prime number (binary version). More...
|
|
mp_integer | nextprime (const mp_integer &n) |
| Compute next prime number (unary version). More...
|
|
int | probab_prime_p (const mp_integer &n, int reps=25) |
| Test primality. More...
|
|
void | sqrt (mp_integer &rop, const mp_integer &n) |
| Integer square root (binary version). More...
|
|
mp_integer | sqrt (const mp_integer &n) |
| Integer square root (unary version). More...
|
|
bool | odd_p (const mp_integer &n) |
| Test if integer is odd. More...
|
|
bool | even_p (const mp_integer &n) |
| Test if integer is even. More...
|
|
void | fac_ui (mp_integer &rop, unsigned long n) |
| Factorial. More...
|
|
void | bin_ui (mp_integer &rop, const mp_integer &n, unsigned long k) |
| Binomial coefficient (ternary version). More...
|
|
mp_integer | bin_ui (const mp_integer &n, unsigned long k) |
| Binomial coefficient (binary version). More...
|
|
template<typename T , typename U , binomial_enabler< T, U > = 0> |
mp_integer | binomial (const T &n, const U &k) |
| Generic binomial coefficient. More...
|
|
void | divexact (mp_integer &rop, const mp_integer &n, const mp_integer &d) |
| Exact division (ternary version). More...
|
|
mp_integer | divexact (const mp_integer &n, const mp_integer &d) |
| Exact division (binary version). More...
|
|
void | gcd (mp_integer &rop, const mp_integer &op1, const mp_integer &op2) |
| GCD (ternary version). More...
|
|
mp_integer | gcd (const mp_integer &op1, const mp_integer &op2) |
| GCD (binary version). More...
|
|
bool | is_zero (const mp_integer &n) |
| Test if an mppp::mp_integer is zero. More...
|
|
bool | is_one (const mp_integer &n) |
| Test if an mppp::mp_integer is equal to one. More...
|
|
bool | is_negative_one (const mp_integer &n) |
| Test if an mppp::mp_integer is equal to minus one. More...
|
|
template<std::size_t SSize>
class mppp::mp_integer< SSize >
Multiprecision integer class.
This class represent arbitrary-precision signed integers. It acts as a wrapper around the GMP mpz_t
type, with a small value optimisation: integers whose size is up to SSize
limbs are stored directly in the storage occupied by the mp_integer object, without resorting to dynamic memory allocation. The value of SSize
must be at least 1 and less than an implementation-defined upper limit.
When the value of an mp_integer is stored directly within the object, the storage type of the integer is said to be static. When the limb size of the integer exceeds the maximum value SSize
, the storage types becomes dynamic. The transition from static to dynamic storage happens transparently whenever the integer value becomes large enough. The demotion from dynamic to static storage usually needs to be requested explicitly. For values of SSize
of 1 and 2, optimised implementations of basic arithmetic operations are employed, if supported by the target architecture and if the storage type is static. For larger values of SSize
, the mpn_
low-level functions of the GMP API are used if the storage type is static. If the storage type is dynamic, the usual mpz_
functions from the GMP API are used.
Interoperable types
This class has the look and feel of a C++ builtin type: it can interact with most of C++'s integral and floating-point primitive types, and it provides overloaded arithmetic operators. Differently from the builtin types, however, this class does not allow any implicit conversion to/from other types (apart from bool
): construction from and conversion to primitive types must always be requested explicitly. As a side effect, syntax such as
mp_integer<1> n = 5;
int m = n;
will not work, and direct initialization and explicit casting should be used instead:
mp_integer<1> n{5};
int m = static_cast<int>(n);
The full list of interoperable builtin types is:
bool
,
char
, signed char
and unsigned char
,
short
and unsigned short
,
int
and unsigned
,
long
and unsigned long
,
long long
and unsigned long long
,
float
, double
and long double
(long double
requires the MPFR library).
API
Most of the functionality of this class is exposed via inline friend functions, with the general convention that the functions are named after the corresponding GMP functions minus the leading mpz_
prefix. For instance, the GMP call
that writes the result of a+b
into rop
becomes simply
where the add() function is resolved via argument-dependent lookup. Function calls with overlapping arguments are allowed, unless noted otherwise.
Multiple overloads of the same functionality are often available. Binary functions in GMP are usually implemented via three-arguments functions, in which the first argument is a reference to the return value. The exponentiation function mpz_pow_ui()
, for instance, takes three arguments: the return value, the base and the exponent. There are two overloads of the corresponding pow_ui() function:
- a ternary overload semantically equivalent to
mpz_pow_ui()
,
- a binary overload taking as inputs the base and the exponent, and returning the result of the exponentiation.
This allows to avoid having to set up a return value for one-off invocations of pow_ui() (the binary overload will do it for you). For example:
mp_integer<1> r1, r2, n{3};
In case of unary functions, there are often three overloads available:
- a binary overload taking as first parameter a reference to the return value (GMP style),
- a unary overload returning the result of the operation,
- a nullary member function that modifies the calling object in-place.
For instance, here are three possible ways of computing the absolute value:
mp_integer<1> r1, r2, n{-5};
n.abs();
Note that at this time only a small subset of the GMP API has been wrapped by mp_integer.
Overloaded operators
This class provides overloaded operators for the basic arithmetic operations, including bit shifting. The binary operators are implemented as inline friend functions, the in-place operators are implemented as member functions. The overloaded operators are resolved via argument-dependent lookup whenever at least one argument is of type mp_integer, and the other argument is either another mp_integer or an instance of an interoperable type.
For the common arithmetic operations (+
, -
, *
and /
), the type promotion rules are a natural extension of the corresponding rules for native C++ types: if the other argument is a C++ integral, the result will be of type mp_integer, if the other argument is a C++ floating-point the result will be of the same floating-point type. For example:
mp_integer<1> n1{1}, n2{2};
auto res1 = n1 + n2;
auto res2 = n1 * 2;
auto res3 = 2 - n2;
auto res4 = n1 / 2.f
auto res5 = 12. / n1
The modulo operator %
accepts only mp_integer and interoperable integral types as arguments, and it always returns mp_integer as result. The bit shifting operators <<
and >>
accept only interoperable integral types as shift arguments, and they always return mp_integer as result.
The relational operators, ==
, !=
, <
, >
, <=
and >=
will promote the arguments to a common type before comparing them. The promotion rules are the same as in the arithmetic operators (that is, both arguments are promoted to mp_integer if they are both integral types, otherwise they are promoted to the type of the floating-point argument).
Interfacing with GMP
This class provides facilities to interface with the GMP library. Specifically, mp_integer features:
- a constructor from the GMP integer type
mpz_t
,
- an mp_integer::get_mpz_t() method that promotes
this
to dynamic storage and returns a pointer to the internal mpz_t
instance,
- an
mpz_view
class, an instance of which can be requested via the mp_integer::get_mpz_view() method, which allows to use mp_integer in the GMP API as a drop-in replacement for const mpz_t
function arguments.
The mpz_view
class represent a read-only view of an mp_integer object which is implicitly convertible to the type const mpz_t
and which is thus usable as an argument to GMP functions. For example:
mpz_t m;
mpz_init_set_si(m,1);
mp_integer<1> n{1};
mpz_add(m,m,n.get_mpz_view());
See the documentation of mp_integer::get_mpz_view() for more details about the mpz_view
class.
Hashing
This class provides a hash() function to compute a hash value for an integer. A specialisation of the standard std::hash
functor is also provided, so that it is possible to use mp_integer in standard unordered associative containers out of the box.
Definition at line 869 of file mp++.hpp.