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

Subject: [Boost-commit] svn:boost r77303 - in sandbox/big_number: boost/multiprecision libs/multiprecision/performance libs/multiprecision/test
From: john_at_[hidden]
Date: 2012-03-11 12:43:33

Author: johnmaddock
Date: 2012-03-11 12:43:31 EDT (Sun, 11 Mar 2012)
New Revision: 77303
URL: http://svn.boost.org/trac/boost/changeset/77303

Log:
Fix several division algorithm bugs.
Add cpp_rational to performance tests.
Add modular arithmetic test to test cases.
Text files modified: 
   sandbox/big_number/boost/multiprecision/cpp_int.hpp                     |    39 ++++++++++++++++++++++++++------------- 
   sandbox/big_number/libs/multiprecision/performance/performance_test.cpp |    15 ++++++++-------                         
   sandbox/big_number/libs/multiprecision/test/test_cpp_int.cpp            |    18 ++++++++++++++++++                      
   3 files changed, 52 insertions(+), 20 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-03-11 12:43:31 EDT (Sun, 11 Mar 2012)
@@ -1061,9 +1061,9 @@
 
    double_limb_type carry = 0;
    std::memset(pr, 0, result.size() * sizeof(limb_type));
-   unsigned inner_limit = result.size() - as;
    for(unsigned i = 0; i < as; ++i)
    {
+      unsigned inner_limit = (std::min)(result.size() - i, b.size());
       for(unsigned j = 0; j < inner_limit; ++j)
       {
          BOOST_ASSERT(i+j < result.size());
@@ -1262,10 +1262,6 @@
    do
    {
       //
-      // Update r_order, this can't run past the end as r must be non-zero at this point:
-      //
-      r_order = r.size() - 1;
-      //
       // Calculate our best guess for how many times y divides into r:
       //
       limb_type guess;
@@ -1329,6 +1325,7 @@
       //
       double_limb_type carry = 0;
       t.resize(y.size() + shift + 1);
+      bool truncated_t = !cpp_int_backend<MinBits, Signed, Allocator>::variable && (t.size() != y.size() + shift + 1);
       typename cpp_int_backend<MinBits, Signed, Allocator>::limb_pointer pt = t.limbs();
       for(unsigned i = 0; i < shift; ++i)
          pt[i] = 0;
@@ -1338,11 +1335,11 @@
          pt[i + shift] = static_cast<limb_type>(carry);
          carry >>= cpp_int_backend<MinBits, Signed, Allocator>::limb_bits;
       }
-      if(carry)
+      if(carry && !truncated_t)
       {
          pt[t.size() - 1] = static_cast<limb_type>(carry);
       }
-      else
+      else if(!truncated_t)
       {
          t.resize(t.size() - 1);
       }
@@ -1365,15 +1362,21 @@
          while(pr[result.size() - 1] == 0)
             result.resize(result.size() - 1);
       }
+      //
+      // Update r_order:
+      //
+      r_order = r.size() - 1;
+      if(r_order < y_order)
+         break;
    }
-   // Termination condition is really just a check that r > y, but with two common
-   // short-circuit cases handled first:
-   while((r_order > y_order) || (prem[r_order] > py[y_order]) || (r.compare_unsigned(y) > 0));
+   // Termination condition is really just a check that r > y, but with a common
+   // short-circuit case handled first:
+   while((r_order > y_order) || (r.compare_unsigned(y) >= 0));
 
    //
    // We now just have to normalise the result:
    //
-   if(r_neg)
+   if(r_neg && get_sign(r))
    {
       // We have one too many in the result:
       decrement(result);
@@ -1480,19 +1483,29 @@
          --r_order;
          pr[r_order] = static_cast<limb_type>(b);
          pres[r_order] = static_cast<limb_type>(a / y);
+         if(r_order && pr[r_order] == 0)
+         {
+            --r_order;  // No remainder, division was exact.
+            r.resize(r.size() - 1);
+         }
       }
       else
       {
          pres[r_order] = pr[r_order] / y;
          pr[r_order] %= y;
+         if(r_order && pr[r_order] == 0)
+         {
+            --r_order;  // No remainder, division was exact.
+            r.resize(r.size() - 1);
+         }
       }
    }
    // Termination condition is really just a check that r > y, but with two common
    // short-circuit cases handled first:
    while(r_order || (pr[r_order] > y));
 
-   if(pres[result.size() - 1] == 0)
-      result.resize(result.size() - 1);
+   result.normalize();
+   r.normalize();
 
    result.sign(x.sign());
    r.sign(x.sign());

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-03-11 12:43:31 EDT (Sun, 11 Mar 2012)
@@ -12,7 +12,7 @@
 #if !defined(TEST_MPF) && !defined(TEST_MPZ) && \
    !defined(TEST_CPP_DEC_FLOAT) && !defined(TEST_MPFR) && !defined(TEST_MPQ) \
    && !defined(TEST_TOMMATH) && !defined(TEST_TOMMATH_BOOST_RATIONAL) && !defined(TEST_MPZ_BOOST_RATIONAL)\
-   && !defined(TEST_FIXED_INT) && !defined(TEST_CPP_INT)
+   && !defined(TEST_FIXED_INT) && !defined(TEST_CPP_INT) && !defined(TEST_CPP_INT_RATIONAL)
 #  define TEST_MPF
 #  define TEST_MPZ
 #  define TEST_MPQ
@@ -22,6 +22,7 @@
 #  define TEST_TOMMATH
 #  define TEST_FIXED_INT
 #  define TEST_CPP_INT
+#  define TEST_CPP_INT_RATIONAL
 
 #ifdef _MSC_VER
 #pragma message("CAUTION!!: No backend type specified so testing everything.... this will take some time!!")
@@ -575,14 +576,12 @@
    test<boost::multiprecision::mpf_float_500>("gmp_float", 500);
 #endif
 #ifdef TEST_MPZ
-   test<boost::multiprecision::mpz_int>("gmp_int", 64);
    test<boost::multiprecision::mpz_int>("gmp_int", 128);
    test<boost::multiprecision::mpz_int>("gmp_int", 256);
    test<boost::multiprecision::mpz_int>("gmp_int", 512);
    test<boost::multiprecision::mpz_int>("gmp_int", 1024);
 #endif
 #ifdef TEST_CPP_INT
-   test<boost::multiprecision::cpp_int>("cpp_int", 64);
    test<boost::multiprecision::cpp_int>("cpp_int", 128);
    test<boost::multiprecision::cpp_int>("cpp_int", 256);
    test<boost::multiprecision::cpp_int>("cpp_int", 512);
@@ -593,15 +592,19 @@
    test<boost::multiprecision::mp_number<boost::multiprecision::cpp_int_backend<512, true, void> > >("cpp_int(fixed)", 512);
    test<boost::multiprecision::mp_number<boost::multiprecision::cpp_int_backend<1024, true, void> > >("cpp_int(fixed)", 1024);
 #endif
+#ifdef TEST_CPP_INT_RATIONAL
+   test<boost::multiprecision::cpp_rational>("cpp_rational", 128);
+   test<boost::multiprecision::cpp_rational>("cpp_rational", 256);
+   test<boost::multiprecision::cpp_rational>("cpp_rational", 512);
+   test<boost::multiprecision::cpp_rational>("cpp_rational", 1024);
+#endif
 #ifdef TEST_MPQ
-   test<boost::multiprecision::mpq_rational>("mpq_rational", 64);
    test<boost::multiprecision::mpq_rational>("mpq_rational", 128);
    test<boost::multiprecision::mpq_rational>("mpq_rational", 256);
    test<boost::multiprecision::mpq_rational>("mpq_rational", 512);
    test<boost::multiprecision::mpq_rational>("mpq_rational", 1024);
 #endif
 #ifdef TEST_TOMMATH
-   test<boost::multiprecision::mp_int>("tommath_int", 64);
    test<boost::multiprecision::mp_int>("tommath_int", 128);
    test<boost::multiprecision::mp_int>("tommath_int", 256);
    test<boost::multiprecision::mp_int>("tommath_int", 512);
@@ -610,7 +613,6 @@
    //
    // These are actually too slow to test!!!
    //
-   test<boost::multiprecision::mp_rational>("mp_rational", 64);
    test<boost::multiprecision::mp_rational>("mp_rational", 128);
    test<boost::multiprecision::mp_rational>("mp_rational", 256);
    test<boost::multiprecision::mp_rational>("mp_rational", 512);
@@ -618,7 +620,6 @@
    */
 #endif
 #ifdef TEST_FIXED_INT
-   test<boost::multiprecision::mp_number<boost::multiprecision::fixed_int<64, true> > >("fixed_int", 64);
    test<boost::multiprecision::mp_int128_t>("fixed_int", 128);
    test<boost::multiprecision::mp_int256_t>("fixed_int", 256);
    test<boost::multiprecision::mp_int512_t>("fixed_int", 512);

Modified: sandbox/big_number/libs/multiprecision/test/test_cpp_int.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_cpp_int.cpp	(original)
+++ sandbox/big_number/libs/multiprecision/test/test_cpp_int.cpp	2012-03-11 12:43:31 EDT (Sun, 11 Mar 2012)
@@ -137,6 +137,24 @@
       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, -d)).str(), test_type(lcm(-c1, -d1)).str());
       BOOST_CHECK_EQUAL(mpz_int(gcd(a, -b)).str(), test_type(gcd(a1, -b1)).str());
       BOOST_CHECK_EQUAL(mpz_int(lcm(c, -d)).str(), test_type(lcm(c1, -d1)).str());
+
+      if(std::numeric_limits<test_type>::is_modulo)
+      {
+         static mpz_int m = mpz_int(1) << std::numeric_limits<test_type>::digits;
+         mpz_int t(a);
+         test_type t1(a1);
+         for(unsigned i = 0; i < 10; ++i)
+         {
+            t *= a;
+            t %= m;
+            t += a;
+            t %= m;
+            t1 *= a1;
+            t1 += a1;
+         }
+         BOOST_CHECK_EQUAL(t.str(), t1.str());
+      }
+
       if(last_error_count != boost::detail::test_errors())
       {
          last_error_count = boost::detail::test_errors();