Subject: [Boost-commit] svn:boost r83080 - in trunk: boost/multiprecision/cpp_int libs/multiprecision/test
From: john_at_[hidden]
Date: 2013-02-22 05:37:36
Author: johnmaddock
Date: 2013-02-22 05:37:36 EST (Fri, 22 Feb 2013)
New Revision: 83080
URL: http://svn.boost.org/trac/boost/changeset/83080
Log:
Fix bug in subtraction of a limb_type.
Fix bug in division/modulus algorithms that results in incorrect sign when source and destination overlap.
Tweak performance of GCD algorithms.
Add test cases for bug reports.
Fixes #8133.
Fixes #8126.
Text files modified:
trunk/boost/multiprecision/cpp_int/add.hpp | 2
trunk/boost/multiprecision/cpp_int/divide.hpp | 18 +++++++++----
trunk/boost/multiprecision/cpp_int/misc.hpp | 12 ++++++++-
trunk/libs/multiprecision/test/test_cpp_int.cpp | 50 ++++++++++++++++++++++++---------------
4 files changed, 54 insertions(+), 28 deletions(-)
Modified: trunk/boost/multiprecision/cpp_int/add.hpp
==============================================================================
--- trunk/boost/multiprecision/cpp_int/add.hpp (original)
+++ trunk/boost/multiprecision/cpp_int/add.hpp 2013-02-22 05:37:36 EST (Fri, 22 Feb 2013)
@@ -211,7 +211,7 @@
result.resize(a.size(), a.size());
typename CppInt1::limb_pointer pr = result.limbs();
typename CppInt2::const_limb_pointer pa = a.limbs();
- if(*pa > b)
+ if(*pa >= b)
{
*pr = *pa - b;
if(&result != &a)
Modified: trunk/boost/multiprecision/cpp_int/divide.hpp
==============================================================================
--- trunk/boost/multiprecision/cpp_int/divide.hpp (original)
+++ trunk/boost/multiprecision/cpp_int/divide.hpp 2013-02-22 05:37:36 EST (Fri, 22 Feb 2013)
@@ -116,7 +116,6 @@
if(result)
{
*result = px[0] / py[0];
- result->sign(x.sign() != y.sign());
}
r = px[0] % py[0];
return;
@@ -131,7 +130,6 @@
if(result)
{
*result = a / b;
- result->sign(x.sign() != y.sign());
}
r = a % b;
return;
@@ -452,8 +450,9 @@
const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
{
cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
+ bool s = a.sign() != b.sign();
divide_unsigned_helper(&result, a, b, r);
- result.sign(a.sign() != b.sign());
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
@@ -464,7 +463,9 @@
limb_type& b)
{
cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
+ bool s = a.sign();
divide_unsigned_helper(&result, a, b, r);
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
@@ -475,9 +476,9 @@
signed_limb_type& b)
{
cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> r;
+ bool s = a.sign() != (b < 0);
divide_unsigned_helper(&result, a, static_cast<limb_type>(std::abs(b)), r);
- if(b < 0)
- result.negate();
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
@@ -520,8 +521,9 @@
const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b)
{
+ bool s = a.sign();
divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
- result.sign(a.sign());
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
@@ -530,7 +532,9 @@
cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a, limb_type b)
{
+ bool s = a.sign();
divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, b, result);
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
@@ -540,7 +544,9 @@
const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
signed_limb_type b)
{
+ bool s = a.sign();
divide_unsigned_helper(static_cast<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>* >(0), a, static_cast<limb_type>(std::abs(b)), result);
+ result.sign(s);
}
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
Modified: trunk/boost/multiprecision/cpp_int/misc.hpp
==============================================================================
--- trunk/boost/multiprecision/cpp_int/misc.hpp (original)
+++ trunk/boost/multiprecision/cpp_int/misc.hpp 2013-02-22 05:37:36 EST (Fri, 22 Feb 2013)
@@ -379,9 +379,16 @@
{
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
- if(u.size() == 1)
+ if(u.size() <= 2)
{
- v = integer_gcd_reduce(*u.limbs(), v);
+ if(u.size() == 1)
+ v = integer_gcd_reduce(*u.limbs(), v);
+ else
+ {
+ double_limb_type i;
+ i = u.limbs()[0] | (static_cast<double_limb_type>(u.limbs()[1]) << sizeof(limb_type) * CHAR_BIT);
+ v = static_cast<limb_type>(integer_gcd_reduce(i, static_cast<double_limb_type>(v)));
+ }
break;
}
eval_subtract(u, v);
@@ -431,6 +438,7 @@
if(b.size() == 1)
{
eval_gcd(result, a, *b.limbs());
+ return;
}
int shift;
Modified: trunk/libs/multiprecision/test/test_cpp_int.cpp
==============================================================================
--- trunk/libs/multiprecision/test/test_cpp_int.cpp (original)
+++ trunk/libs/multiprecision/test/test_cpp_int.cpp 2013-02-22 05:37:36 EST (Fri, 22 Feb 2013)
@@ -387,6 +387,37 @@
BOOST_CHECK_EQUAL(q, a);
BOOST_CHECK_EQUAL(r, 1);
}
+ // Bug https://svn.boost.org/trac/boost/ticket/8126:
+ test_type a("-4294967296");
+ test_type b("4294967296");
+ test_type c("-1");
+ a = (a / b);
+ BOOST_CHECK_EQUAL(a, -1);
+ a = -4294967296;
+ a = (a / b) * c;
+ BOOST_CHECK_EQUAL(a, 1);
+ a = -23;
+ b = 23;
+ a = (a / b) * c;
+ BOOST_CHECK_EQUAL(a, 1);
+ a = -23;
+ a = (a / b) / c;
+ BOOST_CHECK_EQUAL(a, 1);
+ a = test_type("-26607734784073568386365259775");
+ b = test_type("8589934592");
+ a = a / b;
+ BOOST_CHECK_EQUAL(a, test_type("-3097548007973652377"));
+ // Bug https://svn.boost.org/trac/boost/ticket/8133:
+ a = test_type("0x12345600012434ffffffffffffffffffffffff");
+ unsigned ui = 0xffffffff;
+ a = a - ui;
+ BOOST_CHECK_EQUAL(a, test_type("0x12345600012434ffffffffffffffff00000000"));
+ a = test_type("0x12345600012434ffffffffffffffffffffffff");
+#ifndef BOOST_NO_LONG_LONG
+ unsigned long long ull = 0xffffffffffffffffuLL;
+ a = a - ull;
+ BOOST_CHECK_EQUAL(a, test_type("0x12345600012434ffffffff0000000000000000"));
+#endif
}
void test()
@@ -470,25 +501,6 @@
}
}
- //
- // Specific bug report tests come last:
- //
- // Bug https://svn.boost.org/trac/boost/ticket/8126:
- test_type a("-4294967296");
- test_type b("4294967296");
- test_type c("-1");
- a = (a / b);
- BOOST_CHECK_EQUAL(a, -1);
- a = -4294967296;
- a = (a / b) * c;
- BOOST_CHECK_EQUAL(a, 1);
- a = -23;
- b = 23;
- a = (a / b) * c;
- BOOST_CHECK_EQUAL(a, 1);
- a = -23;
- a = (a / b) / c;
- BOOST_CHECK_EQUAL(a, 1);
}
};