Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r65535 - in sandbox/chrono/libs/ratio/doc: . html
From: vicente.botet_at_[hidden]
Date: 2010-09-22 12:06:18

Next message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r65536 - sandbox/chrono/libs/ratio/doc"
Previous message: garcia_at_[hidden]: "[Boost-commit] svn:boost r65534 - website/public_html/live/community"

Author: viboes
Date: 2010-09-22 12:06:17 EDT (Wed, 22 Sep 2010)
New Revision: 65535
URL: http://svn.boost.org/trac/boost/changeset/65535

Log:
Ratio add implementation section
Text files modified:
   sandbox/chrono/libs/ratio/doc/html/index.html | 52 +++++++++++++++++++++++++++++++++------
   sandbox/chrono/libs/ratio/doc/ratio.qbk | 45 ++++++++++++++++++++++++++-------
   2 files changed, 78 insertions(+), 19 deletions(-)

Modified: sandbox/chrono/libs/ratio/doc/html/index.html
==============================================================================
--- sandbox/chrono/libs/ratio/doc/html/index.html (original)
+++ sandbox/chrono/libs/ratio/doc/html/index.html 2010-09-22 12:06:17 EDT (Wed, 22 Sep 2010)
@@ -242,7 +242,7 @@
 variable. Any help is welcome.
 
<a name="boost_ratio.users_guide.getting_started.install.building_boost_ratio_"></a><h5>
-<a name="id4949164"></a>
+<a name="id4949163"></a>
 <a href="index.html#boost_ratio.users_guide.getting_started.install.building_boost_ratio_">Building
 Boost.Ratio </a>
 </h5>
@@ -309,7 +309,7 @@
 of exception safety as long as the underlying parameters provide it.
 
<a name="boost_ratio.users_guide.getting_started.install.thread_safety_"></a><h5>
-<a name="id4949434"></a>
+<a name="id4949433"></a>
 <a href="index.html#boost_ratio.users_guide.getting_started.install.thread_safety_">Thread
 safety </a>
 </h5>
@@ -1348,7 +1348,7 @@
<div class="toc"><dl>
<dt> Appendix A: History</dt>
<dd><dl>
-<dt>Version 0.2.0, September 20, 2010 </dt>
+<dt>Version 0.2.0, September 22, 2010 </dt>
<dt>Version 0.1.0, September 10, 2010 </dt>
</dl></dd>
<dt> Appendix B: Rationale</dt>
@@ -1371,12 +1371,12 @@
<a name="boost_ratio.appendices.history"></a> Appendix A: History
</h3></div></div></div>
<div class="toc"><dl>
-<dt>Version 0.2.0, September 20, 2010 </dt>
+<dt>Version 0.2.0, September 22, 2010 </dt>
<dt>Version 0.1.0, September 10, 2010 </dt>
</dl></div>
<div class="section" lang="en">
<div class="titlepage"><div><div><h4 class="title">
-<a name="boost_ratio.appendices.history.__version_0_2_0__september_20__2010__"></a>Version 0.2.0, September 20, 2010
+<a name="boost_ratio.appendices.history.__version_0_2_0__september_22__2010__"></a>Version 0.2.0, September 22, 2010
</h4></div></div></div>

 Featurs:
@@ -1481,11 +1481,45 @@
r1 = r2; // compiles as both types are the same.
</pre>
</div>
-<div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title">
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
<a name="boost_ratio.appendices.implementation"></a><a href="index.html#boost_ratio.appendices.implementation" title=" Appendix C: Implementation
 Notes"> Appendix C: Implementation
 Notes</a>
-</h3></div></div></div></div>
+</h3></div></div></div>
+<a name="boost_ratio.appendices.implementation.how_boost_ratio_manage_with_compile_time_rational_arithmetic_overflow_"></a><h4>
+<a name="id5012090"></a>
+ <a href="index.html#boost_ratio.appendices.implementation.how_boost_ratio_manage_with_compile_time_rational_arithmetic_overflow_">How
+ Boost.Ratio manage with compile-time rational arithmetic overflow?</a>
+ </h4>
+
+ When the result is representable, but a simple application of arithmetic
+ rules would result in overflow, e.g. <code class="computeroutput">ratio_multiply<ratio<INTMAX_MAX,2>,ratio<2,INTMAX_MAX>></code> can be reduced to <code class="computeroutput">ratio<1,1></code>, but
+ the direct result of <code class="computeroutput">ratio<INTMAX_MAX*2,INTMAX_MAX*2></code> would
+ result in overflow.
+ 
+
+ Boost.Ratio has implemented some simplifications in order to reduce the possibility
+ of overflow, but these don't take care of all possible cases. For example
+ the preceding example doesn't works now.
+ 
+
+ In order to take care of this case we could apply this kind of simplification:
+ 
+<pre class="programlisting">simplify< fraction<times<A,B>, times<C,D> > > ::=
+ case gcd(A,C) > 1 simplify< fraction<times<A/gcd(A,C),B>, times<C/gcd(A,C),D>>>
+ case gcd(A,D) > 1 simplify< fraction<times<A/gcd(A,D),B>, times<C,D
/gcd(A,D)>>>
+ case gcd(B,C) > 1 simplify< fraction<times<A,B/gcd(B,C)>, times<C/gcd(B,C),D>>>
+ case gcd(B,D) > 1 simplify< fraction<times<A,B/gcd(B,D)>, times<C,D
/gcd(B,D)>>>
+ otherwise ratio<A*B, C*D>
+</pre>
+
+ While this works in some cases, a more general factorization algorithm will
+ be needed to manage with all the cases. Whether we should manage with them
+ is an open question, as the compile times will be increassed strongly to
+ cover some causual cases.
+ 
+</div>
<div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title">
<a name="boost_ratio.appendices.faq"></a> Appendix D: FAQ
</h3></div></div></div></div>
@@ -2313,7 +2347,7 @@
<a name="boost_ratio.appendices.todo"></a> Appendix H: Future plans
</h3></div></div></div>
<a name="boost_ratio.appendices.todo.for_later_releases"></a><h4>
-<a name="id5013493"></a>
+<a name="id5014547"></a>
 <a href="index.html#boost_ratio.appendices.todo.for_later_releases">For later
 releases</a>
 </h4>
@@ -2325,7 +2359,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left">Last revised: September 21, 2010 at 08:49:44 GMT</td>
+<td align="left">Last revised: September 22, 2010 at 16:05:04 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox/chrono/libs/ratio/doc/ratio.qbk
==============================================================================
--- sandbox/chrono/libs/ratio/doc/ratio.qbk (original)
+++ sandbox/chrono/libs/ratio/doc/ratio.qbk 2010-09-22 12:06:17 EDT (Wed, 22 Sep 2010)
@@ -983,7 +983,7 @@
[section:history Appendix A: History]
[/==================================]

-[section [*Version 0.2.0, September 20, 2010] ]
+[section [*Version 0.2.0, September 22, 2010] ]

[*Featurs:]

@@ -1050,17 +1050,42 @@
[/======================================================]
[section:implementation Appendix C: Implementation Notes]

-[/
-How compile-time rational arithmetic has been done in Boost.Ratio when the result is representable, but a simple application of arithmetic rules would result in overflow, e.g. `ratio_multiply<ratio<INTMAX_MAX,2>,ratio<2,INTMAX_MAX>>` can be reduced to `ratio<1,1>`, but the direct result of `ratio<INTMAX_MAX*2,INTMAX_MAX*2>` would result in overflow.
+[heading How Boost.Ratio manage with compile-time rational arithmetic overflow?]
+
+When the result is representable, but a simple application of arithmetic rules would result in overflow, e.g. `ratio_multiply<ratio<INTMAX_MAX,2>,ratio<2,INTMAX_MAX>>` can be reduced to `ratio<1,1>`, but the direct result of `ratio<INTMAX_MAX*2,INTMAX_MAX*2>` would result in overflow.
+
+Boost.Ratio has implemented some simplifications in order to reduce the possibility of overflow, but these don't take care of all possible cases. For example the preceding example doesn't works now.

-The Boost.Ratio implementation try to handle with such overflow if the final result can be representable. In order to do that a simplify operation on the product of intmax_t is used.
+In order to take care of this case we could apply this kind of simplification:

-simplify< times<A,B>, times<C,D> >::value
- if gcd(A,C) > 1 symplify< times<A/gcd(A,C),B>, times<C/gcd(A,C),D> >
- if gcd(A,D) > 1 symplify< times<A/gcd(A,D),B>, times<C,D/gcd(A,D)> >
- if gcd(B,C) > 1 symplify< times<A,B/gcd(B,C)>, times<C/gcd(B,C),D> >
- if gcd(B,D) > 1 symplify< times<A,B/gcd(B,D)>, times<C,D/gcd(B,D)> >
- ratio<A*B, C*D>
+ simplify< fraction<times<A,B>, times<C,D> > > ::=
+ case gcd(A,C) > 1 simplify< fraction<times<A/gcd(A,C),B>, times<C/gcd(A,C),D>>>
+ case gcd(A,D) > 1 simplify< fraction<times<A/gcd(A,D),B>, times<C,D/gcd(A,D)>>>
+ case gcd(B,C) > 1 simplify< fraction<times<A,B/gcd(B,C)>, times<C/gcd(B,C),D>>>
+ case gcd(B,D) > 1 simplify< fraction<times<A,B/gcd(B,D)>, times<C,D/gcd(B,D)>>>
+ otherwise ratio<A*B, C*D>
+
+While this works in some cases, a more general factorization algorithm will be needed to manage with all the cases. Whether we should manage with them is an open question, as the compile times will be increassed strongly to cover some causual cases.
+
+[/
+simplify< fraction<times<A,B>, times<C,D> > > ::=
+simplify< fraction<times<factorize<A>,factorize>,
+ times<factorize<C>,factorize<D>> > > ::=
+simplify< fraction<factors<AxB>,
+ factors<CxD> > > ::=
+simplify< factors<AxB>, factors<CxD> >
+
+simplify< void, B > > ::= ratio< 1, B >
+simplify< A, void > > ::= ratio< A, 1 >
+simplify< factors<N, A>, factors<N, B> > > ::= simplify< A, B >
+
+simplify< factors<N, A>, factors<N+M, B> > > ::=
+let xx = simplify< A, factors<N+M, B> > >
+ ratio<N*xx.num, xx.den>
+
+simplify< factors<N+M, A>, factors<M, B> > > ::=
+let xx = simplify< N+M, factors<M, B> > >
+ ratio<xx.num, M*xx.den>

factorize<0> = 0
factorize<1> = 2

Next message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r65536 - sandbox/chrono/libs/ratio/doc"
Previous message: garcia_at_[hidden]: "[Boost-commit] svn:boost r65534 - website/public_html/live/community"

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