Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77471 - in sandbox/big_number: boost/multiprecision libs/multiprecision/doc libs/multiprecision/doc/html libs/multiprecision/doc/html/boost_multiprecision/perf libs/multiprecision/doc/html/boost_multiprecision/ref libs/multiprecision/doc/html/boost_multiprecision/tut libs/multiprecision/example libs/multiprecision/performance libs/multiprecision/test
From: john_at_[hidden]
Date: 2012-03-22 06:29:33

Next message: joel_at_[hidden]: "[Boost-commit] svn:boost r77472 - trunk/boost/fusion/include"
Previous message: pbristow_at_[hidden]: "[Boost-commit] svn:boost r77470 - trunk/libs/math/test"

Author: johnmaddock
Date: 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
New Revision: 77471
URL: http://svn.boost.org/trac/boost/changeset/77471

Log:
Disable expression templates for fixed precision types.
Restrict integer functions to integer types.
Improve Miller Rabin performance by filtering out small primes etc.
Improve Miller Rabin tests.
Change mp_int to tom_int to avoid conflict with global ::mp_Int type.
Text files modified:
   sandbox/big_number/boost/multiprecision/cpp_int.hpp | 16
   sandbox/big_number/boost/multiprecision/integer_ops.hpp | 38 ++++
   sandbox/big_number/boost/multiprecision/miller_rabin.hpp | 77 +++++++-
   sandbox/big_number/boost/multiprecision/tommath.hpp | 10
   sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/perf/int_real_world.html | 132 +--------------
   sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/ref/mp_number.html | 48 +++++
   sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/ints.html | 331 ++++++++++++++++++++-------------------
   sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/rational.html | 18 +-
   sandbox/big_number/libs/multiprecision/doc/html/index.html | 2
   sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk | 226 +++++++++++++++-----------
   sandbox/big_number/libs/multiprecision/example/tommath_snips.cpp | 6
   sandbox/big_number/libs/multiprecision/performance/miller_rabin_performance.cpp | 4
   sandbox/big_number/libs/multiprecision/performance/performance_test.cpp | 16
   sandbox/big_number/libs/multiprecision/test/test_arithmetic.cpp | 17 +
   sandbox/big_number/libs/multiprecision/test/test_int_io.cpp | 2
   sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp | 12 +
   sandbox/big_number/libs/multiprecision/test/test_numeric_limits.cpp | 2
   sandbox/big_number/libs/multiprecision/test/test_rational_io.cpp | 4
   18 files changed, 518 insertions(+), 443 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-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -2206,16 +2206,16 @@
typedef mp_number<cpp_rational_backend> cpp_rational;

// Fixed precision unsigned types:
-typedef mp_number<cpp_int_backend<128, false, void> > mp_uint128_t;
-typedef mp_number<cpp_int_backend<256, false, void> > mp_uint256_t;
-typedef mp_number<cpp_int_backend<512, false, void> > mp_uint512_t;
-typedef mp_number<cpp_int_backend<1024, false, void> > mp_uint1024_t;
+typedef mp_number<cpp_int_backend<128, false, void>, false> mp_uint128_t;
+typedef mp_number<cpp_int_backend<256, false, void>, false> mp_uint256_t;
+typedef mp_number<cpp_int_backend<512, false, void>, false> mp_uint512_t;
+typedef mp_number<cpp_int_backend<1024, false, void>, false> mp_uint1024_t;

// Fixed precision signed types:
-typedef mp_number<cpp_int_backend<128, true, void> > mp_int128_t;
-typedef mp_number<cpp_int_backend<256, true, void> > mp_int256_t;
-typedef mp_number<cpp_int_backend<512, true, void> > mp_int512_t;
-typedef mp_number<cpp_int_backend<1024, true, void> > mp_int1024_t;
+typedef mp_number<cpp_int_backend<128, true, void>, false> mp_int128_t;
+typedef mp_number<cpp_int_backend<256, true, void>, false> mp_int256_t;
+typedef mp_number<cpp_int_backend<512, true, void>, false> mp_int512_t;
+typedef mp_number<cpp_int_backend<1024, true, void>, false> mp_int1024_t;

}} // namespaces

Modified: sandbox/big_number/boost/multiprecision/integer_ops.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/integer_ops.hpp (original)
+++ sandbox/big_number/boost/multiprecision/integer_ops.hpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -41,20 +41,54 @@
}

template <class Backend, bool ExpressionTemplates>
-inline void divide_qr(const mp_number<Backend, ExpressionTemplates>& x, const mp_number<Backend, ExpressionTemplates>& y,
+inline typename enable_if_c<number_category<Backend>::value == number_kind_integer>::type
+ divide_qr(const mp_number<Backend, ExpressionTemplates>& x, const mp_number<Backend, ExpressionTemplates>& y,
 mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r)
{
 using default_ops::eval_qr;
 eval_qr(x.backend(), y.backend(), q.backend(), r.backend());
}

+template <class Backend, bool ExpressionTemplates, class tag, class A1, class A2, class A3>
+inline typename enable_if_c<number_category<Backend>::value == number_kind_integer>::type
+ divide_qr(const mp_number<Backend, ExpressionTemplates>& x, const multiprecision::detail::mp_exp<tag, A1, A2, A3>& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r)
+{
+ divide_qr(x, mp_number<Backend, ExpressionTemplates>(y), q, r);
+}
+
+template <class tag, class A1, class A2, class A3, class Backend, bool ExpressionTemplates>
+inline typename enable_if_c<number_category<Backend>::value == number_kind_integer>::type
+ divide_qr(const multiprecision::detail::mp_exp<tag, A1, A2, A3>& x, const mp_number<Backend, ExpressionTemplates>& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r)
+{
+ divide_qr(mp_number<Backend, ExpressionTemplates>(x), y, q, r);
+}
+
+template <class tag, class A1, class A2, class A3, class tagb, class A1b, class A2b, class A3b, class Backend, bool ExpressionTemplates>
+inline typename enable_if_c<number_category<Backend>::value == number_kind_integer>::type
+ divide_qr(const multiprecision::detail::mp_exp<tag, A1, A2, A3>& x, const multiprecision::detail::mp_exp<tagb, A1b, A2b, A3b>& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r)
+{
+ divide_qr(mp_number<Backend, ExpressionTemplates>(x), mp_number<Backend, ExpressionTemplates>(y), q, r);
+}
+
template <class Backend, bool ExpressionTemplates, class Integer>
-inline typename enable_if<is_integral<Integer>, Integer>::type integer_modulus(const mp_number<Backend, ExpressionTemplates>& x, Integer val)
+inline typename enable_if<mpl::and_<is_integral<Integer>, mpl::bool_<number_category<Backend>::value == number_kind_integer> >, Integer>::type
+ integer_modulus(const mp_number<Backend, ExpressionTemplates>& x, Integer val)
{
 using default_ops::eval_integer_modulus;
 return eval_integer_modulus(x.backend(), val);
}

+template <class tag, class A1, class A2, class A3, class Integer>
+inline typename enable_if<mpl::and_<is_integral<Integer>, mpl::bool_<number_category<typename multiprecision::detail::mp_exp<tag, A1, A2, A3>::result_type>::value == number_kind_integer> >, Integer>::type
+ integer_modulus(const multiprecision::detail::mp_exp<tag, A1, A2, A3>& x, Integer val)
+{
+ typedef typename multiprecision::detail::mp_exp<tag, A1, A2, A3>::result_type result_type;
+ return integer_modulus(result_type(x), val);
+}
+
}} //namespaces

#endif

Modified: sandbox/big_number/boost/multiprecision/miller_rabin.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/miller_rabin.hpp (original)
+++ sandbox/big_number/boost/multiprecision/miller_rabin.hpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -85,35 +85,81 @@
 return false;
 }

- static const boost::uint32_t small_factors5[] = {
- 101u, 103u, 107u, 109u };
- static const boost::uint32_t pp5 = 121330189u;
+ static const boost::uint32_t small_factors5[6][4] = {
+ { 101u, 103u, 107u, 109u },
+ { 113u, 127u, 131u, 137u },
+ { 139u, 149u, 151u, 157u },
+ { 163u, 167u, 173u, 179u },
+ { 181u, 191u, 193u, 197u },
+ { 199u, 211u, 223u, 227u }
+ };
+ static const boost::uint32_t pp5[6] =
+ {
+ 121330189u,
+ 113u * 127u * 131u * 137u,
+ 139u * 149u * 151u * 157u,
+ 163u * 167u * 173u * 179u,
+ 181u * 191u * 193u * 197u,
+ 199u * 211u * 223u * 227u
+ };

- m1 = integer_modulus(n, pp5);
-
- for(unsigned i = 0; i < sizeof(small_factors5) / sizeof(small_factors5[0]); ++i)
+ for(unsigned k = 0; k < sizeof(pp5) / sizeof(*pp5); ++k)
 {
- BOOST_ASSERT(pp5 % small_factors5[i] == 0);
- if(m1 % small_factors5[i] == 0)
- return false;
+ m1 = integer_modulus(n, pp5[k]);
+
+ for(unsigned i = 0; i < 4; ++i)
+ {
+ BOOST_ASSERT(pp5[k] % small_factors5[k][i] == 0);
+ if(m1 % small_factors5[k][i] == 0)
+ return false;
+ }
 }
 return true;
}

+inline bool is_small_prime(unsigned n)
+{
+ static const unsigned char p[] =
+ {
+ 3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u,
+ 37u, 41u, 43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u,
+ 79u, 83u, 89u, 97u, 101u, 103u, 107u, 109u, 113u,
+ 127u, 131u, 137u, 139u, 149u, 151u, 157u, 163u,
+ 167u, 173u, 179u, 181u, 191u, 193u, 197u, 199u,
+ 211u, 223u, 227u
+ };
+ for(unsigned i = 0; i < sizeof(p) / sizeof(*p); ++i)
+ {
+ if(n == p[i])
+ return true;
+ }
+ return false;
+}
+
template <class Backend, bool ExpressionTemplates, class Engine>
-bool miller_rabin_test(const mp_number<Backend, ExpressionTemplates>& n, unsigned trials, Engine& gen)
+typename enable_if_c<number_category<Backend>::value == number_kind_integer, bool>::type
+ miller_rabin_test(const mp_number<Backend, ExpressionTemplates>& n, unsigned trials, Engine& gen)
{
 typedef mp_number<Backend, ExpressionTemplates> number_type;

- if(n < 2)
- return false;
+ if(n <= 227)
+ return is_small_prime(n.template convert_to<unsigned>());
 if((n & 1) == 0)
 return false;

 if(!check_small_factors(n))
 return false;

- number_type q = (n - 1) >> 1;
+ number_type nm1 = n - 1;
+ //
+ // Begin with a single Fermat test - it excludes a lot of candidates:
+ //
+ number_type q(228), x, y; // We know n is greater than this, as we've excluded small factors
+ expmod(q, nm1, n, x);
+ if(x != 1u)
+ return false;
+
+ q = (n - 1) >> 1;
 unsigned k = 1;
 while((q & 1) == 0)
 {
@@ -122,14 +168,13 @@
 }
 // Declare our random number generator:
 boost::random::uniform_int_distribution<number_type> dist(0, n);
- number_type nm1 = n - 1;
 //
 // Execute the trials:
 //
 for(unsigned i = 0; i < trials; ++i)
 {
- number_type x = dist(gen);
- number_type y;
+ x = dist(gen);
+ y;
 expmod(x, q, n, y);
 unsigned j = 0;
 while(true)

Modified: sandbox/big_number/boost/multiprecision/tommath.hpp
==============================================================================
--- sandbox/big_number/boost/multiprecision/tommath.hpp (original)
+++ sandbox/big_number/boost/multiprecision/tommath.hpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -228,14 +228,14 @@
 d = v;
 return t.compare(d);
 }
- mp_int& data() { return m_data; }
- const mp_int& data()const { return m_data; }
+ ::mp_int& data() { return m_data; }
+ const ::mp_int& data()const { return m_data; }
 void swap(tommath_int& o)
 {
 mp_exch(&m_data, &o.data());
 }
protected:
- mp_int m_data;
+ ::mp_int m_data;
};

#define BOOST_MP_TOMMATH_BIT_OP_CHECK(x)\
@@ -478,9 +478,9 @@
template<>
struct number_category<tommath_int> : public mpl::int_<number_kind_integer>{};

-typedef mp_number<tommath_int > mp_int;
+typedef mp_number<tommath_int > tom_int;
typedef rational_adapter<tommath_int> tommath_rational;
-typedef mp_number<tommath_rational> mp_rational;
+typedef mp_number<tommath_rational> tom_rational;

}} // namespaces

Modified: sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/perf/int_real_world.html
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/perf/int_real_world.html (original)
+++ sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/perf/int_real_world.html 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -49,132 +49,12 @@
<tr>
<td>
 
- cpp_int
- 
- </td>
-<td>
- 
- 1.45089(0.481248s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- cpp_int (no Expression templates)
- 
- </td>
-<td>
- 
- 1.61489(0.535646s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- cpp_int (64-bit cache)
- 
- </td>
-<td>
- 
- 1.39273(0.461956s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- cpp_int (256-bit cache)
- 
- </td>
-<td>
- 
- 1.37743(0.456884s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- cpp_int (512-bit cache)
- 
- </td>
-<td>
- 
- 1.0919(0.362175s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- cpp_int (1024-bit cache)
- 
- </td>
-<td>
- 
- 1.10864(0.367726s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- mp_int
- 
- </td>
-<td>
- 
- 3.92956(1.3034s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- mp_int (no Expression templates)
- 
- </td>
-<td>
- 
- 4.02496(1.33505s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- mp_int1024_t
- 
- </td>
-<td>
- 
- 1.01094(0.335322s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- mp_int1024_t (no Expression templates)
- 
- </td>
-<td>
- 
- 1(0.331692s)
- 
- </td>
-</tr>
-<tr>
-<td>
- 
 mpz_int
 
 </td>
<td>
 
- 1.08472(0.359793s)
+ 1.08279(0.370326s)
 
 </td>
</tr>
@@ -186,13 +66,21 @@
 </td>
<td>
 
- 1.20865(0.400901s)
+ 1.1702(0.400222s)
 
 </td>
</tr>
</tbody>
</table></div>

+ [[cpp_int][1.3612(0.465547s)]] [[cpp_int (no Expression templates)][1.33286(0.455854s)]]
+ [[cpp_int (64-bit cache)][1.33134(0.455333s)]] [[cpp_int (256-bit cache)][1.29367(0.442451s)]]
+ [[cpp_int (512-bit cache)][1.08821(0.37218s)]] [[cpp_int (1024-bit cache)][1.07902(0.369037s)]]
+ [[mp_int1024_t][1.02616(0.35096s)]] [[mp_int1024_t (no Expression templates)][1(0.342011s)]]
+ [[tom_int][3.74233(1.27992s)]] [[tom_int (no Expression templates)][3.97646(1.35999s)]]
+ ]
+ 
+
 It's interesting to note that expression templates have little effect here
 - perhaps because the actual expressions involved are relatively trivial
 in this case - so the time taken for multiplication and division tends to

Modified: sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/ref/mp_number.html
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/ref/mp_number.html (original)
+++ sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/ref/mp_number.html 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -143,6 +143,16 @@
template <class T>
struct number_category;

+// Integer specific functions:
+template <class Backend, bool ExpressionTemplates>
+bool divide_qr(const mp_number-or-expression-template-type& x, const mp_number-or-expression-template-type& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r);
+template <class Integer>
+Integer integer_modulus(const mp_number-or-expression-template-type& x, Integer val);
+template <class Engine>
+bool miller_rabin_test(const mp_number-or-expression-template-type& n, unsigned trials, Engine& gen);
+bool miller_rabin_test(const mp_number-or-expression-template-type& n, unsigned trials);
+
// Rational number support:
typename component_type<mp_number-or-expression-template-type>::type numerator (const mp_number-or-expression-template-type&);
typename component_type<mp_number-or-expression-template-type>::type denominator(const mp_number-or-expression-template-type&);
@@ -537,6 +547,40 @@
 
<h5>
<a name="boost_multiprecision.ref.mp_number.h7"></a>
+ <a name="boost_multiprecision.ref.mp_number.integer_functions"></a><a class="link" href="mp_number.html#boost_multiprecision.ref.mp_number.integer_functions">Integer functions</a>
+ </h5>
+<pre class="programlisting">template <class Backend, bool ExpressionTemplates>
+bool divide_qr(const mp_number-or-expression-template-type& x, const mp_number-or-expression-template-type& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r);
+</pre>
+
+ Divides x by y and returns both the quotient and remainder. After the call
+ <code class="computeroutput">q =
+ x / y</code> and <code class="computeroutput">r
+ = x % y</code>.
+ 
+<pre class="programlisting">template <class Integer>
+Integer integer_modulus(const mp_number-or-expression-template-type& x, Integer val);
+</pre>
+
+ Returns the absolute value of <code class="computeroutput">x
+ % val</code>.
+ 
+<pre class="programlisting">template <class Engine>
+bool miller_rabin_test(const mp_number-or-expression-template-type& n, unsigned trials, Engine& gen);
+bool miller_rabin_test(const mp_number-or-expression-template-type& n, unsigned trials);
+</pre>
+
+ Tests to see if the number n is probably prime - the
+ test excludes the vast majority of composite numbers by excluding small prime
+ factors and performing a single Fermat test. Then performs trials
+ Miller-Rabin tests. Returns <code class="computeroutput">false</code>
+ if n is definitely composite, or <code class="computeroutput">true</code>
+ if n is probably prime with the probability of it being
+ composite less than 0.25^trials.
+ 
+<h5>
+<a name="boost_multiprecision.ref.mp_number.h8"></a>
 <a name="boost_multiprecision.ref.mp_number.rational_number_functions"></a><a class="link" href="mp_number.html#boost_multiprecision.ref.mp_number.rational_number_functions">Rational
 Number Functions</a>
 </h5>
@@ -548,7 +592,7 @@
 respectively.
 
<h5>
-<a name="boost_multiprecision.ref.mp_number.h8"></a>
+<a name="boost_multiprecision.ref.mp_number.h9"></a>
 <a name="boost_multiprecision.ref.mp_number.boost_math_interoperability_support"></a><a class="link" href="mp_number.html#boost_multiprecision.ref.mp_number.boost_math_interoperability_support">Boost.Math
 Interoperability Support</a>
 </h5>
@@ -571,7 +615,7 @@
 to ensure interoperability.
 
<h5>
-<a name="boost_multiprecision.ref.mp_number.h9"></a>
+<a name="boost_multiprecision.ref.mp_number.h10"></a>
 <a name="boost_multiprecision.ref.mp_number.std__numeric_limits_support"></a><a class="link" href="mp_number.html#boost_multiprecision.ref.mp_number.std__numeric_limits_support">std::numeric_limits
 support</a>
 </h5>

Modified: sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/ints.html
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/ints.html (original)
+++ sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/ints.html 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -65,12 +65,12 @@
<tr>
<td>
 
- <code class="computeroutput">gmp_int</code>
+ <code class="computeroutput">cpp_int</code>
 
 </td>
<td>
 
- boost/multiprecision/gmp.hpp
+ boost/multiprecision/cpp_int.hpp
 
 </td>
<td>
@@ -80,30 +80,31 @@
 </td>
<td>
 
- GMP
+ None
 
 </td>
<td>
 
- Very fast and efficient backend.
+ Very versatile, Boost licenced, all C++ integer type which support
+ both arbitrary precision and fixed precision integer types.
 
 </td>
<td>
 
- Dependency on GNU licenced GMP
- library.
+ Slower than GMP, though
+ typically not as slow as libtommath
 
 </td>
</tr>
<tr>
<td>
 
- <code class="computeroutput">mp_int</code>
+ <code class="computeroutput">gmp_int</code>
 
 </td>
<td>
 
- boost/multiprecision/tommath.hpp
+ boost/multiprecision/gmp.hpp
 
 </td>
<td>
@@ -113,29 +114,30 @@
 </td>
<td>
 
- libtommath
+ GMP
 
 </td>
<td>
 
- Public domain backend with no licence restrictions.
+ Very fast and efficient backend.
 
 </td>
<td>
 
- Slower than GMP.
+ Dependency on GNU licenced GMP
+ library.
 
 </td>
</tr>
<tr>
<td>
 
- <code class="computeroutput">cpp_int</code>
+ <code class="computeroutput">tom_int</code>
 
 </td>
<td>
 
- boost/multiprecision/cpp_int.hpp
+ boost/multiprecision/tommath.hpp
 
 </td>
<td>
@@ -145,13 +147,12 @@
 </td>
<td>
 
- None
+ libtommath
 
 </td>
<td>
 
- Very versatile, Boost licenced, all C++ integer type which support
- both arbitrary precision and fixed precision integer types.
+ Public domain backend with no licence restrictions.
 
 </td>
<td>
@@ -164,6 +165,147 @@
</table></div>
<h5>
<a name="boost_multiprecision.tut.ints.h0"></a>
+ <a name="boost_multiprecision.tut.ints.cpp_int"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.cpp_int">cpp_int</a>
+ </h5>
+<pre class="programlisting">namespace boost{ namespace multiprecision{
+
+typedef unspecified-type limb_type;
+
+template <unsigned MinDigits = 0, bool Signed = true, class Allocator = std::allocator<limb_type> >
+class cpp_int_backend;
+
+typedef mp_number<cpp_int_backend<> > cpp_int; // arbitrary precision integer
+typedef rational_adapter<cpp_int_backend<> > cpp_rational_backend;
+typedef mp_number<cpp_rational_backend> cpp_rational; // arbitrary precision rational number
+
+// Fixed precision unsigned types:
+typedef mp_number<cpp_int_backend<128, false, void>, false> mp_uint128_t;
+typedef mp_number<cpp_int_backend<256, false, void>, false> mp_uint256_t;
+typedef mp_number<cpp_int_backend<512, false, void>, false> mp_uint512_t;
+typedef mp_number<cpp_int_backend<1024, false, void>, false> mp_uint1024_t;
+
+// Fixed precision signed types:
+typedef mp_number<cpp_int_backend<128, true, void>, false> mp_int128_t;
+typedef mp_number<cpp_int_backend<256, true, void>, false> mp_int256_t;
+typedef mp_number<cpp_int_backend<512, true, void>, false> mp_int512_t;
+typedef mp_number<cpp_int_backend<1024, true, void>, false> mp_int1024_t;
+
+}} // namespaces
+</pre>
+
+ The <code class="computeroutput">cpp_int_backend</code> type
+ is used via one of the typedefs <code class="computeroutput">boost::multiprecision::cpp_int</code>,
+ <code class="computeroutput">boost::multiprecision::mp_uint128_t</code>, <code class="computeroutput">boost::multiprecision::mp_uint256_t</code>,
+ <code class="computeroutput">boost::multiprecision::mp_uint512_t</code>, <code class="computeroutput">boost::multiprecision::mp_int128_t</code>,
+ <code class="computeroutput">boost::multiprecision::mp_int256_t</code> or <code class="computeroutput">boost::multiprecision::mp_int512_t</code>.
+ 
+
+ This backend is the "Swiss Army Knife" of integer types as it can
+ represent both fixed and arbitrary precision integer types, and both signed
+ and unsigned types. There are three template arguments:
+ 
+<div class="variablelist">
+
+<dl>
+<dt>MinBits</dt>
+<dd>
+ Determines the number of Bits to store directly within the object before
+ resorting to dynamic memory allocation. When zero, this field is determined
+ automatically based on how many bits can be stored in union with the
+ dynamic storage header: setting a larger value may improve performance
+ as larger integer values will be stored internally before memory allocation
+ is required. When the Allocator parameter is type <code class="computeroutput">void</code>,
+ then this field determines the total number of bits in the resulting
+ fixed precision type.
+ </dd>
+<dt>Signed</dt>
+<dd>
+ Determines whether the resulting type is signed or not. Note that for
+ arbitrary precision types (where the Allocator parameter is non-void),
+ then this parameter must be <code class="computeroutput">true</code>.
+ For fixed precision types then this type may be either <code class="computeroutput">true</code> (type is signed), or <code class="computeroutput">false</code> (type is unsigned).
+ </dd>
+<dt>Allocator</dt>
+<dd>
+ The allocator to use for dymamic memory allocation, or type <code class="computeroutput">void</code> if this is to be a fixed precision
+ type.
+ </dd>
+</dl>
+</div>
+
+ Things you should know when using this type:
+ 
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<li class="listitem">
+ Default constructed <code class="computeroutput">cpp_int_backend</code>'s
+ have the value zero.
+ </li>
+<li class="listitem">
+ Division by zero results in a <code class="computeroutput">std::runtime_error</code>
+ being thrown.
+ </li>
+<li class="listitem">
+ Construction from a string that contains invalid non-numeric characters
+ results in a <code class="computeroutput">std::runtime_error</code> being thrown.
+ </li>
+<li class="listitem">
+ Since the precision of <code class="computeroutput">cpp_int_backend</code>
+ is necessarily limited when the allocator parameter is void, care should
+ be taken to avoid numeric overflow when using this type unless you actually
+ want modulo-arithmetic behavior.
+ </li>
+<li class="listitem">
+ The type uses a sign-magnitude representation internally, so type <code class="computeroutput">mp_int128_t</code> has 128-bits of precision
+ plus an extra sign bit. In this respect the behaviour of these types
+ differs from built-in 2's complement types. In might be tempting to use
+ a 127-bit type instead, and indeed this does work, but behaviour is still
+ slightly different from a 2's complement built-in type as the min and
+ max values are identical (apart from the sign), where as they differ
+ by one for a true 2's complement type. That said it should be noted that
+ there's no requirement for built-in types to be 2's complement either
+ - it's simply that this is the most common format by far.
+ </li>
+<li class="listitem">
+ Attempting to print negative values as either an Octal or Hexadecimal
+ string results in a <code class="computeroutput">std::runtime_error</code>
+ being thrown, this is a direct consequence of the sign-magnitude representation.
+ </li>
+<li class="listitem">
+ The fixed precision types <code class="computeroutput">mp_[u]intXXX_t</code>
+ have expression template support turned off - it seems to make little
+ difference to the performance of these types either way - so we may as
+ well have the faster compile times by turning the feature off.
+ </li>
+</ul></div>
+<h6>
+<a name="boost_multiprecision.tut.ints.h1"></a>
+ <a name="boost_multiprecision.tut.ints.example_"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example_">Example:</a>
+ </h6>
+
+
+<pre class="programlisting">#include <boost/multiprecision/cpp_int.hpp>
+
+using namespace boost::multiprecision;
+
+mp_int128_t v = 1;
+
+// Do some fixed precision arithmetic:
+for(unsigned i = 1; i <= 20; ++i)
+ v *= i;
+
+std::cout << v << std::endl; // prints 20!
+
+// Try again at arbitrary precision:
+cpp_int u = 1;
+for(unsigned i = 1; i <= 100; ++i)
+ u *= i;
+
+std::cout << u << std::endl; // prints 100!
+</pre>
+
+ 
+<h5>
+<a name="boost_multiprecision.tut.ints.h2"></a>
 <a name="boost_multiprecision.tut.ints.gmp_int"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.gmp_int">gmp_int</a>
 </h5>
<pre class="programlisting">namespace boost{ namespace multiprecision{
@@ -232,8 +374,8 @@
 </li>
</ul></div>
<h6>
-<a name="boost_multiprecision.tut.ints.h1"></a>
- <a name="boost_multiprecision.tut.ints.example_"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example_">Example:</a>
+<a name="boost_multiprecision.tut.ints.h3"></a>
+ <a name="boost_multiprecision.tut.ints.example0"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example0">Example:</a>
 </h6>


@@ -257,22 +399,22 @@

 
<h5>
-<a name="boost_multiprecision.tut.ints.h2"></a>
- <a name="boost_multiprecision.tut.ints.mp_int"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.mp_int">mp_int</a>
+<a name="boost_multiprecision.tut.ints.h4"></a>
+ <a name="boost_multiprecision.tut.ints.tom_int"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.tom_int">tom_int</a>
 </h5>
<pre class="programlisting">namespace boost{ namespace multiprecision{

class tommath_int;

-typedef mp_number<tommath_int > mp_int;
+typedef mp_number<tommath_int > tom_int;

}} // namespaces
</pre>

 The <code class="computeroutput">tommath_int</code> backend is
- used via the typedef <code class="computeroutput">boost::multiprecision::mp_int</code>.
+ used via the typedef <code class="computeroutput">boost::multiprecision::tom_int</code>.
 It acts as a thin wrapper around the libtommath
- <code class="computeroutput">mp_int</code> to provide an integer
+ <code class="computeroutput">tom_int</code> to provide an integer
 type that is a drop-in replacement for the native C++ integer types, but
 with unlimited precision.
 
@@ -285,7 +427,7 @@
 default behavior).
 </li>
<li class="listitem">
- Although <code class="computeroutput">mp_int</code> is mostly
+ Although <code class="computeroutput">tom_int</code> is mostly
 a drop in replacement for the builtin integer types, it should be noted
 that it is a rather strange beast as it's a signed type that is not a
 2's complement type. As a result the bitwise operations <code class="computeroutput">| & ^</code> will throw a <code class="computeroutput">std::runtime_error</code>
@@ -305,14 +447,14 @@
 </li>
</ul></div>
<h6>
-<a name="boost_multiprecision.tut.ints.h3"></a>
- <a name="boost_multiprecision.tut.ints.example0"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example0">Example:</a>
+<a name="boost_multiprecision.tut.ints.h5"></a>
+ <a name="boost_multiprecision.tut.ints.example1"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example1">Example:</a>
 </h6>


<pre class="programlisting">#include <boost/multiprecision/tommath.hpp>

-boost::multiprecision::mp_int v = 1;
+boost::multiprecision::tom_int v = 1;

// Do some arithmetic:
for(unsigned i = 1; i <= 1000; ++i)
@@ -341,141 +483,6 @@
</pre>

 
-<h5>
-<a name="boost_multiprecision.tut.ints.h4"></a>
- <a name="boost_multiprecision.tut.ints.cpp_int"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.cpp_int">cpp_int</a>
- </h5>
-<pre class="programlisting">namespace boost{ namespace multiprecision{
-
-typedef unspecified-type limb_type;
-
-template <unsigned MinDigits = 0, bool Signed = true, class Allocator = std::allocator<limb_type> >
-class cpp_int_backend;
-
-typedef mp_number<cpp_int_backend<> > cpp_int; // arbitrary precision integer
-typedef rational_adapter<cpp_int_backend<> > cpp_rational_backend;
-typedef mp_number<cpp_rational_backend> cpp_rational; // arbitrary precision rational number
-
-// Fixed precision unsigned types:
-typedef mp_number<cpp_int_backend<128, false, void> > mp_uint128_t;
-typedef mp_number<cpp_int_backend<256, false, void> > mp_uint256_t;
-typedef mp_number<cpp_int_backend<512, false, void> > mp_uint512_t;
-typedef mp_number<cpp_int_backend<1024, false, void> > mp_uint1024_t;
-
-// Fixed precision signed types:
-typedef mp_number<cpp_int_backend<128, true, void> > mp_int128_t;
-typedef mp_number<cpp_int_backend<256, true, void> > mp_int256_t;
-typedef mp_number<cpp_int_backend<512, true, void> > mp_int512_t;
-typedef mp_number<cpp_int_backend<1024, true, void> > mp_int1024_t;
-
-}} // namespaces
-</pre>
-
- The <code class="computeroutput">cpp_int_backend</code> type
- is used via one of the typedefs <code class="computeroutput">boost::multiprecision::cpp_int</code>,
- <code class="computeroutput">boost::multiprecision::mp_uint128_t</code>, <code class="computeroutput">boost::multiprecision::mp_uint256_t</code>,
- <code class="computeroutput">boost::multiprecision::mp_uint512_t</code>, <code class="computeroutput">boost::multiprecision::mp_int128_t</code>,
- <code class="computeroutput">boost::multiprecision::mp_int256_t</code> or <code class="computeroutput">boost::multiprecision::mp_int512_t</code>.
- 
-
- This backend is the "Swiss Army Knife" of integer types as it can
- represent both fixed and arbitrary precision integer types, and both signed
- and unsigned types. There are three template arguments:
- 
-<div class="variablelist">
-
-<dl>
-<dt>MinBits</dt>
-<dd>
- Determines the number of Bits to store directly within the object before
- resorting to dynamic memory allocation. When zero, this field is determined
- automatically based on how many bits can be stored in union with the
- dynamic storage header: setting a larger value may improve performance
- as larger integer values will be stored internally before memory allocation
- is required. When the Allocator parameter is type <code class="computeroutput">void</code>,
- then this field determines the total number of bits in the resulting
- fixed precision type.
- </dd>
-<dt>Signed</dt>
-<dd>
- Determines whether the resulting type is signed or not. Note that for
- arbitrary precision types (where the Allocator parameter is non-void),
- then this parameter must be <code class="computeroutput">true</code>.
- For fixed precision types then this type may be either <code class="computeroutput">true</code> (type is signed), or <code class="computeroutput">false</code> (type is unsigned).
- </dd>
-<dt>Allocator</dt>
-<dd>
- The allocator to use for dymamic memory allocation, or type <code class="computeroutput">void</code> if this is to be a fixed precision
- type.
- </dd>
-</dl>
-</div>
-
- Things you should know when using this type:
- 
-<div class="itemizedlist"><ul class="itemizedlist" type="disc">
-<li class="listitem">
- Default constructed <code class="computeroutput">cpp_int_backend</code>'s
- have the value zero.
- </li>
-<li class="listitem">
- Division by zero results in a <code class="computeroutput">std::runtime_error</code>
- being thrown.
- </li>
-<li class="listitem">
- Construction from a string that contains invalid non-numeric characters
- results in a <code class="computeroutput">std::runtime_error</code> being thrown.
- </li>
-<li class="listitem">
- Since the precision of <code class="computeroutput">cpp_int_backend</code>
- is necessarily limited when the allocator parameter is void, care should
- be taken to avoid numeric overflow when using this type unless you actually
- want modulo-arithmetic behavior.
- </li>
-<li class="listitem">
- The type uses a sign-magnitude representation internally, so type <code class="computeroutput">mp_int128_t</code> has 128-bits of precision
- plus an extra sign bit. In this respect the behaviour of these types
- differs from built-in 2's complement types. In might be tempting to use
- a 127-bit type instead, and indeed this does work, but behaviour is still
- slightly different from a 2's complement built-in type as the min and
- max values are identical (apart from the sign), where as they differ
- by one for a true 2's complement type. That said it should be noted that
- there's no requirement for built-in types to be 2's complement either
- - it's simply that this is the most common format by far.
- </li>
-<li class="listitem">
- Attempting to print negative values as either an Octal or Hexadecimal
- string results in a <code class="computeroutput">std::runtime_error</code>
- being thrown, this is a direct consequence of the sign-magnitude representation.
- </li>
-</ul></div>
-<h6>
-<a name="boost_multiprecision.tut.ints.h5"></a>
- <a name="boost_multiprecision.tut.ints.example1"></a><a class="link" href="ints.html#boost_multiprecision.tut.ints.example1">Example:</a>
- </h6>
-
-
-<pre class="programlisting">#include <boost/multiprecision/cpp_int.hpp>
-
-using namespace boost::multiprecision;
-
-mp_int128_t v = 1;
-
-// Do some fixed precision arithmetic:
-for(unsigned i = 1; i <= 20; ++i)
- v *= i;
-
-std::cout << v << std::endl; // prints 20!
-
-// Try again at arbitrary precision:
-cpp_int u = 1;
-for(unsigned i = 1; i <= 100; ++i)
- u *= i;
-
-std::cout << u << std::endl; // prints 100!
-</pre>
-
- 
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>

Modified: sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/rational.html
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/rational.html (original)
+++ sandbox/big_number/libs/multiprecision/doc/html/boost_multiprecision/tut/rational.html 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -414,26 +414,26 @@
<pre class="programlisting">namespace boost{ namespace multiprecision{

typedef rational_adpater<tommath_int> tommath_rational;
-typedef mp_number<tommath_rational > mp_rational;
+typedef mp_number<tommath_rational > tom_rational;

}} // namespaces
</pre>

 The <code class="computeroutput">tommath_rational</code> backend
- is used via the typedef <code class="computeroutput">boost::multiprecision::mp_rational</code>.
- It acts as a thin wrapper around <code class="computeroutput">boost::rational<mp_int></code> to provide a rational number type that
+ is used via the typedef <code class="computeroutput">boost::multiprecision::tom_rational</code>.
+ It acts as a thin wrapper around <code class="computeroutput">boost::rational<tom_int></code> to provide a rational number type that
 is a drop-in replacement for the native C++ number types, but with unlimited
 precision.
 

- The advantage of using this type rather than <code class="computeroutput">boost::rational<mp_int></code> directly, is that it is expression-template
+ The advantage of using this type rather than <code class="computeroutput">boost::rational<tom_int></code> directly, is that it is expression-template
 enabled, greatly reducing the number of temporaries created in complex expressions.
 

 There are also non-member functions:
 
-<pre class="programlisting">mp_int numerator(const mp_rational&);
-mp_int denominator(const mp_rational&);
+<pre class="programlisting">tom_int numerator(const tom_rational&);
+tom_int denominator(const tom_rational&);
</pre>

 which return the numerator and denominator of the number.
@@ -443,7 +443,7 @@
 
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
- Default constructed <code class="computeroutput">mp_rational</code>'s
+ Default constructed <code class="computeroutput">tom_rational</code>'s
 have the value zero (this the inherited Boost.Rational behavior).
 </li>
<li class="listitem">
@@ -472,7 +472,7 @@

using namespace boost::multiprecision;

-mp_rational v = 1;
+tom_rational v = 1;

// Do some arithmetic:
for(unsigned i = 1; i <= 1000; ++i)
@@ -483,7 +483,7 @@
std::cout << numerator(v) << std::endl;
std::cout << denominator(v) << std::endl;

-mp_rational w(2, 3); // Component wise constructor
+tom_rational w(2, 3); // Component wise constructor
std::cout << w << std::endl; // prints 2/3
</pre>

Modified: sandbox/big_number/libs/multiprecision/doc/html/index.html
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/html/index.html (original)
+++ sandbox/big_number/libs/multiprecision/doc/html/index.html 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -63,7 +63,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left">Last revised: March 20, 2012 at 19:02:47 GMT</td>
+<td align="left">Last revised: March 22, 2012 at 08:59:33 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk
==============================================================================
--- sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk (original)
+++ sandbox/big_number/libs/multiprecision/doc/multiprecision.qbk 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -225,77 +225,12 @@

[table
[[Backend Type][Header][Radix][Dependencies][Pros][Cons]]
-[[`gmp_int`][boost/multiprecision/gmp.hpp][2][[gmp]][Very fast and efficient backend.][Dependency on GNU licenced [gmp] library.]]
-[[`mp_int`][boost/multiprecision/tommath.hpp][2][[tommath]][Public domain backend with no licence restrictions.][Slower than [gmp].]]
[[`cpp_int`][boost/multiprecision/cpp_int.hpp][2][None]
- [Very versatile, Boost licenced, all C++ integer type which support both arbitrary precision and fixed precision integer types.][Slower than [gmp].]]
+ [Very versatile, Boost licenced, all C++ integer type which support both arbitrary precision and fixed precision integer types.][Slower than [gmp], though typically not as slow as [tommath]]]
+[[`gmp_int`][boost/multiprecision/gmp.hpp][2][[gmp]][Very fast and efficient backend.][Dependency on GNU licenced [gmp] library.]]
+[[`tom_int`][boost/multiprecision/tommath.hpp][2][[tommath]][Public domain backend with no licence restrictions.][Slower than [gmp].]]
]

-[h4 gmp_int]
-
- namespace boost{ namespace multiprecision{
-
- class gmp_int;
-
- typedef mp_number<gmp_int > mpz_int;
-
- }} // namespaces
-
-The `gmp_int` backend is used via the typedef `boost::multiprecision::mpz_int`. It acts as a thin wrapper around the [gmp] `mpz_t`
-to provide an integer type that is a drop-in replacement for the native C++ integer types, but with unlimited precision.
-
-As well as the usual conversions from arithmetic and string types, type `mpz_int` is copy constructible and assignable from:
-
-* The [gmp] native types: `mpf_t`, `mpz_t`, `mpq_t`.
-* Instances of `mp_number<T>` that are wrappers around those types: `mp_number<gmp_float<N> >`, `mp_number<gmp_rational>`.
-
-It's also possible to access the underlying `mpz_t` via the `data()` member function of `gmp_int`.
-
-Things you should know when using this type:
-
-* No changes are made to the GMP library's global settings - so you can safely mix this type with
-existing code that uses [gmp].
-* Default constructed `gmp_int`'s have the value zero (this is GMP's default behavior).
-* Formatted IO for this type does not support octal or hexadecimal notation for negative values,
-as a result performing formatted output on this type when the argument is negative and either of the flags
-`std::ios_base::oct` or `std::ios_base::hex` are set, will result in a `std::runtime_error` will be thrown.
-* Division by zero is handled by the [gmp] library - it will trigger a division by zero signal.
-* Although this type is a wrapper around [gmp] it will work equally well with [mpir]. Indeed use of [mpir]
-is recomended on Win32.
-
-[h5 Example:]
-
-[mpz_eg]
-
-[h4 mp_int]
-
- namespace boost{ namespace multiprecision{
-
- class tommath_int;
-
- typedef mp_number<tommath_int > mp_int;
-
- }} // namespaces
-
-The `tommath_int` backend is used via the typedef `boost::multiprecision::mp_int`. It acts as a thin wrapper around the [tommath] `mp_int`
-to provide an integer type that is a drop-in replacement for the native C++ integer types, but with unlimited precision.
-
-Things you should know when using this type:
-
-* Default constructed objects have the value zero (this is [tommath]'s default behavior).
-* Although `mp_int` is mostly a drop in replacement for the builtin integer types, it should be noted that it is a
-rather strange beast as it's a signed type that is not a 2's complement type. As a result the bitwise operations
-`| & ^` will throw a `std::runtime_error` exception if either of the arguments is negative. Similarly the complement
-operator`~` is deliberately not implemented for this type.
-* Formatted IO for this type does not support octal or hexadecimal notation for negative values,
-as a result performing formatted output on this type when the argument is negative and either of the flags
-`std::ios_base::oct` or `std::ios_base::hex` are set, will result in a `std::runtime_error` will be thrown.
-* Division by zero will result in a hardware signal being raised by [tommath].
-
-[h5 Example:]
-
-[tommath_eg]
-
[h4 cpp_int]

 namespace boost{ namespace multiprecision{
@@ -310,16 +245,16 @@
 typedef mp_number<cpp_rational_backend> cpp_rational; // arbitrary precision rational number

 // Fixed precision unsigned types:
- typedef mp_number<cpp_int_backend<128, false, void> > mp_uint128_t;
- typedef mp_number<cpp_int_backend<256, false, void> > mp_uint256_t;
- typedef mp_number<cpp_int_backend<512, false, void> > mp_uint512_t;
- typedef mp_number<cpp_int_backend<1024, false, void> > mp_uint1024_t;
+ typedef mp_number<cpp_int_backend<128, false, void>, false> mp_uint128_t;
+ typedef mp_number<cpp_int_backend<256, false, void>, false> mp_uint256_t;
+ typedef mp_number<cpp_int_backend<512, false, void>, false> mp_uint512_t;
+ typedef mp_number<cpp_int_backend<1024, false, void>, false> mp_uint1024_t;

 // Fixed precision signed types:
- typedef mp_number<cpp_int_backend<128, true, void> > mp_int128_t;
- typedef mp_number<cpp_int_backend<256, true, void> > mp_int256_t;
- typedef mp_number<cpp_int_backend<512, true, void> > mp_int512_t;
- typedef mp_number<cpp_int_backend<1024, true, void> > mp_int1024_t;
+ typedef mp_number<cpp_int_backend<128, true, void>, false> mp_int128_t;
+ typedef mp_number<cpp_int_backend<256, true, void>, false> mp_int256_t;
+ typedef mp_number<cpp_int_backend<512, true, void>, false> mp_int512_t;
+ typedef mp_number<cpp_int_backend<1024, true, void>, false> mp_int1024_t;

 }} // namespaces

@@ -360,11 +295,79 @@
is the most common format by far.
* Attempting to print negative values as either an Octal or Hexadecimal string results in a `std::runtime_error` being thrown,
this is a direct consequence of the sign-magnitude representation.
+* The fixed precision types `mp_[u]intXXX_t` have expression template support turned off - it seems to make little
+difference to the performance of these types either way - so we may as well have the faster compile times by turning
+the feature off.

[h5 Example:]

[cpp_int_eg]

+[h4 gmp_int]
+
+ namespace boost{ namespace multiprecision{
+
+ class gmp_int;
+
+ typedef mp_number<gmp_int > mpz_int;
+
+ }} // namespaces
+
+The `gmp_int` backend is used via the typedef `boost::multiprecision::mpz_int`. It acts as a thin wrapper around the [gmp] `mpz_t`
+to provide an integer type that is a drop-in replacement for the native C++ integer types, but with unlimited precision.
+
+As well as the usual conversions from arithmetic and string types, type `mpz_int` is copy constructible and assignable from:
+
+* The [gmp] native types: `mpf_t`, `mpz_t`, `mpq_t`.
+* Instances of `mp_number<T>` that are wrappers around those types: `mp_number<gmp_float<N> >`, `mp_number<gmp_rational>`.
+
+It's also possible to access the underlying `mpz_t` via the `data()` member function of `gmp_int`.
+
+Things you should know when using this type:
+
+* No changes are made to the GMP library's global settings - so you can safely mix this type with
+existing code that uses [gmp].
+* Default constructed `gmp_int`'s have the value zero (this is GMP's default behavior).
+* Formatted IO for this type does not support octal or hexadecimal notation for negative values,
+as a result performing formatted output on this type when the argument is negative and either of the flags
+`std::ios_base::oct` or `std::ios_base::hex` are set, will result in a `std::runtime_error` will be thrown.
+* Division by zero is handled by the [gmp] library - it will trigger a division by zero signal.
+* Although this type is a wrapper around [gmp] it will work equally well with [mpir]. Indeed use of [mpir]
+is recomended on Win32.
+
+[h5 Example:]
+
+[mpz_eg]
+
+[h4 tom_int]
+
+ namespace boost{ namespace multiprecision{
+
+ class tommath_int;
+
+ typedef mp_number<tommath_int > tom_int;
+
+ }} // namespaces
+
+The `tommath_int` backend is used via the typedef `boost::multiprecision::tom_int`. It acts as a thin wrapper around the [tommath] `tom_int`
+to provide an integer type that is a drop-in replacement for the native C++ integer types, but with unlimited precision.
+
+Things you should know when using this type:
+
+* Default constructed objects have the value zero (this is [tommath]'s default behavior).
+* Although `tom_int` is mostly a drop in replacement for the builtin integer types, it should be noted that it is a
+rather strange beast as it's a signed type that is not a 2's complement type. As a result the bitwise operations
+`| & ^` will throw a `std::runtime_error` exception if either of the arguments is negative. Similarly the complement
+operator`~` is deliberately not implemented for this type.
+* Formatted IO for this type does not support octal or hexadecimal notation for negative values,
+as a result performing formatted output on this type when the argument is negative and either of the flags
+`std::ios_base::oct` or `std::ios_base::hex` are set, will result in a `std::runtime_error` will be thrown.
+* Division by zero will result in a hardware signal being raised by [tommath].
+
+[h5 Example:]
+
+[tommath_eg]
+
[endsect]

[section:reals Floating Point Numbers]
@@ -611,27 +614,27 @@
 namespace boost{ namespace multiprecision{

 typedef rational_adpater<tommath_int> tommath_rational;
- typedef mp_number<tommath_rational > mp_rational;
+ typedef mp_number<tommath_rational > tom_rational;

 }} // namespaces

-The `tommath_rational` backend is used via the typedef `boost::multiprecision::mp_rational`. It acts as a thin wrapper around
-`boost::rational<mp_int>`
+The `tommath_rational` backend is used via the typedef `boost::multiprecision::tom_rational`. It acts as a thin wrapper around
+`boost::rational<tom_int>`
to provide a rational number type that is a drop-in replacement for the native C++ number types, but with unlimited precision.

-The advantage of using this type rather than `boost::rational<mp_int>` directly, is that it is expression-template enabled,
+The advantage of using this type rather than `boost::rational<tom_int>` directly, is that it is expression-template enabled,
greatly reducing the number of temporaries created in complex expressions.

There are also non-member functions:

- mp_int numerator(const mp_rational&);
- mp_int denominator(const mp_rational&);
+ tom_int numerator(const tom_rational&);
+ tom_int denominator(const tom_rational&);

which return the numerator and denominator of the number.

Things you should know when using this type:

-* Default constructed `mp_rational`'s have the value zero (this the inherited Boost.Rational behavior).
+* Default constructed `tom_rational`'s have the value zero (this the inherited Boost.Rational behavior).
* Division by zero results in a `boost::bad_rational` exception being thrown (see the rational number library's docs for more information).
* No changes are made to [tommath]'s global state, so this type can safely coexist with other [tommath] code.
* Performance of this type has been found to be pretty poor - this need further investigation - but it appears that Boost.Rational
@@ -860,6 +863,16 @@
 template <class T>
 struct number_category;

+ // Integer specific functions:
+ template <class Backend, bool ExpressionTemplates>
+ bool divide_qr(const ``['mp_number-or-expression-template-type]``& x, const ``['mp_number-or-expression-template-type]``& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r);
+ template <class Integer>
+ Integer integer_modulus(const ``['mp_number-or-expression-template-type]``& x, Integer val);
+ template <class Engine>
+ bool miller_rabin_test(const ``['mp_number-or-expression-template-type]``& n, unsigned trials, Engine& gen);
+ bool miller_rabin_test(const ``['mp_number-or-expression-template-type]``& n, unsigned trials);
+
 // Rational number support:
 typename component_type<``['mp_number-or-expression-template-type]``>::type numerator (const ``['mp_number-or-expression-template-type]``&);
 typename component_type<``['mp_number-or-expression-template-type]``>::type denominator(const ``['mp_number-or-expression-template-type]``&);
@@ -1123,6 +1136,29 @@
A traits class that inherits from `mpl::int_<N>` where `N` is one of the enumerated values `number_kind_integer`, `number_kind_floating_point`,
`number_kind_rational` or `number_kind_fixed_point`.

+
+[h4 Integer functions]
+
+ template <class Backend, bool ExpressionTemplates>
+ bool divide_qr(const ``['mp_number-or-expression-template-type]``& x, const ``['mp_number-or-expression-template-type]``& y,
+ mp_number<Backend, ExpressionTemplates>& q, mp_number<Backend, ExpressionTemplates>& r);
+
+Divides x by y and returns both the quotient and remainder. After the call `q = x / y` and `r = x % y`.
+
+ template <class Integer>
+ Integer integer_modulus(const ``['mp_number-or-expression-template-type]``& x, Integer val);
+
+Returns the absolute value of `x % val`.
+
+ template <class Engine>
+ bool miller_rabin_test(const ``['mp_number-or-expression-template-type]``& n, unsigned trials, Engine& gen);
+ bool miller_rabin_test(const ``['mp_number-or-expression-template-type]``& n, unsigned trials);
+
+Tests to see if the number /n/ is probably prime - the test excludes the vast majority of composite numbers
+by excluding small prime factors and performing a single Fermat test. Then performs /trials/ Miller-Rabin
+tests. Returns `false` if /n/ is definitely composite, or `true` if /n/ is probably prime with the
+probability of it being composite less than 0.25^trials.
+
[h4 Rational Number Functions]

 typename component_type<``['mp_number-or-expression-template-type]``>::type numerator (const ``['mp_number-or-expression-template-type]``&);
@@ -1373,18 +1409,18 @@

[table
[[Integer Type][Relative (and Absolute) Times]]
-[[cpp_int][1.45089(0.481248s)]]
-[[cpp_int (no Expression templates)][1.61489(0.535646s)]]
-[[cpp_int (64-bit cache)][1.39273(0.461956s)]]
-[[cpp_int (256-bit cache)][1.37743(0.456884s)]]
-[[cpp_int (512-bit cache)][1.0919(0.362175s)]]
-[[cpp_int (1024-bit cache)][1.10864(0.367726s)]]
-[[mp_int][3.92956(1.3034s)]]
-[[mp_int (no Expression templates)][4.02496(1.33505s)]]
-[[mp_int1024_t][1.01094(0.335322s)]]
-[[mp_int1024_t (no Expression templates)][1(0.331692s)]]
-[[mpz_int][1.08472(0.359793s)]]
-[[mpz_int (no Expression templates)][1.20865(0.400901s)]]
+[[mpz_int][1.08279(0.370326s)]]
+[[mpz_int (no Expression templates)][1.1702(0.400222s)]]]
+[[cpp_int][1.3612(0.465547s)]]
+[[cpp_int (no Expression templates)][1.33286(0.455854s)]]
+[[cpp_int (64-bit cache)][1.33134(0.455333s)]]
+[[cpp_int (256-bit cache)][1.29367(0.442451s)]]
+[[cpp_int (512-bit cache)][1.08821(0.37218s)]]
+[[cpp_int (1024-bit cache)][1.07902(0.369037s)]]
+[[mp_int1024_t][1.02616(0.35096s)]]
+[[mp_int1024_t (no Expression templates)][1(0.342011s)]]
+[[tom_int][3.74233(1.27992s)]]
+[[tom_int (no Expression templates)][3.97646(1.35999s)]]
]

It's interesting to note that expression templates have little effect here - perhaps because the actual expressions involved

Modified: sandbox/big_number/libs/multiprecision/example/tommath_snips.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/example/tommath_snips.cpp (original)
+++ sandbox/big_number/libs/multiprecision/example/tommath_snips.cpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -11,7 +11,7 @@
 //[tommath_eg
 //=#include <boost/multiprecision/tommath.hpp>

- boost::multiprecision::mp_int v = 1;
+ boost::multiprecision::tom_int v = 1;

 // Do some arithmetic:
 for(unsigned i = 1; i <= 1000; ++i)
@@ -48,7 +48,7 @@

 using namespace boost::multiprecision;

- mp_rational v = 1;
+ tom_rational v = 1;

 // Do some arithmetic:
 for(unsigned i = 1; i <= 1000; ++i)
@@ -59,7 +59,7 @@
 std::cout << numerator(v) << std::endl;
 std::cout << denominator(v) << std::endl;

- mp_rational w(2, 3); // Component wise constructor
+ tom_rational w(2, 3); // Component wise constructor
 std::cout << w << std::endl; // prints 2/3

 //]

Modified: sandbox/big_number/libs/multiprecision/performance/miller_rabin_performance.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/performance/miller_rabin_performance.cpp (original)
+++ sandbox/big_number/libs/multiprecision/performance/miller_rabin_performance.cpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -151,8 +151,8 @@
 std::cout << "Time for mpz_int (native Miller Rabin Test) = " << test_miller_rabin_gmp() << std::endl;
#endif
#ifdef TEST_TOMMATH
- test_miller_rabin<mp_number<boost::multiprecision::tommath_int, false> >("mp_int (no Expression templates)");
- test_miller_rabin<boost::multiprecision::mp_int>("mp_int");
+ test_miller_rabin<mp_number<boost::multiprecision::tommath_int, false> >("tom_int (no Expression templates)");
+ test_miller_rabin<boost::multiprecision::tom_int>("tom_int");
#endif
 mp_get_memory_functions(&alloc_func_ptr, &realloc_func_ptr, &free_func_ptr);
 mp_set_memory_functions(&alloc_func, &realloc_func, &free_func);

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-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -601,18 +601,18 @@
 test<boost::multiprecision::mpq_rational>("mpq_rational", 1024);
#endif
#ifdef TEST_TOMMATH
- test<boost::multiprecision::mp_int>("tommath_int", 128);
- test<boost::multiprecision::mp_int>("tommath_int", 256);
- test<boost::multiprecision::mp_int>("tommath_int", 512);
- test<boost::multiprecision::mp_int>("tommath_int", 1024);
+ test<boost::multiprecision::tom_int>("tommath_int", 128);
+ test<boost::multiprecision::tom_int>("tommath_int", 256);
+ test<boost::multiprecision::tom_int>("tommath_int", 512);
+ test<boost::multiprecision::tom_int>("tommath_int", 1024);
 /*
 //
 // These are actually too slow to test!!!
 //
- test<boost::multiprecision::mp_rational>("mp_rational", 128);
- test<boost::multiprecision::mp_rational>("mp_rational", 256);
- test<boost::multiprecision::mp_rational>("mp_rational", 512);
- test<boost::multiprecision::mp_rational>("mp_rational", 1024);
+ test<boost::multiprecision::tom_rational>("tom_rational", 128);
+ test<boost::multiprecision::tom_rational>("tom_rational", 256);
+ test<boost::multiprecision::tom_rational>("tom_rational", 512);
+ test<boost::multiprecision::tom_rational>("tom_rational", 1024);
 */
#endif
#ifdef TEST_CPP_DEC_FLOAT

Modified: sandbox/big_number/libs/multiprecision/test/test_arithmetic.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_arithmetic.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_arithmetic.cpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -69,7 +69,7 @@

#ifdef TEST_TOMMATH_BOOST_RATIONAL
template<>
-struct number_category<rational<mp_int> > : public mpl::int_<number_kind_rational> {};
+struct number_category<rational<tom_int> > : public mpl::int_<number_kind_rational> {};
#endif
#ifdef TEST_MPZ_BOOST_RATIONAL
template<>
@@ -117,7 +117,7 @@

#ifdef TEST_TOMMATH
template <>
-struct is_twos_complement_integer<boost::multiprecision::mp_int> : public boost::mpl::false_ {};
+struct is_twos_complement_integer<boost::multiprecision::tom_int> : public boost::mpl::false_ {};
#endif

template <class Real>
@@ -362,6 +362,15 @@
 divide_qr(a, b, c, r);
 BOOST_TEST(c == a / b);
 BOOST_TEST(r = a % b);
+ divide_qr(a + 0, b, c, r);
+ BOOST_TEST(c == a / b);
+ BOOST_TEST(r = a % b);
+ divide_qr(a, b+0, c, r);
+ BOOST_TEST(c == a / b);
+ BOOST_TEST(r = a % b);
+ divide_qr(a+0, b+0, c, r);
+ BOOST_TEST(c == a / b);
+ BOOST_TEST(r = a % b);
 BOOST_TEST(integer_modulus(a, 57) == a % 57);
 if(std::numeric_limits<Real>::is_signed)
 {
@@ -1035,11 +1044,11 @@
 test<boost::multiprecision::mpfr_float_50>();
#endif
#ifdef TEST_TOMMATH
- test<boost::multiprecision::mp_int>();
+ test<boost::multiprecision::tom_int>();
 test<boost::multiprecision::mp_number<boost::multiprecision::rational_adapter<boost::multiprecision::tommath_int> > >();
#endif
#ifdef TEST_TOMMATH_BOOST_RATIONAL
- test<boost::rational<boost::multiprecision::mp_int> >();
+ test<boost::rational<boost::multiprecision::tom_int> >();
#endif
#ifdef TEST_MPZ_BOOST_RATIONAL
 test<boost::rational<boost::multiprecision::mpz_int> >();

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-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -120,7 +120,7 @@
test_round_trip<boost::multiprecision::mpz_int>();
#endif
#ifdef TEST_TOMMATH
- test_round_trip<boost::multiprecision::mp_int>();
+ test_round_trip<boost::multiprecision::tom_int>();
#endif
#ifdef TEST_CPP_INT
test_round_trip<boost::multiprecision::mp_number<boost::multiprecision::cpp_int_backend<> > >();

Modified: sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_miller_rabin.cpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -5,6 +5,7 @@

#include <boost/multiprecision/gmp.hpp>
#include <boost/multiprecision/miller_rabin.hpp>
+#include <boost/math/special_functions/prime.hpp>
#include <iostream>
#include <iomanip>
#include "test.hpp"
@@ -20,6 +21,7 @@
 //
 using namespace boost::random;
 using namespace boost::multiprecision;
+
 independent_bits_engine<mt11213b, 256, mpz_int> gen;
 //
 // We must use a different generator for the tests and number generation, otherwise
@@ -28,6 +30,16 @@
 //
 mt19937 gen2;

+ //
+ // Begin by testing the primes in our table as all these should return true:
+ //
+ for(unsigned i = 1; i < boost::math::max_prime; ++i)
+ {
+ BOOST_TEST(miller_rabin_test(mpz_int(boost::math::prime(i)), 25, gen));
+ }
+ //
+ // Now test some random values and compare GMP's native routine with ours.
+ //
 for(unsigned i = 0; i < 10000; ++i)
 {
 mpz_int n = gen();

Modified: sandbox/big_number/libs/multiprecision/test/test_numeric_limits.cpp
==============================================================================
--- sandbox/big_number/libs/multiprecision/test/test_numeric_limits.cpp (original)
+++ sandbox/big_number/libs/multiprecision/test/test_numeric_limits.cpp 2012-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -220,7 +220,7 @@
test<boost::multiprecision::mpfr_float_50>();
#endif
#ifdef TEST_TOMMATH
- test<boost::multiprecision::mp_int>();
+ test<boost::multiprecision::tom_int>();
#endif
#ifdef TEST_CPP_INT
test<boost::multiprecision::cpp_int>();

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-03-22 06:29:30 EDT (Thu, 22 Mar 2012)
@@ -130,8 +130,8 @@
test_round_trip<boost::multiprecision::mp_number<boost::multiprecision::rational_adapter<boost::multiprecision::gmp_int> > >();
#endif
#ifdef TEST_TOMMATH
- test_round_trip<boost::rational<boost::multiprecision::mp_int> >();
- test_round_trip<boost::multiprecision::mp_rational >();
+ test_round_trip<boost::rational<boost::multiprecision::tom_int> >();
+ test_round_trip<boost::multiprecision::tom_rational >();
#endif
return boost::report_errors();
}

Next message: joel_at_[hidden]: "[Boost-commit] svn:boost r77472 - trunk/boost/fusion/include"
Previous message: pbristow_at_[hidden]: "[Boost-commit] svn:boost r77470 - trunk/libs/math/test"

Date view	Thread view	Subject view	Author view

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