Appendices

| Home | Libraries | People | FAQ | More

## Appendices

### Appendix A: History

#### Version 1.0.1, Jan 8, 2011

- Added MPL Rational Constant and the associated numeric metafunction specializations.

#### Version 1.0.0, Jan 2, 2011

- Moved ratio to trunk.
- Documentation revision.

#### Version 0.2.1, September 27, 2010

Fixes:

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

#### Version 0.2.0, September 22, 2010

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.

#### Version 0.1.0, September 10, 2010

Features:

- Ratio has been extracted from Boost.Chrono.

### Appendix B: Rationale

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

### Appendix C: Implementation Notes

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

### Appendix D: FAQ

### Appendix E: Acknowledgements

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.

### Appendix F: Tests

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

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

#### `comparison`

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

#### `arithmetic`

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

### Appendix G: Tickets

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

### Appendix H: Future Plans

##### For later releases

- Use template aliases on compiler providing it.
- Implement multiple arguments ratio arithmetic.