[Boost-commit] svn:boost r76409 - in sandbox/big_number: boost/multiprecision libs/multiprecision/performance libs/multiprecision/test

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