...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
#include <boost/multiprecision/cpp_int.hpp>
namespace boost{ namespace multiprecision{ typedef unspecified-type limb_type; enum cpp_integer_type { signed_magnitude, unsigned_magnitude }; enum cpp_int_check_type { checked, unchecked }; template <unsigned MinBits = 0, unsigned MaxBits = 0, cpp_integer_type SignType = signed_magnitude, cpp_int_check_type Checked = unchecked, class Allocator = std::allocator<limb_type> > class cpp_int_backend; // // Expression templates default to et_off if there is no allocator: // template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked> struct expression_template_default<cpp_int_backend<MinBits, MaxBits, SignType, Checked, void> > { static const expression_template_option value = et_off; }; typedef number<cpp_int_backend<> > cpp_int; // arbitrary precision integer typedef rational_adaptor<cpp_int_backend<> > cpp_rational_backend; typedef number<cpp_rational_backend> cpp_rational; // arbitrary precision rational number // Fixed precision unsigned types: typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> > uint128_t; typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> > uint256_t; typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> > uint512_t; typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t; // Fixed precision signed types: typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> > int128_t; typedef number<cpp_int_backend<256, 256, signed_magnitude, unchecked, void> > int256_t; typedef number<cpp_int_backend<512, 512, signed_magnitude, unchecked, void> > int512_t; typedef number<cpp_int_backend<1024, 1024, signed_magnitude, unchecked, void> > int1024_t; // Over again, but with checking enabled this time: typedef number<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_int; typedef rational_adaptor<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_rational_backend; typedef number<cpp_rational_backend> checked_cpp_rational; // Checked fixed precision unsigned types: typedef number<cpp_int_backend<128, 128, unsigned_magnitude, checked, void> > checked_uint128_t; typedef number<cpp_int_backend<256, 256, unsigned_magnitude, checked, void> > checked_uint256_t; typedef number<cpp_int_backend<512, 512, unsigned_magnitude, checked, void> > checked_uint512_t; typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, checked, void> > checked_uint1024_t; // Fixed precision signed types: typedef number<cpp_int_backend<128, 128, signed_magnitude, checked, void> > checked_int128_t; typedef number<cpp_int_backend<256, 256, signed_magnitude, checked, void> > checked_int256_t; typedef number<cpp_int_backend<512, 512, signed_magnitude, checked, void> > checked_int512_t; typedef number<cpp_int_backend<1024, 1024, signed_magnitude, checked, void> > checked_int1024_t; }} // namespaces
The cpp_int_backend
type
is normally used via one of the convenience typedefs given above.
This back-end is the "Swiss Army Knife" of integer types as it can represent both fixed and arbitrary precision integer types, and both signed and unsigned types. There are five template arguments:
Determines the number of Bits to store directly within the object before resorting to dynamic memory allocation. When zero, this field is determined automatically based on how many bits can be stored in union with the dynamic storage header: setting a larger value may improve performance as larger integer values will be stored internally before memory allocation is required.
Determines the maximum number of bits to be stored in the type: resulting
in a fixed precision type. When this value is the same as MinBits,
then the Allocator parameter is ignored, as no dynamic memory allocation
will ever be performed: in this situation the Allocator parameter
should be set to type void
.
Note that this parameter should not be used simply to prevent large
memory allocations, not only is that role better performed by the
allocator, but fixed precision integers have a tendency to allocate
all of MaxBits of storage more often than one would expect.
Determines whether the resulting type is signed or not. Note that
for arbitrary
precision types this parameter must be signed_magnitude
.
For fixed precision types then this type may be either signed_magnitude
or unsigned_magnitude
.
This parameter has two values: checked
or unchecked
. See
below.
The allocator to use for dynamic memory allocation, or type void
if MaxBits == MinBits.
When the template parameter Checked is set to checked
then the result is a checked-integer, checked and
unchecked integers have the following properties:
Condition |
Checked-Integer |
Unchecked-Integer |
---|---|---|
Numeric overflow in fixed precision arithmetic |
Throws a |
Performs arithmetic modulo 2^{MaxBits} |
Constructing an integer from a value that can not be represented in the target type |
Throws a |
Converts the value modulo 2^{MaxBits}, signed to unsigned conversions extract the last MaxBits bits of the 2's complement representation of the input value. |
Unsigned subtraction yielding a negative value. |
Throws a |
Yields the value that would result from treating the unsigned type as a 2's complement signed type. |
Attempting a bitwise operation on a negative value. |
Throws a |
Yields the value, but not the bit pattern, that would result from performing the operation on a 2's complement integer type. |
Things you should know when using this type:
cpp_int_backend
s
have the value zero.
std::overflow_error
being thrown.
std::runtime_error
being thrown.
cpp_int_backend
is necessarily limited when the allocator parameter is void, care should
be taken to avoid numeric overflow when using this type unless you
actually want modulo-arithmetic behavior.
int128_t
has 128-bits
of precision plus an extra sign bit. In this respect the behaviour
of these types differs from fundamental
(built-in) 2's complement types. In might be tempting to use
a 127-bit type instead, and indeed this does work, but behaviour is
still slightly different from a 2's complement fundamental
(built-in) type as the minimum and maximum values are identical
(apart from the sign), where as they differ by one for a true 2's complement
type. That said it should be noted that there's no requirement for
fundamental_types to be 2's complement either - it's simply that this
is the most common format by far.
std::runtime_error
being thrown, this is a direct consequence of the sign-magnitude representation.
[checked_][u]intXXX_t
have expression template
support turned off - it seems to make little difference to the performance
of these types either way - so we may as well have the faster compile
times by turning the feature off.
uint128_t
then uint128_t(1)-4
would result in the value 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD
of type uint128_t
.
However, had this operation been performed on checked_uint128_t
then a std::range_error
would have been thrown.
number
on this backend
move aware.
cpp_int_backend
switches to a "trivial"
implementation where it is just a thin wrapper around a single integer.
Note that it will still be slightly slower than a bare native integer,
as it emulates a signed-magnitude representation rather than simply
using the platforms native sign representation: this ensures there
is no step change in behavior as a cpp_int grows in size.
cpp_int
's
have some support for constexpr
values and user-defined literals, see here
for the full description. For example 0xfffff_cppi1024
specifies a 1024-bit integer
with the value 0xffff. This can be used to generate compile-time constants
that are too large to fit into any fundamental
(built-in) number type.
abs
,
swap
, multiply
, add
,
subtract
, divide_qr
, integer_modulus
,
powm
, lsb
, msb
,
bit_test
, bit_set
, bit_unset
,
bit_flip
, sqrt
, gcd
,
lcm
are all supported.
Use of cpp_int
in this way requires either a C++2a compiler (one which supports std::is_constant_evaluated()
),
or GCC-6 or later in C++14 mode. Compilers other than GCC and without
std::is_constant_evaluated()
will support a very limited set of operations: expect to hit roadblocks
rather easily.
import_bits
and export_bits
functions.
More information is in the section
on import/export.
#include <boost/multiprecision/cpp_int.hpp> #include <iostream> int main() { using namespace boost::multiprecision; int128_t v = 1; // Do some fixed precision arithmetic: for(unsigned i = 1; i <= 20; ++i) v *= i; std::cout << v << std::endl; // prints 2432902008176640000 (i.e. 20!) // Repeat at arbitrary precision: cpp_int u = 1; for(unsigned i = 1; i <= 100; ++i) u *= i; // prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 (i.e. 100!) std::cout << u << std::endl; return 0; }