Making sense of STL <ratio>

Note: this is just one article in a series discussing the STL headers. In particular, reading the first article in the series might be helpful, as it introduces a bunch of standard techniques.

Today we are going to look at something rather different: handling integer fractions in templates, courtesy of ratio. We start up with the usual boilerplate stuff:

// ratio standard header
#pragma once
#ifndef _RATIO_
#define _RATIO_
#ifndef RC_INVOKED
#include <stdint.h>
#include <type_traits>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)
 #pragma push_macro("new")
 #undef new

_STD_BEGIN

Nothing unsurprising, if you've read the previous installments of this series.

Getting the absolute value in a template

Let's see what is next:

// CLASS TEMPLATE _Abs
template<intmax_t _Val> struct _Abs
{
    // computes absolute value of _Val
    static const intmax_t value = _Val < 0 ? -_Val : _Val;
};

A brief recap of the basics: the template evalutes the absolute value of a numeric input at compiletime. This is possible, because _Val is known at compiletime, and it is assigned to a static const value, and because a different expansion is done for every different input value. For example, if you call _Abs<-1>, the compiler either has already expanded that earlier, then it is reusing that earlier value, or it has not, then it creates a unique expansion of the struct, with a unique static _Abs<-1>::value.

The only thing slightly interesting here could be intmax_t, which I had forgotten about: it is defined in stdint as 'the integer type with the maximum width supported'.

How to detect overflow on multiplication in a template

OK, the next three templates really need to go together:

// CLASS TEMPLATE _Safe_mult
template<intmax_t _Ax, intmax_t _Bx, bool _Good> struct _Safe_multX
{
    // computes _Ax * _Bx without overflow
    static const intmax_t value = _Ax * _Bx;
};

template<intmax_t _Ax, intmax_t _Bx> struct _Safe_multX<_Ax, _Bx, false>
{
    // _Ax * _Bx would overflow
    static_assert(_Always_false<_Safe_multX>::value, "integer arithmetic overflow");
};

template<intmax_t _Ax, intmax_t _Bx> struct _Safe_mult
{
    // computes _Ax * _Bx, forbids overflow
    static const intmax_t value = _Safe_multX<_Ax, _Bx, (_Abs<_Ax>::value <= INTMAX_MAX / _Abs<_Bx>::value)>::value;
};

This does take a bit of thinking, let's start with the easy bits first.

Time for a bit of anticlimax, adressing a small part missing in the above:

template<intmax_t _Ax> struct _Safe_mult<_Ax, 0>
{
    // computes _Ax * 0, avoids division by 0
    static const intmax_t value = 0;
};

OK, that is easy: if _Bx is 0, then the result of the product will always be 0 as well, and we avoid dividing by zero in the "overflow check".

Getting the sign of a numeric value, in a template

// CLASS TEMPLATE _Sign_of
template<intmax_t _Val> struct _Sign_of
{   
    // computes sign of _Val
    static const intmax_t value = _Val < 0 ? -1 : 1;
};

That was too easy, right? It should have been grouped together with _Abs, because conceptually the two are very similar.

How to detect overflow on addition of two numeric values in a template

// CLASS TEMPLATE _Safe_add
template<intmax_t _Ax, intmax_t _Bx, bool _Good, bool _Also_good> struct _Safe_addX
{
    // computes _Ax + _Bx without overflow
    static const intmax_t value = _Ax + _Bx;
};

template<intmax_t _Ax, intmax_t _Bx> struct _Safe_addX<_Ax, _Bx, false, false>
{
    // _Ax + _Bx would overflow
    static_assert(_Always_false<_Safe_addX>::value, "integer arithmetic overflow");
};

template<intmax_t _Ax, intmax_t _Bx> struct _Safe_add
{
    // computes _Ax + _Bx, forbids overflow
    static const intmax_t value = _Safe_addX<_Ax, _Bx,
        _Sign_of<_Ax>::value != _Sign_of<_Bx>::value,
        (_Abs<_Ax>::value <= INTMAX_MAX - _Abs<_Bx>::value)>::value;
};

With the information from above, this becomes really simple now:

The GCD (Greatest Common Denominator), in templates, without overflow

// CLASS TEMPLATE _Gcd
template<intmax_t _Ax, intmax_t _Bx> struct _GcdX
{
    // computes greatest common divisor of _Ax and _Bx
    static const intmax_t value = _GcdX<_Bx, _Ax % _Bx>::value;
};

template<intmax_t _Ax> struct _GcdX<_Ax, 0>
{  
    // computes greatest common divisor of _Ax and 0
    static const intmax_t value = _Ax;
};

template<intmax_t _Ax, intmax_t _Bx> struct _Gcd
{   
    // computes greatest common divisor of abs(_Ax) and abs(_Bx)
    static const intmax_t value = _GcdX<_Abs<_Ax>::value, _Abs<_Bx>::value>::value;
};

template<> struct _Gcd<0, 0>
{   
    // avoids division by 0 in ratio_less
    static const intmax_t value = 1;    // contrary to mathematical convention
};

This is the famous Euclidean Algorithm in its modern variant (using modulo rather than a loop of subtractions), and of course recursive.

The actual ratio template

// CLASS TEMPLATE ratio
template<intmax_t _Nx, intmax_t _Dx = 1> struct ratio
{   
    // holds the ratio of _Nx to _Dx
    static_assert(_Dx != 0, "zero denominator");
    static_assert(-INTMAX_MAX <= _Nx, "numerator too negative");
    static_assert(-INTMAX_MAX <= _Dx, "denominator too negative");

    static const intmax_t num = _Sign_of<_Nx>::value * 
                                _Sign_of<_Dx>::value * 
                                    _Abs<_Nx>::value / 
                                    _Gcd<_Nx, _Dx>::value;

    static const intmax_t den = _Abs<_Dx>::value / _Gcd<_Nx, _Dx>::value;

    typedef ratio<num, den> type;
};

So, this is the famed ratio of two values together.

Verifying that two template arguments are of a specific type

// CLASS TEMPLATE _Are_ratios
template<class _Ty1, class _Ty2> struct _Are_ratios : false_type
{
    // determine whether _Ty1 and _Ty2 are both ratios
};

template<intmax_t _N1, intmax_t _D1, intmax_t _N2, intmax_t _D2> 
    struct _Are_ratios<ratio<_N1, _D1>, ratio<_N2, _D2> > : true_type
{
    // determine whether _Ty1 and _Ty2 are both ratios
};

If you read these few lines, and you don't feel a sense of wonder: my (proverbial, non-existing) hat is off to you.

Please, for the sake of my sanity, admit that this code makes Perl code look readable by comparison.

Simple ratio math in templates

// ALIAS TEMPLATE ratio_add
template<class _R1, class _R2> struct _Ratio_add
{
    // add two ratios
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_add<R1, R2> requires R1 and R2 to be ratio<>s.");

    static const intmax_t _N1 = _R1::num;
    static const intmax_t _D1 = _R1::den;
    static const intmax_t _N2 = _R2::num;
    static const intmax_t _D2 = _R2::den;

    static const intmax_t _Gx = _Gcd<_D1, _D2>::value;

    // typename ratio<>::type is necessary here
    typedef typename ratio< 
            _Safe_add<
                _Safe_mult<_N1, _D2 / _Gx>::value, 
                _Safe_mult<_N2, _D1 / _Gx>::value
                >::value,
            _Safe_mult<_D1, _D2 / _Gx>::value
        >::type type;
};

OK, time for a bit of math recap:

a   c    a*d + c*b
- + -  = ---------
b   d      (b*d)

Even though the syntax is really really really really really ugly, what is going on here is pretty simple: it is a more or less direct translation of that expression in templatese.

template<class _R1, class _R2> using ratio_add = typename _Ratio_add<_R1, _R2>::type;

Something new: a template alias in the C++11 'using' syntax. Nice.

// ALIAS TEMPLATE ratio_subtract
template<class _R1, class _R2> struct _Ratio_subtract
{
    // subtract two ratios
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_subtract<R1, R2> requires R1 and R2 to be ratio<>s.");

    static const intmax_t _N2 = _R2::num;
    static const intmax_t _D2 = _R2::den;

    typedef ratio_add<_R1, ratio<-_N2, _D2> > type;
};

template<class _R1, class _R2> using ratio_subtract = typename _Ratio_subtract<_R1, _R2>::type;

This was refreshingly simple: just add a negative fraction.

// ALIAS TEMPLATE ratio_multiply
template<class _R1, class _R2> struct _Ratio_multiply
{
    // multiply two ratios
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_multiply<R1, R2> requires R1 and R2 to be ratio<>s.");

    static const intmax_t _N1 = _R1::num;
    static const intmax_t _D1 = _R1::den;
    static const intmax_t _N2 = _R2::num;
    static const intmax_t _D2 = _R2::den;

    static const intmax_t _Gx = _Gcd<_N1, _D2>::value;
    static const intmax_t _Gy = _Gcd<_N2, _D1>::value;

    // typename ratio<>::type is unnecessary here
    typedef ratio<
            _Safe_mult<_N1 / _Gx, _N2 / _Gy>::value,
            _Safe_mult<_D1 / _Gy, _D2 / _Gx>::value
        > type;
};

template<class _R1, class _R2> using ratio_multiply = typename _Ratio_multiply<_R1, _R2>::type;

Once again, a straightforward implementation of what standard mathematics says:

a   c    a * c
- * -  = -----
b   d    b * d

Followed by the template alias. Boring!

// ALIAS TEMPLATE ratio_divide
template<class _R1,
class _R2>
struct _Ratio_divide
{
    // divide two ratios
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_divide<R1, R2> requires R1 and R2 to be ratio<>s.");

    static const intmax_t _N2 = _R2::num;
    static const intmax_t _D2 = _R2::den;

    typedef ratio_multiply<_R1, ratio<_D2, _N2> > type;
};

template<class _R1, class _R2> using ratio_divide = typename _Ratio_divide<_R1, _R2>::type;

which is this:

a   c    a * d
- : -  = -----
b   d    b * c

Some comparison operators

// CLASS TEMPLATE ratio_equal
template<class _R1, class _R2> struct ratio_equal
    : _Cat_base<_R1::num == _R2::num && _R1::den == _R2::den>
{
    // tests if ratio == ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
};

If you'd think that not_equal is along similar lines, you'd be both right and wrong:

// CLASS TEMPLATE ratio_not_equal
template<class _R1, class _R2> struct ratio_not_equal
    : integral_constant<bool, !ratio_equal<_R1, _R2>::value>
{
    // tests if ratio != ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_not_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
};

You are wrong, because now we are using integral_constant as a base class, which - again in xtr1common is defined thus:

// TEMPLATE CLASS integral_constant
template<class _Ty, _Ty _Val> struct integral_constant
{
    // convenient template for integral constant types
    static const _Ty value = _Val;

    typedef _Ty value_type;
    typedef integral_constant<_Ty, _Val> type;

    operator value_type() const
    {
        // return stored value
        return (value);
    }
};

Sometimes I wonder if the STL authors choose which template to use based on a test run of their RNG classes. Well anyway, this is a 'convenient template for integral constant types'. Now looking back to our ratio_not_equal we begin to understand it: If the two values are not equal, the resulting template will have an integral bool value of true. Now, for bonus points: I cannot think for the life of me why you'd prefer this implementation over that one:

// CLASS TEMPLATE ratio_not_equal_as_it_could_have_been_but_is_not
template<class _R1, class _R2> struct ratio_not_equal_as_it_could_have_been_but_is_not
    : _Cat_base<_R1::num != _R2::num || _R1::den != _R2::den>
{
    // tests if ratio == ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
};

Not that it would have been more beautiful (there are many attributes for template code of STL quality, but 'beautiful' is seldom heard, and if it is heard then based on a misunderstanding of the concept of 'beauty' and what 50 years of aesthetic philosophy have tought us).

// CLASS TEMPLATE ratio_less
template<class _R1, class _R2> struct _Ratio_less
{
    // tests if ratio < ratio
    static const intmax_t _N1 = _R1::num;
    static const intmax_t _D1 = _R1::den;
    static const intmax_t _N2 = _R2::num;
    static const intmax_t _D2 = _R2::den;

    static const intmax_t _Gn = _Gcd<_N1, _N2>::value;
    static const intmax_t _Gd = _Gcd<_D1, _D2>::value;
    
    static const intmax_t _Left  = _Safe_mult<_N1 / _Gn, _D2 / _Gd>::value;
    static const intmax_t _Right = _Safe_mult<_N2 / _Gn, _D1 / _Gd>::value;

    typedef integral_constant<bool, (_Left < _Right)> type;
};

OK, in this template I see why one would use integral_constant, because it is a simple way of getting a truth-type value. What this code does is basically this:

a   c
- < - = ad < cb
b   d 

With this information, the rest is simple:

template<class _R1, class _R2> struct ratio_less : _Ratio_less<_R1, _R2>::type
{
    // tests if ratio < ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_less<R1, R2> requires R1 and R2 to be ratio<>s.");
};

// CLASS TEMPLATE ratio_less_equal
template<class _R1, class _R2> struct ratio_less_equal
    : integral_constant<bool, !ratio_less<_R2, _R1>::value>
{
    // tests if ratio <= ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_less_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
};

// CLASS TEMPLATE ratio_greater
template<class _R1, class _R2> struct ratio_greater
    : integral_constant<bool, ratio_less<_R2, _R1>::value>
{
    // tests if ratio > ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_greater<R1, R2> requires R1 and R2 to be ratio<>s.");
};

// CLASS TEMPLATE ratio_greater_equal
template<class _R1, class _R2> struct ratio_greater_equal
    : integral_constant<bool, !ratio_less<_R1, _R2>::value>
{
    // tests if ratio >= ratio
    static_assert(_Are_ratios<_R1, _R2>::value, "ratio_greater_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
};

Really, no comment needed at this point.

SI units in templates.

What more can a man want?

// SI TYPEDEFS
typedef ratio<1, 1000000000000000000LL> atto;
typedef ratio<1, 1000000000000000LL> femto;
typedef ratio<1, 1000000000000LL> pico;

typedef ratio<1, 1000000000> nano;
typedef ratio<1, 1000000> micro;
typedef ratio<1, 1000> milli;
typedef ratio<1, 100> centi;
typedef ratio<1, 10> deci;
typedef ratio<10, 1> deca;
typedef ratio<100, 1> hecto;
typedef ratio<1000, 1> kilo;
typedef ratio<1000000, 1> mega;
typedef ratio<1000000000, 1> giga;

typedef ratio<1000000000000LL, 1> tera;
typedef ratio<1000000000000000LL, 1> peta;
typedef ratio<1000000000000000000LL, 1> exa;

Behold the beauty of the metric system! Laugh at those poor bastards stuck in the imperial measurement system! Pitty the Javascript Fullstack Developers who have to deal with stupid floating point numbers only!

We finish our discussion of this header with more boilerplate:

_STD_END
 #pragma pop_macro("new")
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _RATIO_ */

/*
 * Copyright (c) 1992-2012 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V6.00:0009 */

Lessons learnt

To summarize, here are the most interesting techniques we've seen in this header:

Not too bad for such a short header.

That's it for today. Tune in next time when we investigate other mysteries of the STL...

->Back to the STL overview