comparison DEPENDENCIES/generic/include/boost/multiprecision/cpp_int/divide.hpp @ 16:2665513ce2d3

Add boost headers

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