1[/ 2 Copyright 2011 - 2020 John Maddock. 3 Copyright 2013 - 2019 Paul A. Bristow. 4 Copyright 2013 Christopher Kormanyos. 5 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE_1_0.txt or copy at 8 http://www.boost.org/LICENSE_1_0.txt). 9] 10 11[section:cpp_int cpp_int] 12 13`#include <boost/multiprecision/cpp_int.hpp>` 14 15 namespace boost{ namespace multiprecision{ 16 17 typedef unspecified-type limb_type; 18 19 enum cpp_integer_type { signed_magnitude, unsigned_magnitude }; 20 enum cpp_int_check_type { checked, unchecked }; 21 22 template <unsigned MinBits = 0, 23 unsigned MaxBits = 0, 24 cpp_integer_type SignType = signed_magnitude, 25 cpp_int_check_type Checked = unchecked, 26 class Allocator = std::allocator<limb_type> > 27 class cpp_int_backend; 28 // 29 // Expression templates default to et_off if there is no allocator: 30 // 31 template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked> 32 struct expression_template_default<cpp_int_backend<MinBits, MaxBits, SignType, Checked, void> > 33 { static const expression_template_option value = et_off; }; 34 35 typedef number<cpp_int_backend<> > cpp_int; // arbitrary precision integer 36 typedef rational_adaptor<cpp_int_backend<> > cpp_rational_backend; 37 typedef number<cpp_rational_backend> cpp_rational; // arbitrary precision rational number 38 39 // Fixed precision unsigned types: 40 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> > uint128_t; 41 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> > uint256_t; 42 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> > uint512_t; 43 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t; 44 45 // Fixed precision signed types: 46 typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> > int128_t; 47 typedef number<cpp_int_backend<256, 256, signed_magnitude, unchecked, void> > int256_t; 48 typedef number<cpp_int_backend<512, 512, signed_magnitude, unchecked, void> > int512_t; 49 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, unchecked, void> > int1024_t; 50 51 // Over again, but with checking enabled this time: 52 typedef number<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_int; 53 typedef rational_adaptor<cpp_int_backend<0, 0, signed_magnitude, checked> > checked_cpp_rational_backend; 54 typedef number<cpp_rational_backend> checked_cpp_rational; 55 56 // Checked fixed precision unsigned types: 57 typedef number<cpp_int_backend<128, 128, unsigned_magnitude, checked, void> > checked_uint128_t; 58 typedef number<cpp_int_backend<256, 256, unsigned_magnitude, checked, void> > checked_uint256_t; 59 typedef number<cpp_int_backend<512, 512, unsigned_magnitude, checked, void> > checked_uint512_t; 60 typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, checked, void> > checked_uint1024_t; 61 62 // Fixed precision signed types: 63 typedef number<cpp_int_backend<128, 128, signed_magnitude, checked, void> > checked_int128_t; 64 typedef number<cpp_int_backend<256, 256, signed_magnitude, checked, void> > checked_int256_t; 65 typedef number<cpp_int_backend<512, 512, signed_magnitude, checked, void> > checked_int512_t; 66 typedef number<cpp_int_backend<1024, 1024, signed_magnitude, checked, void> > checked_int1024_t; 67 68 }} // namespaces 69 70The `cpp_int_backend` type is normally used via one of the convenience typedefs given above. 71 72This back-end is the "Swiss Army Knife" of integer types as it can represent both fixed and 73[@http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic arbitrary precision] 74integer types, and both signed and unsigned types. There are five template arguments: 75 76[variablelist 77[[MinBits][Determines the number of Bits to store directly within the object before resorting to dynamic memory 78 allocation. When zero, this field is determined automatically based on how many bits can be stored 79 in union with the dynamic storage header: setting a larger value may improve performance as larger integer 80 values will be stored internally before memory allocation is required.]] 81[[MaxBits][Determines the maximum number of bits to be stored in the type: resulting in a fixed precision type. 82 When this value is the same as MinBits, then the Allocator parameter is ignored, as no dynamic 83 memory allocation will ever be performed: in this situation the Allocator parameter should be set to 84 type `void`. Note that this parameter should not be used simply to prevent large memory 85 allocations, not only is that role better performed by the allocator, but fixed precision 86 integers have a tendency to allocate all of MaxBits of storage more often than one would expect.]] 87[[SignType][Determines whether the resulting type is signed or not. Note that for 88[@http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic arbitrary precision] types 89 this parameter must be `signed_magnitude`. For fixed precision 90 types then this type may be either `signed_magnitude` or `unsigned_magnitude`.]] 91[[Checked][This parameter has two values: `checked` or `unchecked`. See below.]] 92[[Allocator][The allocator to use for dynamic memory allocation, or type `void` if MaxBits == MinBits.]] 93] 94 95When the template parameter Checked is set to `checked` then the result is a ['checked-integer], checked 96and unchecked integers have the following properties: 97 98[table 99[[Condition][Checked-Integer][Unchecked-Integer]] 100[[Numeric overflow in fixed precision arithmetic][Throws a `std::overflow_error`.][Performs arithmetic modulo 2[super MaxBits]]] 101[[Constructing an integer from a value that can not be represented in the target type][Throws a `std::range_error`.] 102[Converts the value modulo 2[super MaxBits], signed to unsigned conversions extract the last MaxBits bits of the 1032's complement representation of the input value.]] 104[[Unsigned subtraction yielding a negative value.][Throws a `std::range_error`.][Yields the value that would 105result from treating the unsigned type as a 2's complement signed type.]] 106[[Attempting a bitwise operation on a negative value.][Throws a `std::range_error`][Yields the value, but not the bit pattern, 107that would result from performing the operation on a 2's complement integer type.]] 108] 109 110Things you should know when using this type: 111 112* Default constructed `cpp_int_backend`s have the value zero. 113* Division by zero results in a `std::overflow_error` being thrown. 114* Construction from a string that contains invalid non-numeric characters results in a `std::runtime_error` being thrown. 115* Since the precision of `cpp_int_backend` is necessarily limited when the allocator parameter is void, 116care should be taken to avoid numeric overflow when using this type 117unless you actually want modulo-arithmetic behavior. 118* The type uses a sign-magnitude representation internally, so type `int128_t` has 128-bits of precision plus an extra sign bit. 119In this respect the behaviour of these types differs from __fundamental 2's complement types. In might be tempting to use a 120127-bit type instead, and indeed this does work, but behaviour is still slightly different from a 2's complement __fundamental type 121as the minimum and maximum values are identical (apart from the sign), where as they differ by one for a true 2's complement type. 122That said it should be noted that there's no requirement for fundamental_types to be 2's complement either - it's simply that this 123is the most common format by far. 124* Attempting to print negative values as either an Octal or Hexadecimal string results in a `std::runtime_error` being thrown, 125this is a direct consequence of the sign-magnitude representation. 126* The fixed precision types `[checked_][u]intXXX_t` have expression template support turned off - it seems to make little 127difference to the performance of these types either way - so we may as well have the faster compile times by turning 128the feature off. 129* Unsigned types support subtraction - the result is "as if" a 2's complement operation had been performed as long as they are not 130 ['checked-integers] (see above). 131 In other words they behave pretty much as a __fundamental integer type would in this situation. So for example if we were using 132 `uint128_t` then `uint128_t(1)-4` would result in the value `0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD` 133 of type `uint128_t`. However, had this operation been performed on `checked_uint128_t` then a `std::range_error` would have 134 been thrown. 135* Unary negation of unsigned types results in a compiler error (static assertion). 136* This backend supports rvalue-references and is move-aware, making instantiations of `number` on this backend move aware. 137* When used at fixed precision, the size of this type is always one machine word (plus any compiler-applied alignment padding) 138larger than you would expect for an N-bit integer: 139the extra word stores both the sign, and how many machine words in the integer are actually in use. 140The latter is an optimisation for larger fixed precision integers, so that a 1024-bit integer has almost the same performance 141characteristics as a 128-bit integer, rather than being 4 times slower for addition and 16 times slower for multiplication 142 (assuming the values involved would always fit in 128 bits). 143Typically this means you can use 144an integer type wide enough for the "worst case scenario" with only minor performance degradation even if most of the time 145the arithmetic could in fact be done with a narrower type. 146Also note that unsigned fixed precision types small enough to fit inside the largest native integer become a simple wrapper around that type, 147this includes the "checked" variants. Small signed types will always have an extra sign word and so be larger than their native equivalent. 148* When used at fixed precision and MaxBits is smaller than the number of bits in the largest native integer type, then 149internally `cpp_int_backend` switches to a "trivial" implementation where it is just a thin wrapper around a single 150integer. Note that it will still be slightly slower than a bare native integer, as it emulates a 151signed-magnitude representation rather than simply using the platforms native sign representation: this ensures 152there is no step change in behavior as a cpp_int grows in size. 153* Fixed precision `cpp_int`'s have some support for `constexpr` values and user-defined literals, see 154[link boost_multiprecision.tut.lits here] for the full description. For example `0xfffff_cppi1024` 155specifies a 1024-bit integer with the value 0xffff. This can be used to generate compile-time constants that are 156too large to fit into any __fundamental number type. 157* The __cpp_int types support constexpr arithmetic, provided it is a fixed-precision type with no allocator. It may also 158be a checked integer: in which case a compiler error will be generated on overflow or undefined behaviour. In addition 159the free functions `abs`, `swap`, `multiply`, `add`, `subtract`, `divide_qr`, `integer_modulus`, `powm`, `lsb`, `msb`, 160`bit_test`, `bit_set`, `bit_unset`, `bit_flip`, `sqrt`, `gcd`, `lcm` are all supported. Use of __cpp_int in this way 161requires either a C++2a compiler (one which supports `std::is_constant_evaluated()`), or GCC-6 or later in C++14 mode. 162Compilers other than GCC and without `std::is_constant_evaluated()` will support a very limited set of operations: 163expect to hit roadblocks rather easily. 164* You can import/export the raw bits of a __cpp_int to and from external storage via the `import_bits` and `export_bits` 165functions. More information is in the [link boost_multiprecision.tut.import_export section on import/export]. 166 167[h5:cpp_int_eg Example:] 168 169[cpp_int_eg] 170 171[endsect] [/section:cpp_int cpp_int] 172