multiprecision/cpp_int/multiply.hpp

0001 ///////////////////////////////////////////////////////////////
0002 //  Copyright 2012-20 John Maddock.
0003 //  Copyright 2019-20 Christopher Kormanyos.
0004 //  Copyright 2019-20 Madhur Chauhan.
0005 //  Distributed under the Boost Software License, Version 1.0.
0006 //  (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // Comparison operators for cpp_int_backend:
0009 //
0010 #ifndef BOOST_MP_CPP_INT_MULTIPLY_HPP
0011 #define BOOST_MP_CPP_INT_MULTIPLY_HPP
0012
0013 #include <limits>
0014 #include <boost/multiprecision/detail/standalone_config.hpp>
0015 #include <boost/multiprecision/detail/endian.hpp>
0016 #include <boost/multiprecision/detail/assert.hpp>
0017 #include <boost/multiprecision/integer.hpp>
0018
0019 namespace boost { namespace multiprecision { namespace backends {
0020
0021 #ifdef BOOST_MSVC
0022 #pragma warning(push)
0023 #pragma warning(disable : 4127) // conditional expression is constant
0024 #endif
0025 //
0026 // Multiplication by a single limb:
0027 //
0028 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0029 inline BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0030 eval_multiply(
0031     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0032     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0033     const limb_type&                                                            val) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0034 {
0035    if (!val)
0036    {
0037       result = static_cast<limb_type>(0);
0038       return;
0039    }
0040    if ((void*)&a != (void*)&result)
0041       result.resize(a.size(), a.size());
0042    double_limb_type                                                                                  carry = 0;
0043    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer       p     = result.limbs();
0044    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer       pe    = result.limbs() + result.size();
0045    typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa    = a.limbs();
0046    while (p != pe)
0047    {
0048       carry += static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(val);
0049 #ifdef __MSVC_RUNTIME_CHECKS
0050       *p = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0051 #else
0052       *p = static_cast<limb_type>(carry);
0053 #endif
0054       carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
0055       ++p, ++pa;
0056    }
0057    if (carry)
0058    {
0059       std::size_t i = result.size();
0060       result.resize(i + 1, i + 1);
0061       if (result.size() > i)
0062          result.limbs()[i] = static_cast<limb_type>(carry);
0063    }
0064    result.sign(a.sign());
0065    if (is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
0066       result.normalize();
0067 }
0068
0069 //
0070 // resize_for_carry forces a resize of the underlying buffer only if a previous request
0071 // for "required" elements could possibly have failed, *and* we have checking enabled.
0072 // This will cause an overflow error inside resize():
0073 //
0074 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0075 inline BOOST_MP_CXX14_CONSTEXPR void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& /*result*/, std::size_t /*required*/) {}
0076
0077 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, class Allocator1>
0078 inline BOOST_MP_CXX14_CONSTEXPR void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, checked, Allocator1>& result, std::size_t required)
0079 {
0080    if (result.size() < required)
0081       result.resize(required, required);
0082 }
0083 //
0084 // Minimum number of limbs required for Karatsuba to be worthwhile:
0085 //
0086 #ifdef BOOST_MP_KARATSUBA_CUTOFF
0087 const size_t karatsuba_cutoff = BOOST_MP_KARATSUBA_CUTOFF;
0088 #else
0089 const size_t karatsuba_cutoff = 40;
0090 #endif
0091 //
0092 // Core (recursive) Karatsuba multiplication, all the storage required is allocated upfront and
0093 // passed down the stack in this routine.  Note that all the cpp_int_backend's must be the same type
0094 // and full variable precision.  Karatsuba really doesn't play nice with fixed-size integers.  If necessary
0095 // fixed precision integers will get aliased as variable-precision types before this is called.
0096 //
0097 template <std::size_t MinBits, std::size_t MaxBits, cpp_int_check_type Checked, class Allocator>
0098 inline void multiply_karatsuba(
0099     cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>&       result,
0100     const cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>& a,
0101     const cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>& b,
0102     typename cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>::scoped_shared_storage& storage)
0103 {
0104    using cpp_int_type = cpp_int_backend<MinBits, MaxBits, signed_magnitude, Checked, Allocator>;
0105
0106    std::size_t as = a.size();
0107    std::size_t bs = b.size();
0108    //
0109    // Termination condition: if either argument is smaller than karatsuba_cutoff
0110    // then schoolboy multiplication will be faster:
0111    //
0112    if ((as < karatsuba_cutoff) || (bs < karatsuba_cutoff))
0113    {
0114       eval_multiply(result, a, b);
0115       return;
0116    }
0117    //
0118    // Partitioning size: split the larger of a and b into 2 halves
0119    //
0120    std::size_t n  = (as > bs ? as : bs) / 2 + 1;
0121    //
0122    // Partition a and b into high and low parts.
0123    // ie write a, b as a = a_h * 2^n + a_l, b = b_h * 2^n + b_l
0124    //
0125    // We could copy the high and low parts into new variables, but we'll
0126    // use aliasing to reference the internal limbs of a and b.  There is one wart here:
0127    // if a and b are mismatched in size, then n may be larger than the smaller
0128    // of a and b.  In that situation the high part is zero, and we have no limbs
0129    // to alias, so instead alias a local variable.
0130    // This raises 2 questions:
0131    // * Is this the best way to partition a and b?
0132    // * Since we have one high part zero, the arithmetic simplifies considerably,
0133    //   so should we have a special routine for this?
0134    //
0135    std::size_t          sz = (std::min)(as, n);
0136    const cpp_int_type a_l(a.limbs(), 0, sz);
0137
0138    sz = (std::min)(bs, n);
0139    const cpp_int_type b_l(b.limbs(), 0, sz);
0140
0141    limb_type          zero = 0;
0142    const cpp_int_type a_h(as > n ? a.limbs() + n : &zero, 0, as > n ? as - n : 1);
0143    const cpp_int_type b_h(bs > n ? b.limbs() + n : &zero, 0, bs > n ? bs - n : 1);
0144    //
0145    // The basis for the Karatsuba algorithm is as follows:
0146    //
0147    // let                x = a_h * b_ h
0148    //                    y = a_l * b_l
0149    //                    z = (a_h + a_l)*(b_h + b_l) - x - y
0150    // and therefore  a * b = x * (2 ^ (2 * n))+ z * (2 ^ n) + y
0151    //
0152    // Begin by allocating our temporaries, these alias the memory already allocated in the shared storage:
0153    //
0154    cpp_int_type t1(storage, 2 * n + 2);
0155    cpp_int_type t2(storage, n + 1);
0156    cpp_int_type t3(storage, n + 1);
0157    //
0158    // Now we want:
0159    //
0160    // result = | a_h*b_h  | a_l*b_l |
0161    // (bits)              <-- 2*n -->
0162    //
0163    // We create aliases for the low and high parts of result, and multiply directly into them:
0164    //
0165    cpp_int_type result_low(result.limbs(), 0, 2 * n);
0166    cpp_int_type result_high(result.limbs(), 2 * n, result.size() - 2 * n);
0167    //
0168    // low part of result is a_l * b_l:
0169    //
0170    multiply_karatsuba(result_low, a_l, b_l, storage);
0171    //
0172    // We haven't zeroed out memory in result, so set to zero any unused limbs,
0173    // if a_l and b_l have mostly random bits then nothing happens here, but if
0174    // one is zero or nearly so, then a memset might be faster... it's not clear
0175    // that it's worth the extra logic though (and is darn hard to measure
0176    // what the "average" case is).
0177    //
0178    for (std::size_t i = result_low.size(); i < 2 * n; ++i)
0179       result.limbs()[i] = 0;
0180    //
0181    // Set the high part of result to a_h * b_h:
0182    //
0183    multiply_karatsuba(result_high, a_h, b_h, storage);
0184    for (std::size_t i = result_high.size() + 2 * n; i < result.size(); ++i)
0185       result.limbs()[i] = 0;
0186    //
0187    // Now calculate (a_h+a_l)*(b_h+b_l):
0188    //
0189    add_unsigned(t2, a_l, a_h);
0190    add_unsigned(t3, b_l, b_h);
0191    multiply_karatsuba(t1, t2, t3, storage); // t1 = (a_h+a_l)*(b_h+b_l)
0192    //
0193    // There is now a slight deviation from Karatsuba, we want to subtract
0194    // a_l*b_l + a_h*b_h from t1, but rather than use an addition and a subtraction
0195    // plus one temporary, we'll use 2 subtractions.  On the minus side, a subtraction
0196    // is on average slightly slower than an addition, but we save a temporary (ie memory)
0197    // and also hammer the same piece of memory over and over rather than 2 disparate
0198    // memory regions.  Overall it seems to be a slight win.
0199    //
0200    subtract_unsigned(t1, t1, result_high);
0201    subtract_unsigned(t1, t1, result_low);
0202    //
0203    // The final step is to left shift t1 by n bits and add to the result.
0204    // Rather than do an actual left shift, we can simply alias the result
0205    // and add to the alias:
0206    //
0207    cpp_int_type result_alias(result.limbs(), n, result.size() - n);
0208    add_unsigned(result_alias, result_alias, t1);
0209    //
0210    // Free up storage for use by sister branches to this one:
0211    //
0212    storage.deallocate(t1.capacity() + t2.capacity() + t3.capacity());
0213
0214    result.normalize();
0215 }
0216
0217 inline std::size_t karatsuba_storage_size(std::size_t s)
0218 {
0219    //
0220    // This estimates how much memory we will need based on
0221    // s-limb multiplication.  In an ideal world the number of limbs
0222    // would halve with each recursion, and our storage requirements
0223    // would be 4s in the limit, and rather less in practice since
0224    // we bail out long before we reach one limb.  In the real world
0225    // we don't quite halve s in each recursion, so this is an heuristic
0226    // which over-estimates how much we need.  We could compute an exact
0227    // value, but it would be rather time consuming.
0228    //
0229    return 5 * s;
0230 }
0231 //
0232 // There are 2 entry point routines for Karatsuba multiplication:
0233 // one for variable precision types, and one for fixed precision types.
0234 // These are responsible for allocating all the storage required for the recursive
0235 // routines above, and are always at the outermost level.
0236 //
0237 // Normal variable precision case comes first:
0238 //
0239 template <std::size_t MinBits, std::size_t MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
0240 inline typename std::enable_if<!is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>::type
0241 setup_karatsuba(
0242    cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& result,
0243    const cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& a,
0244    const cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>& b)
0245 {
0246    std::size_t as = a.size();
0247    std::size_t bs = b.size();
0248    std::size_t s = as > bs ? as : bs;
0249    std::size_t storage_size = karatsuba_storage_size(s);
0250    if (storage_size < 300)
0251    {
0252       //
0253       // Special case: if we don't need too much memory, we can use stack based storage
0254       // and save a call to the allocator, this allows us to use Karatsuba multiply
0255       // at lower limb counts than would otherwise be possible:
0256       //
0257       limb_type limbs[300];
0258       typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::scoped_shared_storage storage(limbs, storage_size);
0259       multiply_karatsuba(result, a, b, storage);
0260    }
0261    else
0262    {
0263       typename cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>::scoped_shared_storage storage(result.allocator(), storage_size);
0264       multiply_karatsuba(result, a, b, storage);
0265    }
0266 }
0267
0268 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
0269 inline typename std::enable_if<is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_fixed_precision<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value || is_fixed_precision<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
0270 setup_karatsuba(
0271     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0272     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0273     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
0274 {
0275    //
0276    // Now comes the fixed precision case.
0277    // In fact Karatsuba doesn't really work with fixed precision since the logic
0278    // requires that we calculate all the bits of the result (especially in the
0279    // temporaries used internally).  So... we'll convert all the arguments
0280    // to variable precision types by aliasing them, this also
0281    // reduce the number of template instantations:
0282    //
0283    using variable_precision_type = cpp_int_backend<0, 0, signed_magnitude, unchecked, std::allocator<limb_type> >;
0284    variable_precision_type a_t(a.limbs(), 0, a.size()), b_t(b.limbs(), 0, b.size());
0285    std::size_t as = a.size();
0286    std::size_t bs = b.size();
0287    std::size_t s = as > bs ? as : bs;
0288    std::size_t sz = as + bs;
0289    std::size_t storage_size = karatsuba_storage_size(s);
0290
0291    if (!is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || (sz * sizeof(limb_type) * CHAR_BIT <= MaxBits1))
0292    {
0293       // Result is large enough for all the bits of the result, so we can use aliasing:
0294       result.resize(sz, sz);
0295       variable_precision_type t(result.limbs(), 0, result.size());
0296       typename variable_precision_type::scoped_shared_storage storage(t.allocator(), storage_size);
0297       multiply_karatsuba(t, a_t, b_t, storage);
0298       result.resize(t.size(), t.size());
0299    }
0300    else
0301    {
0302       //
0303       // Not enough bit in result for the answer, so we must use a temporary
0304       // and then truncate (ie modular arithmetic):
0305       //
0306       typename variable_precision_type::scoped_shared_storage storage(variable_precision_type::allocator_type(), sz + storage_size);
0307       variable_precision_type t(storage, sz);
0308       multiply_karatsuba(t, a_t, b_t, storage);
0309       //
0310       // If there is truncation, and result is a checked type then this will throw:
0311       //
0312       result = t;
0313    }
0314 }
0315 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
0316 inline typename std::enable_if<!is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_fixed_precision<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_fixed_precision<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
0317 setup_karatsuba(
0318    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
0319    const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0320    const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
0321 {
0322    //
0323    // Variable precision, mixed arguments, just alias and forward:
0324    //
0325    using variable_precision_type = cpp_int_backend<0, 0, signed_magnitude, unchecked, std::allocator<limb_type> >;
0326    variable_precision_type a_t(a.limbs(), 0, a.size()), b_t(b.limbs(), 0, b.size());
0327    std::size_t as = a.size();
0328    std::size_t bs = b.size();
0329    std::size_t s = as > bs ? as : bs;
0330    std::size_t sz = as + bs;
0331    std::size_t storage_size = karatsuba_storage_size(s);
0332
0333    result.resize(sz, sz);
0334    variable_precision_type t(result.limbs(), 0, result.size());
0335    typename variable_precision_type::scoped_shared_storage storage(t.allocator(), storage_size);
0336    multiply_karatsuba(t, a_t, b_t, storage);
0337 }
0338
0339 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
0340 inline BOOST_MP_CXX14_CONSTEXPR void
0341 eval_multiply_comba(
0342     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0343     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0344     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0345 {
0346    //
0347    // see PR #182
0348    // Comba Multiplier - based on Paul Comba's
0349    // Exponentiation cryptosystems on the IBM PC, 1990
0350    //
0351    std::ptrdiff_t as                                                                                         = a.size(),
0352        bs                                                                                         = b.size(),
0353        rs                                                                                         = result.size();
0354    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
0355
0356    double_limb_type carry    = 0,
0357                     temp     = 0;
0358    limb_type      overflow   = 0;
0359    const std::size_t limb_bits  = sizeof(limb_type) * CHAR_BIT;
0360    const bool     must_throw = rs < as + bs - 1;
0361    for (std::ptrdiff_t r = 0, lim = (std::min)(rs, as + bs - 1); r < lim; ++r, overflow = 0)
0362    {
0363       std::ptrdiff_t i = r >= as ? as - 1 : r,
0364           j = r - i,
0365           k = i < bs - j ? i + 1 : bs - j; // min(i+1, bs-j);
0366
0367       typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs() + i;
0368       typename cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>::const_limb_pointer pb = b.limbs() + j;
0369
0370       temp = carry;
0371       carry += static_cast<double_limb_type>(*(pa)) * (*(pb));
0372       overflow += carry < temp;
0373       for (--k; k; k--)
0374       {
0375          temp = carry;
0376          carry += static_cast<double_limb_type>(*(--pa)) * (*(++pb));
0377          overflow += carry < temp;
0378       }
0379       *(pr++) = static_cast<limb_type>(carry);
0380       carry   = (static_cast<double_limb_type>(overflow) << limb_bits) | (carry >> limb_bits);
0381    }
0382    if (carry || must_throw)
0383    {
0384       resize_for_carry(result, as + bs);
0385       if (static_cast<int>(result.size()) >= as + bs)
0386          *pr = static_cast<limb_type>(carry);
0387    }
0388 }
0389 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, std::size_t MinBits3, std::size_t MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
0390 inline BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value>::type
0391 eval_multiply(
0392     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0393     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0394     const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
0395    noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
0396       && (karatsuba_cutoff * sizeof(limb_type) * CHAR_BIT > MaxBits1)
0397       && (karatsuba_cutoff * sizeof(limb_type)* CHAR_BIT > MaxBits2)
0398       && (karatsuba_cutoff * sizeof(limb_type)* CHAR_BIT > MaxBits3)))
0399 {
0400    // Uses simple (O(n^2)) multiplication when the limbs are less
0401    // otherwise switches to karatsuba algorithm based on experimental value (~40 limbs)
0402    //
0403    // Trivial cases first:
0404    //
0405    std::size_t                                                                                          as = a.size();
0406    std::size_t                                                                                          bs = b.size();
0407    typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs();
0408    typename cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>::const_limb_pointer pb = b.limbs();
0409    if (as == 1)
0410    {
0411       bool s = b.sign() != a.sign();
0412       if (bs == 1)
0413       {
0414          result = static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(*pb);
0415       }
0416       else
0417       {
0418          limb_type l = *pa;
0419          eval_multiply(result, b, l);
0420       }
0421       result.sign(s);
0422       return;
0423    }
0424    if (bs == 1)
0425    {
0426       bool      s = b.sign() != a.sign();
0427       limb_type l = *pb;
0428       eval_multiply(result, a, l);
0429       result.sign(s);
0430       return;
0431    }
0432
0433    if ((void*)&result == (void*)&a)
0434    {
0435       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(a);
0436       eval_multiply(result, t, b);
0437       return;
0438    }
0439    if ((void*)&result == (void*)&b)
0440    {
0441       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(b);
0442       eval_multiply(result, a, t);
0443       return;
0444    }
0445
0446    constexpr double_limb_type limb_max        = static_cast<double_limb_type>(~static_cast<limb_type>(0u));
0447    constexpr double_limb_type double_limb_max = static_cast<double_limb_type>(~static_cast<double_limb_type>(0u));
0448
0449    result.resize(as + bs, as + bs - 1);
0450 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0451    if (!BOOST_MP_IS_CONST_EVALUATED(as) && (as >= karatsuba_cutoff && bs >= karatsuba_cutoff))
0452 #else
0453    if (as >= karatsuba_cutoff && bs >= karatsuba_cutoff)
0454 #endif
0455    {
0456       setup_karatsuba(result, a, b);
0457       //
0458       // Set the sign of the result:
0459       //
0460       result.sign(a.sign() != b.sign());
0461       return;
0462    }
0463    typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
0464    static_assert(double_limb_max - 2 * limb_max >= limb_max * limb_max, "failed limb size sanity check");
0465
0466 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0467    if (BOOST_MP_IS_CONST_EVALUATED(as))
0468    {
0469       for (std::size_t i = 0; i < result.size(); ++i)
0470          pr[i] = 0;
0471    }
0472    else
0473 #endif
0474    std::memset(pr, 0, result.size() * sizeof(limb_type));
0475
0476 #if defined(BOOST_MP_COMBA)
0477        //
0478        // Comba Multiplier might not be efficient because of less efficient assembly
0479        // by the compiler as of 09/01/2020 (DD/MM/YY). See PR #182
0480        // Till then this will lay dormant :(
0481        //
0482        eval_multiply_comba(result, a, b);
0483 #else
0484
0485    double_limb_type carry = 0;
0486    for (std::size_t i = 0; i < as; ++i)
0487    {
0488       BOOST_MP_ASSERT(result.size() > i);
0489       std::size_t inner_limit = !is_fixed_precision<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value ? bs : (std::min)(result.size() - i, bs);
0490       std::size_t j           = 0;
0491       for (; j < inner_limit; ++j)
0492       {
0493          BOOST_MP_ASSERT(i + j < result.size());
0494 #if (!defined(__GLIBCXX__) && !defined(__GLIBCPP__)) || !BOOST_WORKAROUND(BOOST_GCC_VERSION, <= 50100)
0495          BOOST_MP_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized || ((std::numeric_limits<double_limb_type>::max)() - carry >
0496                                                                                  static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value) * static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value)));
0497 #endif
0498          carry += static_cast<double_limb_type>(pa[i]) * static_cast<double_limb_type>(pb[j]);
0499          BOOST_MP_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized || ((std::numeric_limits<double_limb_type>::max)() - carry >= pr[i + j]));
0500          carry += pr[i + j];
0501 #ifdef __MSVC_RUNTIME_CHECKS
0502          pr[i + j] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0503 #else
0504          pr[i + j] = static_cast<limb_type>(carry);
0505 #endif
0506          carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
0507          BOOST_MP_ASSERT(carry <= (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value));
0508       }
0509       if (carry)
0510       {
0511          resize_for_carry(result, i + j + 1); // May throw if checking is enabled
0512          if (i + j < result.size())
0513 #ifdef __MSVC_RUNTIME_CHECKS
0514             pr[i + j] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0515 #else
0516             pr[i + j] = static_cast<limb_type>(carry);
0517 #endif
0518       }
0519       carry = 0;
0520    }
0521 #endif // ifdef(BOOST_MP_COMBA) ends
0522
0523    result.normalize();
0524    //
0525    // Set the sign of the result:
0526    //
0527    result.sign(a.sign() != b.sign());
0528 }
0529
0530 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0531 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0532 eval_multiply(
0533     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0534     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a)
0535    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>()))))
0536 {
0537    eval_multiply(result, result, a);
0538 }
0539
0540 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0541 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0542 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const limb_type& val)
0543    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>()))))
0544 {
0545    eval_multiply(result, result, val);
0546 }
0547
0548 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0549 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0550 eval_multiply(
0551     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0552     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0553     const double_limb_type&                                                     val)
0554    noexcept(
0555       (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>())))
0556       && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
0557    )
0558 {
0559    if (val <= (std::numeric_limits<limb_type>::max)())
0560    {
0561       eval_multiply(result, a, static_cast<limb_type>(val));
0562    }
0563    else
0564    {
0565 #if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
0566       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
0567 #else
0568       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
0569       t = val;
0570 #endif
0571       eval_multiply(result, a, t);
0572    }
0573 }
0574
0575 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0576 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0577 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const double_limb_type& val)
0578    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const double_limb_type&>()))))
0579 {
0580    eval_multiply(result, result, val);
0581 }
0582
0583 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0584 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0585 eval_multiply(
0586     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0587     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0588     const signed_limb_type&                                                     val)
0589    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>()))))
0590 {
0591    if (val > 0)
0592       eval_multiply(result, a, static_cast<limb_type>(val));
0593    else
0594    {
0595       eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
0596       result.negate();
0597    }
0598 }
0599
0600 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0601 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0602 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_limb_type& val)
0603    noexcept((noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>()))))
0604 {
0605    eval_multiply(result, result, val);
0606 }
0607
0608 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0609 inline BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0610 eval_multiply(
0611     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0612     const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
0613     const signed_double_limb_type&                                              val)
0614    noexcept(
0615    (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const limb_type&>())))
0616       && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
0617    )
0618 {
0619    if (val > 0)
0620    {
0621       if (val <= (std::numeric_limits<limb_type>::max)())
0622       {
0623          eval_multiply(result, a, static_cast<limb_type>(val));
0624          return;
0625       }
0626    }
0627    else if (val >= -static_cast<signed_double_limb_type>((std::numeric_limits<limb_type>::max)()))
0628    {
0629       eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
0630       result.negate();
0631       return;
0632    }
0633 #if BOOST_MP_ENDIAN_LITTLE_BYTE && !defined(BOOST_MP_TEST_NO_LE)
0634    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
0635 #else
0636    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
0637    t = val;
0638 #endif
0639    eval_multiply(result, a, t);
0640 }
0641
0642 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0643 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0644 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_double_limb_type& val)
0645    noexcept(
0646    (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const limb_type&>())))
0647    && (noexcept(eval_multiply(std::declval<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>(), std::declval<const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&>())))
0648    )
0649 {
0650    eval_multiply(result, result, val);
0651 }
0652
0653 //
0654 // Now over again for trivial cpp_int's:
0655 //
0656 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0657 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0658     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)>::type
0659 eval_multiply(
0660     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0661     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0662 {
0663    *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
0664    result.sign(result.sign() != o.sign());
0665    result.normalize();
0666 }
0667
0668 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0669 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0670     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0671 eval_multiply(
0672     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0673     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0674 {
0675    *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
0676    result.normalize();
0677 }
0678
0679 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0680 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0681     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)>::type
0682 eval_multiply(
0683     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0684     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
0685     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0686 {
0687    *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
0688    result.sign(a.sign() != b.sign());
0689    result.normalize();
0690 }
0691
0692 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0693 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0694     is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0695 eval_multiply(
0696     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0697     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
0698     const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) noexcept((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
0699 {
0700    *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
0701    result.normalize();
0702 }
0703
0704 //
0705 // Special routines for multiplying two integers to obtain a multiprecision result:
0706 //
0707 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0708 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0709     !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0710 eval_multiply(
0711     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
0712     signed_double_limb_type a, signed_double_limb_type b)
0713 {
0714    constexpr signed_double_limb_type mask      = static_cast<signed_double_limb_type>(~static_cast<limb_type>(0));
0715    constexpr std::size_t             limb_bits = static_cast<std::size_t>(sizeof(limb_type) * CHAR_BIT);
0716
0717    bool s = false;
0718    if (a < 0)
0719    {
0720       a = -a;
0721       s = true;
0722    }
0723    if (b < 0)
0724    {
0725       b = -b;
0726       s = !s;
0727    }
0728    double_limb_type w = a & mask;
0729    double_limb_type x = static_cast<double_limb_type>(a >> limb_bits);
0730    double_limb_type y = b & mask;
0731    double_limb_type z = static_cast<double_limb_type>(b >> limb_bits);
0732
0733    result.resize(4, 4);
0734    limb_type* pr = result.limbs();
0735
0736    double_limb_type carry = w * y;
0737 #ifdef __MSVC_RUNTIME_CHECKS
0738    pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0739    carry >>= limb_bits;
0740    carry += w * z + x * y;
0741    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0742    carry >>= limb_bits;
0743    carry += x * z;
0744    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0745    pr[3] = static_cast<limb_type>(carry >> limb_bits);
0746 #else
0747    pr[0] = static_cast<limb_type>(carry);
0748    carry >>= limb_bits;
0749    carry += w * z + x * y;
0750    pr[1] = static_cast<limb_type>(carry);
0751    carry >>= limb_bits;
0752    carry += x * z;
0753    pr[2] = static_cast<limb_type>(carry);
0754    pr[3] = static_cast<limb_type>(carry >> limb_bits);
0755 #endif
0756    result.sign(s);
0757    result.normalize();
0758 }
0759
0760 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
0761 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0762     !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
0763 eval_multiply(
0764     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
0765     double_limb_type a, double_limb_type b)
0766 {
0767    constexpr signed_double_limb_type mask      = static_cast<signed_double_limb_type>(~static_cast<limb_type>(0));
0768    constexpr std::size_t             limb_bits = static_cast<std::size_t>(sizeof(limb_type) * CHAR_BIT);
0769
0770    double_limb_type w = a & mask;
0771    double_limb_type x = a >> limb_bits;
0772    double_limb_type y = b & mask;
0773    double_limb_type z = b >> limb_bits;
0774
0775    result.resize(4, 4);
0776    limb_type* pr = result.limbs();
0777
0778    double_limb_type carry = w * y;
0779 #ifdef __MSVC_RUNTIME_CHECKS
0780    pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0781    carry >>= limb_bits;
0782    carry += w * z;
0783    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0784    carry >>= limb_bits;
0785    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0786    carry = x * y + pr[1];
0787    pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0788    carry >>= limb_bits;
0789    carry += pr[2] + x * z;
0790    pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
0791    pr[3] = static_cast<limb_type>(carry >> limb_bits);
0792 #else
0793    pr[0] = static_cast<limb_type>(carry);
0794    carry >>= limb_bits;
0795    carry += w * z;
0796    pr[1] = static_cast<limb_type>(carry);
0797    carry >>= limb_bits;
0798    pr[2] = static_cast<limb_type>(carry);
0799    carry = x * y + pr[1];
0800    pr[1] = static_cast<limb_type>(carry);
0801    carry >>= limb_bits;
0802    carry += pr[2] + x * z;
0803    pr[2] = static_cast<limb_type>(carry);
0804    pr[3] = static_cast<limb_type>(carry >> limb_bits);
0805 #endif
0806    result.sign(false);
0807    result.normalize();
0808 }
0809
0810 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1,
0811           std::size_t MinBits2, std::size_t MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
0812 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<
0813     !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>::type
0814 eval_multiply(
0815     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>&       result,
0816     cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& a,
0817     cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& b)
0818 {
0819    using canonical_type = typename boost::multiprecision::detail::canonical<typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type, cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::type;
0820    eval_multiply(result, static_cast<canonical_type>(*a.limbs()), static_cast<canonical_type>(*b.limbs()));
0821    result.sign(a.sign() != b.sign());
0822 }
0823
0824 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class SI>
0825 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<boost::multiprecision::detail::is_signed<SI>::value && boost::multiprecision::detail::is_integral<SI>::value && (sizeof(SI) <= sizeof(signed_double_limb_type) / 2)>::type
0826 eval_multiply(
0827     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
0828     SI a, SI b)
0829 {
0830    result = static_cast<signed_double_limb_type>(a) * static_cast<signed_double_limb_type>(b);
0831 }
0832
0833 template <std::size_t MinBits1, std::size_t MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class UI>
0834 BOOST_MP_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR typename std::enable_if<boost::multiprecision::detail::is_unsigned<UI>::value && (sizeof(UI) <= sizeof(signed_double_limb_type) / 2)>::type
0835 eval_multiply(
0836     cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
0837     UI a, UI b)
0838 {
0839    result = static_cast<double_limb_type>(a) * static_cast<double_limb_type>(b);
0840 }
0841
0842 #ifdef BOOST_MSVC
0843 #pragma warning(pop)
0844 #endif
0845
0846 }}} // namespace boost::multiprecision::backends
0847
0848 #endif