[Boost-commit] svn:boost r49503 - in sandbox/mp_math: boost/mp_math/mp_int boost/mp_math/mp_int/detail libs/mp_math/test

Subject: [Boost-commit] svn:boost r49503 - in sandbox/mp_math: boost/mp_math/mp_int boost/mp_math/mp_int/detail libs/mp_math/test
From: baraclese_at_[hidden]
Date: 2008-10-31 19:37:03

Author: baraclese
Date: 2008-10-31 19:37:02 EDT (Fri, 31 Oct 2008)
New Revision: 49503
URL: http://svn.boost.org/trac/boost/changeset/49503

Log:
* added <limits> include to traits.hpp
* <boost/mp_math/mp_int/detail/primitive_ops.hpp>:
  - improved performance of comba_mul and comba_sqr slightly
  - minor stylistic changes

Text files modified: 
   sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp |   133 +++++++++++++++++++++------------------ 
   sandbox/mp_math/boost/mp_math/mp_int/traits.hpp               |     1                                         
   sandbox/mp_math/libs/mp_math/test/mul.cpp                     |     2                                         
   3 files changed, 72 insertions(+), 64 deletions(-)

Modified: sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp	(original)
+++ sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp	2008-10-31 19:37:02 EDT (Fri, 31 Oct 2008)
@@ -86,23 +86,23 @@
                                       digit_type x);
 
   // z = x * y
-  static void classic_mul(digit_type* z, const digit_type* x, size_type x_size,
-                                         const digit_type* y, size_type y_size);
+  static void classic_mul(digit_type* z, const digit_type* x, size_type xlen,
+                                         const digit_type* y, size_type ylen);
 
-  // z = x * y; precondition: x_size >= y_size
-  static void comba_mul(digit_type* z, const digit_type* x, size_type x_size,
-                                       const digit_type* y, size_type y_size);
+  // z = x * y; precondition: xlen >= ylen
+  static void comba_mul(digit_type* z, const digit_type* x, size_type xlen,
+                                       const digit_type* y, size_type ylen);
 
   // z = x * y; for numbers of the same size
   static void comba_mul(digit_type* z,
                         const digit_type* x,
-                        const digit_type* y, size_type xy_size);
-  
+                        const digit_type* y, size_type xylen);
+
   // SQR ------------------------------------
 
   // z = x * x;
-  static void comba_sqr(digit_type* z, const digit_type* x, size_type x_size);
-  
+  static void comba_sqr(digit_type* z, const digit_type* x, size_type xlen);
+
   // MADD ------------------------------------
 
   // z = w * x + y
@@ -300,14 +300,14 @@
 template<typename D, typename W, typename S>
 void
 basic_primitive_ops<D,W,S>::classic_mul(
-    digit_type* z, const digit_type* x, size_type x_size,
-                   const digit_type* y, size_type y_size)
+    digit_type* z, const digit_type* x, size_type xlen,
+                   const digit_type* y, size_type ylen)
 {
   // phase 1
   word_type tmp = static_cast<word_type>(x[0]) * static_cast<word_type>(y[0]);
   z[0] = static_cast<digit_type>(tmp);
   
-  for (size_type i = 1; i < x_size; ++i)
+  for (size_type i = 1; i < xlen; ++i)
   {
     tmp = (tmp >> digit_bits)
         + static_cast<word_type>(x[i])
@@ -316,17 +316,17 @@
   }
   
   tmp >>= digit_bits;
-  z[x_size] = static_cast<digit_type>(tmp);
+  z[xlen] = static_cast<digit_type>(tmp);
   
   // phase 2
-  for (size_type i = 1; i < y_size; ++i)
+  for (size_type i = 1; i < ylen; ++i)
   {
     tmp = static_cast<word_type>(y[i])
         * static_cast<word_type>(x[0])
         + static_cast<word_type>(z[i]);
     z[i] = static_cast<digit_type>(tmp);
     
-    for (size_type j = 1; j < x_size; ++j)
+    for (size_type j = 1; j < xlen; ++j)
     {
       tmp = (tmp >> digit_bits)
           + static_cast<word_type>(y[i]) * static_cast<word_type>(x[j])
@@ -335,7 +335,7 @@
     }
     
     tmp >>= digit_bits;
-    z[i + x_size] = static_cast<digit_type>(tmp);
+    z[i + xlen] = static_cast<digit_type>(tmp);
   }
 }
 
@@ -357,68 +357,69 @@
 // operator *= (). Just check if (smaller number).used_ >= overflow_count.
 template<typename D, typename W, typename S>
 void
-basic_primitive_ops<D,W,S>::comba_mul(
-    digit_type* z, const digit_type* x, size_type x_size,
-                   const digit_type* y, size_type y_size)
+basic_primitive_ops<D,W,S>::comba_mul(digit_type* z,
+                                      const digit_type* x, size_type xlen,
+                                      const digit_type* y, size_type ylen)
 {
-  assert(x_size >= y_size);
-
-  const size_type k = x_size + y_size;
+  assert(xlen >= ylen);
 
-  word_type acc = 0;  // accumulator in each column
+  word_type acc = 0;  // accumulator for each column
   word_type carry = 0;
   
   // phase 1
-  for (size_type i = 0; i < y_size; ++i)
+  for (size_type i = 0; i < ylen; ++i)
   {
+    const digit_type* a = x;
+    const digit_type* b = y + i;
+
     for (size_type j = 0; j <= i; ++j)
     {
-      const word_type r = static_cast<word_type>(y[j])
-                        * static_cast<word_type>(x[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a++) * static_cast<word_type>(*b--);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc  = static_cast<digit_type>(carry);
     carry >>= digit_bits;
   }
-  
+
   // phase 2
-  for (size_type i = 0; i < x_size - y_size; ++i)
+  for (size_type i = 0; i < xlen - ylen; ++i)
   {
-    size_type j = 0;
-    size_type m = y_size;
-    while (j < y_size)
+    const digit_type* a = x + ylen + i;
+    const digit_type* b = y;
+
+    for (size_type j = 0; j < ylen; ++j)
     {
-      const word_type r = static_cast<word_type>(y[j])
-                        * static_cast<word_type>(x[m+i]);
-      acc += r;
+      acc += static_cast<word_type>(*a--) * static_cast<word_type>(*b++);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
-      ++j; --m;
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc = static_cast<digit_type>(carry);
     carry >>= digit_bits;
   }
   
   // phase 3
-  for (size_type i = x_size; i < k - 1; ++i)
+  for (size_type i = 0; i < ylen - 1; ++i)
   {
-    for (size_type j = y_size - (k - i - 1); j < y_size; ++j)
+    const digit_type* a = x + xlen - 1;
+    const digit_type* b = y + i + 1;
+
+    for (size_type j = i + 1; j < ylen; ++j)
     {
-      const word_type r = static_cast<word_type>(y[j])
-                        * static_cast<word_type>(x[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a--) * static_cast<word_type>(*b++);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc  = static_cast<digit_type>(carry);
     carry >>= digit_bits;
   }
-  
+
   *z = static_cast<digit_type>(acc);
 }
 
@@ -426,38 +427,42 @@
 void
 basic_primitive_ops<D,W,S>::comba_mul(digit_type* z,
                                       const digit_type* x,
-                                      const digit_type* y, size_type xy_size)
+                                      const digit_type* y, size_type xylen)
 {
   word_type acc = 0;  // accumulator for each column
   word_type carry = 0;
 
   // phase 1
-  for (size_type i = 0; i < xy_size; ++i)
+  for (size_type i = 0; i < xylen; ++i)
   {
+    const digit_type* a = x;
+    const digit_type* b = y + i;
+
     for (size_type j = 0; j <= i; ++j)
     {
-      const word_type r = static_cast<word_type>(x[j])
-                        * static_cast<word_type>(y[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a++) * static_cast<word_type>(*b--);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc = static_cast<digit_type>(carry);
     carry >>= digit_bits;
   }
 
   // phase 2
-  for (size_type i = xy_size; i < 2 * xy_size - 1; ++i)
+  for (size_type i = 1; i < xylen; ++i)
   {
-    for (size_type j = i - xy_size + 1; j < xy_size; ++j)
+    const digit_type* a = y + xylen - 1;
+    const digit_type* b = x + i;
+
+    for (size_type j = 0; j < xylen - i; ++j)
     {
-      const word_type r = static_cast<word_type>(x[j])
-                        * static_cast<word_type>(y[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a--) * static_cast<word_type>(*b++);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc = static_cast<digit_type>(carry);
     carry >>= digit_bits;
@@ -470,38 +475,42 @@
 void
 basic_primitive_ops<D,W,S>::comba_sqr(digit_type* z,
                                       const digit_type* x,
-                                      size_type x_size)
+                                      size_type xlen)
 {
   word_type acc = 0;  // accumulator for each column
   word_type carry = 0;
 
   // phase 1
-  for (size_type i = 0; i < x_size; ++i)
+  for (size_type i = 0; i < xlen; ++i)
   {
+    const digit_type* a = x;
+    const digit_type* b = x + i;
+
     for (size_type j = 0; j <= i; ++j)
     {
-      const word_type r = static_cast<word_type>(x[j])
-                        * static_cast<word_type>(x[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a++) * static_cast<word_type>(*b--);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc = static_cast<digit_type>(carry);
     carry >>= digit_bits;
   }
 
   // phase 2
-  for (size_type i = x_size; i < 2 * x_size - 1; ++i)
+  for (size_type i = 1; i < xlen; ++i)
   {
-    for (size_type j = i - x_size + 1; j < x_size; ++j)
+    const digit_type* a = x + xlen - 1;
+    const digit_type* b = x + i;
+
+    for (size_type j = 0; j < xlen - i; ++j)
     {
-      const word_type r = static_cast<word_type>(x[j])
-                        * static_cast<word_type>(x[i-j]);
-      acc += r;
+      acc += static_cast<word_type>(*a--) * static_cast<word_type>(*b++);
       carry += acc >> digit_bits;
       acc = static_cast<digit_type>(acc);
     }
+
     *z++ = static_cast<digit_type>(acc);
     acc = static_cast<digit_type>(carry);
     carry >>= digit_bits;

Modified: sandbox/mp_math/boost/mp_math/mp_int/traits.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/traits.hpp	(original)
+++ sandbox/mp_math/boost/mp_math/mp_int/traits.hpp	2008-10-31 19:37:02 EDT (Fri, 31 Oct 2008)
@@ -7,6 +7,7 @@
 #define BOOST_MP_MATH_MP_INT_TRAITS_HPP
 
 #include <cstddef> // size_t
+#include <limits>
 #include <boost/config.hpp>
 #include <boost/static_assert.hpp>
 #include <boost/mpl/back.hpp>

Modified: sandbox/mp_math/libs/mp_math/test/mul.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/test/mul.cpp	(original)
+++ sandbox/mp_math/libs/mp_math/test/mul.cpp	2008-10-31 19:37:02 EDT (Fri, 31 Oct 2008)
@@ -47,7 +47,6 @@
   BOOST_CHECK_EQUAL(z, "43076328327684465744675616648356768900793087398990591539995027544295");
 }
 
-
 BOOST_AUTO_TEST_CASE_TEMPLATE(mul6, mp_int_type, mp_int_types)
 {
   // this tests karatsuba multiplication for 8, 16 and 32 bit digit_type
@@ -365,4 +364,3 @@
   BOOST_CHECK_EQUAL(z, w);
 }
 
-