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();
+}
+
+
+