Boost-Commit :

Date view	Thread view	Subject view	Author view

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

Next message: afojgo_at_[hidden]: "[Boost-commit] svn:boost r65553 - in sandbox/itl/boost/itl: . concept/interval detail"
Previous message: cppljevans_at_[hidden]: "[Boost-commit] svn:boost r65551 - sandbox/variadic_templates/libs/composite_storage/sandbox/pack"

Author: viboes
Date: 2010-09-23 12:18:44 EDT (Thu, 23 Sep 2010)
New Revision: 65552
URL: http://svn.boost.org/trac/boost/changeset/65552

Log:
Ratio update doc
Binary files modified:
   sandbox/chrono/libs/ratio/doc/ratio.pdf
Text files modified:
   sandbox/chrono/libs/ratio/doc/html/index.html | 458 +++++++++++++++++++++++++++++++++++++++
   sandbox/chrono/libs/ratio/doc/ratio.qbk | 173 +++++++++++++++
   2 files changed, 626 insertions(+), 5 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-23 12:18:44 EDT (Thu, 23 Sep 2010)
@@ -1500,9 +1500,459 @@
 

 Boost.Ratio implementes some simplifications in order to reduce the possibility
- of overflow. The general idea is to use the gcd of some of the possible products
- that can overflow, and simplify before doing the product.
+ of overflow. The general ideas are:
 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ The <code class="computeroutput">num</code> and <code class="computeroutput">den</code> <code class="computeroutput">ratio<></code> fields are normalized.
+ </li>
+<li>
+ Use the gcd of some of the possible products that can overflow, and simplify
+ before doing the product.
+ </li>
+<li>
+ Use some equivalences relations that avoid addition or substraction can
+ overflow or underflow.
+ </li>
+</ul></div>
+
+ Next follows more detail:
+ 
+
+ ratio_add
+ 
+
+ In
+ 
+<pre class="programlisting">(n1/d1)+(n2/d2)=(n1*d2+n2*d1)/(d1*d2)
+</pre>
+
+ either n1*d2+n2*d1 or d1*d2 can overflow.
+ 
+<pre class="programlisting"> ( (n1 * d2) + (n2 * d1) )
+/ (d1 * d2)
+</pre>
+
+ Dividing by gcd(d1,d2) on both num and den
+ 
+<pre class="programlisting"> ( (n1 * (d2/gcd(d1,d2))) +
+ (n2 * (d1/gcd(d1,d2)))
+ )
+/ ((d1 * d2) / gcd(d1,d2))
+</pre>
+
+ Multipliying and diving by gcd(n1,n2) in numerator
+ 
+<pre class="programlisting"> ( ((gcd(n1,n2)*(n1/gcd(n1,n2))) * (d2/gcd(d1,d2))) +
+ ((gcd(n1,n2)*(n2/gcd(n1,n2))) * (d1/gcd(d1,d2)))
+ )
+/ ( (d1 * d2) / gcd(d1,d2) )
+</pre>
+
+ Factorizing gcd(n1,n2)
+ 
+<pre class="programlisting"> ( gcd(n1,n2) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+/ ( (d1 * d2) / gcd(d1,d2) )
+</pre>
+
+ Regrouping
+ 
+<pre class="programlisting"> ( gcd(n1,n2) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+/ ( (d1 / gcd(d1,d2)) * d2 )
+</pre>
+
+ Dividing by (d1 / gcd(d1,d2))
+ 
+<pre class="programlisting"> ( ( gcd(n1,n2) / (d1 / gcd(d1,d2)) ) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+/ d2
+</pre>
+
+ Dividing by d2
+ 
+<pre class="programlisting">( gcd(n1,n2) / (d1 / gcd(d1,d2)) ) *
+( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (</spa
n>d1/gcd(d1,d2))) / d2 )
+</pre>
+
+ This expression correspond to the multiply of two ratios that have less risk
+ of overflow as the initial numerators and denomitators appear now in most
+ of the cases divided by a gcd.
+ 
+
+ For ratio_subtract the reasoning is the same
+ 
+
+ ratio_multiply
+ 
+
+ In
+ 
+<pre class="programlisting">(n1/d1)*(n2/d2)=((n1*n2)/(d1*d2))
+</pre>
+
+ either n1*n2 or d1*d2 can overflow.
+ 
+
+ Dividing by gcc(n1,d2) numerator and denominator
+ 
+<pre class="programlisting"> (((n1/gcc(n1,d2))*n2)
+/ (d1*(d2/gcc(n1,d2))))
+</pre>
+
+ Dividing by gcc(n2,d1)
+ 
+<pre class="programlisting"> ((n1/gcc(n1,d2))*(n2/gcc(n2,d1)))
+/ ((d1/gcc(n2,d1))*(d2/gcc(n1,d2)))
+</pre>
+
+ And now all the initial numerator and denominators have been reduced, avoiding
+ the overflow.
+ 
+
+ For ratio_divide the reasoning is similar.
+ 
+
+ ratio_less
+ 
+
+ In order to evaluate
+ 
+<pre class="programlisting">(n1/d1)<(n2/d2)
+</pre>
+
+ without moving to floating point numbers, two techniques are used:
+ 
+<div class="itemizedlist"><ul type="disc"><li>
+ First compare the sign of the numerators
+ </li></ul></div>
+
+ If sign(n1) < sign(n2) the result is true.
+ 
+
+ If sign(n1) == sign(n2) the result depends on the following after making
+ the numerators positive
+ 
+<div class="itemizedlist"><ul type="disc"><li>
+ When the sign is equal the technique used is to work with integer division
+ and modulo when the signs are equal.
+ </li></ul></div>
+
+ Let call Qi the integer division of ni and di and Mi the modulo of ni and
+ di.
+ 
+<pre class="programlisting">ni = Qi * di + Mi and Mi < di
+</pre>
+
+ Form
+ 
+<pre class="programlisting">((n1*d2)<(d1*n2))
+</pre>
+
+ we get
+ 
+<pre class="programlisting">(((Q1 * d1 + M1)*d2)<(d1*((Q2 * d2 + M2))))
+</pre>
+
+ Developing
+ 
+<pre class="programlisting">((Q1 * d1 * d2)+ (M1*d2))<((d1 * Q2 * d2) + (d1*M2))
+</pre>
+
+ Dividing by d1*d2
+ 
+<pre class="programlisting">Q1 + (M1/d1) < Q2 + (M2/d2)
+</pre>
+
+ If Q1=Q2 the result depends on
+ 
+<pre class="programlisting">(M1/d1) < (M2/d2)
+</pre>
+
+ If M1<code class="literal">=0</code>=M2 the result is false
+ 
+
+ If M1=0 M2!=0 the result is true
+ 
+
+ If M1!<code class="literal">0 M2</code>=0 the result is false
+ 
+
+ If M1!=0 M2!=0 the result depends on
+ 
+<pre class="programlisting">(d2/M2) < (d1/M1)
+</pre>
+
+ If Q1!=Q2, the result of
+ 
+<pre class="programlisting">Q1 + (M1/d1) < Q2 + (M2/d2)
+</pre>
+
+ depends only on Q1 and Q2 as Qi are integers and (Mi/di) <1 because Mi<di.
+ 
+
+ if Q1>Q2, Q1==Q2+k, k>=1
+ 
+<pre class="programlisting">Q2+k + (M1/d1) < Q2 + (M2/d2)
+k + (M1/d1) < (M2/d2)
+k < (M2/d2) - (M1/d1)
+</pre>
+
+ but the difference between two numbers between 0 and 1 can not be greater
+ than 1, so the result is false.
+ 
+
+ if Q2>Q1, Q2==Q1+k, k>=1
+ 
+<pre class="programlisting">Q1 + (M1/d1) < Q1+k + (M2/d2)
+(M1/d1) < k + (M2/d2)
+(M1/d1) - (M2/d2) < k
+</pre>
+
+ which is always true, so the result is true.
+ 
+
+ The following table recapitulates this analisys
+ 
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ 
+ ratio<n1,d1>
+ 
+ </th>
+<th>
+ 
+ ratio<n2,d2>
+ 
+ </th>
+<th>
+ 
+ Q1
+ 
+ </th>
+<th>
+ 
+ Q2
+ 
+ </th>
+<th>
+ 
+ M1
+ 
+ </th>
+<th>
+ 
+ M2
+ 
+ </th>
+<th>
+ 
+ Result
+ 
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ 
+ ratio<n1,d1>
+ 
+ </td>
+<td>
+ 
+ ratio<n2,d2>
+ 
+ </td>
+<td>
+ 
+ Q1
+ 
+ </td>
+<td>
+ 
+ Q2
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ Odd ? Q2 < Q1 : Q1 < Q2
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ ratio<n1,d1>
+ 
+ </td>
+<td>
+ 
+ ratio<n2,d2>
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ 0
+ 
+ </td>
+<td>
+ 
+ 0
+ 
+ </td>
+<td>
+ 
+ false
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ ratio<n1,d1>
+ 
+ </td>
+<td>
+ 
+ ratio<n2,d2>
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ 0
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ true
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ ratio<n1,d1>
+ 
+ </td>
+<td>
+ 
+ ratio<n2,d2>
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ 0
+ 
+ </td>
+<td>
+ 
+ false
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ ratio<n1,d1>
+ 
+ </td>
+<td>
+ 
+ ratio<n2,d2>
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ Q
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ !=0
+ 
+ </td>
+<td>
+ 
+ ratio_less<ratio<d2,M2>, ratio<d1/M1>>
+ 
+ </td>
+</tr>
+</tbody>
+</table></div>
</div>
<div class="section" lang="en"><div class="titlepage"><div><div><h3 class="title">
<a name="boost_ratio.appendices.faq"></a> Appendix D: FAQ
@@ -2331,7 +2781,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="id5013689"></a>
+<a name="id5017727"></a>
 <a href="index.html#boost_ratio.appendices.todo.for_later_releases">For later
 releases</a>
 </h4>
@@ -2343,7 +2793,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 23, 2010 at 05:36:54 GMT</td>
+<td align="left">Last revised: September 23, 2010 at 10:28:54 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox/chrono/libs/ratio/doc/ratio.pdf
==============================================================================
Binary files. No diff available.

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-23 12:18:44 EDT (Thu, 23 Sep 2010)
@@ -1054,7 +1054,178 @@

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 implementes some simplifications in order to reduce the possibility of overflow. The general idea is to use the gcd of some of the possible products that can overflow, and simplify before doing the product.
+Boost.Ratio implementes some simplifications in order to reduce the possibility of overflow. The general ideas are:
+
+* The `num` and `den` `ratio<>` fields are normalized.
+* Use the gcd of some of the possible products that can overflow, and simplify before doing the product.
+* Use some equivalences relations that avoid addition or substraction can overflow or underflow.
+
+
+Next follows more detail:
+
+[*ratio_add]
+
+In
+
+ (n1/d1)+(n2/d2)=(n1*d2+n2*d1)/(d1*d2)
+
+either n1*d2+n2*d1 or d1*d2 can overflow.
+
+ ( (n1 * d2) + (n2 * d1) )
+ / (d1 * d2)
+
+Dividing by gcd(d1,d2) on both num and den
+
+ ( (n1 * (d2/gcd(d1,d2))) +
+ (n2 * (d1/gcd(d1,d2)))
+ )
+ / ((d1 * d2) / gcd(d1,d2))
+
+
+Multipliying and diving by gcd(n1,n2) in numerator
+
+ ( ((gcd(n1,n2)*(n1/gcd(n1,n2))) * (d2/gcd(d1,d2))) +
+ ((gcd(n1,n2)*(n2/gcd(n1,n2))) * (d1/gcd(d1,d2)))
+ )
+ / ( (d1 * d2) / gcd(d1,d2) )
+
+Factorizing gcd(n1,n2)
+
+ ( gcd(n1,n2) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+ / ( (d1 * d2) / gcd(d1,d2) )
+
+Regrouping
+
+ ( gcd(n1,n2) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+ / ( (d1 / gcd(d1,d2)) * d2 )
+
+Dividing by (d1 / gcd(d1,d2))
+
+ ( ( gcd(n1,n2) / (d1 / gcd(d1,d2)) ) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) )
+ )
+ / d2
+
+
+Dividing by d2
+
+ ( gcd(n1,n2) / (d1 / gcd(d1,d2)) ) *
+ ( ((n1/gcd(n1,n2)) * (d2/gcd(d1,d2))) + ((n2/gcd(n1,n2)) * (d1/gcd(d1,d2))) / d2 )
+
+This expression correspond to the multiply of two ratios that have less risk of overflow as the initial numerators and denomitators appear now in most of the cases divided by a gcd.
+
+
+For ratio_subtract the reasoning is the same
+
+[*ratio_multiply]
+
+In
+
+ (n1/d1)*(n2/d2)=((n1*n2)/(d1*d2))
+
+either n1*n2 or d1*d2 can overflow.
+
+Dividing by gcc(n1,d2) numerator and denominator
+
+ (((n1/gcc(n1,d2))*n2)
+ / (d1*(d2/gcc(n1,d2))))
+
+Dividing by gcc(n2,d1)
+
+ ((n1/gcc(n1,d2))*(n2/gcc(n2,d1)))
+ / ((d1/gcc(n2,d1))*(d2/gcc(n1,d2)))
+
+And now all the initial numerator and denominators have been reduced, avoiding the overflow.
+
+For ratio_divide the reasoning is similar.
+
+[*ratio_less]
+
+In order to evaluate
+
+ (n1/d1)<(n2/d2)
+
+without moving to floating point numbers, two techniques are used:
+
+* First compare the sign of the numerators
+
+If sign(n1) < sign(n2) the result is true.
+
+If sign(n1) == sign(n2) the result depends on the following after making the numerators positive
+
+* When the sign is equal the technique used is to work with integer division and modulo when the signs are equal.
+
+Let call Qi the integer division of ni and di and Mi the modulo of ni and di.
+
+ ni = Qi * di + Mi and Mi < di
+
+Form
+
+ ((n1*d2)<(d1*n2))
+
+we get
+
+ (((Q1 * d1 + M1)*d2)<(d1*((Q2 * d2 + M2))))
+
+Developing
+
+ ((Q1 * d1 * d2)+ (M1*d2))<((d1 * Q2 * d2) + (d1*M2))
+
+Dividing by d1*d2
+
+ Q1 + (M1/d1) < Q2 + (M2/d2)
+
+If Q1=Q2 the result depends on
+
+ (M1/d1) < (M2/d2)
+
+If M1==0==M2 the result is false
+
+If M1=0 M2!=0 the result is true
+
+If M1!=0 M2==0 the result is false
+
+If M1!=0 M2!=0 the result depends on
+
+ (d2/M2) < (d1/M1)
+
+If Q1!=Q2, the result of
+
+ Q1 + (M1/d1) < Q2 + (M2/d2)
+
+depends only on Q1 and Q2 as Qi are integers and (Mi/di) <1 because Mi<di.
+
+if Q1>Q2, Q1==Q2+k, k>=1
+
+ Q2+k + (M1/d1) < Q2 + (M2/d2)
+ k + (M1/d1) < (M2/d2)
+ k < (M2/d2) - (M1/d1)
+
+but the difference between two numbers between 0 and 1 can not be greater than 1, so the result is false.
+
+if Q2>Q1, Q2==Q1+k, k>=1
+
+ Q1 + (M1/d1) < Q1+k + (M2/d2)
+ (M1/d1) < k + (M2/d2)
+ (M1/d1) - (M2/d2) < k
+
+which is always true, so the result is true.
+
+The following table recapitulates this analisys
+
+[table
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q1] [Q2] [M1] [M2] [Result]]
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q1] [Q2] [!=0] [!=0] [Odd ? Q2 < Q1 : Q1 < Q2]]
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q] [Q] [0] [0] [false]]
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q] [Q] [0] [!=0] [true]]
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q] [Q] [!=0] [0] [false]]
+ [[ratio<n1,d1>][ratio<n2,d2>] [Q] [Q] [!=0] [!=0] [ratio_less<ratio<d2,M2>, ratio<d1/M1>>]]
+]
+

[endsect]

Next message: afojgo_at_[hidden]: "[Boost-commit] svn:boost r65553 - in sandbox/itl/boost/itl: . concept/interval detail"
Previous message: cppljevans_at_[hidden]: "[Boost-commit] svn:boost r65551 - sandbox/variadic_templates/libs/composite_storage/sandbox/pack"

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