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 astatic_assert
is raised at compiletime. - the real magic is in the following expression:
which results in a boolean value, (and must be
(_Abs<_Ax>::value <= INTMAX_MAX / _Abs<_Bx>::value)
false
for overflow). So how does it work?- First of all, remember operator precedence: in
a <= b/c
, the expressionb/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 intoINTMAX_MAX
. - Note that there is no need for optimization here: all these calculations are done at compiletime: there is zero overhead at runtime.
- First of all, remember operator precedence: in
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:
_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:This is_Sign_of<_Ax>::value != _Sign_of<_Bx>::value
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:and multiplication had something very similar: the maximum possible value for_Abs<_Ax>::value <= INTMAX_MAX - _Abs<_Bx>::value
_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 tofalse_type
, which is more or less the valuefalse
. 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
{
// 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.
- 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 inxtr1common
like this:So, standard template-writing technique: define a template that defaults to false, provide a specialization that returns a true-type.// 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 };
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:
- 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
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...