[Boost-commit] svn:boost r81269 - in sandbox/big_number: boost/multiprecision boost/multiprecision/cpp_int boost/multiprecision/detail libs/multiprecision/doc libs/multiprecision/test

Subject: [Boost-commit] svn:boost r81269 - in sandbox/big_number: boost/multiprecision boost/multiprecision/cpp_int boost/multiprecision/detail libs/multiprecision/doc libs/multiprecision/test
From: john_at_[hidden]
Date: 2012-11-09 13:55:21

Author: johnmaddock
Date: 2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
New Revision: 81269
URL: http://svn.boost.org/trac/boost/changeset/81269

Log:
Add overloads of the integer-only functions which work with native integer types.
Ensure powm promotes fixed precision types to avoid numeric overflow.
Allow the Miller-Rabin code to be used by native integers.
Fix Miller Rabin tests to actually return the test result!
Fix some bugs in cpp_int unsigned arithmetic, and ensure the Miller Rabin and random number code can be safely used with checked fixed precision integers.
Added:
   sandbox/big_number/boost/multiprecision/integer.hpp   (contents, props changed)
   sandbox/big_number/libs/multiprecision/test/test_native_integer.cpp   (contents, props changed)
Text files modified: 
   sandbox/big_number/boost/multiprecision/cpp_int.hpp               |    27 ++++++++++++                            
   sandbox/big_number/boost/multiprecision/cpp_int/comparison.hpp    |     2                                         
   sandbox/big_number/boost/multiprecision/cpp_int/divide.hpp        |    22 +++++++---                              
   sandbox/big_number/boost/multiprecision/cpp_int/misc.hpp          |     9 +++                                     
   sandbox/big_number/boost/multiprecision/detail/integer_ops.hpp    |    84 +++++++++++++++++++++++++-------------- 
   sandbox/big_number/boost/multiprecision/gmp.hpp                   |     9 ++++                                    
   sandbox/big_number/boost/multiprecision/miller_rabin.hpp          |    53 ++++++++++++++++---------               
   sandbox/big_number/boost/multiprecision/number.hpp                |     2                                         
   sandbox/big_number/boost/multiprecision/random.hpp                |    14 ++++++                                  
   sandbox/big_number/boost/multiprecision/tommath.hpp               |     9 ++++                                    
   sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk     |     4 +                                       
   sandbox/big_number/libs/multiprecision/test/Jamfile.v2            |     1                                         
   sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp |    43 +++++++++++++++++--                     
   13 files changed, 210 insertions(+), 69 deletions(-)

Modified: sandbox/big_number/boost/multiprecision/cpp_int.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/cpp_int.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/cpp_int.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -29,7 +29,7 @@
 #ifdef BOOST_MSVC
 // warning C4127: conditional expression is constant
 #pragma warning(push)
-#pragma warning(disable:4127 4351 4293)
+#pragma warning(disable:4127 4351 4293 4996 4307)
 #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 >
@@ -1736,6 +1736,31 @@
 
 } // 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> >
 {

Modified: sandbox/big_number/boost/multiprecision/cpp_int/comparison.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/cpp_int/comparison.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/cpp_int/comparison.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -14,7 +14,7 @@
 
 #ifdef BOOST_MSVC
 #pragma warning(push)
-#pragma warning(disable:4018 4389)
+#pragma warning(disable:4018 4389 4996)
 #endif
 
 //

Modified: sandbox/big_number/boost/multiprecision/cpp_int/divide.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/cpp_int/divide.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/cpp_int/divide.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -215,7 +215,7 @@
       // rather than a full O(N^2) multiply:
       //
       double_limb_type carry = 0;
-      t.resize(y.size() + shift + 1, y.size() + shift + 1);
+      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)
@@ -235,12 +235,18 @@
          t.resize(t.size() - 1, t.size() - 1);
       }
       //
-      // Update r:
+      // Update r in a way that won't actually produce a negative result
+      // in case the argument types are unsigned:
       //
-      eval_subtract(r, t);
-      if(r.isneg())
+      if(r.compare(t) > 0)
       {
-         r.negate();
+         eval_subtract(r, t);
+      }
+      else
+      {
+         r.swap(t);
+         eval_subtract(r, t);
+         prem = r.limbs();
          r_neg = !r_neg;
       }
       //
@@ -272,11 +278,13 @@
       // We have one too many in the result:
       if(result)
          eval_decrement(*result);
-      r.negate();
       if(y.sign())
+      {
+         r.negate();
          eval_subtract(r, y);
+      }
       else
-         eval_add(r, y);
+         eval_subtract(r, y, r);
    }
 
    BOOST_ASSERT(r.compare_unsigned(y) < 0); // remainder must be less than the divisor or our code has failed

Modified: sandbox/big_number/boost/multiprecision/cpp_int/misc.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/cpp_int/misc.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/cpp_int/misc.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -110,7 +110,14 @@
    eval_lsb(const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a) BOOST_NOEXCEPT
 {
    using default_ops::eval_get_sign;
-   BOOST_ASSERT(eval_get_sign(a) != 0);
+   if(eval_get_sign(a) == 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
+   }
+   if(a.sign())
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
+   }
 
    unsigned result = 0;
    //

Modified: sandbox/big_number/boost/multiprecision/detail/integer_ops.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/detail/integer_ops.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/detail/integer_ops.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -242,6 +242,16 @@
 namespace detail{
 
 //
+// Within powm, we need a type with twice as many digits as the argument type, define
+// a traits class to obtain that type:
+//
+template <class Backend>
+struct double_precision_type
+{
+   typedef Backend type;
+};
+
+//
 // Calculate (a^p)%c:
 //
 template <class Backend>
@@ -253,29 +263,34 @@
    using default_ops::eval_modulus;
    using default_ops::eval_right_shift;
 
-   typedef typename canonical<unsigned char, Backend>::type ui_type;
+   typedef typename double_precision_type<Backend>::type double_type;
+   typedef typename canonical<unsigned char, double_type>::type ui_type;
    
-   Backend x, y(a), b(p);
+   double_type x, y(a), b(p), t;
    x = ui_type(1u);
+
    while(eval_get_sign(b) > 0)
    {
       if(eval_bit_test(b, 0))
       {
-         eval_multiply(result, x, y);
-         eval_modulus(x, result, c);
+         eval_multiply(t, x, y);
+         eval_modulus(x, t, c);
       }
-      eval_multiply(result, y, y);
-      eval_modulus(y, result, c);
+      eval_multiply(t, y, y);
+      eval_modulus(y, t, c);
       eval_right_shift(b, ui_type(1));
    }
-   eval_modulus(result, x, c);
+   Backend x2(x);
+   eval_modulus(result, x2, c);
 }
 
 template <class Backend, class Integer>
 void eval_powm(Backend& result, const Backend& a, const Backend& p, Integer c)
 {
-   typedef typename canonical<unsigned char, Backend>::type ui_type;
-   typedef typename canonical<Integer, Backend>::type i_type;
+   typedef typename double_precision_type<Backend>::type double_type;
+   typedef typename canonical<unsigned char, double_type>::type ui_type;
+   typedef typename canonical<Integer, double_type>::type i1_type;
+   typedef typename canonical<Integer, Backend>::type i2_type;
 
    using default_ops::eval_bit_test;
    using default_ops::eval_get_sign;
@@ -288,27 +303,29 @@
       BOOST_THROW_EXCEPTION(std::runtime_error("powm requires a positive exponent."));
    }
 
-   Backend x, y(a), b(p);
+   double_type x, y(a), b(p), t;
    x = ui_type(1u);
+
    while(eval_get_sign(b) > 0)
    {
       if(eval_bit_test(b, 0))
       {
-         eval_multiply(result, x, y);
-         eval_modulus(x, result, static_cast<i_type>(c));
+         eval_multiply(t, x, y);
+         eval_modulus(x, t, static_cast<i1_type>(c));
       }
-      eval_multiply(result, y, y);
-      eval_modulus(y, result, static_cast<i_type>(c));
+      eval_multiply(t, y, y);
+      eval_modulus(y, t, static_cast<i1_type>(c));
       eval_right_shift(b, ui_type(1));
    }
-   eval_modulus(result, x, static_cast<i_type>(c));
+   Backend x2(x);
+   eval_modulus(result, x2, static_cast<i2_type>(c));
 }
 
 template <class Backend, class Integer>
 typename enable_if<is_unsigned<Integer> >::type eval_powm(Backend& result, const Backend& a, Integer b, const Backend& c)
 {
-   typedef typename canonical<unsigned char, Backend>::type ui_type;
-   typedef typename canonical<Integer, Backend>::type i_type;
+   typedef typename double_precision_type<Backend>::type double_type;
+   typedef typename canonical<unsigned char, double_type>::type ui_type;
 
    using default_ops::eval_bit_test;
    using default_ops::eval_get_sign;
@@ -316,20 +333,22 @@
    using default_ops::eval_modulus;
    using default_ops::eval_right_shift;
 
-   Backend x, y(a);
+   double_type x, y(a), t;
    x = ui_type(1u);
+
    while(b > 0)
    {
       if(b & 1)
       {
-         eval_multiply(result, x, y);
-         eval_modulus(x, result, c);
+         eval_multiply(t, x, y);
+         eval_modulus(x, t, c);
       }
-      eval_multiply(result, y, y);
-      eval_modulus(y, result, c);
+      eval_multiply(t, y, y);
+      eval_modulus(y, t, c);
       b >>= 1;
    }
-   eval_modulus(result, x, c);
+   Backend x2(x);
+   eval_modulus(result, x2, c);
 }
 
 template <class Backend, class Integer>
@@ -345,8 +364,9 @@
 template <class Backend, class Integer1, class Integer2>
 typename enable_if<is_unsigned<Integer1> >::type eval_powm(Backend& result, const Backend& a, Integer1 b, Integer2 c)
 {
-   typedef typename canonical<unsigned char, Backend>::type ui_type;
-   typedef typename canonical<Integer1, Backend>::type i1_type;
+   typedef typename double_precision_type<Backend>::type double_type;
+   typedef typename canonical<unsigned char, double_type>::type ui_type;
+   typedef typename canonical<Integer1, double_type>::type i1_type;
    typedef typename canonical<Integer2, Backend>::type i2_type;
 
    using default_ops::eval_bit_test;
@@ -355,20 +375,22 @@
    using default_ops::eval_modulus;
    using default_ops::eval_right_shift;
 
-   Backend x, y(a);
+   double_type x, y(a), t;
    x = ui_type(1u);
+
    while(b > 0)
    {
       if(b & 1)
       {
-         eval_multiply(result, x, y);
-         eval_modulus(x, result, static_cast<i2_type>(c));
+         eval_multiply(t, x, y);
+         eval_modulus(x, t, static_cast<i1_type>(c));
       }
-      eval_multiply(result, y, y);
-      eval_modulus(y, result, static_cast<i2_type>(c));
+      eval_multiply(t, y, y);
+      eval_modulus(y, t, static_cast<i1_type>(c));
       b >>= 1;
    }
-   eval_modulus(result, x, static_cast<i2_type>(c));
+   Backend x2(x);
+   eval_modulus(result, x2, static_cast<i2_type>(c));
 }
 
 template <class Backend, class Integer1, class Integer2>

Modified: sandbox/big_number/boost/multiprecision/gmp.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/gmp.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/gmp.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -1593,6 +1593,15 @@
 
 inline unsigned eval_lsb(const gmp_int& val)
 {
+   int c = eval_get_sign(val);
+   if(c == 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
+   }
+   if(c < 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
+   }
    return mpz_scan1(val.data(), 0);
 }
 

Added: sandbox/big_number/boost/multiprecision/integer.hpp
==============================================================================
--- (empty file)
+++ sandbox/big_number/boost/multiprecision/integer.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -0,0 +1,174 @@
+///////////////////////////////////////////////////////////////
+//  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_INTEGER_HPP
+#define BOOST_MP_INTEGER_HPP
+
+#include <boost/multiprecision/cpp_int.hpp>
+
+namespace boost{
+namespace multiprecision{
+
+template <class Integer, class I2>
+typename enable_if_c<is_integral<Integer>::value && is_integral<I2>::value, Integer>::type 
+   multiply(Integer& result, const I2& a, const I2& b)
+{
+   return result = static_cast<Integer>(a) * static_cast<Integer>(b);
+}
+template <class Integer, class I2>
+typename enable_if_c<is_integral<Integer>::value && is_integral<I2>::value, Integer>::type 
+   add(Integer& result, const I2& a, const I2& b)
+{
+   return result = static_cast<Integer>(a) + static_cast<Integer>(b);
+}
+template <class Integer, class I2>
+typename enable_if_c<is_integral<Integer>::value && is_integral<I2>::value, Integer>::type 
+   subtract(Integer& result, const I2& a, const I2& b)
+{
+   return result = static_cast<Integer>(a) - static_cast<Integer>(b);
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value>::type divide_qr(const Integer& x, const Integer& y, Integer& q, Integer& r)
+{
+   q = x / y;
+   r = x % y;
+}
+
+template <class I1, class I2>
+typename enable_if_c<is_integral<I1>::value && is_integral<I2>::value, I2>::type integer_modulus(const I1& x, I2 val)
+{
+   return static_cast<I2>(x % val);
+}
+
+namespace detail{
+//
+// Figure out the kind of integer that has twice as many bits as some builtin 
+// integer type I.  Use a native type if we can (including types which may not
+// be recognised by boost::int_t because they're larger than long long), 
+// otherwise synthesize a cpp_int to do the job.
+//
+template <class I>
+struct double_integer
+{
+   static const unsigned int_t_digits = 
+      2 * sizeof(I) <= sizeof(long long) ? std::numeric_limits<I>::digits * 2 : 1;
+
+   typedef typename mpl::if_c<
+      2 * sizeof(I) <= sizeof(long long),
+      typename mpl::if_c<
+         is_signed<I>::value,
+         typename boost::int_t<int_t_digits>::least,
+         typename boost::uint_t<int_t_digits>::least
+      >::type,
+      typename mpl::if_c<
+         2 * sizeof(I) <= sizeof(double_limb_type),
+         typename mpl::if_c<
+            is_signed<I>::value,
+            signed_double_limb_type,
+            double_limb_type
+         >::type,
+         number<cpp_int_backend<sizeof(I)*CHAR_BIT*2, sizeof(I)*CHAR_BIT*2, (is_signed<I>::value ? signed_magnitude : unsigned_magnitude), unchecked, void> >
+      >::type
+   >::type type;
+};
+
+}
+
+template <class I1, class I2, class I3>
+typename enable_if_c<is_integral<I1>::value && is_integral<I2>::value && is_integral<I3>::value, I1>::type
+   powm(const I1& a, I2 b, I3 c)
+{
+   typedef typename detail::double_integer<I1>::type double_type;
+
+   I1 x(1), y(a);
+   double_type result;
+
+   while(b > 0)
+   {
+      if(b & 1)
+      {
+         multiply(result, x, y);
+         x = integer_modulus(result, c);
+      }
+      multiply(result, y, y);
+      y = integer_modulus(result, c);
+      b >>= 1;
+   }
+   return x % c;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, unsigned>::type lsb(const Integer& val)
+{
+   if(val == 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
+   }
+   if(val < 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
+   }
+   unsigned index = 0;
+   Integer mask = 1;
+
+   while(((mask & val) == 0) && (index < sizeof(Integer) * CHAR_BIT))
+   {
+      ++index;
+      mask <<= 1;
+   }
+   return index;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, bool>::type bit_test(const Integer& val, unsigned index)
+{
+   Integer mask = 1;
+   if(index >= sizeof(Integer) * CHAR_BIT)
+      return 0;
+   if(index)
+      mask <<= index;
+   return val & mask ? true : false;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, Integer&>::type bit_set(Integer& val, unsigned index)
+{
+   Integer mask = 1;
+   if(index >= sizeof(Integer) * CHAR_BIT)
+      return val;
+   if(index)
+      mask <<= index;
+   val |= mask;
+   return val;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, Integer&>::type bit_unset(Integer& val, unsigned index)
+{
+   Integer mask = 1;
+   if(index >= sizeof(Integer) * CHAR_BIT)
+      return val;
+   if(index)
+      mask <<= index;
+   val &= ~mask;
+   return val;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, Integer&>::type bit_flip(Integer& val, unsigned index)
+{
+   Integer mask = 1;
+   if(index >= sizeof(Integer) * CHAR_BIT)
+      return val;
+   if(index)
+      mask <<= index;
+   val ^= mask;
+   return val;
+}
+
+}} // namespaces
+
+#endif

Modified: sandbox/big_number/boost/multiprecision/miller_rabin.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/miller_rabin.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/miller_rabin.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -7,12 +7,14 @@
 #define BOOST_MP_MR_HPP
 
 #include <boost/multiprecision/random.hpp>
+#include <boost/multiprecision/integer.hpp>
 
 namespace boost{
 namespace multiprecision{
+namespace detail{
 
-template <class Backend, expression_template_option ExpressionTemplates>
-bool check_small_factors(const number<Backend, ExpressionTemplates>& n)
+template <class I>
+bool check_small_factors(const I& n)
 {
    static const boost::uint32_t small_factors1[] = {
       3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u };
@@ -117,22 +119,37 @@
    return false;
 }
 
-template <class Backend, expression_template_option ExpressionTemplates, class Engine>
-typename enable_if_c<number_category<Backend>::value == number_kind_integer, bool>::type 
-   miller_rabin_test(const number<Backend, ExpressionTemplates>& n, unsigned trials, Engine& gen)
+template <class I>
+typename enable_if_c<is_convertible<I, unsigned>::value, unsigned>::type
+   cast_to_unsigned(const I& val)
+{
+   return static_cast<unsigned>(val);
+}
+template <class I>
+typename disable_if_c<is_convertible<I, unsigned>::value, unsigned>::type
+   cast_to_unsigned(const I& val)
+{
+   return val.template convert_to<unsigned>();
+}
+
+} // namespace detail
+
+template <class I, class Engine>
+typename enable_if_c<number_category<I>::value == number_kind_integer, bool>::type 
+   miller_rabin_test(const I& n, unsigned trials, Engine& gen)
 {
 #ifdef BOOST_MSVC
 #pragma warning(push)
 #pragma warning(disable:4127)
 #endif
-   typedef number<Backend, ExpressionTemplates> number_type;
+   typedef I number_type;
 
    if(n <= 227)
-      return is_small_prime(n.template convert_to<unsigned>());
+      return detail::is_small_prime(detail::cast_to_unsigned(n));
    if((n & 1) == 0)
       return false;
 
-   if(!check_small_factors(n))
+   if(!detail::check_small_factors(n))
       return false;
 
    number_type nm1 = n - 1;
@@ -144,15 +161,12 @@
    if(x != 1u)
       return false;
 
-   q = (n - 1) >> 1;
-   unsigned k = 1;
-   while((q & 1) == 0)
-   {
-      q >>= 1;
-      ++k;
-   }
+   q = n - 1;
+   unsigned k = lsb(q);
+   q >>= k;
+
    // Declare our random number generator:
-   boost::random::uniform_int_distribution<number_type> dist(0, n);
+   boost::random::uniform_int_distribution<number_type> dist(2, n - 2);
    //
    // Execute the trials:
    //
@@ -169,7 +183,7 @@
             return false; // test failed
          if(++j == k)
             return false; // failed
-         y = (y * y) % n;
+         y = powm(y, 2, n);
       }
    }
    return true;  // Yeheh! probably prime.
@@ -178,8 +192,9 @@
 #endif
 }
 
-template <class Backend, expression_template_option ExpressionTemplates>
-bool miller_rabin_test(const number<Backend, ExpressionTemplates>& x, unsigned trials)
+template <class I>
+typename enable_if_c<number_category<I>::value == number_kind_integer, bool>::type 
+   miller_rabin_test(const I& x, unsigned trials)
 {
    static mt19937 gen;
    return miller_rabin_test(x, trials, gen);

Modified: sandbox/big_number/boost/multiprecision/number.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/number.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/number.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -88,7 +88,7 @@
    }
    */
    template<expression_template_option ET>
-   BOOST_FORCEINLINE BOOST_CONSTEXPR number(const number<Backend, ET>& val) BOOST_NOEXCEPT_IF(noexcept(Backend(static_cast<const Backend&>(std::declval<Backend>())))) : m_backend(val.m_backend) {}
+   BOOST_FORCEINLINE BOOST_CONSTEXPR number(const number<Backend, ET>& val) BOOST_NOEXCEPT_IF(noexcept(Backend(static_cast<const Backend&>(std::declval<Backend>())))) : m_backend(val.backend()) {}
 
    template <class Other, expression_template_option ET>
    BOOST_FORCEINLINE number(const number<Other, ET>& val, 

Modified: sandbox/big_number/boost/multiprecision/random.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/random.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/random.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -8,6 +8,11 @@
 #ifndef BOOST_MP_RANDOM_HPP
 #define BOOST_MP_RANDOM_HPP
 
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable:4127)
+#endif
+
 #include <boost/multiprecision/number.hpp>
 
 namespace boost{ namespace random{ namespace detail{
@@ -50,7 +55,10 @@
     { return 0; }
     // This is the only function we modify compared to the primary template:
     static result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
-    { return (result_type(1) << w) - 1; }
+    {
+       // This expression allows for the possibility that w == std::numeric_limits<result_type>::digits:
+       return (((result_type(1) << (w - 1)) - 1) << 1) + 1; 
+    }
 
     independent_bits_engine() { }
 
@@ -572,4 +580,8 @@
 
 }} // namespaces
 
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
 #endif

Modified: sandbox/big_number/boost/multiprecision/tommath.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/tommath.hpp	(original)
+++ sandbox/big_number/boost/multiprecision/tommath.hpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -588,6 +588,15 @@
 
 inline unsigned eval_lsb(const tommath_int& val)
 {
+   int c = eval_get_sign(val);
+   if(c == 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand."));
+   }
+   if(c < 0)
+   {
+      BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined."));
+   }
    return mp_cnt_lsb(const_cast< ::mp_int*>(&val.data()));
 }
 

Modified: sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk	(original)
+++ sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -1874,7 +1874,7 @@
 Returns ['b[super p] mod m] as an expression template.
 
    template <class Backend, expression_template_option ExpressionTemplates>
-   bool divide_qr(const ``['number-or-expression-template-type]``& x, const ``['number-or-expression-template-type]``& y,
+   void divide_qr(const ``['number-or-expression-template-type]``& x, const ``['number-or-expression-template-type]``& y,
                   number<Backend, ExpressionTemplates>& q, number<Backend, ExpressionTemplates>& r);
 
 Divides x by y and returns both the quotient and remainder.  After the call `q = x / y` and `r = x % y`.
@@ -1888,6 +1888,8 @@
 
 Returns the index of the least significant bit that is set to 1.
 
+Throws a `std::range_error` if the argument is <= 0.
+
    template <class Backend, class ExpressionTemplates>
    bool bit_test(const number<Backend, ExpressionTemplates>& val, unsigned index);
 

Modified: sandbox/big_number/libs/multiprecision/test/Jamfile.v2
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/Jamfile.v2	(original)
+++ sandbox/big_number/libs/multiprecision/test/Jamfile.v2	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -821,6 +821,7 @@
          [ check-target-builds ../config//has_tommath : : <build>no ] ;
 run ../example/floating_point_examples.cpp : : : <toolset>gcc:<cxxflags>-std=c++0x ;
 run test_cpp_int_conv.cpp ;
+run test_native_integer.cpp ;
 
 run test_mixed_cpp_int.cpp ;
 run test_mixed_float.cpp

Modified: sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp	(original)
+++ sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -3,14 +3,21 @@
 //  Software License, Version 1.0. (See accompanying file
 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
 
+#ifdef _MSC_VER
+#  define _SCL_SECURE_NO_WARNINGS
+#endif
+
 #include <boost/multiprecision/gmp.hpp>
+#include <boost/multiprecision/cpp_int.hpp>
 #include <boost/multiprecision/miller_rabin.hpp>
 #include <boost/math/special_functions/prime.hpp>
 #include <iostream>
 #include <iomanip>
 #include "test.hpp"
 
-int main()
+
+template <class I>
+void test()
 {
    //
    // Very simple test program to verify that the GMP's Miller-Rabin
@@ -22,7 +29,14 @@
    using namespace boost::random;
    using namespace boost::multiprecision;
 
-   independent_bits_engine<mt11213b, 256, mpz_int> gen;
+   typedef I test_type;
+
+   static const unsigned test_bits = 
+      std::numeric_limits<test_type>::digits && (std::numeric_limits<test_type>::digits <= 256)
+      ? std::numeric_limits<test_type>::digits
+      : 128;
+
+   independent_bits_engine<mt11213b, test_bits, test_type> gen;
    //
    // We must use a different generator for the tests and number generation, otherwise
    // we get false positives.  Further we use the same random number engine for the
@@ -35,16 +49,17 @@
    //
    for(unsigned i = 1; i < boost::math::max_prime; ++i)
    {
-      BOOST_TEST(miller_rabin_test(mpz_int(boost::math::prime(i)), 25, gen));
+      BOOST_TEST(miller_rabin_test(test_type(boost::math::prime(i)), 25, gen));
+      BOOST_TEST(mpz_probab_prime_p(mpz_int(boost::math::prime(i)).backend().data(), 25));
    }
    //
    // Now test some random values and compare GMP's native routine with ours.
    //
    for(unsigned i = 0; i < 10000; ++i)
    {
-      mpz_int n = gen();
+      test_type n = gen();
       bool is_prime_boost = miller_rabin_test(n, 25, gen2);
-      bool is_gmp_prime = mpz_probab_prime_p(n.backend().data(), 25);
+      bool is_gmp_prime = mpz_probab_prime_p(mpz_int(n).backend().data(), 25) ? true : false;
       if(is_prime_boost && is_gmp_prime)
       {
          std::cout << "We have a prime: " << std::hex << std::showbase << n << std::endl;
@@ -53,7 +68,23 @@
          std::cout << std::hex << std::showbase << "n = " << n << std::endl;
       BOOST_CHECK_EQUAL(is_prime_boost, is_gmp_prime);
    }
-   return 0;
+}
+
+int main()
+{
+   using namespace boost::multiprecision;
+
+   test<mpz_int>();
+   test<number<gmp_int, et_off> >();
+   test<boost::uint64_t>();
+   test<boost::uint32_t>();
+
+   test<cpp_int>();
+   test<number<cpp_int_backend<64, 64, unsigned_magnitude, checked, void>, et_off> >();
+   test<checked_uint128_t>();
+   test<checked_uint1024_t>();
+
+   return boost::report_errors();
 }
 
 

Added: sandbox/big_number/libs/multiprecision/test/test_native_integer.cpp
==============================================================================
--- (empty file)
+++ sandbox/big_number/libs/multiprecision/test/test_native_integer.cpp	2012-11-09 13:55:19 EST (Fri, 09 Nov 2012)
@@ -0,0 +1,79 @@
+///////////////////////////////////////////////////////////////
+//  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_
+
+//
+// Compare arithmetic results using fixed_int to GMP results.
+//
+
+#ifdef _MSC_VER
+#  define _SCL_SECURE_NO_WARNINGS
+#endif
+
+#include <boost/multiprecision/integer.hpp>
+#include "test.hpp"
+
+#ifdef BOOST_MSVC
+#pragma warning(disable:4146)
+#endif
+
+template <class I, class H>
+void test()
+{
+   using namespace boost::multiprecision;
+
+   I i(0);
+
+   BOOST_CHECK_THROW(lsb(i), std::range_error);
+   BOOST_CHECK(bit_test(bit_set(i, 0), 0));
+   BOOST_CHECK_EQUAL(bit_set(i, 0), 1);
+   BOOST_CHECK_EQUAL(bit_unset(i, 0), 0);
+   BOOST_CHECK_EQUAL(bit_flip(bit_set(i, 0), 0), 0);
+
+   unsigned max_index = (std::numeric_limits<I>::digits) - 1;
+   BOOST_CHECK(bit_test(bit_set(i, max_index), max_index));
+   BOOST_CHECK_EQUAL(bit_unset(i, max_index), 0);
+   BOOST_CHECK_EQUAL(bit_flip(bit_set(i, max_index), max_index), 0);
+
+   if(std::numeric_limits<I>::is_signed)
+   {
+      i = -1;
+      BOOST_CHECK_THROW(lsb(i), std::range_error);
+   }
+
+   H mx = (std::numeric_limits<H>::max)();
+
+   BOOST_CHECK_EQUAL(multiply(i, mx, mx), static_cast<I>(mx) * static_cast<I>(mx));
+   BOOST_CHECK_EQUAL(add(i, mx, mx), static_cast<I>(mx) + static_cast<I>(mx));
+   if(std::numeric_limits<I>::is_signed)
+   {
+      BOOST_CHECK_EQUAL(subtract(i, mx, static_cast<H>(-mx)), static_cast<I>(mx) - static_cast<I>(-mx));
+      BOOST_CHECK_EQUAL(add(i, static_cast<H>(-mx), static_cast<H>(-mx)), static_cast<I>(-mx) + static_cast<I>(-mx));
+   }
+
+   i = (std::numeric_limits<I>::max)();
+   I j = 12345;
+   I r, q;
+   divide_qr(i, j, q, r);
+   BOOST_CHECK_EQUAL(q, i / j);
+   BOOST_CHECK_EQUAL(r, i % j);
+   BOOST_CHECK_EQUAL(integer_modulus(i, j), i % j);
+   I p = 456;
+   BOOST_CHECK_EQUAL(powm(i, p, j), pow(cpp_int(i), static_cast<unsigned>(p)) % j);
+}
+
+int main()
+{
+   using namespace boost::multiprecision;
+
+   test<boost::int32_t, boost::int16_t>();
+   test<boost::int64_t, boost::int32_t>();
+   test<boost::uint32_t, boost::uint16_t>();
+   test<boost::uint64_t, boost::uint32_t>();
+   
+   return boost::report_errors();
+}
+
+
+