///////////////////////////////////////////////////////////////
//  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_

#ifndef BOOST_MP_CPP_INT_HPP
#define BOOST_MP_CPP_INT_HPP

#include <iostream>
#include <iomanip>
#include <boost/cstdint.hpp>
#include <boost/multiprecision/number.hpp>
#include <boost/multiprecision/detail/integer_ops.hpp>
#include <boost/array.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_floating_point.hpp>
#include <boost/multiprecision/cpp_int/cpp_int_config.hpp>
#include <boost/multiprecision/rational_adapter.hpp>
#include <boost/detail/endian.hpp>
#include <boost/integer/static_min_max.hpp>
#include <boost/type_traits/common_type.hpp>
#include <boost/multiprecision/cpp_int/checked.hpp>

namespace boost{
namespace multiprecision{

namespace backends{

#ifdef BOOST_MSVC
// warning C4127: conditional expression is constant
#pragma warning(push)
#pragma warning(disable:4127 4351 4293 4996 4307 4702)
#endif

template <unsigned MinBits = 0, unsigned MaxBits = 0, cpp_integer_type SignType = signed_magnitude, cpp_int_check_type Checked = unchecked, class Allocator = typename mpl::if_c<MinBits && (MinBits == MaxBits), void, std::allocator<limb_type> >::type >
struct cpp_int_backend;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, bool trivial = false>
struct cpp_int_base;
//
// Traits class determines the maximum and minimum precision values:
//
template <class T> struct max_precision;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
{
   static const unsigned value = is_void<Allocator>::value ?
      static_unsigned_max<MinBits, MaxBits>::value
      : (((MaxBits >= MinBits) && MaxBits) ? MaxBits : UINT_MAX);
};

template <class T> struct min_precision;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
{
   static const unsigned value = (is_void<Allocator>::value ? static_unsigned_max<MinBits, MaxBits>::value : MinBits);
};
//
// Traits class determines whether the number of bits precision requested could fit in a native type,
// we call this a "trivial" cpp_int:
//
template <class T>
struct is_trivial_cpp_int
{
   static const bool value = false;
};

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
{
   typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> self;
   static const bool value = is_void<Allocator>::value && (max_precision<self>::value <= (sizeof(double_limb_type) * CHAR_BIT) - (SignType == signed_packed ? 1 : 0));
};

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct is_trivial_cpp_int<cpp_int_base<MinBits, MaxBits, SignType, Checked, Allocator, true> >
{
   static const bool value = true;
};

} // namespace backends
//
// Traits class to determine whether a cpp_int_backend is signed or not:
//
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct is_unsigned_number<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
   : public mpl::bool_<(SignType == unsigned_magnitude) || (SignType == unsigned_packed)>{};

namespace backends{
//
// Traits class determines whether T should be implicitly convertible to U, or
// whether the constructor should be made explicit.  The latter happens if we
// are losing the sign, or have fewer digits precision in the target type:
//
template <class T, class U>
struct is_implicit_cpp_int_conversion;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
struct is_implicit_cpp_int_conversion<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >
{
   typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t1;
   typedef cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t2;
   static const bool value =
      (is_signed_number<t2>::value || !is_signed_number<t1>::value)
      && (max_precision<t1>::value <= max_precision<t2>::value);
};

//
// Traits class to determine whether operations on a cpp_int may throw:
//
template <class T>
struct is_non_throwing_cpp_int : public mpl::false_{};
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType>
struct is_non_throwing_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, unchecked, void> > : public mpl::true_ {};

//
// Traits class, determines whether the cpp_int is fixed precision or not:
//
template <class T>
struct is_fixed_precision;
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct is_fixed_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
   : public mpl::bool_<max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value != UINT_MAX> {};

namespace detail{

inline void verify_new_size(unsigned new_size, unsigned min_size, const mpl::int_<checked>&)
{
   if(new_size < min_size)
      BOOST_THROW_EXCEPTION(std::overflow_error("Unable to allocate sufficient storage for the value of the result: value overflows the maximum allowable magnitude."));
}
inline void verify_new_size(unsigned /*new_size*/, unsigned /*min_size*/, const mpl::int_<unchecked>&){}

template <class U>
inline void verify_limb_mask(bool b, U limb, U mask, const mpl::int_<checked>&)
{
   // When we mask out "limb" with "mask", do we loose bits?  If so it's an overflow error:
   if(b && (limb & ~mask))
      BOOST_THROW_EXCEPTION(std::overflow_error("Overflow in cpp_int arithmetic: there is insufficient precision in the target type to hold all of the bits of the result."));
}
template <class U>
inline void verify_limb_mask(bool /*b*/, U /*limb*/, U /*mask*/, const mpl::int_<unchecked>&){}

}

//
// Now define the various data layouts that are possible as partial specializations of the base class,
// starting with the default arbitrary precision signed integer type:
//
template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
struct cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false> : private Allocator::template rebind<limb_type>::other
{
   typedef typename Allocator::template rebind<limb_type>::other allocator_type;
   typedef typename allocator_type::pointer                      limb_pointer;
   typedef typename allocator_type::const_pointer                const_limb_pointer;
   typedef mpl::int_<Checked>                                    checked_type;

   //
   // Interface invariants:
   //
   BOOST_STATIC_ASSERT(!is_void<Allocator>::value);

private:
   struct limb_data
   {
      unsigned capacity;
      limb_pointer data;
   };

public:
   BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
   BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
   BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
   BOOST_STATIC_CONSTANT(unsigned, internal_limb_count =
      MinBits
         ? MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0)
         : sizeof(limb_data) / sizeof(limb_type));
   BOOST_STATIC_CONSTANT(bool, variable = true);

private:
   union data_type
   {
      limb_data ld;
      limb_type la[internal_limb_count];
      limb_type first;
      double_limb_type double_first;

      BOOST_CONSTEXPR data_type() : first(0) {}
      BOOST_CONSTEXPR data_type(limb_type i) : first(i) {}
      BOOST_CONSTEXPR data_type(signed_limb_type i) : first(i < 0 ? -i : i) {}
#ifdef BOOST_LITTLE_ENDIAN
      BOOST_CONSTEXPR data_type(double_limb_type i) : double_first(i) {}
      BOOST_CONSTEXPR data_type(signed_double_limb_type i) : double_first(i < 0 ? -i : i) {}
#endif
   };

   data_type   m_data;
   unsigned    m_limbs;
   bool        m_sign, m_internal;

public:
   //
   // Direct construction:
   //
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
      : m_data(i), m_limbs(1), m_sign(false), m_internal(true) { }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT
      : m_data(i), m_limbs(1), m_sign(i < 0), m_internal(true) { }
#if defined(BOOST_LITTLE_ENDIAN)
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
      : m_data(i), m_limbs(i > max_limb_value ? 2 : 1), m_sign(false), m_internal(true) { }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT
      : m_data(i), m_limbs(i < 0 ? (-i > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
        m_sign(i < 0), m_internal(true) { }
#endif
   //
   // Helper functions for getting at our internal data, and manipulating storage:
   //
   BOOST_MP_FORCEINLINE allocator_type& allocator() BOOST_NOEXCEPT { return *this; }
   BOOST_MP_FORCEINLINE const allocator_type& allocator()const BOOST_NOEXCEPT { return *this; }
   BOOST_MP_FORCEINLINE unsigned size()const  BOOST_NOEXCEPT { return m_limbs; }
   BOOST_MP_FORCEINLINE limb_pointer limbs()  BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
   BOOST_MP_FORCEINLINE const_limb_pointer limbs()const  BOOST_NOEXCEPT { return m_internal ? m_data.la : m_data.ld.data; }
   BOOST_MP_FORCEINLINE unsigned capacity()const  BOOST_NOEXCEPT { return m_internal ? internal_limb_count : m_data.ld.capacity; }
   BOOST_MP_FORCEINLINE bool sign()const  BOOST_NOEXCEPT { return m_sign; }
   void sign(bool b)  BOOST_NOEXCEPT
   {
      m_sign = b;
      // Check for zero value:
      if(m_sign && (m_limbs == 1))
      {
         if(limbs()[0] == 0)
            m_sign = false;
      }
   }
   void resize(unsigned new_size, unsigned min_size)
   {
      static const unsigned max_limbs = MaxBits / (CHAR_BIT * sizeof(limb_type)) + (MaxBits % (CHAR_BIT * sizeof(limb_type)) ? 1 : 0);
      // We never resize beyond MaxSize:
      if(new_size > max_limbs)
         new_size = max_limbs;
      detail::verify_new_size(new_size, min_size, checked_type());
      // See if we have enough capacity already:
      unsigned cap = capacity();
      if(new_size > cap)
      {
         // Allocate a new buffer and copy everything over:
         cap = (std::min)((std::max)(cap * 4, new_size), max_limbs);
         limb_pointer pl = allocator().allocate(cap);
         std::copy(limbs(), limbs() + size(), pl);
         if(!m_internal)
            allocator().deallocate(limbs(), capacity());
         else
            m_internal = false;
         m_limbs = new_size;
         m_data.ld.capacity = cap;
         m_data.ld.data = pl;
      }
      else
      {
         m_limbs = new_size;
      }
   }
   BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT
   {
      limb_pointer p = limbs();
      while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
   }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT : m_data(), m_limbs(1), m_sign(false), m_internal(true) {}
   BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) : allocator_type(o), m_limbs(0), m_internal(true)
   {
      resize(o.size(), o.size());
      std::copy(o.limbs(), o.limbs() + o.size(), limbs());
      m_sign = o.m_sign;
   }
#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
   cpp_int_base(cpp_int_base&& o)
      : allocator_type(static_cast<Allocator&&>(o)), m_limbs(o.m_limbs), m_sign(o.m_sign), m_internal(o.m_internal)
   {
      if(m_internal)
      {
         std::copy(o.limbs(), o.limbs() + o.size(), limbs());
      }
      else
      {
         m_data.ld = o.m_data.ld;
         o.m_limbs = 0;
         o.m_internal = true;
      }
   }
   cpp_int_base& operator = (cpp_int_base&& o) BOOST_NOEXCEPT
   {
      if(!m_internal)
         allocator().deallocate(m_data.ld.data, m_data.ld.capacity);
      *static_cast<Allocator*>(this) = static_cast<Allocator&&>(o);
      m_limbs = o.m_limbs;
      m_sign = o.m_sign;
      m_internal = o.m_internal;
      if(m_internal)
      {
         std::copy(o.limbs(), o.limbs() + o.size(), limbs());
      }
      else
      {
         m_data.ld = o.m_data.ld;
         o.m_limbs = 0;
         o.m_internal = true;
      }
      return *this;
   }
#endif
   BOOST_MP_FORCEINLINE ~cpp_int_base() BOOST_NOEXCEPT
   {
      if(!m_internal)
         allocator().deallocate(limbs(), capacity());
   }
   void assign(const cpp_int_base& o)
   {
      if(this != &o)
      {
         static_cast<allocator_type&>(*this) = static_cast<const allocator_type&>(o);
         m_limbs = 0;
         resize(o.size(), o.size());
         std::copy(o.limbs(), o.limbs() + o.size(), limbs());
         m_sign = o.m_sign;
      }
   }
   BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
   {
      m_sign = !m_sign;
      // Check for zero value:
      if(m_sign && (m_limbs == 1))
      {
         if(limbs()[0] == 0)
            m_sign = false;
      }
   }
   BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
   {
      return m_sign;
   }
   BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
   {
      std::swap(m_data, o.m_data);
      std::swap(m_sign, o.m_sign);
      std::swap(m_internal, o.m_internal);
      std::swap(m_limbs, o.m_limbs);
   }
};

#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::limb_bits;
template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::max_limb_value;
template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
const limb_type cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::sign_bit_mask;
template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
const unsigned cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::internal_limb_count;
template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
const bool cpp_int_base<MinBits, MaxBits, signed_magnitude, Checked, Allocator, false>::variable;

#endif

template <unsigned MinBits, unsigned MaxBits, cpp_int_check_type Checked, class Allocator>
struct cpp_int_base<MinBits, MaxBits, unsigned_magnitude, Checked, Allocator, false> : private Allocator::template rebind<limb_type>::other
{
   //
   // There is currently no support for unsigned arbitrary precision arithmetic, largely
   // because it's not clear what subtraction should do:
   //
   BOOST_STATIC_ASSERT_MSG(((sizeof(Allocator) == 0) && !is_void<Allocator>::value), "There is curently no support for unsigned arbitrary precision integers.");
};
//
// Fixed precision (i.e. no allocator), signed-magnitude type with limb-usage count:
//
template <unsigned MinBits, cpp_int_check_type Checked>
struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>
{
   typedef limb_type*                      limb_pointer;
   typedef const limb_type*                const_limb_pointer;
   typedef mpl::int_<Checked>              checked_type;

   //
   // Interface invariants:
   //
   BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");

public:
   BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
   BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
   BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
   BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0));
   BOOST_STATIC_CONSTANT(bool, variable = false);
   BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = MinBits % limb_bits ? (limb_type(1) << (MinBits % limb_bits)) -1 : (~limb_type(0)));
   BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");

private:
   union data_type{
      limb_type          m_data[internal_limb_count];
      limb_type          m_first_limb;
      double_limb_type   m_double_first_limb;

      BOOST_CONSTEXPR data_type() : m_first_limb(0) {}
      BOOST_CONSTEXPR data_type(limb_type i) : m_first_limb(i) {}
      BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i) {}
   } m_wrapper;
   boost::uint16_t    m_limbs;
   bool               m_sign;

public:
   //
   // Direct construction:
   //
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
      : m_wrapper(i), m_limbs(1), m_sign(false) {}
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT
      : m_wrapper(limb_type(i < 0 ? -i : i)), m_limbs(1), m_sign(i < 0) {}
#if defined(BOOST_LITTLE_ENDIAN)
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
      : m_wrapper(i), m_limbs(i > max_limb_value ? 2 : 1), m_sign(false) {}
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT
      : m_wrapper(double_limb_type(i < 0 ? -i : i)),
        m_limbs(i < 0 ? (-i > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)),
        m_sign(i < 0) {}
#endif
   //
   // Helper functions for getting at our internal data, and manipulating storage:
   //
   BOOST_MP_FORCEINLINE unsigned size()const BOOST_NOEXCEPT { return m_limbs; }
   BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
   BOOST_MP_FORCEINLINE const_limb_pointer limbs()const BOOST_NOEXCEPT { return m_wrapper.m_data; }
   BOOST_MP_FORCEINLINE bool sign()const BOOST_NOEXCEPT { return m_sign; }
   BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT
   {
      m_sign = b;
      // Check for zero value:
      if(m_sign && (m_limbs == 1))
      {
         if(limbs()[0] == 0)
            m_sign = false;
      }
   }
   BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size) BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      m_limbs = static_cast<boost::uint16_t>((std::min)(new_size, internal_limb_count));
      detail::verify_new_size(m_limbs, min_size, checked_type());
   }
   BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      limb_pointer p = limbs();
      detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count-1], upper_limb_mask, checked_type());
      p[internal_limb_count-1] &= upper_limb_mask;
      while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
      if((m_limbs == 1) && (!*p)) m_sign = false; // zero is always unsigned
   }

   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_wrapper(limb_type(0u)), m_limbs(1), m_sign(false) {}
   BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT : m_limbs(o.m_limbs), m_sign(o.m_sign)
   {
      std::copy(o.limbs(), o.limbs() + o.size(), limbs());
   }
   //~cpp_int_base() BOOST_NOEXCEPT {}
   void assign(const cpp_int_base& o) BOOST_NOEXCEPT
   {
      if(this != &o)
      {
         resize(o.size(), o.size());
         std::copy(o.limbs(), o.limbs() + o.size(), limbs());
         m_sign = o.m_sign;
      }
   }
   BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
   {
      m_sign = !m_sign;
      // Check for zero value:
      if(m_sign && (m_limbs == 1))
      {
         if(limbs()[0] == 0)
            m_sign = false;
      }
   }
   BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
   {
      return m_sign;
   }
   BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
   {
      for(unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
         std::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
      std::swap(m_sign, o.m_sign);
      std::swap(m_limbs, o.m_limbs);
   }
};
#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

template <unsigned MinBits, cpp_int_check_type Checked>
const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::limb_bits;
template <unsigned MinBits, cpp_int_check_type Checked>
const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::max_limb_value;
template <unsigned MinBits, cpp_int_check_type Checked>
const limb_type cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::sign_bit_mask;
template <unsigned MinBits, cpp_int_check_type Checked>
const unsigned cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::internal_limb_count;
template <unsigned MinBits, cpp_int_check_type Checked>
const bool cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, false>::variable;

#endif
//
// Fixed precision (i.e. no allocator), unsigned type with limb-usage count:
//
template <unsigned MinBits, cpp_int_check_type Checked>
struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>
{
   typedef limb_type*                      limb_pointer;
   typedef const limb_type*                const_limb_pointer;
   typedef mpl::int_<Checked>              checked_type;

   //
   // Interface invariants:
   //
   BOOST_STATIC_ASSERT_MSG(MinBits > sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");

public:
   BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(limb_type) * CHAR_BIT);
   BOOST_STATIC_CONSTANT(limb_type, max_limb_value = ~static_cast<limb_type>(0u));
   BOOST_STATIC_CONSTANT(limb_type, sign_bit_mask = 1u << (limb_bits - 1));
   BOOST_STATIC_CONSTANT(unsigned, internal_limb_count = MinBits / limb_bits + (MinBits % limb_bits ? 1 : 0));
   BOOST_STATIC_CONSTANT(bool, variable = false);
   BOOST_STATIC_CONSTANT(limb_type, upper_limb_mask = MinBits % limb_bits ? (limb_type(1) << (MinBits % limb_bits)) -1 : (~limb_type(0)));
   BOOST_STATIC_ASSERT_MSG(internal_limb_count >= 2, "A fixed precision integer type must have at least 2 limbs");

private:
   union data_type{
      limb_type          m_data[internal_limb_count];
      limb_type          m_first_limb;
      double_limb_type   m_double_first_limb;

      BOOST_CONSTEXPR data_type() : m_first_limb(0) {}
      BOOST_CONSTEXPR data_type(limb_type i) : m_first_limb(i) {}
      BOOST_CONSTEXPR data_type(double_limb_type i) : m_double_first_limb(i) {}
   } m_wrapper;
   limb_type          m_limbs;

public:
   //
   // Direct construction:
   //
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(limb_type i)BOOST_NOEXCEPT
      : m_wrapper(i), m_limbs(1) {}
   BOOST_MP_FORCEINLINE cpp_int_base(signed_limb_type i)BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_wrapper(limb_type(i < 0 ? -i : i)), m_limbs(1) { if(i < 0) negate(); }
#ifdef BOOST_LITTLE_ENDIAN
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(double_limb_type i)BOOST_NOEXCEPT
      : m_wrapper(i), m_limbs(i > max_limb_value ? 2 : 1) {}
   BOOST_MP_FORCEINLINE cpp_int_base(signed_double_limb_type i)BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_wrapper(double_limb_type(i < 0 ? -i : i)), m_limbs(i < 0 ? (-i > max_limb_value ? 2 : 1) : (i > max_limb_value ? 2 : 1)) { if(i < 0) negate(); }
#endif
   //
   // Helper functions for getting at our internal data, and manipulating storage:
   //
   BOOST_MP_FORCEINLINE unsigned size()const BOOST_NOEXCEPT { return m_limbs; }
   BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return m_wrapper.m_data; }
   BOOST_MP_FORCEINLINE const_limb_pointer limbs()const BOOST_NOEXCEPT { return m_wrapper.m_data; }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign()const BOOST_NOEXCEPT { return false; }
   BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT_IF((Checked == unchecked)) {  if(b) negate(); }
   BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size) BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      m_limbs = (std::min)(new_size, internal_limb_count);
      detail::verify_new_size(m_limbs, min_size, checked_type());
   }
   BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      limb_pointer p = limbs();
      detail::verify_limb_mask(m_limbs == internal_limb_count, p[internal_limb_count-1], upper_limb_mask, checked_type());
      p[internal_limb_count-1] &= upper_limb_mask;
      while((m_limbs-1) && !p[m_limbs - 1])--m_limbs;
   }

   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() BOOST_NOEXCEPT
      : m_wrapper(limb_type(0u)), m_limbs(1) {}
   BOOST_MP_FORCEINLINE cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
      : m_limbs(o.m_limbs)
   {
      std::copy(o.limbs(), o.limbs() + o.size(), limbs());
   }
   //~cpp_int_base() BOOST_NOEXCEPT {}
   BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
   {
      if(this != &o)
      {
         resize(o.size(), o.size());
         std::copy(o.limbs(), o.limbs() + o.size(), limbs());
      }
   }
private:
   void check_negate(const mpl::int_<checked>&)
   {
      BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned number."));
   }
   void check_negate(const mpl::int_<unchecked>&){}
public:
   void negate() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      // Not so much a negate as a complement - this gets called when subtraction
      // would result in a "negative" number:
      unsigned i;
      if((m_limbs == 1) && (m_wrapper.m_data[0] == 0))
         return; // negating zero is always zero, and always OK.
      check_negate(checked_type());
      for(i = m_limbs; i < internal_limb_count; ++i)
         m_wrapper.m_data[i] = 0;
      m_limbs = internal_limb_count;
      for(i = 0; i < internal_limb_count; ++i)
         m_wrapper.m_data[i] = ~m_wrapper.m_data[i];
      normalize();
      eval_increment(static_cast<cpp_int_backend<MinBits, MinBits, unsigned_magnitude, Checked, void>& >(*this));
   }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg()const BOOST_NOEXCEPT
   {
      return false;
   }
   BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
   {
      for(unsigned i = 0; i < (std::max)(size(), o.size()); ++i)
         std::swap(m_wrapper.m_data[i], o.m_wrapper.m_data[i]);
      std::swap(m_limbs, o.m_limbs);
   }
};
#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

template <unsigned MinBits, cpp_int_check_type Checked>
const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::limb_bits;
template <unsigned MinBits, cpp_int_check_type Checked>
const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::max_limb_value;
template <unsigned MinBits, cpp_int_check_type Checked>
const limb_type cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::sign_bit_mask;
template <unsigned MinBits, cpp_int_check_type Checked>
const unsigned cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::internal_limb_count;
template <unsigned MinBits, cpp_int_check_type Checked>
const bool cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, false>::variable;

#endif
//
// Traits classes to figure out a native type with N bits, these vary from boost::uint_t<N> only
// because some platforms have native integer types longer than long long, "really long long" anyone??
//
template <unsigned N, bool s>
struct trivial_limb_type_imp
{
   typedef double_limb_type type;
};

template <unsigned N>
struct trivial_limb_type_imp<N, true>
{
   typedef typename boost::uint_t<N>::least type;
};

template <unsigned N>
struct trivial_limb_type : public trivial_limb_type_imp<N, N <= sizeof(long long) * CHAR_BIT> {};
//
// Backend for fixed precision signed-magnitude type which will fit entirely inside a "double_limb_type":
//
template <unsigned MinBits, cpp_int_check_type Checked>
struct cpp_int_base<MinBits, MinBits, signed_magnitude, Checked, void, true>
{
   typedef typename trivial_limb_type<MinBits>::type  local_limb_type;
   typedef local_limb_type*                           limb_pointer;
   typedef const local_limb_type*                     const_limb_pointer;
   typedef mpl::int_<Checked>                         checked_type;
protected:
   BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
   BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = (MinBits < limb_bits) ? local_limb_type((local_limb_type(~local_limb_type(0))) >> (limb_bits - MinBits)) : local_limb_type(~local_limb_type(0)));
private:
   local_limb_type    m_data;
   bool               m_sign;

   //
   // Interface invariants:
   //
   BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
protected:
   template <class T>
   typename disable_if_c<std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits)>::type
      check_in_range(T val, const mpl::int_<checked>&)
   {
      BOOST_MP_USING_ABS
      typedef typename common_type<T, local_limb_type>::type common_type;

      if(static_cast<common_type>(abs(val)) > static_cast<common_type>(limb_mask))
         BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
   }
   template <class T, int C>
   void check_in_range(T, const mpl::int_<C>&){}

   template <class T>
   void check_in_range(T val)
   {
      check_in_range(val, checked_type());
   }

public:
   //
   // Direct construction:
   //
   template <class SI>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename enable_if_c<is_signed<SI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(i < 0 ? static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)), m_sign(i < 0) {}
   template <class SI>
   BOOST_MP_FORCEINLINE cpp_int_base(SI i, typename enable_if_c<is_signed<SI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(i < 0 ? static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)), m_sign(i < 0) { check_in_range(i); }
   template <class UI>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename enable_if_c<is_unsigned<UI>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(i)), m_sign(false) {}
   template <class UI>
   BOOST_MP_FORCEINLINE cpp_int_base(UI i, typename enable_if_c<is_unsigned<UI>::value && (Checked == checked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(i)), m_sign(false) { check_in_range(i); }
   template <class F>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(F i, typename enable_if_c<is_floating_point<F>::value && (Checked == unchecked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(std::fabs(i))), m_sign(i < 0) {}
   template <class F>
   BOOST_MP_FORCEINLINE cpp_int_base(F i, typename enable_if_c<is_floating_point<F>::value && (Checked == checked)>::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(std::fabs(i))), m_sign(i < 0) { check_in_range(i); }
   //
   // Helper functions for getting at our internal data, and manipulating storage:
   //
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size()const BOOST_NOEXCEPT { return 1; }
   BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
   BOOST_MP_FORCEINLINE const_limb_pointer limbs()const BOOST_NOEXCEPT { return &m_data; }
   BOOST_MP_FORCEINLINE bool sign()const BOOST_NOEXCEPT { return m_sign; }
   BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT
   {
      m_sign = b;
      // Check for zero value:
      if(m_sign && !m_data)
      {
         m_sign = false;
      }
   }
   BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size)
   {
      detail::verify_new_size(2, min_size, checked_type());
   }
   BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      if(!m_data)
         m_sign = false; // zero is always unsigned
      detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
      m_data &= limb_mask;
   }

   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_data(0), m_sign(false) {}
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
      : m_data(o.m_data), m_sign(o.m_sign) {}
   //~cpp_int_base() BOOST_NOEXCEPT {}
   BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
   {
      m_data = o.m_data;
      m_sign = o.m_sign;
   }
   BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT
   {
      m_sign = !m_sign;
      // Check for zero value:
      if(m_data == 0)
      {
         m_sign = false;
      }
   }
   BOOST_MP_FORCEINLINE bool isneg()const BOOST_NOEXCEPT
   {
      return m_sign;
   }
   BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
   {
      std::swap(m_sign, o.m_sign);
      std::swap(m_data, o.m_data);
   }
};
//
// Backend for unsigned fixed precision (i.e. no allocator) type which will fit entirely inside a "double_limb_type":
//
template <unsigned MinBits, cpp_int_check_type Checked>
struct cpp_int_base<MinBits, MinBits, unsigned_magnitude, Checked, void, true>
{
   typedef typename trivial_limb_type<MinBits>::type  local_limb_type;
   typedef local_limb_type*                           limb_pointer;
   typedef const local_limb_type*                     const_limb_pointer;
private:
   BOOST_STATIC_CONSTANT(unsigned, limb_bits = sizeof(local_limb_type) * CHAR_BIT);
   BOOST_STATIC_CONSTANT(local_limb_type, limb_mask = (~local_limb_type(0)) >> (limb_bits - MinBits));

   local_limb_type    m_data;

   typedef mpl::int_<Checked>                          checked_type;

   //
   // Interface invariants:
   //
   BOOST_STATIC_ASSERT_MSG(MinBits <= sizeof(double_limb_type) * CHAR_BIT, "Template parameter MinBits is inconsistent with the parameter trivial - did you mistakingly try to override the trivial parameter?");
protected:
   template <class T>
   typename disable_if_c<std::numeric_limits<T>::is_specialized && (std::numeric_limits<T>::digits <= (int)MinBits)>::type
      check_in_range(T val, const mpl::int_<checked>&, const mpl::false_&)
   {
      typedef typename common_type<T, local_limb_type>::type common_type;

      if(static_cast<common_type>(val) > limb_mask)
         BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
   }
   template <class T>
   void check_in_range(T val, const mpl::int_<checked>&, const mpl::true_&)
   {
      typedef typename common_type<T, local_limb_type>::type common_type;

      if(static_cast<common_type>(val) > limb_mask)
         BOOST_THROW_EXCEPTION(std::range_error("The argument to a cpp_int constructor exceeded the largest value it can represent."));
      if(val < 0)
         BOOST_THROW_EXCEPTION(std::range_error("The argument to an unsigned cpp_int constructor was negative."));
   }
   template <class T, int C, bool B>
   BOOST_MP_FORCEINLINE void check_in_range(T, const mpl::int_<C>&, const mpl::bool_<B>&){}

   template <class T>
   BOOST_MP_FORCEINLINE void check_in_range(T val)
   {
      check_in_range(val, checked_type(), is_signed<T>());
   }

public:
   //
   // Direct construction:
   //
   template <class SI>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(SI i, typename enable_if_c<is_signed<SI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)) {}
   template <class SI>
   BOOST_MP_FORCEINLINE cpp_int_base(SI i, typename enable_if_c<is_signed<SI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(i < 0 ? 1 + ~static_cast<local_limb_type>(-i) : static_cast<local_limb_type>(i)) { check_in_range(i); }
   template <class UI>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(UI i, typename enable_if_c<is_unsigned<UI>::value && (Checked == unchecked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(i)) {}
   template <class UI>
   BOOST_MP_FORCEINLINE cpp_int_base(UI i, typename enable_if_c<is_unsigned<UI>::value && (Checked == checked) >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(i)) { check_in_range(i); }
   template <class F>
   BOOST_MP_FORCEINLINE cpp_int_base(F i, typename enable_if<is_floating_point<F> >::type const* = 0) BOOST_NOEXCEPT_IF((Checked == unchecked))
      : m_data(static_cast<local_limb_type>(std::fabs(i)))
   {
      check_in_range(i);
      if(i < 0)
         negate();
   }
   //
   // Helper functions for getting at our internal data, and manipulating storage:
   //
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR unsigned size()const BOOST_NOEXCEPT { return 1; }
   BOOST_MP_FORCEINLINE limb_pointer limbs() BOOST_NOEXCEPT { return &m_data; }
   BOOST_MP_FORCEINLINE const_limb_pointer limbs()const BOOST_NOEXCEPT { return &m_data; }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool sign()const BOOST_NOEXCEPT { return false; }
   BOOST_MP_FORCEINLINE void sign(bool b) BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      if(b)
         negate();
   }
   BOOST_MP_FORCEINLINE void resize(unsigned new_size, unsigned min_size)
   {
      detail::verify_new_size(2, min_size, checked_type());
   }
   BOOST_MP_FORCEINLINE void normalize() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      detail::verify_limb_mask(true, m_data, limb_mask, checked_type());
      m_data &= limb_mask;
   }

   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base() : m_data(0) {}
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_base(const cpp_int_base& o) BOOST_NOEXCEPT
      : m_data(o.m_data) {}
   //~cpp_int_base() BOOST_NOEXCEPT {}
   BOOST_MP_FORCEINLINE void assign(const cpp_int_base& o) BOOST_NOEXCEPT
   {
      m_data = o.m_data;
   }
   BOOST_MP_FORCEINLINE void negate() BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      if(Checked == checked)
      {
         BOOST_THROW_EXCEPTION(std::range_error("Attempt to negate an unsigned type."));
      }
      m_data = ~m_data;
      ++m_data;
   }
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR bool isneg()const BOOST_NOEXCEPT
   {
      return false;
   }
   BOOST_MP_FORCEINLINE void do_swap(cpp_int_base& o) BOOST_NOEXCEPT
   {
      std::swap(m_data, o.m_data);
   }
};
//
// Traits class, lets us know whether type T can be directly converted to the base type,
// used to enable/disable constructors etc:
//
template <class Arg, class Base>
struct is_allowed_cpp_int_base_conversion : public mpl::if_c<
      is_same<Arg, limb_type>::value || is_same<Arg, signed_limb_type>::value
#ifdef BOOST_LITTLE_ENDIAN
      || is_same<Arg, double_limb_type>::value || is_same<Arg, signed_double_limb_type>::value
#endif
      || (is_trivial_cpp_int<Base>::value && is_arithmetic<Arg>::value),
      mpl::true_,
      mpl::false_
   >::type
{};
//
// Now the actual backend, normalising parameters passed to the base class:
//
template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct cpp_int_backend
   : public cpp_int_base<
               min_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
               max_precision<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
               SignType,
               Checked,
               Allocator,
               is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value>
{
   typedef cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>    self_type;
   typedef cpp_int_base<
               min_precision<self_type>::value,
               max_precision<self_type>::value,
               SignType,
               Checked,
               Allocator,
               is_trivial_cpp_int<self_type>::value>                 base_type;
   typedef mpl::bool_<is_trivial_cpp_int<self_type>::value>          trivial_tag;
public:
   typedef typename mpl::if_<
      trivial_tag,
      mpl::list<
      signed char, short, int, long,
      long long, signed_double_limb_type>,
      mpl::list<signed_limb_type, signed_double_limb_type>
   >::type                                                           signed_types;
   typedef typename mpl::if_<
      trivial_tag,
      mpl::list<unsigned char, unsigned short, unsigned,
      unsigned long long, double_limb_type>,
      mpl::list<limb_type, double_limb_type>
   >::type                                                           unsigned_types;
   typedef typename mpl::if_<
      trivial_tag,
      mpl::list<float, double, long double>,
      mpl::list<long double>
   >::type                                                           float_types;
   typedef mpl::int_<Checked>                                        checked_type;

   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend() BOOST_NOEXCEPT{}
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(const cpp_int_backend& o) BOOST_NOEXCEPT_IF(boost::is_void<Allocator>::value) : base_type(o) {}
#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(cpp_int_backend&& o) BOOST_NOEXCEPT
      : base_type(static_cast<base_type&&>(o)) {}
#endif
   //
   // Direct construction from arithmetic type:
   //
   template <class Arg>
   BOOST_MP_FORCEINLINE BOOST_CONSTEXPR cpp_int_backend(Arg i, typename enable_if_c<is_allowed_cpp_int_base_conversion<Arg, base_type>::value >::type const* = 0)BOOST_NOEXCEPT_IF((Checked == unchecked) && boost::is_void<Allocator>::value)
      : base_type(i) {}

private:
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::true_ const &)
   {
      // Assigning trivial type to trivial type:
      this->check_in_range(*other.limbs());
      *this->limbs() = static_cast<typename self_type::local_limb_type>(*other.limbs());
      this->sign(other.sign());
      this->normalize();
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::true_ const&, mpl::false_ const &)
   {
      // non-trivial to trivial narrowing conversion:
      double_limb_type v = *other.limbs();
      if(other.size() > 1)
      {
         v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
         if((Checked == checked) && (other.size() > 2))
         {
            BOOST_THROW_EXCEPTION(std::range_error("Assignment of a cpp_int that is out of range for the target type."));
         }
      }
      *this = v;
      this->sign(other.sign());
      this->normalize();
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::true_ const &)
   {
      // trivial to non-trivial, treat the trivial argument as if it were an unsigned arithmetic type, then set the sign afterwards:
       *this = static_cast<
            typename boost::multiprecision::detail::canonical<
               typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type,
               cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>
            >::type
         >(*other.limbs());
       this->sign(other.sign());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   void do_assign(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other, mpl::false_ const&, mpl::false_ const &)
   {
      // regular non-trivial to non-trivial assign:
      this->resize(other.size(), other.size());
      std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), this->limbs());
      this->sign(other.sign());
      this->normalize();
   }
public:
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   cpp_int_backend(
      const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
      typename enable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
      : base_type()
   {
      do_assign(
         other,
         mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
         mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   explicit cpp_int_backend(
      const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other,
      typename disable_if_c<is_implicit_cpp_int_conversion<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>, self_type>::value>::type* = 0)
      : base_type()
   {
      do_assign(
         other,
         mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
         mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   cpp_int_backend& operator=(
      const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& other)
   {
      do_assign(
         other,
         mpl::bool_<is_trivial_cpp_int<self_type>::value>(),
         mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value>());
      return *this;
   }
#if 0
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, class Allocator2>
   cpp_int_backend(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other, typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value >::type* = 0)
      : base_type()
   {
       *this = static_cast<
            typename boost::multiprecision::detail::canonical<
               typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>::local_limb_type,
               cpp_int_backend<MinBits, MaxBits, SignType, Allocator>
            >::type
         >(*other.limbs());
      this->sign(other.sign());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, class Allocator2>
   typename enable_if_c<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value, cpp_int_backend&>::type
    operator=(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other)
   {
       *this = static_cast<
            typename boost::multiprecision::detail::canonical<
               typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>::local_limb_type,
               cpp_int_backend<MinBits, MaxBits, SignType, Allocator>
            >::type
         >(*other.limbs());
      this->sign(other.sign());
      return *this;
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   cpp_int_backend(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other,
      typename enable_if_c<
         ((is_signed_number<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value || !is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value)
         && (!is_void<Allocator>::value || (is_void<Allocator2>::value && (MinBits >= MinBits2)))
         && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && !is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value)
      >::type* = 0)
      : base_type()
   {
      this->resize(other.size(), other_size());
      std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), this->limbs());
      this->sign(other.sign());
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   explicit cpp_int_backend(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other,
      typename enable_if_c<
         (!((is_signed_number<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value || !is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value)
         && (!is_void<Allocator>::value || (is_void<Allocator2>::value && (MinBits >= MinBits2))))
         && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value)
      >::type* = 0)
      : base_type()
   {
      double_limb_type v = *other.limbs();
      if(other.size() > 1)
         v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
      *this = v;
      this->sign(other.sign());
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   explicit cpp_int_backend(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other,
      typename enable_if_c<
         (!((is_signed_number<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value || !is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value))
         && (!is_void<Allocator>::value || (is_void<Allocator2>::value && (MinBits >= MinBits2)))
         && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && !is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value)
      >::type* = 0)
      : base_type()
   {
      this->resize(other.size(), other.size());
      std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), this->limbs());
      this->sign(other.sign());
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   explicit cpp_int_backend(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other,
      typename enable_if_c<
         (!((is_signed_number<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value || !is_signed_number<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value))
         && (!is_void<Allocator>::value || (is_void<Allocator2>::value && (MinBits >= MinBits2)))
         && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value)
      >::type* = 0)
      : base_type()
   {
      double_limb_type v = *other.limbs();
      if(other.size() > 1)
         v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
      *this = v;
      this->sign(other.sign());
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   typename enable_if_c<(!is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && !is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value), cpp_int_backend&>::type
      operator=(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other)
   {
      this->resize(other.size(), other.size());
      std::copy(other.limbs(), other.limbs() + (std::min)(other.size(), this->size()), this->limbs());
      this->sign(other.sign());
      return *this;
   }

   template <unsigned MinBits2, unsigned MaxBits2, bool SignType2, class Allocator2>
   typename enable_if_c<(!is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2> >::value
         && is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Allocator> >::value), cpp_int_backend&>::type
      operator=(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Allocator2>& other)
   {
      double_limb_type v = *other.limbs();
      if(other.size() > 1)
         v |= static_cast<double_limb_type>(other.limbs()[1]) << bits_per_limb;
      *this = v;
      this->sign(other.sign());
   }
#endif
   BOOST_MP_FORCEINLINE cpp_int_backend& operator = (const cpp_int_backend& o) BOOST_NOEXCEPT_IF((Checked == unchecked) && boost::is_void<Allocator>::value)
   {
      this->assign(o);
      return *this;
   }
#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
   BOOST_MP_FORCEINLINE cpp_int_backend& operator = (cpp_int_backend&& o) BOOST_NOEXCEPT_IF(boost::is_void<Allocator>::value)
   {
      *static_cast<base_type*>(this) = static_cast<base_type&&>(o);
      return *this;
   }
#endif
private:
   template <class A>
   typename enable_if<is_unsigned<A> >::type do_assign_arithmetic(A val, const mpl::true_&)
   {
      this->check_in_range(val);
      *this->limbs() = static_cast<typename self_type::local_limb_type>(val);
      this->normalize();
   }
   template <class A>
   typename disable_if<is_unsigned<A> >::type do_assign_arithmetic(A val, const mpl::true_&)
   {
      this->check_in_range(val);
      *this->limbs() = (val < 0) ? static_cast<typename self_type::local_limb_type>(-val) : static_cast<typename self_type::local_limb_type>(val);
      this->sign(val < 0);
      this->normalize();
   }
   BOOST_MP_FORCEINLINE void do_assign_arithmetic(limb_type i, const mpl::false_&) BOOST_NOEXCEPT
   {
      this->resize(1, 1);
      *this->limbs() = i;
      this->sign(false);
   }
   BOOST_MP_FORCEINLINE void do_assign_arithmetic(signed_limb_type i, const mpl::false_&) BOOST_NOEXCEPT_IF((Checked == unchecked))
   {
      this->resize(1, 1);
      *this->limbs() = static_cast<limb_type>(std::abs(i));
      this->sign(i < 0);
   }
   void do_assign_arithmetic(double_limb_type i, const mpl::false_&)
   {
      BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
      BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
      typename base_type::limb_pointer p = this->limbs();
      *p = static_cast<limb_type>(i);
      p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
      this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
      this->sign(false);
   }
   void do_assign_arithmetic(signed_double_limb_type i, const mpl::false_&)
   {
      BOOST_STATIC_ASSERT(sizeof(i) == 2 * sizeof(limb_type));
      BOOST_STATIC_ASSERT(base_type::internal_limb_count >= 2);
      bool s = false;
      if(i < 0)
      {
         s = true;
         i = -i;
      }
      else
         this->sign(false);
      typename base_type::limb_pointer p = this->limbs();
      *p = static_cast<limb_type>(i);
      p[1] = static_cast<limb_type>(i >> base_type::limb_bits);
      this->resize(p[1] ? 2 : 1, p[1] ? 2 : 1);
      this->sign(s);
   }

   void do_assign_arithmetic(long double a, const mpl::false_&)
   {
      using default_ops::eval_add;
      using default_ops::eval_subtract;
      using std::frexp;
      using std::ldexp;
      using std::floor;

      if (a == 0) {
         *this = static_cast<limb_type>(0u);
      }

      if (a == 1) {
         *this = static_cast<limb_type>(1u);
      }

      BOOST_ASSERT(!(boost::math::isinf)(a));
      BOOST_ASSERT(!(boost::math::isnan)(a));

      int e;
      long double f, term;
      *this = static_cast<limb_type>(0u);

      f = frexp(a, &e);

      static const limb_type shift = std::numeric_limits<limb_type>::digits;

      while(f)
      {
         // extract int sized bits from f:
         f = ldexp(f, shift);
         term = floor(f);
         e -= shift;
         eval_left_shift(*this, shift);
         if(term > 0)
            eval_add(*this, static_cast<limb_type>(term));
         else
            eval_subtract(*this, static_cast<limb_type>(-term));
         f -= term;
      }
      if(e > 0)
         eval_left_shift(*this, e);
      else if(e < 0)
         eval_right_shift(*this, -e);
   }
public:
   template <class Arithmetic>
   BOOST_MP_FORCEINLINE cpp_int_backend& operator = (Arithmetic val)
   {
      do_assign_arithmetic(val, trivial_tag());
      return *this;
   }
private:
   void do_assign_string(const char* s, const mpl::true_&)
   {
      std::size_t n = s ? std::strlen(s) : 0;
      *this->limbs() = 0;
      unsigned radix = 10;
      bool isneg = false;
      if(n && (*s == '-'))
      {
         --n;
         ++s;
         isneg = true;
      }
      if(n && (*s == '0'))
      {
         if((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
         {
            radix = 16;
            s +=2;
            n -= 2;
         }
         else
         {
            radix = 8;
            n -= 1;
         }
      }
      if(n)
      {
         unsigned val;
         while(*s)
         {
            if(*s >= '0' && *s <= '9')
               val = *s - '0';
            else if(*s >= 'a' && *s <= 'f')
               val = 10 + *s - 'a';
            else if(*s >= 'A' && *s <= 'F')
               val = 10 + *s - 'A';
            else
               val = radix + 1;
            if(val >= radix)
            {
               BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
            }
            *this->limbs() = detail::checked_multiply(*this->limbs(), static_cast<typename base_type::local_limb_type>(radix), checked_type());
            *this->limbs() = detail::checked_add(*this->limbs(), static_cast<typename base_type::local_limb_type>(val), checked_type());
            ++s;
         }
      }
      if(isneg)
         this->negate();
   }
   void do_assign_string(const char* s, const mpl::false_&)
   {
      using default_ops::eval_multiply;
      using default_ops::eval_add;
      std::size_t n = s ? std::strlen(s) : 0;
      *this = static_cast<limb_type>(0u);
      unsigned radix = 10;
      bool isneg = false;
      if(n && (*s == '-'))
      {
         --n;
         ++s;
         isneg = true;
      }
      if(n && (*s == '0'))
      {
         if((n > 1) && ((s[1] == 'x') || (s[1] == 'X')))
         {
            radix = 16;
            s +=2;
            n -= 2;
         }
         else
         {
            radix = 8;
            n -= 1;
         }
      }
      if(n)
      {
         if(radix == 8 || radix == 16)
         {
            unsigned shift = radix == 8 ? 3 : 4;
            unsigned block_count = base_type::limb_bits / shift;
            unsigned block_shift = shift * block_count;
            limb_type val, block;
            while(*s)
            {
               block = 0;
               for(unsigned i = 0; (i < block_count); ++i)
               {
                  if(*s >= '0' && *s <= '9')
                     val = *s - '0';
                  else if(*s >= 'a' && *s <= 'f')
                     val = 10 + *s - 'a';
                  else if(*s >= 'A' && *s <= 'F')
                     val = 10 + *s - 'A';
                  else
                     val = base_type::max_limb_value;
                  if(val >= radix)
                  {
                     BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string."));
                  }
                  block <<= shift;
                  block |= val;
                  if(!*++s)
                  {
                     // final shift is different:
                     block_shift = (i + 1) * shift;
                     break;
                  }
               }
               eval_left_shift(*this, block_shift);
               this->limbs()[0] |= block;
            }
         }
         else
         {
            // Base 10, we extract blocks of size 10^9 at a time, that way
            // the number of multiplications is kept to a minimum:
            limb_type block_mult = max_block_10;
            while(*s)
            {
               limb_type block = 0;
               for(unsigned i = 0; i < digits_per_block_10; ++i)
               {
                  limb_type val;
                  if(*s >= '0' && *s <= '9')
                     val = *s - '0';
                  else
                     BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input."));
                  block *= 10;
                  block += val;
                  if(!*++s)
                  {
                     block_mult = block_multiplier(i);
                     break;
                  }
               }
               eval_multiply(*this, block_mult);
               eval_add(*this, block);
            }
         }
      }
      if(isneg)
         this->negate();
   }
public:
   cpp_int_backend& operator = (const char* s)
   {
      do_assign_string(s, trivial_tag());
      return *this;
   }
   BOOST_MP_FORCEINLINE void swap(cpp_int_backend& o) BOOST_NOEXCEPT
   {
      this->do_swap(o);
   }
private:
   std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::false_&)const
   {
      if(this->sign() && (((f & std::ios_base::hex) == std::ios_base::hex) || ((f & std::ios_base::oct) == std::ios_base::oct)))
         BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
      std::stringstream ss;
      ss.flags(f & ~std::ios_base::showpos);
      ss << *this->limbs();
      std::string result;
      if(this->sign())
         result += '-';
      else if(f & std::ios_base::showpos)
         result += '+';
      result += ss.str();
      return result;
   }
   std::string do_get_trivial_string(std::ios_base::fmtflags f, const mpl::true_&)const
   {
      // Even though we have only one limb, we can't do IO on it :-(
      int base = 10;
      if((f & std::ios_base::oct) == std::ios_base::oct)
         base = 8;
      else if((f & std::ios_base::hex) == std::ios_base::hex)
         base = 16;
      std::string result;

      unsigned Bits = sizeof(typename base_type::local_limb_type) * CHAR_BIT;

      if(base == 8 || base == 16)
      {
         if(this->sign())
            BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
         limb_type shift = base == 8 ? 3 : 4;
         limb_type mask = static_cast<limb_type>((1u << shift) - 1);
         typename base_type::local_limb_type v = *this->limbs();
         result.assign(Bits / shift + (Bits % shift ? 1 : 0), '0');
         int pos = result.size() - 1;
         for(unsigned i = 0; i < Bits / shift; ++i)
         {
            char c = '0' + static_cast<char>(v & mask);
            if(c > '9')
               c += 'A' - '9' - 1;
            result[pos--] = c;
            v >>= shift;
         }
         if(Bits % shift)
         {
            mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
            char c = '0' + static_cast<char>(v & mask);
            if(c > '9')
               c += 'A' - '9';
            result[pos] = c;
         }
         //
         // Get rid of leading zeros:
         //
         std::string::size_type n = result.find_first_not_of('0');
         if(!result.empty() && (n == std::string::npos))
            n = result.size() - 1;
         result.erase(0, n);
         if(f & std::ios_base::showbase)
         {
            const char* pp = base == 8 ? "0" : "0x";
            result.insert(0, pp);
         }
      }
      else
      {
         result.assign(Bits / 3 + 1, '0');
         int pos = result.size() - 1;
         typename base_type::local_limb_type v(*this->limbs());
         bool neg = false;
         if(this->sign())
         {
            neg = true;
         }
         while(v)
         {
            result[pos] = (v % 10) + '0';
            --pos;
            v /= 10;
         }
         unsigned n = result.find_first_not_of('0');
         result.erase(0, n);
         if(result.empty())
            result = "0";
         if(neg)
            result.insert(0, 1, '-');
         else if(f & std::ios_base::showpos)
            result.insert(0, 1, '+');
      }
      return result;
   }
   std::string do_get_string(std::ios_base::fmtflags f, const mpl::true_&)const
   {
#ifdef BOOST_MP_NO_DOUBLE_LIMB_TYPE_IO
      return do_get_trivial_string(f, mpl::bool_<is_same<typename base_type::local_limb_type, double_limb_type>::value>());
#else
      return do_get_trivial_string(f, mpl::bool_<false>());
#endif
   }
   std::string do_get_string(std::ios_base::fmtflags f, const mpl::false_&)const
   {
      using default_ops::eval_get_sign;
      int base = 10;
      if((f & std::ios_base::oct) == std::ios_base::oct)
         base = 8;
      else if((f & std::ios_base::hex) == std::ios_base::hex)
         base = 16;
      std::string result;

      unsigned Bits = this->size() * base_type::limb_bits;

      if(base == 8 || base == 16)
      {
         if(this->sign())
            BOOST_THROW_EXCEPTION(std::runtime_error("Base 8 or 16 printing of negative numbers is not supported."));
         limb_type shift = base == 8 ? 3 : 4;
         limb_type mask = static_cast<limb_type>((1u << shift) - 1);
         cpp_int_backend t(*this);
         result.assign(Bits / shift + (Bits % shift ? 1 : 0), '0');
         int pos = result.size() - 1;
         for(unsigned i = 0; i < Bits / shift; ++i)
         {
            char c = '0' + static_cast<char>(t.limbs()[0] & mask);
            if(c > '9')
               c += 'A' - '9' - 1;
            result[pos--] = c;
            eval_right_shift(t, shift);
         }
         if(Bits % shift)
         {
            mask = static_cast<limb_type>((1u << (Bits % shift)) - 1);
            char c = '0' + static_cast<char>(t.limbs()[0] & mask);
            if(c > '9')
               c += 'A' - '9';
            result[pos] = c;
         }
         //
         // Get rid of leading zeros:
         //
         std::string::size_type n = result.find_first_not_of('0');
         if(!result.empty() && (n == std::string::npos))
            n = result.size() - 1;
         result.erase(0, n);
         if(f & std::ios_base::showbase)
         {
            const char* pp = base == 8 ? "0" : "0x";
            result.insert(0, pp);
         }
      }
      else
      {
         result.assign(Bits / 3 + 1, '0');
         int pos = result.size() - 1;
         cpp_int_backend t(*this);
         cpp_int_backend r;
         bool neg = false;
         if(t.sign())
         {
            t.negate();
            neg = true;
         }
         if(this->size() == 1)
         {
            result = boost::lexical_cast<std::string>(t.limbs()[0]);
         }
         else
         {
            cpp_int_backend block10;
            block10 = max_block_10;
            while(eval_get_sign(t) != 0)
            {
               cpp_int_backend t2;
               divide_unsigned_helper(&t2, t, block10, r);
               t = t2;
               limb_type v = r.limbs()[0];
               for(unsigned i = 0; i < digits_per_block_10; ++i)
               {
                  char c = '0' + v % 10;
                  v /= 10;
                  result[pos] = c;
                  if(pos-- == 0)
                     break;
               }
            }
         }
         unsigned n = result.find_first_not_of('0');
         result.erase(0, n);
         if(result.empty())
            result = "0";
         if(neg)
            result.insert(0, 1, '-');
         else if(f & std::ios_base::showpos)
            result.insert(0, 1, '+');
      }
      return result;
   }
public:
   std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f)const
   {
      return do_get_string(f, trivial_tag());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::false_&)const BOOST_NOEXCEPT
   {
      if(this->sign() != o.sign())
         return this->sign() ? -1 : 1;

      // Only do the compare if the same sign:
      int result = compare_unsigned(o);

      if(this->sign())
         result = -result;
      return result;
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::false_&)const
   {
      cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> t(*this);
      return t.compare(o);
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::false_&, const mpl::true_&)const
   {
      cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> t(o);
      return compare(t);
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare_imp(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o, const mpl::true_&, const mpl::true_&)const BOOST_NOEXCEPT
   {
      if(this->sign())
      {
         if(o.sign())
         {
            return *this->limbs() < *o.limbs() ? 1 : (*this->limbs() > *o.limbs() ? -1 : 0);
         }
         else
            return -1;
      }
      else
      {
         if(o.sign())
            return 1;
         return *this->limbs() < *o.limbs() ? -1 : (*this->limbs() > *o.limbs() ? 1 : 0);
      }
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o)const BOOST_NOEXCEPT
   {
      typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value> t1;
      typedef mpl::bool_<is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value> t2;
      return compare_imp(o, t1(), t2());
   }
   template <unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
   int compare_unsigned(const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& o)const BOOST_NOEXCEPT
   {
      if(this->size() != o.size())
      {
         return this->size() > o.size() ? 1 : -1;
      }
      typename base_type::const_limb_pointer pa = this->limbs();
      typename base_type::const_limb_pointer pb = o.limbs();
      for(int i = this->size() - 1; i >= 0; --i)
      {
         if(pa[i] != pb[i])
            return pa[i] > pb[i] ? 1 : -1;
      }
      return 0;
   }
   template <class Arithmetic>
   BOOST_MP_FORCEINLINE typename enable_if<is_arithmetic<Arithmetic>, int>::type compare(Arithmetic i)const
   {
      // braindead version:
      cpp_int_backend t;
      t = i;
      return compare(t);
   }
};

} // namespace backends

namespace detail{

template <class Backend>
struct double_precision_type;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct double_precision_type<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >
{
   typedef typename mpl::if_c<
      backends::is_fixed_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
      backends::cpp_int_backend<
         (is_void<Allocator>::value ?
            2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value
            : MinBits),
         2 * backends::max_precision<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> >::value,
         SignType,
         Checked,
         Allocator>,
      backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>
   >::type type;
};


}

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked>
struct expression_template_default<backends::cpp_int_backend<MinBits, MaxBits, SignType, Checked, void> >
{
   static const expression_template_option value = et_off;
};

using boost::multiprecision::backends::cpp_int_backend;

template <unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator>
struct number_category<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator> > : public mpl::int_<number_kind_integer>{};

typedef number<cpp_int_backend<> >                   cpp_int;
typedef rational_adapter<cpp_int_backend<> >         cpp_rational_backend;
typedef number<cpp_rational_backend>                 cpp_rational;

// Fixed precision unsigned types:
typedef number<cpp_int_backend<128, 128, unsigned_magnitude, unchecked, void> >   uint128_t;
typedef number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void> >   uint256_t;
typedef number<cpp_int_backend<512, 512, unsigned_magnitude, unchecked, void> >   uint512_t;
typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, unchecked, void> > uint1024_t;

// Fixed precision signed types:
typedef number<cpp_int_backend<128, 128, signed_magnitude, unchecked, void> >    int128_t;
typedef number<cpp_int_backend<256, 256, signed_magnitude, unchecked, void> >    int256_t;
typedef number<cpp_int_backend<512, 512, signed_magnitude, unchecked, void> >    int512_t;
typedef number<cpp_int_backend<1024, 1024, signed_magnitude, unchecked, void> >  int1024_t;

// Over again, but with checking enabled this time:
typedef number<cpp_int_backend<0, 0, signed_magnitude, checked> >  checked_cpp_int;
typedef rational_adapter<cpp_int_backend<0, 0, signed_magnitude, checked> >  checked_cpp_rational_backend;
typedef number<cpp_rational_backend>                 checked_cpp_rational;
// Fixed precision unsigned types:
typedef number<cpp_int_backend<128, 128, unsigned_magnitude, checked, void> >   checked_uint128_t;
typedef number<cpp_int_backend<256, 256, unsigned_magnitude, checked, void> >   checked_uint256_t;
typedef number<cpp_int_backend<512, 512, unsigned_magnitude, checked, void> >   checked_uint512_t;
typedef number<cpp_int_backend<1024, 1024, unsigned_magnitude, checked, void> > checked_uint1024_t;

// Fixed precision signed types:
typedef number<cpp_int_backend<128, 128, signed_magnitude, checked, void> >    checked_int128_t;
typedef number<cpp_int_backend<256, 256, signed_magnitude, checked, void> >    checked_int256_t;
typedef number<cpp_int_backend<512, 512, signed_magnitude, checked, void> >    checked_int512_t;
typedef number<cpp_int_backend<1024, 1024, signed_magnitude, checked, void> >  checked_int1024_t;

#ifdef BOOST_NO_SFINAE_EXPR

namespace detail{

template<unsigned MinBits, unsigned MaxBits, cpp_integer_type SignType, cpp_int_check_type Checked, class Allocator, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
struct is_explicitly_convertible<cpp_int_backend<MinBits, MaxBits, SignType, Checked, Allocator>, cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> > : public mpl::true_ {};

}
#endif

}} // namespaces

//
// Last of all we include the implementations of all the eval_* non member functions:
//
#include <boost/multiprecision/cpp_int/comparison.hpp>
#include <boost/multiprecision/cpp_int/add.hpp>
#include <boost/multiprecision/cpp_int/multiply.hpp>
#include <boost/multiprecision/cpp_int/divide.hpp>
#include <boost/multiprecision/cpp_int/bitwise.hpp>
#include <boost/multiprecision/cpp_int/misc.hpp>
#include <boost/multiprecision/cpp_int/limits.hpp>

#endif