Chris@16: ///////////////////////////////////////////////////////////////
Chris@16: //  Copyright 2012 John Maddock. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
Chris@16: //
Chris@16: // Comparison operators for cpp_int_backend:
Chris@16: //
Chris@16: #ifndef BOOST_MP_CPP_INT_DIV_HPP
Chris@16: #define BOOST_MP_CPP_INT_DIV_HPP
Chris@16: 
Chris@16: namespace boost{ namespace multiprecision{ namespace backends{
Chris@16: 
Chris@16: template <class CppInt1, class CppInt2, class CppInt3>
Chris@16: void divide_unsigned_helper(
Chris@16:    CppInt1* result, 
Chris@16:    const CppInt2& x, 
Chris@16:    const CppInt3& y, 
Chris@16:    CppInt1& r)
Chris@16: {
Chris@16:    if(((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
Chris@16:    {
Chris@16:       CppInt2 t(x);
Chris@16:       divide_unsigned_helper(result, t, y, r);
Chris@16:       return;
Chris@16:    }
Chris@16:    if(((void*)result == (void*)&y) || ((void*)&r == (void*)&y))
Chris@16:    {
Chris@16:       CppInt3 t(y);
Chris@16:       divide_unsigned_helper(result, x, t, r);
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    /*
Chris@16:     Very simple, fairly braindead long division.
Chris@16:     Start by setting the remainder equal to x, and the
Chris@16:     result equal to 0.  Then in each loop we calculate our
Chris@16:     "best guess" for how many times y divides into r,
Chris@16:     add our guess to the result, and subtract guess*y
Chris@16:     from the remainder r.  One wrinkle is that the remainder
Chris@16:     may go negative, in which case we subtract the current guess
Chris@16:     from the result rather than adding.  The value of the guess
Chris@16:     is determined by dividing the most-significant-limb of the
Chris@16:     current remainder by the most-significant-limb of y.
Chris@16: 
Chris@16:     Note that there are more efficient algorithms than this
Chris@16:     available, in particular see Knuth Vol 2.  However for small
Chris@16:     numbers of limbs this generally outperforms the alternatives
Chris@16:     and avoids the normalisation step which would require extra storage.
Chris@16:     */
Chris@16: 
Chris@16: 
Chris@16:    using default_ops::eval_subtract;
Chris@16: 
Chris@16:    if(result == &r)
Chris@16:    {
Chris@16:       CppInt1 rem;
Chris@16:       divide_unsigned_helper(result, x, y, rem);
Chris@16:       r = rem;
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    //
Chris@16:    // Find the most significant words of numerator and denominator.
Chris@16:    //
Chris@16:    limb_type y_order = y.size() - 1;
Chris@16: 
Chris@16:    if(y_order == 0)
Chris@16:    {
Chris@16:       //
Chris@16:       // Only a single non-zero limb in the denominator, in this case
Chris@16:       // we can use a specialized divide-by-single-limb routine which is
Chris@16:       // much faster.  This also handles division by zero:
Chris@16:       //
Chris@16:       divide_unsigned_helper(result, x, y.limbs()[y_order], r);
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    typename CppInt2::const_limb_pointer px = x.limbs();
Chris@16:    typename CppInt3::const_limb_pointer py = y.limbs();
Chris@16: 
Chris@16:    limb_type r_order = x.size() - 1;
Chris@16:    if((r_order == 0) && (*px == 0))
Chris@16:    {
Chris@16:       // x is zero, so is the result:
Chris@16:       r = x;
Chris@16:       if(result)
Chris@16:          *result = x;
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    r = x;
Chris@16:    r.sign(false);
Chris@16:    if(result)
Chris@16:       *result = static_cast<limb_type>(0u);
Chris@16:    //
Chris@16:    // Check if the remainder is already less than the divisor, if so
Chris@16:    // we already have the result.  Note we try and avoid a full compare
Chris@16:    // if we can:
Chris@16:    //
Chris@16:    if(r_order <= y_order)
Chris@16:    {
Chris@16:       if((r_order < y_order) || (r.compare_unsigned(y) < 0))
Chris@16:       {
Chris@16:          return;
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@16:    CppInt1 t;
Chris@16:    bool r_neg = false;
Chris@16: 
Chris@16:    //
Chris@16:    // See if we can short-circuit long division, and use basic arithmetic instead:
Chris@16:    //
Chris@16:    if(r_order == 0)
Chris@16:    {
Chris@16:       if(result)
Chris@16:       {
Chris@16:          *result = px[0] / py[0];
Chris@16:       }
Chris@16:       r = px[0] % py[0];
Chris@16:       return;
Chris@16:    }
Chris@16:    else if(r_order == 1)
Chris@16:    {
Chris@16:       double_limb_type a, b;
Chris@16:       a = (static_cast<double_limb_type>(px[1]) << CppInt1::limb_bits) | px[0];
Chris@16:       b = y_order ? 
Chris@16:          (static_cast<double_limb_type>(py[1]) << CppInt1::limb_bits) | py[0] 
Chris@16:          : py[0];
Chris@16:       if(result)
Chris@16:       {
Chris@16:          *result = a / b;
Chris@16:       }
Chris@16:       r = a % b;
Chris@16:       return;
Chris@16:    }
Chris@16:    //
Chris@16:    // prepare result:
Chris@16:    //
Chris@16:    if(result)
Chris@16:       result->resize(1 + r_order - y_order, 1 + r_order - y_order);
Chris@16:    typename CppInt1::const_limb_pointer prem = r.limbs();
Chris@16:    // This is initialised just to keep the compiler from emitting useless warnings later on:
Chris@16:    typename CppInt1::limb_pointer pr 
Chris@16:       = typename CppInt1::limb_pointer();
Chris@16:    if(result)
Chris@16:    {
Chris@16:       pr = result->limbs();
Chris@16:       for(unsigned i = 1; i < 1 + r_order - y_order; ++i)
Chris@16:          pr[i] = 0;
Chris@16:    }
Chris@16:    bool first_pass = true;
Chris@16: 
Chris@16:    do
Chris@16:    {
Chris@16:       //
Chris@16:       // Calculate our best guess for how many times y divides into r:
Chris@16:       //
Chris@16:       limb_type guess;
Chris@16:       if((prem[r_order] <= py[y_order]) && (r_order > 0))
Chris@16:       {
Chris@16:          double_limb_type a, b, v;
Chris@16:          a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
Chris@16:          b = py[y_order];
Chris@16:          v = a / b;
Chris@16:          if(v > CppInt1::max_limb_value)
Chris@16:             guess = 1;
Chris@16:          else
Chris@16:          {
Chris@16:             guess = static_cast<limb_type>(v);
Chris@16:             --r_order;
Chris@16:          }
Chris@16:       }
Chris@16:       else if(r_order == 0)
Chris@16:       {
Chris@16:          guess = prem[0] / py[y_order];
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          double_limb_type a, b, v;
Chris@16:          a = (static_cast<double_limb_type>(prem[r_order]) << CppInt1::limb_bits) | prem[r_order - 1];
Chris@16:          b = (y_order > 0) ? (static_cast<double_limb_type>(py[y_order]) << CppInt1::limb_bits) | py[y_order - 1] : (static_cast<double_limb_type>(py[y_order])  << CppInt1::limb_bits);
Chris@16:          v = a / b;
Chris@16:          guess = static_cast<limb_type>(v);
Chris@16:       }
Chris@16:       BOOST_ASSERT(guess); // If the guess ever gets to zero we go on forever....
Chris@16:       //
Chris@16:       // Update result:
Chris@16:       //
Chris@16:       limb_type shift = r_order - y_order;
Chris@16:       if(result)
Chris@16:       {
Chris@16:          if(r_neg)
Chris@16:          {
Chris@16:             if(pr[shift] > guess)
Chris@16:                pr[shift] -= guess;
Chris@16:             else
Chris@16:             {
Chris@16:                t.resize(shift + 1, shift + 1);
Chris@16:                t.limbs()[shift] = guess;
Chris@16:                for(unsigned i = 0; i < shift; ++i)
Chris@16:                   t.limbs()[i] = 0;
Chris@16:                eval_subtract(*result, t);
Chris@16:             }
Chris@16:          }
Chris@16:          else if(CppInt1::max_limb_value - pr[shift] > guess)
Chris@16:             pr[shift] += guess;
Chris@16:          else
Chris@16:          {
Chris@16:             t.resize(shift + 1, shift + 1);
Chris@16:             t.limbs()[shift] = guess;
Chris@16:             for(unsigned i = 0; i < shift; ++i)
Chris@16:                t.limbs()[i] = 0;
Chris@16:             eval_add(*result, t);
Chris@16:          }
Chris@16:       }
Chris@16:       //
Chris@16:       // Calculate guess * y, we use a fused mutiply-shift O(N) for this
Chris@16:       // rather than a full O(N^2) multiply:
Chris@16:       //
Chris@16:       double_limb_type carry = 0;
Chris@16:       t.resize(y.size() + shift + 1, y.size() + shift);
Chris@16:       bool truncated_t = !CppInt1::variable && (t.size() != y.size() + shift + 1);
Chris@16:       typename CppInt1::limb_pointer pt = t.limbs();
Chris@16:       for(unsigned i = 0; i < shift; ++i)
Chris@16:          pt[i] = 0;
Chris@16:       for(unsigned i = 0; i < y.size(); ++i)
Chris@16:       {
Chris@16:          carry += static_cast<double_limb_type>(py[i]) * static_cast<double_limb_type>(guess);
Chris@16:          pt[i + shift] = static_cast<limb_type>(carry);
Chris@16:          carry >>= CppInt1::limb_bits;
Chris@16:       }
Chris@16:       if(carry && !truncated_t)
Chris@16:       {
Chris@16:          pt[t.size() - 1] = static_cast<limb_type>(carry);
Chris@16:       }
Chris@16:       else if(!truncated_t)
Chris@16:       {
Chris@16:          t.resize(t.size() - 1, t.size() - 1);
Chris@16:       }
Chris@16:       //
Chris@16:       // Update r in a way that won't actually produce a negative result
Chris@16:       // in case the argument types are unsigned:
Chris@16:       //
Chris@16:       if(r.compare(t) > 0)
Chris@16:       {
Chris@16:          eval_subtract(r, t);
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          r.swap(t);
Chris@16:          eval_subtract(r, t);
Chris@16:          prem = r.limbs();
Chris@16:          r_neg = !r_neg;
Chris@16:       }
Chris@16:       //
Chris@16:       // First time through we need to strip any leading zero, otherwise
Chris@16:       // the termination condition goes belly-up:
Chris@16:       //
Chris@16:       if(result && first_pass)
Chris@16:       {
Chris@16:          first_pass = false;
Chris@16:          while(pr[result->size() - 1] == 0)
Chris@16:             result->resize(result->size() - 1, result->size() - 1);
Chris@16:       }
Chris@16:       //
Chris@16:       // Update r_order:
Chris@16:       //
Chris@16:       r_order = r.size() - 1;
Chris@16:       if(r_order < y_order)
Chris@16:          break;
Chris@16:    }
Chris@16:    // Termination condition is really just a check that r > y, but with a common
Chris@16:    // short-circuit case handled first:
Chris@16:    while((r_order > y_order) || (r.compare_unsigned(y) >= 0));
Chris@16: 
Chris@16:    //
Chris@16:    // We now just have to normalise the result:
Chris@16:    //
Chris@16:    if(r_neg && eval_get_sign(r))
Chris@16:    {
Chris@16:       // We have one too many in the result:
Chris@16:       if(result)
Chris@16:          eval_decrement(*result);
Chris@16:       if(y.sign())
Chris@16:       {
Chris@16:          r.negate();
Chris@16:          eval_subtract(r, y);
Chris@16:       }
Chris@16:       else
Chris@16:          eval_subtract(r, y, r);
Chris@16:    }
Chris@16: 
Chris@16:    BOOST_ASSERT(r.compare_unsigned(y) < 0); // remainder must be less than the divisor or our code has failed
Chris@16: }
Chris@16: 
Chris@16: template <class CppInt1, class CppInt2>
Chris@16: void divide_unsigned_helper(
Chris@16:    CppInt1* result, 
Chris@16:    const CppInt2& x, 
Chris@16:    limb_type y, 
Chris@16:    CppInt1& r)
Chris@16: {
Chris@16:    if(((void*)result == (void*)&x) || ((void*)&r == (void*)&x))
Chris@16:    {
Chris@16:       CppInt2 t(x);
Chris@16:       divide_unsigned_helper(result, t, y, r);
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    if(result == &r)
Chris@16:    {
Chris@16:       CppInt1 rem;
Chris@16:       divide_unsigned_helper(result, x, y, rem);
Chris@16:       r = rem;
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    // As above, but simplified for integer divisor:
Chris@16: 
Chris@16:    using default_ops::eval_subtract;
Chris@16: 
Chris@16:    if(y == 0)
Chris@16:    {
Chris@16:       BOOST_THROW_EXCEPTION(std::overflow_error("Integer Division by zero."));
Chris@16:    }
Chris@16:    //
Chris@16:    // Find the most significant word of numerator.
Chris@16:    //
Chris@16:    limb_type r_order = x.size() - 1;
Chris@16: 
Chris@16:    //
Chris@16:    // Set remainder and result to their initial values:
Chris@16:    //
Chris@16:    r = x;
Chris@16:    r.sign(false);
Chris@16:    typename CppInt1::limb_pointer pr = r.limbs();
Chris@16: 
Chris@16:    //
Chris@16:    // check for x < y, try to do this without actually having to 
Chris@16:    // do a full comparison:
Chris@16:    //
Chris@16:    if((r_order == 0) && (*pr < y))
Chris@16:    {
Chris@16:       if(result)
Chris@16:          *result = static_cast<limb_type>(0u);
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    //
Chris@16:    // See if we can short-circuit long division, and use basic arithmetic instead:
Chris@16:    //
Chris@16:    if(r_order == 0)
Chris@16:    {
Chris@16:       if(result)
Chris@16:       {
Chris@16:          *result = *pr / y;
Chris@16:          result->sign(x.sign());
Chris@16:       }
Chris@16:       *pr %= y;
Chris@16:       r.sign(x.sign());
Chris@16:       return;
Chris@16:    }
Chris@16:    else if(r_order == 1)
Chris@16:    {
Chris@16:       double_limb_type a;
Chris@16:       a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[0];
Chris@16:       if(result)
Chris@16:       {
Chris@16:          *result = a / y;
Chris@16:          result->sign(x.sign());
Chris@16:       }
Chris@16:       r = a % y;
Chris@16:       r.sign(x.sign());
Chris@16:       return;
Chris@16:    }
Chris@16: 
Chris@16:    // This is initialised just to keep the compiler from emitting useless warnings later on:
Chris@16:    typename CppInt1::limb_pointer pres = typename CppInt1::limb_pointer();
Chris@16:    if(result)
Chris@16:    {
Chris@16:       result->resize(r_order + 1, r_order + 1);
Chris@16:       pres = result->limbs();
Chris@16:       if(result->size() > r_order)
Chris@16:          pres[r_order] = 0;  // just in case we don't set the most significant limb below.
Chris@16:    }
Chris@16: 
Chris@16:    do
Chris@16:    {
Chris@16:       //
Chris@16:       // Calculate our best guess for how many times y divides into r:
Chris@16:       //
Chris@16:       if((pr[r_order] < y) && r_order)
Chris@16:       {
Chris@16:          double_limb_type a, b;
Chris@16:          a = (static_cast<double_limb_type>(pr[r_order]) << CppInt1::limb_bits) | pr[r_order - 1];
Chris@16:          b = a % y;
Chris@16:          r.resize(r.size() - 1, r.size() - 1);
Chris@16:          --r_order;
Chris@16:          pr[r_order] = static_cast<limb_type>(b);
Chris@16:          if(result)
Chris@16:             pres[r_order] = static_cast<limb_type>(a / y);
Chris@16:          if(r_order && pr[r_order] == 0)
Chris@16:          {
Chris@16:             --r_order;  // No remainder, division was exact.
Chris@16:             r.resize(r.size() - 1, r.size() - 1);
Chris@16:             if(result)
Chris@16:                pres[r_order] = static_cast<limb_type>(0u);
Chris@16:          }
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:          if(result)
Chris@16:             pres[r_order] = pr[r_order] / y;
Chris@16:          pr[r_order] %= y;
Chris@16:          if(r_order && pr[r_order] == 0)
Chris@16:          {
Chris@16:             --r_order;  // No remainder, division was exact.
Chris@16:             r.resize(r.size() - 1, r.size() - 1);
Chris@16:             if(result)
Chris@16:                pres[r_order] = static_cast<limb_type>(0u);
Chris@16:          }
Chris@16:       }
Chris@16:    }
Chris@16:    // Termination condition is really just a check that r >= y, but with two common
Chris@16:    // short-circuit cases handled first:
Chris@16:    while(r_order || (pr[r_order] >= y));
Chris@16: 
Chris@16:    if(result)
Chris@16:    {
Chris@16:       result->normalize();
Chris@16:       result->sign(x.sign());
Chris@16:    }
Chris@16:    r.normalize();
Chris@16:    r.sign(x.sign());
Chris@16: 
Chris@16:    BOOST_ASSERT(r.compare(y) < 0); // remainder must be less than the divisor or our code has failed
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, unsigned MinBits3, unsigned MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, 
Chris@16:       const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
Chris@16: {
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
Chris@16:    bool s = a.sign() != b.sign();
Chris@16:    divide_unsigned_helper(&result, a, b, r);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, 
Chris@16:       limb_type& b)
Chris@16: {
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
Chris@16:    bool s = a.sign();
Chris@16:    divide_unsigned_helper(&result, a, b, r);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, 
Chris@16:       signed_limb_type& b)
Chris@16: {
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
Chris@16:    bool s = a.sign() != (b < 0);
Chris@101:    divide_unsigned_helper(&result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(b)), r);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_divide(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       limb_type b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_divide(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       signed_limb_type b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_divide(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, unsigned MinBits3, unsigned MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, 
Chris@16:       const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
Chris@16: {
Chris@16:    bool s = a.sign();
Chris@16:    divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, limb_type b)
Chris@16: {
Chris@16:    bool s = a.sign();
Chris@16:    divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, 
Chris@16:       signed_limb_type b)
Chris@16: {
Chris@16:    bool s = a.sign();
Chris@16:    divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, static_cast<limb_type>(std::abs(b)), result);
Chris@16:    result.sign(s);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!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 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_modulus(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       limb_type b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_modulus(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       signed_limb_type b)
Chris@16: {
Chris@16:    // There is no in place divide:
Chris@16:    cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> a(result);
Chris@16:    eval_modulus(result, a, b);
Chris@16: }
Chris@16: 
Chris@16: //
Chris@16: // Over again for trivial cpp_int's:
Chris@16: //
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value 
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value 
Chris@16:             || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
Chris@16:          >::type 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
Chris@16: {
Chris@16:    if(!*o.limbs())
Chris@16:       BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
Chris@16:    *result.limbs() /= *o.limbs();
Chris@16:    result.sign(result.sign() != o.sign());
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value 
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value 
Chris@16:          && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:       >::type 
Chris@16:    eval_divide(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
Chris@16: {
Chris@16:    if(!*o.limbs())
Chris@16:       BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
Chris@16:    *result.limbs() /= *o.limbs();
Chris@16: }
Chris@16: 
Chris@16: template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
Chris@16: BOOST_MP_FORCEINLINE typename enable_if_c<
Chris@16:          is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value 
Chris@16:          && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
Chris@16:       >::type 
Chris@16:    eval_modulus(
Chris@16:       cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, 
Chris@16:       const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o)
Chris@16: {
Chris@16:    if(!*o.limbs())
Chris@16:       BOOST_THROW_EXCEPTION(std::overflow_error("Division by zero."));
Chris@16:    *result.limbs() %= *o.limbs();
Chris@16:    result.sign(result.sign());
Chris@16: }
Chris@16: 
Chris@16: }}} // namespaces
Chris@16: 
Chris@16: #endif