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