Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Appendices

Appendix A: History
Appendix B: Rationale
Appendix C: Implementation Notes
Appendix D: FAQ
Appendix E: Acknowledgements
Appendix F: Tests
Appendix G: Tickets
Appendix H: Future Plans

Fixes:

  • #7075 Workaround for error: the type of partial specialization template parameter constant "n1" depends on another template parameter.

Fixes:

  • #6498 boost::ratio won't compile with default settings.

Features:

  • Added MPL Rational Constant and the associated numeric metafunction specializations.
  • Moved ratio to trunk.
  • Documentation revision.

Fixes:

  • Removal of LLVM adapted files due to incompatible License issue.

Features:

  • Added ratio_string traits.

Fixes:

  • ratio_less overflow avoided following the algorithm from libc++.

Test:

  • A more complete test has been included adapted from the test of from libc++/ratio.

Features:

  • Ratio has been extracted from Boost.Chrono.
Why ratio needs CopyConstruction and Assignment from ratios having the same normalized form

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 ratio_subtract<ratio<2,3>,ratio<1,3> > could be ratio<3,9> so the compilation could fail in (2). It could also be ratio<1,3> and the compilation succeeds.

Why ratio needs the nested normalizer typedef type

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.

How does Boost.Ratio try to avoid 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 implements 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 subtraction that can overflow or underflow.

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:

  • 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

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

For later releases
  • Use template aliases on compiler providing it.
  • Implement multiple arguments ratio arithmetic.

PrevUpHomeNext