Subject: [Boost-commit] svn:boost r76409 - in sandbox/big_number: boost/multiprecision libs/multiprecision/performance libs/multiprecision/test
From: john_at_[hidden]
Date: 2012-01-11 06:53:52
Author: johnmaddock
Date: 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
New Revision: 76409
URL: http://svn.boost.org/trac/boost/changeset/76409
Log:
Fix GCC failures and generally improve performance of packed_cpp_int.
Text files modified:
sandbox/big_number/boost/multiprecision/packed_cpp_int.hpp | 107 ++++++++++++++++++++++++---------------
sandbox/big_number/libs/multiprecision/performance/performance_test.cpp | 22 ++++++++
sandbox/big_number/libs/multiprecision/test/Jamfile.v2 | 4
sandbox/big_number/libs/multiprecision/test/packed_int_test.cpp | 26 ---------
sandbox/big_number/libs/multiprecision/test/test_float_io.cpp | 4 +
sandbox/big_number/libs/multiprecision/test/test_int_io.cpp | 4 +
sandbox/big_number/libs/multiprecision/test/test_rational_io.cpp | 4 +
7 files changed, 101 insertions(+), 70 deletions(-)
Modified: sandbox/big_number/boost/multiprecision/packed_cpp_int.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/packed_cpp_int.hpp (original)
+++ sandbox/big_number/boost/multiprecision/packed_cpp_int.hpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -97,7 +97,7 @@
}
packed_cpp_int& operator = (long double a)
{
- BOOST_STATIC_ASSERT(Bits >= std::numeric_limits<long double>::digits);
+ BOOST_STATIC_ASSERT(Bits >= (unsigned)std::numeric_limits<long double>::digits);
using std::frexp;
using std::ldexp;
using std::floor;
@@ -306,10 +306,14 @@
}
void negate()
{
- using default_ops::increment;
- // complement and add 1:
- complement(*this, *this);
- increment(*this);
+ boost::uintmax_t carry = 1;
+ for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; i >= 0; --i)
+ {
+ carry += static_cast<boost::uintmax_t>(~m_value[i]);
+ m_value[i] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ }
+ m_value[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
int compare(const packed_cpp_int& o)const
{
@@ -318,7 +322,7 @@
{
return m_value[0] & sign_bit_mask ? -1 : 1;
}
- for(data_type::size_type i = 0; i < limb_count; ++i)
+ for(typename data_type::size_type i = 0; i < limb_count; ++i)
{
if(m_value[i] != o.data()[i])
{
@@ -345,14 +349,19 @@
template <unsigned Bits, bool Signed>
inline void add(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
+ add(result, result, o);
+}
+template <unsigned Bits, bool Signed>
+inline void add(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& a, const packed_cpp_int<Bits, Signed>& b)
+{
// Addition using modular arithmatic.
// Nothing fancy, just let uintmax_t take the strain:
boost::uintmax_t carry = 0;
for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; i >= 0; --i)
{
- boost::uintmax_t v = static_cast<boost::uintmax_t>(result.data()[i]) + static_cast<boost::uintmax_t>(o.data()[i]) + carry;
- result.data()[i] = static_cast<packed_cpp_int<Bits, Signed>::limb_type>(v);
- carry = v > packed_cpp_int<Bits, Signed>::max_limb_value ? 1 : 0;
+ carry += static_cast<boost::uintmax_t>(a.data()[i]) + static_cast<boost::uintmax_t>(b.data()[i]);
+ result.data()[i] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
@@ -364,9 +373,9 @@
boost::uintmax_t carry = o;
for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; carry && i >= 0; --i)
{
- boost::uintmax_t v = static_cast<boost::uintmax_t>(result.data()[i]) + carry;
- result.data()[i] = static_cast<packed_cpp_int<Bits, Signed>::limb_type>(v);
- carry = v > packed_cpp_int<Bits, Signed>::max_limb_value ? 1 : 0;
+ carry += static_cast<boost::uintmax_t>(result.data()[i]);
+ result.data()[i] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
@@ -381,16 +390,19 @@
template <unsigned Bits, bool Signed>
inline void subtract(packed_cpp_int<Bits, Signed>& result, const boost::uint32_t& o)
{
- if(o)
- {
- packed_cpp_int<Bits, Signed> t;
- t.data()[packed_cpp_int<Bits, Signed>::limb_count - 1] = ~o + 1;
- for(int i = packed_cpp_int<Bits, Signed>::limb_count - 2; i >= 0; --i)
- {
- t.data()[i] = packed_cpp_int<Bits, Signed>::max_limb_value;
- }
- add(result, t);
+ // Subtract using modular arithmatic.
+ // This is the same code as for addition, with the twist that we negate o "on the fly":
+ boost::uintmax_t carry = static_cast<boost::uintmax_t>(result.data()[packed_cpp_int<Bits, Signed>::limb_count - 1])
+ + 1uLL + static_cast<boost::uintmax_t>(~o);
+ result.data()[packed_cpp_int<Bits, Signed>::limb_count - 1] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
+ for(int i = packed_cpp_int<Bits, Signed>::limb_count - 2; i >= 0; --i)
+ {
+ carry += static_cast<boost::uintmax_t>(result.data()[i]) + 0xFFFFFFFF;
+ result.data()[i] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
+ result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
template <unsigned Bits, bool Signed>
inline void subtract(packed_cpp_int<Bits, Signed>& result, const boost::int32_t& o)
@@ -418,10 +430,21 @@
template <unsigned Bits, bool Signed>
inline void subtract(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
- // Negate and add:
- packed_cpp_int<Bits, Signed> t(o);
- t.negate();
- add(result, t);
+ subtract(result, result, o);
+}
+template <unsigned Bits, bool Signed>
+inline void subtract(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& a, const packed_cpp_int<Bits, Signed>& b)
+{
+ // Subtract using modular arithmatic.
+ // This is the same code as for addition, with the twist that we negate b "on the fly":
+ boost::uintmax_t carry = 1;
+ for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; i >= 0; --i)
+ {
+ carry += static_cast<boost::uintmax_t>(a.data()[i]) + static_cast<boost::uintmax_t>(~b.data()[i]);
+ result.data()[i] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
+ }
+ result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
template <unsigned Bits, bool Signed>
inline void multiply(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& a, const packed_cpp_int<Bits, Signed>& b)
@@ -447,10 +470,10 @@
{
for(int j = packed_cpp_int<Bits, Signed>::limb_count - 1; j >= static_cast<int>(packed_cpp_int<Bits, Signed>::limb_count) - i - 1; --j)
{
- boost::uintmax_t v = static_cast<boost::uintmax_t>(a.data()[i]) * static_cast<boost::uintmax_t>(b.data()[j]) + carry;
- v += result.data()[i + j + 1 - packed_cpp_int<Bits, Signed>::limb_count];
- result.data()[i + j + 1 - packed_cpp_int<Bits, Signed>::limb_count] = static_cast<packed_cpp_int<Bits, Signed>::limb_type>(v);
- carry = v >> sizeof(packed_cpp_int<Bits, Signed>::limb_type) * CHAR_BIT;
+ carry += static_cast<boost::uintmax_t>(a.data()[i]) * static_cast<boost::uintmax_t>(b.data()[j]);
+ carry += result.data()[i + j + 1 - packed_cpp_int<Bits, Signed>::limb_count];
+ result.data()[i + j + 1 - packed_cpp_int<Bits, Signed>::limb_count] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
carry = 0;
}
@@ -469,9 +492,9 @@
boost::uintmax_t carry = 0;
for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; i >= 0; --i)
{
- boost::uintmax_t v = static_cast<boost::uintmax_t>(result.data()[i]) * static_cast<boost::uintmax_t>(a) + carry;
- result.data()[i] = static_cast<packed_cpp_int<Bits, Signed>::limb_type>(v);
- carry = v >> sizeof(packed_cpp_int<Bits, Signed>::limb_type) * CHAR_BIT;
+ carry += static_cast<boost::uintmax_t>(result.data()[i]) * static_cast<boost::uintmax_t>(a);
+ result.data()[i] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
@@ -487,6 +510,7 @@
}
}
+/*
template <unsigned Bits, bool Signed>
boost::uint32_t bitcount(const packed_cpp_int<Bits, Signed>& a)
{
@@ -504,7 +528,6 @@
}
return count;
}
-/*
template <unsigned Bits, bool Signed>
void divide_unsigned_helper(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& x, const packed_cpp_int<Bits, Signed>& y, packed_cpp_int<Bits, Signed>& r)
{
@@ -722,9 +745,9 @@
t.data()[i] = 0;
for(int i = packed_cpp_int<Bits, Signed>::limb_count - 1; i >= static_cast<int>(shift); --i)
{
- boost::uintmax_t v = static_cast<boost::uintmax_t>(y.data()[i]) * static_cast<boost::uintmax_t>(guess) + carry;
- t.data()[i - shift] = static_cast<packed_cpp_int<Bits, Signed>::limb_type>(v);
- carry = v >> sizeof(packed_cpp_int<Bits, Signed>::limb_type) * CHAR_BIT;
+ carry += static_cast<boost::uintmax_t>(y.data()[i]) * static_cast<boost::uintmax_t>(guess);
+ t.data()[i - shift] = static_cast<typename packed_cpp_int<Bits, Signed>::limb_type>(carry);
+ carry >>= packed_cpp_int<Bits, Signed>::limb_bits;
}
t.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
//
@@ -837,26 +860,26 @@
template <unsigned Bits, bool Signed>
inline void bitwise_and(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
- for(packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
+ for(typename packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
result.data()[i] &= o.data()[i];
}
template <unsigned Bits, bool Signed>
inline void bitwise_or(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
- for(packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
+ for(typename packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
result.data()[i] |= o.data()[i];
}
template <unsigned Bits, bool Signed>
inline void bitwise_xor(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
- for(packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
+ for(typename packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
result.data()[i] ^= o.data()[i];
result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
template <unsigned Bits, bool Signed>
inline void complement(packed_cpp_int<Bits, Signed>& result, const packed_cpp_int<Bits, Signed>& o)
{
- for(packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
+ for(typename packed_cpp_int<Bits, Signed>::data_type::size_type i = 0; i < packed_cpp_int<Bits, Signed>::limb_count; ++i)
result.data()[i] = ~o.data()[i];
result.data()[0] &= packed_cpp_int<Bits, Signed>::upper_limb_mask;
}
@@ -1073,8 +1096,8 @@
};
template <unsigned Bits, bool Signed>
-typename numeric_limits<boost::multiprecision::mp_number<boost::multiprecision::packed_cpp_int<Bits, Signed> > >::initializer
- typename numeric_limits<boost::multiprecision::mp_number<boost::multiprecision::packed_cpp_int<Bits, Signed> > >::init;
+typename numeric_limits<boost::multiprecision::mp_number<boost::multiprecision::packed_cpp_int<Bits, Signed> > >::initializer const
+ numeric_limits<boost::multiprecision::mp_number<boost::multiprecision::packed_cpp_int<Bits, Signed> > >::init;
}
#endif
Modified: sandbox/big_number/libs/multiprecision/performance/performance_test.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/performance/performance_test.cpp (original)
+++ sandbox/big_number/libs/multiprecision/performance/performance_test.cpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -109,6 +109,26 @@
}
return boost::chrono::duration_cast<boost::chrono::duration<double> >(w.elapsed()).count();
}
+ double test_add_int()
+ {
+ stopwatch<boost::chrono::high_resolution_clock> w;
+ for(unsigned i = 0; i < 1000; ++i)
+ {
+ for(unsigned i = 0; i < b.size(); ++i)
+ a[i] = b[i] + 1;
+ }
+ return boost::chrono::duration_cast<boost::chrono::duration<double> >(w.elapsed()).count();
+ }
+ double test_subtract_int()
+ {
+ stopwatch<boost::chrono::high_resolution_clock> w;
+ for(unsigned i = 0; i < 1000; ++i)
+ {
+ for(unsigned i = 0; i < b.size(); ++i)
+ a[i] = b[i] - 1;
+ }
+ return boost::chrono::duration_cast<boost::chrono::duration<double> >(w.elapsed()).count();
+ }
double test_multiply()
{
stopwatch<boost::chrono::high_resolution_clock> w;
@@ -296,6 +316,8 @@
tester<Number, boost::multiprecision::number_category<Number>::value> t;
std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "+" << t.test_add() << std::endl;
std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "-" << t.test_subtract() << std::endl;
+ std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "+ (int)" << t.test_add_int() << std::endl;
+ std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "- (int)" << t.test_subtract_int() << std::endl;
std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "*" << t.test_multiply() << std::endl;
std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "/" << t.test_divide() << std::endl;
std::cout << std::left << std::setw(15) << type << std::setw(10) << precision << std::setw(5) << "str" << t.test_str() << std::endl;
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-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -600,8 +600,8 @@
: # input files
: # requirements
[ check-target-builds ../config//has_gmp : : <build>no ]
- release # otherwise runtime is too slow!!
- : packed_int_test.cpp ;
+ release # otherwise runtime is too slow!!
+ ;
run test_rational_io.cpp $(TOMMATH)
: # command line
Modified: sandbox/big_number/libs/multiprecision/test/packed_int_test.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/packed_int_test.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/packed_int_test.cpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -11,36 +11,12 @@
# define _SCL_SECURE_NO_WARNINGS
#endif
-#define BOOST_CHRONO_HEADER_ONLY
-
#include <boost/multiprecision/gmp.hpp>
#include <boost/multiprecision/packed_cpp_int.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
-#include <boost/chrono.hpp>
#include "test.hpp"
-template <class Clock>
-struct stopwatch
-{
- typedef typename Clock::duration duration;
- stopwatch()
- {
- m_start = Clock::now();
- }
- duration elapsed()
- {
- return Clock::now() - m_start;
- }
- void reset()
- {
- m_start = Clock::now();
- }
-
-private:
- typename Clock::time_point m_start;
-};
-
template <class T>
T generate_random(unsigned bits_wanted)
{
@@ -79,7 +55,6 @@
{
using namespace boost::multiprecision;
typedef mp_number<packed_cpp_int<1024, true> > packed_type;
- stopwatch<boost::chrono::high_resolution_clock> w;
unsigned last_error_count = 0;
for(int i = 0; i < 1000; ++i)
{
@@ -143,7 +118,6 @@
std::cout << "a1%d1 = " << a1%d1 << std::endl;
}
}
- std::cout << w.elapsed() << std::endl;
return boost::report_errors();
}
Modified: sandbox/big_number/libs/multiprecision/test/test_float_io.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_float_io.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_float_io.cpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -212,7 +212,11 @@
void do_round_trip(const T& val, std::ios_base::fmtflags f)
{
std::stringstream ss;
+#ifndef BOOST_NO_NUMERIC_LIMITS_LOWEST
ss << std::setprecision(std::numeric_limits<T>::max_digits10);
+#else
+ ss << std::setprecision(std::numeric_limits<T>::digits10 + 5);
+#endif
ss.flags(f);
ss << val;
T new_val = ss.str();
Modified: sandbox/big_number/libs/multiprecision/test/test_int_io.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_int_io.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_int_io.cpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -60,7 +60,11 @@
void do_round_trip(const T& val, std::ios_base::fmtflags f)
{
std::stringstream ss;
+#ifndef BOOST_NO_NUMERIC_LIMITS_LOWEST
ss << std::setprecision(std::numeric_limits<T>::max_digits10);
+#else
+ ss << std::setprecision(std::numeric_limits<T>::digits10 + 5);
+#endif
ss.flags(f);
ss << val;
T new_val = ss.str();
Modified: sandbox/big_number/libs/multiprecision/test/test_rational_io.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_rational_io.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_rational_io.cpp 2012-01-11 06:53:49 EST (Wed, 11 Jan 2012)
@@ -64,7 +64,11 @@
void do_round_trip(const T& val, std::ios_base::fmtflags f, const boost::mpl::true_&)
{
std::stringstream ss;
+#ifndef BOOST_NO_NUMERIC_LIMITS_LOWEST
ss << std::setprecision(std::numeric_limits<T>::max_digits10);
+#else
+ ss << std::setprecision(std::numeric_limits<T>::digits10 + 5);
+#endif
ss.flags(f);
ss << val;
T new_val = ss.str();