Boost logo

Boost-Commit :

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


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk