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 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

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

For later releases