|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81200 - in sandbox/big_number: boost/multiprecision boost/multiprecision/concepts boost/multiprecision/cpp_int boost/multiprecision/depricated boost/multiprecision/detail libs/multiprecision/performance libs/multiprecision/test
From: john_at_[hidden]
Date: 2012-11-05 07:36:27
Author: johnmaddock
Date: 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
New Revision: 81200
URL: http://svn.boost.org/trac/boost/changeset/81200
Log:
Optimize cpp_int multiplication with precision extension.
Turn off some warnings.
Text files modified:
sandbox/big_number/boost/multiprecision/concepts/mp_number_archetypes.hpp | 1
sandbox/big_number/boost/multiprecision/cpp_int/multiply.hpp | 153 +++++++++++++++++++++++++++++++++++++++
sandbox/big_number/boost/multiprecision/depricated/arithmetic_backend.hpp | 1
sandbox/big_number/boost/multiprecision/detail/default_ops.hpp | 1
sandbox/big_number/boost/multiprecision/detail/number_base.hpp | 7 +
sandbox/big_number/boost/multiprecision/gmp.hpp | 8 +
sandbox/big_number/boost/multiprecision/mpfr.hpp | 1
sandbox/big_number/boost/multiprecision/rational_adapter.hpp | 8 +
sandbox/big_number/boost/multiprecision/tommath.hpp | 1
sandbox/big_number/libs/multiprecision/performance/delaunay_test.cpp | 19 +++-
sandbox/big_number/libs/multiprecision/test/test_mixed_cpp_int.cpp | 7 +
11 files changed, 192 insertions(+), 15 deletions(-)
Modified: sandbox/big_number/boost/multiprecision/concepts/mp_number_archetypes.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/concepts/mp_number_archetypes.hpp (original)
+++ sandbox/big_number/boost/multiprecision/concepts/mp_number_archetypes.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -11,7 +11,6 @@
#include <iomanip>
#include <cmath>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/multiprecision/number.hpp>
#include <boost/math/special_functions/fpclassify.hpp>
#include <boost/mpl/list.hpp>
Modified: sandbox/big_number/boost/multiprecision/cpp_int/multiply.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/cpp_int/multiply.hpp (original)
+++ sandbox/big_number/boost/multiprecision/cpp_int/multiply.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -271,9 +271,7 @@
template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
BOOST_FORCEINLINE typename enable_if_c<
is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
- && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
&& is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
- && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
>::type
eval_multiply(
cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
@@ -283,6 +281,157 @@
result.normalize();
}
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
+BOOST_FORCEINLINE typename enable_if_c<
+ is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
+ >::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
+ const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
+{
+ *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
+ result.sign(a.sign() != b.sign());
+ result.normalize();
+}
+
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
+BOOST_FORCEINLINE typename enable_if_c<
+ is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ >::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
+ const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
+{
+ *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
+ result.normalize();
+}
+
+//
+// Special routines for multiplying two integers to obtain a multiprecision result:
+//
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
+BOOST_FORCEINLINE typename enable_if_c<
+ !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ >::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ signed_double_limb_type a, signed_double_limb_type b)
+{
+ static const signed_double_limb_type mask = ~static_cast<limb_type>(0);
+ static const unsigned limb_bits = sizeof(limb_type) * CHAR_BIT;
+ bool s = false;
+ double_limb_type w, x, y, z;
+ if(a < 0)
+ {
+ a = -a;
+ s = true;
+ }
+ if(b < 0)
+ {
+ b = -b;
+ s = !s;
+ }
+ w = a & mask;
+ x = a >> limb_bits;
+ y = b & mask;
+ z = b >> limb_bits;
+
+ result.resize(4, 4);
+ limb_type* pr = result.limbs();
+
+ double_limb_type carry = w * y;
+ pr[0] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ carry += w * z + x * y;
+ pr[1] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ carry += x * z;
+ pr[2] = static_cast<limb_type>(carry);
+ pr[3] = static_cast<limb_type>(carry >> limb_bits);
+
+ result.sign(s);
+ result.normalize();
+}
+
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
+BOOST_FORCEINLINE typename enable_if_c<
+ !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ >::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ double_limb_type a, double_limb_type b)
+{
+ static const signed_double_limb_type mask = ~static_cast<limb_type>(0);
+ static const unsigned limb_bits = sizeof(limb_type) * CHAR_BIT;
+
+ double_limb_type w, x, y, z;
+ w = a & mask;
+ x = a >> limb_bits;
+ y = b & mask;
+ z = b >> limb_bits;
+
+ result.resize(4, 4);
+ limb_type* pr = result.limbs();
+
+ double_limb_type carry = w * y;
+ pr[0] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ carry += w * z;
+ pr[1] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ pr[2] = static_cast<limb_type>(carry);
+ carry = x * y + pr[1];
+ pr[1] = static_cast<limb_type>(carry);
+ carry >>= limb_bits;
+ carry += pr[2] + x * z;
+ pr[2] = static_cast<limb_type>(carry);
+ pr[3] = static_cast<limb_type>(carry >> limb_bits);
+
+ result.sign(false);
+ result.normalize();
+}
+
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1,
+ unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
+BOOST_FORCEINLINE typename enable_if_c<
+ !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
+ && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
+ && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
+ >::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& a,
+ cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& b)
+{
+ typedef typename boost::multiprecision::detail::canonical<typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type, cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::type canonical_type;
+ eval_multiply(result, static_cast<canonical_type>(*a.limbs()), static_cast<canonical_type>(*b.limbs()));
+ result.sign(a.sign() != b.sign());
+}
+
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class SI>
+BOOST_FORCEINLINE typename enable_if_c<is_signed<SI>::value && (sizeof(SI) <= sizeof(signed_double_limb_type) / 2)>::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ SI a, SI b)
+{
+ result = static_cast<signed_double_limb_type>(a) * static_cast<signed_double_limb_type>(b);
+}
+
+template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class UI>
+BOOST_FORCEINLINE typename enable_if_c<is_unsigned<UI>::value && (sizeof(UI) <= sizeof(signed_double_limb_type) / 2)>::type
+ eval_multiply(
+ cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
+ UI a, UI b)
+{
+ result = static_cast<double_limb_type>(a) * static_cast<double_limb_type>(b);
+}
+
}}} // namespaces
#endif
Modified: sandbox/big_number/boost/multiprecision/depricated/arithmetic_backend.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/depricated/arithmetic_backend.hpp (original)
+++ sandbox/big_number/boost/multiprecision/depricated/arithmetic_backend.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -10,7 +10,6 @@
#include <iomanip>
#include <sstream>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/multiprecision/number.hpp>
namespace boost{
Modified: sandbox/big_number/boost/multiprecision/detail/default_ops.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/detail/default_ops.hpp (original)
+++ sandbox/big_number/boost/multiprecision/detail/default_ops.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -9,7 +9,6 @@
#include <boost/math/policies/error_handling.hpp>
#include <boost/multiprecision/detail/number_base.hpp>
#include <boost/math/special_functions/fpclassify.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/mpl/front.hpp>
#include <boost/cstdint.hpp>
Modified: sandbox/big_number/boost/multiprecision/detail/number_base.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/detail/number_base.hpp (original)
+++ sandbox/big_number/boost/multiprecision/detail/number_base.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -10,7 +10,14 @@
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/decay.hpp>
+#ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable:4307)
+#endif
#include <boost/lexical_cast.hpp>
+#ifdef BOOST_MSVC
+# pragma warning(pop)
+#endif
namespace boost{ namespace multiprecision{
Modified: sandbox/big_number/boost/multiprecision/gmp.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/gmp.hpp (original)
+++ sandbox/big_number/boost/multiprecision/gmp.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -12,8 +12,14 @@
#include <boost/multiprecision/detail/digits.hpp>
#include <boost/math/special_functions/fpclassify.hpp>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
+#ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable:4127)
+#endif
#include <gmp.h>
+#ifdef BOOST_MSVC
+# pragma warning(pop)
+#endif
#include <cmath>
#include <limits>
#include <climits>
Modified: sandbox/big_number/boost/multiprecision/mpfr.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/mpfr.hpp (original)
+++ sandbox/big_number/boost/multiprecision/mpfr.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -10,7 +10,6 @@
#include <boost/multiprecision/gmp.hpp>
#include <boost/math/special_functions/fpclassify.hpp>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/multiprecision/detail/big_lanczos.hpp>
#include <boost/multiprecision/detail/digits.hpp>
#include <mpfr.h>
Modified: sandbox/big_number/boost/multiprecision/rational_adapter.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/rational_adapter.hpp (original)
+++ sandbox/big_number/boost/multiprecision/rational_adapter.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -10,9 +10,15 @@
#include <iomanip>
#include <sstream>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/multiprecision/number.hpp>
+#ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable:4512)
+#endif
#include <boost/rational.hpp>
+#ifdef BOOST_MSVC
+# pragma warning(pop)
+#endif
namespace boost{
namespace multiprecision{
Modified: sandbox/big_number/boost/multiprecision/tommath.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/tommath.hpp (original)
+++ sandbox/big_number/boost/multiprecision/tommath.hpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -11,7 +11,6 @@
#include <boost/multiprecision/detail/integer_ops.hpp>
#include <boost/math/special_functions/fpclassify.hpp>
#include <boost/cstdint.hpp>
-#include <boost/lexical_cast.hpp>
#include <boost/scoped_array.hpp>
#include <tommath.h>
#include <cmath>
Modified: sandbox/big_number/libs/multiprecision/performance/delaunay_test.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/performance/delaunay_test.cpp (original)
+++ sandbox/big_number/libs/multiprecision/performance/delaunay_test.cpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -135,6 +135,12 @@
r *= b;
}
+template <class B, boost::multiprecision::expression_template_option ET, class T>
+BOOST_FORCEINLINE void mul_2n(boost::multiprecision::number<B, ET>& r, const T& a, const T& b)
+{
+ multiply(r, a, b);
+}
+
BOOST_FORCEINLINE void mul_2n(int128_t& r, const boost::int64_t& a, const boost::int64_t& b)
{
r = mult_64x64_to_128(a, b);
@@ -270,10 +276,15 @@
std::cout << "calculating...\n";
do_calc<test_traits<boost::int64_t, boost::int64_t> >("int64_t, int64_t");
- do_calc<test_traits<number<arithmetic_backend<boost::int64_t>, et_off>, number<arithmetic_backend<boost::int64_t>, et_off> > >("arithmetic_backend<int64_t>");
- do_calc<test_traits<boost::int64_t, int128_t> >("int64_t, int128_t");
- do_calc<test_traits<boost::int64_t, int128_t> >("int64_t, int128_t");
- do_calc<test_traits<boost::int64_t, number<cpp_int_backend<128, true, void>, et_on> > >("int64_t, int128_t (ET)");
+ do_calc<test_traits<number<arithmetic_backend<boost::int64_t>, et_off>, number<arithmetic_backend<boost::int64_t>, et_off> > >("arithmetic_backend<int64_t>, arithmetic_backend<int64_t>");
+ do_calc<test_traits<boost::int64_t, number<arithmetic_backend<boost::int64_t>, et_off> > >("int64_t, arithmetic_backend<int64_t>");
+ do_calc<test_traits<number<cpp_int_backend<64, 64, boost::multiprecision::signed_magnitude, boost::multiprecision::unchecked, void>, et_off>, number<cpp_int_backend<64, 64, boost::multiprecision::signed_magnitude, boost::multiprecision::unchecked, void>, et_off> > >("multiprecision::int64_t, multiprecision::int64_t");
+
+ do_calc<test_traits<boost::int64_t, ::int128_t> >("int64_t, int128_t");
+ do_calc<test_traits<boost::int64_t, boost::multiprecision::int128_t> >("int64_t, boost::multiprecision::int128_t");
+ do_calc<test_traits<boost::int64_t, number<cpp_int_backend<128, 128, boost::multiprecision::signed_magnitude, boost::multiprecision::unchecked, void>, et_on> > >("int64_t, int128_t (ET)");
+ do_calc<test_traits<number<cpp_int_backend<64, 64, boost::multiprecision::signed_magnitude, boost::multiprecision::unchecked, void>, et_off>, boost::multiprecision::int128_t > >("multiprecision::int64_t, multiprecision::int128_t");
+
do_calc<test_traits<boost::int64_t, cpp_int> >("int64_t, cpp_int");
do_calc<test_traits<boost::int64_t, number<cpp_int_backend<>, et_off> > >("int64_t, cpp_int (no ET's)");
do_calc<test_traits<boost::int64_t, number<cpp_int_backend<128> > > >("int64_t, cpp_int(128-bit cache)");
Modified: sandbox/big_number/libs/multiprecision/test/test_mixed_cpp_int.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_mixed_cpp_int.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_mixed_cpp_int.cpp 2012-11-05 07:36:25 EST (Mon, 05 Nov 2012)
@@ -73,11 +73,14 @@
test<checked_int512_t, checked_int1024_t>();
test<checked_int256_t, checked_int512_t>();
- test<number<cpp_int_backend<64, 64, signed_magnitude, checked, void>, et_off>, checked_int512_t>();
+ test<number<cpp_int_backend<64, 64, signed_magnitude, checked, void>, et_off>, checked_int128_t>();
+ test<boost::int64_t, checked_int128_t>();
test<checked_uint512_t, checked_uint1024_t>();
test<checked_uint256_t, checked_uint512_t>();
- test<number<cpp_int_backend<64, 64, unsigned_magnitude, checked, void>, et_off>, checked_uint512_t>();
+ test<number<cpp_int_backend<64, 64, unsigned_magnitude, checked, void>, et_off>, checked_uint128_t>();
+ test<boost::uint64_t, checked_int128_t>();
+
return boost::report_errors();
}
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