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.

• the template `_Safe_mult` has two arguments, `_Ax` and `_Bx`, and provides a way of multiplying these without overflow.
• there is a helper template `_Safe_multX` that gets instantiated for two values i it is safe to calculate their product (at runtime).
• there is a specialization of the `_Safe_multX` template that gets called if a third parameter is false: in this case, you have an overflow, and a `static_assert` is raised at compiletime.
• the real magic is in the following expression:
```(_Abs<_Ax>::value <= INTMAX_MAX / _Abs<_Bx>::value)
```
which results in a boolean value, (and must be `false` for overflow). So how does it work?
• First of all, remember operator precedence: in `a <= b/c`, the expression `b/c` is evaluated first.
• So this expression is the number of times c fits into b, which here is: the number of times the second template fits into `INTMAX_MAX` at all
• And the overall expression returns true if `_Ax` is less than or equal to the maximum number of times `_Bx` fits into `INTMAX_MAX`.
• Note that there is no need for optimization here: all these calculations are done at compiletime: there is zero overhead at runtime.

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

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:

• `_Safe_add` is a template that adds two template arguments `_Ax` and `_Bx` at compiletime, overflow-safe.
• `_Safe_addX` is an internal helper template that calculates the actual value of `_Ax+_Bx`
• The only difference with the multiplication-case shown above is that there are now two template arguments waiting for specialization, named `_Good` and `_Also_good` fter advice found in the 'How to write unmaintainable code' FAQ.
• There is a specialization where these two parameters are both false: in that case, the assertion is raised and the compiler aborts.
• The value for `_Good` is calculated from this expression:
```_Sign_of<_Ax>::value != _Sign_of<_Bx>::value
```
This is `true` if the two sides have different signs, which means we are effectively dealing with subtraction, for which no overflow can occur.
• The value for `_Also_good` is calculated from that expression:
```_Abs<_Ax>::value <= INTMAX_MAX - _Abs<_Bx>::value
```
and multiplication had something very similar: the maximum possible value for `_Ax` is determined, and only if `_Ax` is less than or equal to this value, the standard template expansion proceeds.

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.

• `_Gcd` is a template of two arguments, that calculates the GCD of both values using a helper template `_Gcdx`.
• `_GcdX` is a template that calls itself recursively. The recursion ends if the second operand is 0, in which case the new `_Ax` is the GCD.
• There is one specialization 'contrary to mathematical convention': if both values are 0, then the GCD is 1 (this prevents division-by-zero errors further down below).

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.

• The template has two arguments, `_Nx` and `_Dx`, that are the nominator and the denominator of the (as of yet arbitrary) ratio.
• The template starts with three compile-time assertions that just check you've passed in arguments that make basic sense.
• The template-static constant `num` is calculated like this:
• Get the GCD of nominator and denominator
• Divide absolute value of nominator by GCD. We must use the absolute value, because the GCD is always defined as a positive number.
• Mulitply that by the product of both nominator and denominator sign: which returns the actual sign of the overall expression. This is necessary because we will normalize the denominator to be a positive value always
• The template-static constant `den` is calculated similiarly, but remains positive (the overall ratio needs only one sign, and that is part of the denominator.

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.

• The template is normally called using two arguments, `_Ty1` and `_Ty2`, and defaults to `false_type`, which is more or less the value `false`. So basically, if you pass in anything, you get false back.
• The second template is a partial specialization for something that has no general type: the template, using 4 arguments. But hypothetically, if the 4 arguments result in two `ratio` instances, then the specialization expands to a different 'base class' type: `true`.

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
{
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_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.

• The GCD of both denominators (b and d in my example) is calculated to make the result smaller right from the start.
• The new nominator is the expression shown, using the 'overflow-safe' template variants shown above.
• The new denominator does this, too.
```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.");
};
```
• This template evaluates if two ratios are equal. They are equal, if both nominator and denominator are equal. We can use this generic check, because the template class above already guarantees that the values are factored using the smallest possible value.
• About the only thing strange here is this: `_Cat_base`. What is it? It is defined in `xtr1common` like this:
```// TEMPLATE CLASS _Cat_base
template<bool> struct _Cat_base : false_type
{
// base class for type predicates
};

template<> struct _Cat_base<true>> : true_type
{
// base class for type predicates
};
```
So, standard template-writing technique: define a template that defaults to false, provide a specialization that returns a true-type.

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_ */

/*
V6.00:0009 */
```

Lessons learnt

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

• How to detect - and prevent against - overflow in integer math in templates
• How to write a simple recursive algorithm - here: euclidean GCD - in templates
• Template aliases using 'using' is a thing.
• Template authors have less focus on optimization, because their bit runs at compile time, which by definition has zero impact on runtime. (This is not true, of course: think of increased memory usage and so on, but it is an idealized assumption)
• SI units >> imperial units