Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r85184 - in trunk: boost/multiprecision boost/multiprecision/detail libs/multiprecision/doc libs/multiprecision/doc/html libs/multiprecision/doc/html/boost_multiprecision/indexes libs/multiprecision/doc/html/boost_multiprecision/ref libs/multiprecision/doc/html/boost_multiprecision/tut libs/multiprecision/test
From: john_at_[hidden]
Date: 2013-08-01 13:50:18

Next message: andrey.semashev_at_[hidden]: "[Boost-commit] svn:boost r85185 - trunk/boost/log/detail"
Previous message: steven_at_[hidden]: "[Boost-commit] svn:boost r85183 - in trunk/tools/build/v2: build tools"

Author: johnmaddock
Date: 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013)
New Revision: 85184
URL: http://svn.boost.org/trac/boost/changeset/85184

Log:
Add support for integer square roots.

Text files modified:
   trunk/boost/multiprecision/detail/default_ops.hpp | 73 ++++++++++++++++++++++++++++++++++++++++
   trunk/boost/multiprecision/gmp.hpp | 5 ++
   trunk/boost/multiprecision/integer.hpp | 53 +++++++++++++++++++++++++++++
   trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s01.html | 13 ++++++
   trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s02.html | 2
   trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s03.html | 2
   trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s04.html | 16 ++++++++
   trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/backendconc.html | 26 ++++++++++++++
   trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/number.html | 38 ++++++++++++++++++++
   trunk/libs/multiprecision/doc/html/boost_multiprecision/tut/gen_int.html | 10 +++++
   trunk/libs/multiprecision/doc/html/index.html | 2
   trunk/libs/multiprecision/doc/multiprecision.qbk | 32 +++++++++++++++++
   trunk/libs/multiprecision/test/test_cpp_int.cpp | 5 ++
   trunk/libs/multiprecision/test/test_native_integer.cpp | 13 +++++++
   14 files changed, 285 insertions(+), 5 deletions(-)

Modified: trunk/boost/multiprecision/detail/default_ops.hpp
==============================================================================
--- trunk/boost/multiprecision/detail/default_ops.hpp Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/boost/multiprecision/detail/default_ops.hpp 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -1116,6 +1116,59 @@
eval_bitwise_xor(val, mask);
}

+template <class B>
+void eval_integer_sqrt(B& s, B& r, const B& x)
+{
+ //
+ // This is slow bit-by-bit integer square root, see for example
+ // http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
+ // There are better methods such as http://hal.inria.fr/docs/00/07/28/54/PDF/RR-3805.pdf
+ // and http://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf which should be implemented
+ // at some point.
+ //
+ typedef typename boost::multiprecision::detail::canonical<unsigned char, B>::type ui_type;
+
+ s = ui_type(0u);
+ if(eval_get_sign(x) == 0)
+ {
+ r = ui_type(0u);
+ return;
+ }
+ int g = eval_msb(x);
+ if(g == 0)
+ {
+ r = ui_type(1);
+ return;
+ }
+
+ B t;
+ r = x;
+ g /= 2;
+ int org_g = g;
+ eval_bit_set(s, g);
+ eval_bit_set(t, 2 * g);
+ eval_subtract(r, x, t);
+ --g;
+ int msbr = eval_msb(r);
+ do
+ {
+ if(msbr >= org_g + g + 1)
+ {
+ t = s;
+ eval_left_shift(t, g + 1);
+ eval_bit_set(t, 2 * g);
+ if(t.compare(r) <= 0)
+ {
+ eval_bit_set(s, g);
+ eval_subtract(r, t);
+ msbr = eval_msb(r);
+ }
+ }
+ --g;
+ }
+ while(g >= 0);
+}
+
//
// These have to implemented by the backend, declared here so that our macro generated code compiles OK.
//
@@ -1465,6 +1518,26 @@
}
#endif

+template <class B, expression_template_option ExpressionTemplates>
+inline typename enable_if_c<number_category::value == number_kind_integer, number<B, ExpressionTemplates> >::type
+ sqrt(const number<B, ExpressionTemplates>& x)
+{
+ using default_ops::eval_integer_sqrt;
+ number<B, ExpressionTemplates> s, r;
+ eval_integer_sqrt(s.backend(), r.backend(), x.backend());
+ return s;
+}
+
+template <class B, expression_template_option ExpressionTemplates>
+inline typename enable_if_c<number_category::value == number_kind_integer, number<B, ExpressionTemplates> >::type
+ sqrt(const number<B, ExpressionTemplates>& x, number<B, ExpressionTemplates>& r)
+{
+ using default_ops::eval_integer_sqrt;
+ number<B, ExpressionTemplates> s;
+ eval_integer_sqrt(s.backend(), r.backend(), x.backend());
+ return s;
+}
+
#define UNARY_OP_FUNCTOR(func, category)\
namespace detail{\
template <class Backend> \

Modified: trunk/boost/multiprecision/gmp.hpp
==============================================================================
--- trunk/boost/multiprecision/gmp.hpp Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/boost/multiprecision/gmp.hpp 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -1592,6 +1592,11 @@
mpz_lcm_ui(result.data(), a.data(), std::abs(b));
}

+inline void eval_integer_sqrt(gmp_int& s, gmp_int& r, const gmp_int& x)
+{
+ mpz_sqrtrem(s.data(), r.data(), x.data());
+}
+
inline unsigned eval_lsb(const gmp_int& val)
{
int c = eval_get_sign(val);

Modified: trunk/boost/multiprecision/integer.hpp
==============================================================================
--- trunk/boost/multiprecision/integer.hpp Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/boost/multiprecision/integer.hpp 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -182,6 +182,59 @@
return val;
}

+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, Integer>::type sqrt(const Integer& x, Integer& r)
+{
+ //
+ // This is slow bit-by-bit integer square root, see for example
+ // http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
+ // There are better methods such as http://hal.inria.fr/docs/00/07/28/54/PDF/RR-3805.pdf
+ // and http://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf which should be implemented
+ // at some point.
+ //
+ Integer s = 0;
+ if(x == 0)
+ {
+ r = 0;
+ return s;
+ }
+ int g = msb(x);
+ if(g == 0)
+ {
+ r = 1;
+ return s;
+ }
+
+ Integer t;
+ r = x;
+ g /= 2;
+ bit_set(s, g);
+ bit_set(t, 2 * g);
+ r = x - t;
+ --g;
+ do
+ {
+ t = s;
+ t <<= g + 1;
+ bit_set(t, 2 * g);
+ if(t <= r)
+ {
+ bit_set(s, g);
+ r -= t;
+ }
+ --g;
+ }
+ while(g >= 0);
+ return s;
+}
+
+template <class Integer>
+typename enable_if_c<is_integral<Integer>::value, Integer>::type sqrt(const Integer& x)
+{
+ Integer r;
+ return sqrt(x, r);
+}
+
}} // namespaces

#endif

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s01.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s01.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s01.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -24,7 +24,7 @@
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
-<a name="id1033084"></a>Function Index</h3></div></div></div>
+<a name="id991805"></a>Function Index</h3></div></div></div>
<a class="link" href="s01.html#idx_id_0">A</a> <a class="link" href="s01.html#idx_id_1">B</a> <a class="link" href="s01.html#idx_id_2">C</a> <a class="link" href="s01.html#idx_id_3">D</a> <a class="link" href="s01.html#idx_id_4">E</a> <a class="link" href="s01.html#idx_id_5">F</a> <a class="link" href="s01.html#idx_id_7">I</a> <a class="link" href="s01.html#idx_id_8">L</a> <a class="link" href="s01.html#idx_id_9">M</a> <a class="link" href="s01.html#idx_id_11">O</a> <a class="link" href="s01.html#idx_id_12">P</a> <a class="link" href="s01.html#idx_id_13">R</a> <a class="link" href="s01.html#idx_id_14">S</a> <a class="link" href="s01.html#idx_id_15">T</a> <a class="link" href="s01.html#idx_id_17">V</a> <a class="link" href="s01.html#idx_id_18">Z</a>
<div class="variablelist"><dl class="variablelist">
<dt>
@@ -257,6 +257,10 @@
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
</li>
<li class="listitem" style="list-style-type: none">
+eval_integer_sqrt
+<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
+</li>
+<li class="listitem" style="list-style-type: none">
eval_is_zero
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
</li>
@@ -537,6 +541,13 @@
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../tut/interval/mpfi.html" title="mpfi_float">mpfi_float</a></li></ul></div>
</li>
<li class="listitem" style="list-style-type: none">
+sqrt
+<div class="index"><ul class="index" style="list-style-type: none; ">
+<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">Generic Integer Operations</a></li>
+<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">number</a></li>
+</ul></div>
+</li>
+<li class="listitem" style="list-style-type: none">
str
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">number</a></li></ul></div>
</li>

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s02.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s02.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s02.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -24,7 +24,7 @@
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
-<a name="id1037364"></a>Class Index</h3></div></div></div>
+<a name="id995984"></a>Class Index</h3></div></div></div>
<a class="link" href="s02.html#idx_id_21">C</a> <a class="link" href="s02.html#idx_id_22">D</a> <a class="link" href="s02.html#idx_id_23">E</a> <a class="link" href="s02.html#idx_id_24">F</a> <a class="link" href="s02.html#idx_id_25">G</a> <a class="link" href="s02.html#idx_id_26">I</a> <a class="link" href="s02.html#idx_id_27">L</a> <a class="link" href="s02.html#idx_id_28">M</a> <a class="link" href="s02.html#idx_id_29">N</a> <a class="link" href="s02.html#idx_id_34">T</a>
<div class="variablelist"><dl class="variablelist">
<dt>

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s03.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s03.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s03.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -24,7 +24,7 @@
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
-<a name="id1037883"></a>Typedef Index</h3></div></div></div>
+<a name="id997596"></a>Typedef Index</h3></div></div></div>
<a class="link" href="s03.html#idx_id_40">C</a> <a class="link" href="s03.html#idx_id_43">F</a> <a class="link" href="s03.html#idx_id_45">I</a> <a class="link" href="s03.html#idx_id_46">L</a> <a class="link" href="s03.html#idx_id_47">M</a> <a class="link" href="s03.html#idx_id_52">S</a> <a class="link" href="s03.html#idx_id_53">T</a> <a class="link" href="s03.html#idx_id_54">U</a>
<div class="variablelist"><dl class="variablelist">
<dt>

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s04.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s04.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/indexes/s04.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -23,7 +23,7 @@
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
-<a name="id1041139"></a>Index</h3></div></div></div>
+<a name="id998666"></a>Index</h3></div></div></div>
<a class="link" href="s04.html#idx_id_57">A</a> <a class="link" href="s04.html#idx_id_58">B</a> <a class="link" href="s04.html#idx_id_59">C</a> <a class="link" href="s04.html#idx_id_60">D</a> <a class="link" href="s04.html#idx_id_61">E</a> <a class="link" href="s04.html#idx_id_62">F</a> <a class="link" href="s04.html#idx_id_63">G</a> <a class="link" href="s04.html#idx_id_64">I</a> <a class="link" href="s04.html#idx_id_65">L</a> <a class="link" href="s04.html#idx_id_66">M</a> <a class="link" href="s04.html#idx_id_67">N</a> <a class="link" href="s04.html#idx_id_68">O</a> <a class="link" href="s04.html#idx_id_69">P</a> <a class="link" href="s04.html#idx_id_70">R</a> <a class="link" href="s04.html#idx_id_71">S</a> <a class="link" href="s04.html#idx_id_72">T</a> <a class="link" href="s04.html#idx_id_73">U</a> <a class="link" href="s04.html#idx_id_74">V</a> <a class="link" href="s04.html#idx_id_75">Z</a>
<div class="variablelist"><dl class="variablelist">
<dt>
@@ -404,6 +404,10 @@
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
</li>
<li class="listitem" style="list-style-type: none">
+eval_integer_sqrt
+<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
+</li>
+<li class="listitem" style="list-style-type: none">
eval_is_zero
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">Optional Requirements on the Backend Type</a></li></ul></div>
</li>
@@ -564,6 +568,7 @@
<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">multiply</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">powm</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">precision</a></li>
+<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">sqrt</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">subtract</a></li>
</ul></div>
</li>
@@ -952,6 +957,7 @@
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">powm</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">precision</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">round</a></li>
+<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">sqrt</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">str</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">subtract</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">swap</a></li>
@@ -996,6 +1002,7 @@
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_get_sign</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_gt</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_increment</a></li>
+<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_integer_sqrt</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_is_zero</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_lcm</a></li>
<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/backendconc.html#boost_multiprecision.ref.backendconc.optional_requirements_on_the_backend_type" title="Table 1.5. Optional Requirements on the Backend Type">eval_left_shift</a></li>
@@ -1084,6 +1091,13 @@
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../tut/interval/mpfi.html" title="mpfi_float">mpfi_float</a></li></ul></div>
</li>
<li class="listitem" style="list-style-type: none">
+sqrt
+<div class="index"><ul class="index" style="list-style-type: none; ">
+<li class="listitem" style="list-style-type: none"><a class="link" href="../tut/gen_int.html" title="Generic Integer Operations">Generic Integer Operations</a></li>
+<li class="listitem" style="list-style-type: none"><a class="link" href="../ref/number.html" title="number">number</a></li>
+</ul></div>
+</li>
+<li class="listitem" style="list-style-type: none">
static_mpfr_float_100
<div class="index"><ul class="index" style="list-style-type: none; "><li class="listitem" style="list-style-type: none"><a class="link" href="../tut/floats/mpfr_float.html" title="mpfr_float">mpfr_float</a></li></ul></div>
</li>

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/backendconc.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/backendconc.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/backendconc.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -3262,6 +3262,32 @@
<tr>
<td>
 
+ <code class="computeroutput">eval_integer_sqrt(b, cb, b2)</code>
+ 
+ </td>
+<td>
+ 
+ <code class="computeroutput">void</code>
+ 
+ </td>
+<td>
+ 
+ Sets <code class="computeroutput">b</code> to the largest
+ integer which when squared is less than <code class="computeroutput">cb</code>,
+ also sets <code class="computeroutput">b2</code> to
+ the remainder, ie to cb - b2. The default
+ version of this function is synthesised from other operations above.
+ 
+ </td>
+<td>
+ 
+  
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
 Sign manipulation:
 
 </td>

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/number.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/number.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/ref/number.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -176,8 +176,13 @@
struct is_number_expression;

// Integer specific functions:
+unmentionable-expression-template-type gcd(const number-or-expression-template-type&, const number-or-expression-template-type&);
+unmentionable-expression-template-type lcm(const number-or-expression-template-type&, const number-or-expression-template-type&);
unmentionable-expression-template-type pow(const number-or-expression-template-type&, unsigned);
unmentionable-expression-template-type powm(const number-or-expression-template-type& b, const number-or-expression-template-type& p, const number-or-expression-template-type& m);
+unmentionable-expression-template-type sqrt(const number-or-expression-template-type&);
+template <class Backend, expression_template_option ExpressionTemplates>
+number<Backend, EXpressionTemplates> sqrt(const number-or-expression-template-type&, number<Backend, EXpressionTemplates>&);
template <class Backend, expression_template_option ExpressionTemplates>
void divide_qr(const number-or-expression-template-type& x, const number-or-expression-template-type& y,
 number<Backend, ExpressionTemplates>& q, number<Backend, ExpressionTemplates>& r);
@@ -1110,6 +1115,20 @@
 when the algorithm requires it. Versions overloaded for built in integer
 types return that integer type rather than an expression template.
 
+<pre class="programlisting">unmentionable-expression-template-type gcd(const number-or-expression-template-type& a, const number-or-expression-template-type& b);
+</pre>
+
+ Returns the largest integer <code class="computeroutput">x</code>
+ that divides both <code class="computeroutput">a</code> and
+ <code class="computeroutput">b</code>.
+ 
+<pre class="programlisting">unmentionable-expression-template-type lcm(const number-or-expression-template-type& a, const number-or-expression-template-type& b);
+</pre>
+
+ Returns the smallest integer <code class="computeroutput">x</code>
+ that is divisible by both <code class="computeroutput">a</code>
+ and <code class="computeroutput">b</code>.
+ 
<pre class="programlisting">unmentionable-expression-template-type pow(const number-or-expression-template-type& b, unsigned p);
</pre>

@@ -1127,6 +1146,25 @@
 Returns bp mod m as an expression template. Fixed precision
 types are promoted internally to ensure accuracy.
 
+<pre class="programlisting">unmentionable-expression-template-type sqrt(const number-or-expression-template-type& a);
+</pre>
+
+ Returns the largest integer <code class="computeroutput">x</code>
+ such that <code class="computeroutput">x *
+ x <
+ a</code>.
+ 
+<pre class="programlisting">template <class Backend, expression_template_option ExpressionTemplates>
+number<Backend, EXpressionTemplates> sqrt(const number-or-expression-template-type& a, number<Backend, EXpressionTemplates>& r);
+</pre>
+
+ Returns the largest integer <code class="computeroutput">x</code>
+ such that <code class="computeroutput">x *
+ x <
+ a</code>, and sets the remainder <code class="computeroutput">r</code> such that <code class="computeroutput">r
+ = a - x *
+ x</code>.
+ 
<pre class="programlisting">template <class Backend, expression_template_option ExpressionTemplates>
void divide_qr(const number-or-expression-template-type& x, const number-or-expression-template-type& y,
 number<Backend, ExpressionTemplates>& q, number<Backend, ExpressionTemplates>& r);

Modified: trunk/libs/multiprecision/doc/html/boost_multiprecision/tut/gen_int.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/boost_multiprecision/tut/gen_int.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/boost_multiprecision/tut/gen_int.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -144,6 +144,16 @@

Flips the <code class="computeroutput">index</code> bit in <code class="computeroutput">val</code>.

+<pre class="programlisting">template <class Integer>
+Integer sqrt(const Integer& x);
+template <class Integer>
+Integer sqrt(const Integer& x, Integer& r);
+</pre>
+
+ Returns the integer square root <code class="computeroutput">s</code>
+ of x and sets <code class="computeroutput">r</code> to the remainder
+ x - s2.
+ 
<pre class="programlisting">template <class Engine>
bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials, Engine& gen);
bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials);

Modified: trunk/libs/multiprecision/doc/html/index.html
==============================================================================
--- trunk/libs/multiprecision/doc/html/index.html Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/html/index.html 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -147,7 +147,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left">Last revised: July 08, 2013 at 12:29:44 GMT</td>
+<td align="left">Last revised: August 01, 2013 at 15:58:28 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: trunk/libs/multiprecision/doc/multiprecision.qbk
==============================================================================
--- trunk/libs/multiprecision/doc/multiprecision.qbk Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/doc/multiprecision.qbk 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -1828,6 +1828,13 @@

Flips the `index` bit in `val`.

+ template <class Integer>
+ Integer sqrt(const Integer& x);
+ template <class Integer>
+ Integer sqrt(const Integer& x, Integer& r);
+
+Returns the integer square root `s` of x and sets `r` to the remainder ['x - s[super 2]].
+
 template <class Engine>
 bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials, Engine& gen);
 bool miller_rabin_test(const number-or-expression-template-type& n, unsigned trials);
@@ -1991,8 +1998,13 @@
 struct is_number_expression;

 // Integer specific functions:
+ ``['unmentionable-expression-template-type]`` gcd(const ``['number-or-expression-template-type]``&, const ``['number-or-expression-template-type]``&);
+ ``['unmentionable-expression-template-type]`` lcm(const ``['number-or-expression-template-type]``&, const ``['number-or-expression-template-type]``&);
 ``['unmentionable-expression-template-type]`` pow(const ``['number-or-expression-template-type]``&, unsigned);
 ``['unmentionable-expression-template-type]`` powm(const ``['number-or-expression-template-type]``& b, const ``['number-or-expression-template-type]``& p, const ``['number-or-expression-template-type]``& m);
+ ``['unmentionable-expression-template-type]`` sqrt(const ``['number-or-expression-template-type]``&);
+ template <class Backend, expression_template_option ExpressionTemplates>
+ number<Backend, EXpressionTemplates> sqrt(const ``['number-or-expression-template-type]``&, number<Backend, EXpressionTemplates>&);
 template <class Backend, expression_template_option ExpressionTemplates>
 void divide_qr(const ``['number-or-expression-template-type]``& x, const ``['number-or-expression-template-type]``& y,
 number<Backend, ExpressionTemplates>& q, number<Backend, ExpressionTemplates>& r);
@@ -2387,6 +2399,14 @@
requires it. Versions overloaded for built in integer types return that integer type rather than an expression
template.

+ ``['unmentionable-expression-template-type]`` gcd(const ``['number-or-expression-template-type]``& a, const ``['number-or-expression-template-type]``& b);
+
+Returns the largest integer `x` that divides both `a` and `b`.
+
+ ``['unmentionable-expression-template-type]`` lcm(const ``['number-or-expression-template-type]``& a, const ``['number-or-expression-template-type]``& b);
+
+Returns the smallest integer `x` that is divisible by both `a` and `b`.
+
 ``['unmentionable-expression-template-type]`` pow(const ``['number-or-expression-template-type]``& b, unsigned p);

Returns ['b[super p]] as an expression template. Note that this function should be used with extreme care as the result can grow so
@@ -2398,6 +2418,15 @@

Returns ['b[super p] mod m] as an expression template. Fixed precision types are promoted internally to ensure accuracy.

+ ``['unmentionable-expression-template-type]`` sqrt(const ``['number-or-expression-template-type]``& a);
+
+Returns the largest integer `x` such that `x * x < a`.
+
+ template <class Backend, expression_template_option ExpressionTemplates>
+ number<Backend, EXpressionTemplates> sqrt(const ``['number-or-expression-template-type]``& a, number<Backend, EXpressionTemplates>& r);
+
+Returns the largest integer `x` such that `x * x < a`, and sets the remainder `r` such that `r = a - x * x`.
+
 template <class Backend, expression_template_option ExpressionTemplates>
 void divide_qr(const ``['number-or-expression-template-type]``& x, const ``['number-or-expression-template-type]``& y,
 number<Backend, ExpressionTemplates>& q, number<Backend, ExpressionTemplates>& r);
@@ -3097,6 +3126,9 @@
 The type of `a` shall be listed in one of the type lists
 `B::signed_types`, `B::unsigned_types`.
 The default version of this function is synthesised from other operations above.][[space]]]
+[[`eval_integer_sqrt(b, cb, b2)`][`void`][Sets `b` to the largest integer which when squared is less than `cb`, also
+ sets `b2` to the remainder, ie to ['cb - b[super 2]].
+ The default version of this function is synthesised from other operations above.][[space]]]

[[['Sign manipulation:]]]
[[`eval_abs(b, cb)`][`void`][Set `b` to the absolute value of `cb`.

Modified: trunk/libs/multiprecision/test/test_cpp_int.cpp
==============================================================================
--- trunk/libs/multiprecision/test/test_cpp_int.cpp Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/test/test_cpp_int.cpp 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -190,6 +190,11 @@
       BOOST_CHECK_EQUAL(mpz_int(lcm(-c, -d)).str(), test_type(lcm(-c1, -d1)).str());
       BOOST_CHECK_EQUAL(mpz_int(gcd(a, -b)).str(), test_type(gcd(a1, -b1)).str());
       BOOST_CHECK_EQUAL(mpz_int(lcm(c, -d)).str(), test_type(lcm(c1, -d1)).str());
+ // Integer sqrt:
+ mpz_int r;
+ test_type r1;
+ BOOST_CHECK_EQUAL(sqrt(a, r).str(), sqrt(a1, r1).str());
+ BOOST_CHECK_EQUAL(r.str(), r1.str());
    }

    void t3()

Modified: trunk/libs/multiprecision/test/test_native_integer.cpp
==============================================================================
--- trunk/libs/multiprecision/test/test_native_integer.cpp Thu Aug 1 11:49:37 2013 (r85183)
+++ trunk/libs/multiprecision/test/test_native_integer.cpp 2013-08-01 13:50:17 EDT (Thu, 01 Aug 2013) (r85184)
@@ -68,6 +68,19 @@
 BOOST_CHECK_EQUAL(integer_modulus(i, j), i % j);
 I p = 456;
 BOOST_CHECK_EQUAL(powm(i, p, j), pow(cpp_int(i), static_cast<unsigned>(p)) % j);
+
+ for(I i = 0; i < (2 < 8) - 1; ++i)
+ {
+ I j = i * i;
+ I s, r;
+ s = sqrt(j, r);
+ BOOST_CHECK_EQUAL(s, i);
+ BOOST_CHECK(r == 0);
+ j += 3;
+ s = sqrt(i, r);
+ BOOST_CHECK_EQUAL(s, i);
+ BOOST_CHECK(r == 3);
+ }
}

int main()

Next message: andrey.semashev_at_[hidden]: "[Boost-commit] svn:boost r85185 - trunk/boost/log/detail"
Previous message: steven_at_[hidden]: "[Boost-commit] svn:boost r85183 - in trunk/tools/build/v2: build tools"

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