...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
All of the non-member
integer operations are overloaded for the built in integer types in
<boost/multiprecision/integer.hpp>
.
Where these operations require a temporary increase in precision (such as
for powm), then if no built in type is available, a cpp_int
of appropriate precision will be used.
Some of these functions are trivial, others use compiler intrinsics (where available) to ensure optimal evaluation.
The overloaded functions are:
template <class Integer, class I2> Integer& multiply(Integer& result, const I2& a, const I2& b);
Multiplies two I2
values,
to produce a wider Integer
result.
Returns result =
a * b
without overflow or loss of precision
in the multiplication.
template <class Integer, class I2> Integer& add(Integer& result, const I2& a, const I2& b);
Adds two I2
values, to produce
a wider Integer
result.
Returns result =
a + b
without overflow or loss of precision
in the addition.
template <class Integer, class I2> Integer& subtract(Integer& result, const I2& a, const I2& b);
Subtracts two I2
values,
to produce a wider Integer
result.
Returns result =
a - b
without overflow or loss of precision
in the subtraction.
template <class Integer> Integer powm(const Integer& b, const Integer& p, const Integer& m);
Returns bp % m.
template <class Integer> void divide_qr(const Integer& x, const Integer& y, Integer& q, Integer& r);
Sets q =
x / y
and r
= x % y
.
template <class Integer1, class Integer2> Integer2 integer_modulus(const Integer1& x, Integer2 val);
Returns x % val;
template <class Integer> unsigned lsb(const Integer& x);
Returns the (zero-based) index of the least significant bit of x
.
Throws a std::domain_error
if x
<= 0
.
template <class Integer> unsigned msb(const Integer& x);
Returns the (zero-based) index of the most significant bit of x
.
Throws a std::domain_error
if x
<= 0
.
template <class Integer> bool bit_test(const Integer& val, unsigned index);
Returns true
if bit index
is set in val
.
template <class Integer> Integer& bit_set(Integer& val, unsigned index);
Sets the index
bit in val
.
template <class Integer> Integer& bit_unset(Integer& val, unsigned index);
Unsets the index
bit in
val
.
template <class Integer> Integer& bit_flip(Integer& val, unsigned index);
Flips the index
bit in val
.
template <class Integer> Integer sqrt(const Integer& x); template <class Integer> Integer sqrt(const Integer& x, Integer& r);
Returns the integer square root s
of x and sets r
to the remainder
x - s2.
template <class Engine> bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials, Engine& gen); bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials);
The regular Miller-Rabin functions in <boost/multiprecision/miller_rabin.hpp>
are defined in terms of the above generic operations, and so function equally
well for built in and multiprecision types.