...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Fixes:
Features:
Fixes:
Test:
Current N3000 doesn't allows to copy-construct or assign ratio instances of ratio classes having the same normalized form.
This simple example
ratio
<1,3> r1;ratio
<3,9> r2; r1 = r2; // (1)
fails to compile in (1). Other example
ratio
<1,3> r1;ratio_subtract
<ratio
<2,3>,ratio
<1,3> > r2=r1; // (2)
The type of
could be ratio_subtract
<ratio
<2,3>,ratio
<1,3> >
so the compilation could fail in (2).
It could also be ratio
<3,9>ratio
<1,3> and the compilation
succeeds.
The current resolution of issue LWG 1281 acknowledges the need for a nested type typedef, so Boost.Ratio is tracking the likely final version of std::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.
Boost.Ratio implements some simplifications in order to reduce the possibility of overflow. The general ideas are:
num
and den
ratio<>
fields are normalized.
The following subsections cover each case in 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 denominators 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:
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
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
ratio<n1,d1> |
ratio<n2,d2> |
Q1 |
Q2 |
M1 |
M2 |
Result |
---|---|---|---|---|---|---|
ratio<n1,d1> |
ratio<n2,d2> |
Q1 |
Q2 |
!=0 |
!=0 |
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>> |
The library code was derived from Howard Hinnant's time2_demo
prototype. Many thanks to Howard for making his code available under the
Boost license. The original code was modified by Beman Dawes to conform to
Boost conventions.
time2_demo
contained this
comment:
Much thanks to Andrei Alexandrescu, Walter Brown, Peter Dimov, Jeff Garland, Terry Golubiewski, Daniel Krugler, Anthony Williams.
Howard Hinnant, who is the real author of the library, has provided valuable
feedback and suggestions during the development of the library. In particular,
The ratio_io.hpp source has been adapted from the experimental header <ratio_io>
from Howard Hinnant.
The acceptance review of Boost.Ratio took place between October 2nd and 11th 2010. Many thanks to Anthony Williams, the review manager, and to all the reviewers: Bruno Santos, Joel Falcou, Robert Stewart, Roland Bock, Tom Tan and Paul A. Bristol.
Thanks to Andrew Chinoff and Paul A. Bristol for his help polishing the documentation.
In order to test you need to run
bjam libs/ratio/test
You can also run a specific suite of test by doing
cd libs/chrono/test bjam ratio
Name |
kind |
Description |
Result |
Ticket |
---|---|---|---|---|
typedefs.pass |
run |
check the num/den are correct for the predefined typedefs |
Pass |
# |
ratio.pass |
run |
check the num/den are correctly simplified |
Pass |
# |
ratio1.fail |
compile-fails |
The template argument D shall not be zero |
Pass |
# |
ratio2.fail |
compile-fails |
the absolute values of the template arguments N and D shall be representable by type intmax_t |
Pass |
# |
ratio3.fail |
compile-fails |
the absolute values of the template arguments N and D shall be representable by type intmax_t |
Pass |
# |
Name |
kind |
Description |
Result |
Ticket |
---|---|---|---|---|
ratio_equal.pass |
run |
check ratio_equal metafunction class |
Pass |
# |
ratio_not_equal.pass |
run |
check ratio_not_equal metafunction class |
Pass |
# |
ratio_less.pass |
run |
check ratio_less metafunction class |
Pass |
# |
ratio_less_equal.pass |
run |
check ratio_less_equal metafunction class |
Pass |
# |
ratio_greater.pass |
run |
check ratio_greater metafunction class |
Pass |
# |
ratio_greater_equal.pass |
run |
check ratio_greater_equal metafunction class |
Pass |
# |
Name |
kind |
Description |
Result |
Ticket |
---|---|---|---|---|
ratio_add.pass |
run |
check ratio_add metafunction class |
Pass |
# |
ratio_subtract.pass |
run |
check ratio_subtract metafunction class |
Pass |
# |
ratio_multiply.pass |
run |
check ratio_multiply metafunction class |
Pass |
# |
ratio_divide.pass |
run |
check ratio_divide metafunction class |
Pass |
# |
ratio_add.fail |
compile-fails |
check ratio_add overflow metafunction class |
Pass |
# |
ratio_subtract.fail |
compile-fails |
check ratio_subtract underflow metafunction class |
Pass |
# |
ratio_multiply.fail |
compile-fails |
check ratio_multiply overflow metafunction class |
Pass |
# |
ratio_divide.fail |
compile-fails |
check ratio_divide overflow metafunction class |
Pass |
# |
Ticket |
Description |
Resolution |
State |
---|---|---|---|
1 |
result of metafunctions ratio_multiply and ratio_divide were not normalized ratios. |
Use of the nested ratio typedef type on ratio arithmetic operations. |
Closed |
2 |
INTMAX_C is not always defined. |
Replace INTMAX_C by BOOST_INTMAX_C until boost/cstdint.hpp ensures INTMAX_C is always defined. |
Closed |
3 |
MSVC reports a warning instead of an error when there is an integral constant overflow. |
manage with MSVC reporting a warning instead of an error when there is an integral constant overflow. |
Closed |
4 |
ration_less overflow on cases where it can be avoided. |
Change the algorithm as implemented in libc++. |
Closed |