17
Numerics
The purpose of computing is insight, not numbers.
– R. W. Hamming
... but for the student, numbers are often the best road to insight.
– A. Ralston
17.1 Introduction
C++ was not designed primarily with numeric computation in mind. However, numeric computation typically occurs in the context of other work – such as scientific computation, database access, networking, instrument control, graphics, simulation, and financial analysis – so C++ becomes an attractive vehicle for computations that are part of a larger system. Furthermore, numeric methods have come a long way from being simple loops over vectors of floating-point numbers. Where more complex data structures are needed as part of a computation, C++’s strengths become relevant. The net effect is that C++ is widely used for scientific, engineering, financial, and other computation involving sophisticated numerics. Consequently, facilities and techniques supporting such computation have emerged. This chapter describes the parts of the standard library that support numerics.
17.2 Mathematical Functions
In <cmath>, we find the standard mathematical functions, such as sqrt(), log(), and sin() for arguments of type float, double, and long double:
Selected Standard Mathematical Functions | |
|---|---|
abs(x) | Absolute value |
ceil(x) | Smallest integer >= x |
floor(x) | Largest integer <= x |
sqrt(x) | Square root; x must be non-negative |
cos(x) | Cosine |
sin(x) | Sine |
tan(x) | Tangent |
acos(x) | Arccosine; the result is non-negative |
asin(x) | Arcsine; the result nearest to 0 is returned |
atan(x) | Arctangent |
sinh(x) | Hyperbolic sine |
cosh(x) | Hyperbolic cosine |
tanh(x) | Hyperbolic tangent |
exp(x) | Base e exponential |
exp2(x) | Base 2 exponential |
log(x) | Natural logarithm, base e; x must be positive |
log2(x) | Natural logarithm, base 2; x must be positive |
log10(x) | Base 10 logarithm; x must be positive |
The versions of these functions for complex (§17.4) are found in <complex>. For each function, the return type is the same as the argument type.
Errors are reported by setting errno from <cerrno> to EDOM for a domain error and to ERANGE for a range error. For example:
errno = 0; // clear old error state
double d = sqrt(-1);
if (errno==EDOM)
cerr << "sqrt() not defined for negative argument
";
errno = 0; // clear old error state
double dd = pow(numeric_limits<double>::max(),2);
if (errno == ERANGE)
cerr << "result of pow() too large to represent as a double
";More mathematical functions are found in <cmath> and <cstdlib>. The so-called special mathematical functions, such as beta(), riemann_zeta(), and sph_bessel(), are also in <cmath>.
17.3 Numerical Algorithms
In <numeric>, we find a small set of generalized numerical algorithms, such as accumulate().
Numerical Algorithms | |
|---|---|
x=accumulate(b,e,i) | x is the sum of i and the elements of [b:e) |
x=accumulate(b,e,i,f) | accumulate using f instead of + |
x=inner_product(b,e,b2,i) | x is the inner product of [b:e) and [b2:b2+(e-b)), that is, the sum of i and (*p1)*(*p2) for each p1 in [b:e) and the corresponding p2 in [b2:b2+(e-b)) |
x=inner_product(b,e,b2,i,f,f2) | inner_product using f and f2 instead of + and * |
p=partial_sum(b,e,out) | Element i of [out:p) is the sum of elements [b:b+i] |
p=partial_sum(b,e,out,f) | partial_sum using f instead of + |
p=adjacent_difference(b,e,out) | Element i of [out:p) is *(b+i)-*(b+i-1) for i>0; if e-b>0, then *out is *b |
p=adjacent_difference(b,e,out,f) | adjacent_difference using f instead of − |
iota(b,e,v) | For each element in [b:e) assign v and increment ++v; thus the sequence becomes v, v+1, v+2, ... |
x=gcd(n,m) | x is the greatest common denominator of integers n and m |
x=lcm(n,m) | x is the least common multiple of integers n and m |
x=midpoint(n,m) | x is the midpoint between n and m |
These algorithms generalize common operations such as computing a sum by letting them apply to all kinds of sequences. They also make the operation applied to elements of those sequences a parameter. For each algorithm, the general version is supplemented by a version applying the most common operator for that algorithm. For example:
list<double> lst {1, 2, 3, 4, 5, 9999.99999};
auto s = accumulate(lst.begin(),lst.end(),0.0); // calculate the sum: 10014.9999These algorithms work for every standard-library sequence and can have operations supplied as arguments (§17.3).
17.3.1 Parallel Numerical Algorithms
In <numeric>, the numerical algorithms (§17.3) have parallel versions that differ slightly from the sequentional ones. In particular, the parallel versions allow operations on elements in unspecified order. The parallel numerical algorithms can take an execution policy argument (§13.6): seq, unseq, par, and par_unseq.
Parallel Numerical Algorithms | |
|---|---|
x=reduce(b,e,v) | x=accumulate(b,e,v), except out of order |
x=reduce(b,e) | x=reduce(b,e,V{}), where V is b’s value type |
x=reduce(pol,b,e,v) | x=reduce(b,e,v) with execution policy pol |
x=reduce(pol,b,e) | x=reduce(pol,b,e,V{}), where V is b’s value type |
p=exclusive_scan(pol,b,e,out) | p=partial_sum(b,e,out) according to pol, excludes the ith input element from the ith sum |
p=inclusive_scan(pol,b,e,out) | p=partial_sum(b,e,out) according to pol includes the ith input element in the ith sum |
p=transform_reduce(pol,b,e,f,v) | f(x) for each x in [b:e), then reduce |
p=transform_exclusive_scan(pol,b,e,out,f,v) | f(x) for each x in [b:e), then exclusive_scan |
p=transform_inclusive_scan(pol,b,e,out,f,v) | f(x) for each x in [b:e), then inclusive_scan |
For simplicity, I left out the versions of these algorithms that take operations as arguments, rather than just using defaults, such as +. Except for reduce(), I also left out the versions with default policy (sequential) and default value.
Just as for the parallel algorithms in <algorithm> (§13.6), we can specify an execution policy:
vector<double> v {1, 2, 3, 4, 5, 9999.99999};
auto s = reduce(v.begin(),v.end()); // calculate the sum using a double as the accumulator
vector<double> large;
// ... fill large with lots of values ...
auto s2 = reduce(par_unseq,large.begin(),large.end()); // calculate the sum using available parallelismThe execution policies, par, sec, unsec, and par_unsec are hidden in namespace std::execution in <execution>.
Measure to verify that using a parallel or vectorized algorithm is worthwhile.
17.4 Complex Numbers
The standard library supports a family of complex number types along the lines of the complex class described in §5.2.1. To support complex numbers where the scalars are single-precision floating-point numbers (floats), double-precision floating-point numbers (doubles), etc., the standard library complex is a template:
template<typename Scalar>
class complex {
public:
complex(const Scalar& re ={}, const Scalar& im ={}); // default function arguments; see §3.4.1
// ...
};The usual arithmetic operations and the most common mathematical functions are supported for complex numbers. For example:
void f(complex<float> fl, complex<double> db)
{
complex<long double> ld {fl+sqrt(db)};
db += fl*3;
fl = pow(1/fl,2);
// ...
}The sqrt() and pow() (exponentiation) functions are among the usual mathematical functions defined in <complex> (§17.2).
17.5 Random Numbers
Random numbers are useful in many contexts, such as testing, games, simulation, and security. The diversity of application areas is reflected in the wide selection of random number generators provided by the standard library in <random>. A random number generator consists of two parts:
[1] An engine that produces a sequence of random or pseudo-random values
[2] A distribution that maps those values into a mathematical distribution in a range
Examples of distributions are uniform_int_distribution (where all integers produced are equally likely), normal_distribution (“the bell curve”), and exponential_distribution (exponential growth); each for some specified range. For example:
using my_engine = default_random_engine; // type of engine
using my_distribution = uniform_int_distribution<>; // type of distribution
my_engine eng {}; // the default version of the engine
my_distribution dist {1,6}; // distribution that maps to the ints 1..6
auto die = [&](){ return dist(eng); }; // make a generator
int x = die(); // roll the die: x becomes a value in [1:6]Thanks to its uncompromising attention to generality and performance, one expert has deemed the standard-library random number component “what every random number library wants to be when it grows up.” However, it can hardly be deemed “novice friendly.” The using statements and the lambda make what is being done a bit more obvious.
For novices (of any background) the fully general interface to the random number library can be a serious obstacle. A simple uniform random number generator is often sufficient to get started. For example:
Rand_int rnd {1,10}; // make a random number generator for [1:10]
int x = rnd(); // x is a number in [1:10]So, how could we get that? We have to get something that, like die(), combines an engine with a distribution inside a class Rand_int:
class Rand_int {
public:
Rand_int(int low, int high) :dist{low,high} { }
int operator()() { return dist(re); } // draw an int
void seed(int s) { re.seed(s); } // choose new random engine seed
private
default_random_engine re;
uniform_int_distribution<> dist;
};That definition is still “expert level,” but the use of Rand_int() is manageable in the first week of a C++ course for novices. For example:
int main()
{
constexpr int max = 9;
Rand_int rnd {0,max}; // make a uniform random number generator
vector<int> histogram(max+1); // make a vector of appropriate size
for (int i=0; i!=200; ++i)
++histogram[rnd()]; // fill histogram with the frequencies of numbers [0:max]
for (int i = 0; i!=histogram.size(); ++i) { // write out a bar graph
cout << i << ' ' ;
for (int j=0; j!=histogram[i]; ++j) cout <<'*' ;
cout << '
' ;
}
}The output is a (reassuringly boring) uniform distribution (with reasonable statistical variation):
0 ********************* 1 **************** 2 ******************* 3 ******************** 4 **************** 5 *********************** 6 ************************** 7 *********** 8 ********************** 9 *************************
There is no standard graphics library for C++, so I use “ASCII graphics.” Obviously, there are lots of open source and commercial graphics and GUI libraries for C++, but in this book I restrict myself to ISO standard facilities.
To get a repeated or different sequence of values, we seed the engine; that is, we give its internal state a new value. For example:
Rand_int rnd {10,20};
for (int i = 0; i<10; ++i) cout << rnd() << ' '; // 16 13 20 19 14 17 10 16 15 14
cout << '
';
rnd.seed(999);
for (int i = 0; i<10; ++i) cout << rnd() << ' '; // 11 17 14 19 20 13 20 14 16 19
cout << '
';
rnd.seed(999);
for (int i = 0; i<10; ++i) cout << rnd() << ' '; // 11 17 14 19 20 13 20 14 16 19
cout << '
';Repeated sequences are important for deterministic debugging. Seeding with different values is important when we don’t want repetition. If you need genuine random numbers, rather than a generated pseudo-random sequence, look to see how random_device is implemented on your machine.
17.6 Vector Arithmetic
The vector described in §12.2 was designed to be a general mechanism for holding values, to be flexible, and to fit into the architecture of containers, iterators, and algorithms. However, it does not support mathematical vector operations. Adding such operations to vector would be easy, but its generality and flexibility preclude optimizations that are often considered essential for serious numerical work. Consequently, the standard library provides (in <valarray>) a vector-like template, called valarray, that is less general and more amenable to optimization for numerical computation:
template<typename T>
class valarray {
// ...
};The usual arithmetic operations and the most common mathematical functions are supported for valarrays. For example:
void f(valarray<double>& a1, valarray<double>& a2)
{
valarray<double> a = a1*3.14+a2/a1; // numeric array operators *, +, /, and =
a2 += a1*3.14;
a = abs(a);
double d = a2[7];
// ...
}The operations are vector operations; that is, they are applied to each element of the vectors involved.
In addition to arithmetic operations, valarray offers stride access to help implement multidimensional computations.
17.7 Numeric Limits
In <limits>, the standard library provides classes that describe the properties of built-in types – such as the maximum exponent of a float or the number of bytes in an int. For example, we can assert that a char is signed:
static_assert(numeric_limits<char>::is_signed,"unsigned characters!"); static_assert(100000<numeric_limits<int>::max(),"small ints!");
The second assert (only) works because numeric_limits<int>::max() is a constexpr function (§1.6).
We can define numeric_limits for our own user-defined types.
17.8 Type Aliases
The size of fundamental types, such as int and long long are implementation defined; that is, they may be different on different implementations of C++. If we need to be specific about the size of our integers, we can use aliases defined in <stdint>, such as int32_t and uint_least64_t. The latter means an unsigned integer with at least 64 bits.
The curious _t suffix is a relict from the days of C when it was deemed important to have a name reflect that it named an alias.
Other common aliases, such as size_t (the type returned by the sizeof operator) and ptrdiff_t (the type of the result of subtracting one pointer from another) can be found in <stddef>.
17.9 Mathematical Constants
When doing mathematical computations, we need common mathematical constants such as e, pi, and log2e. The standard library offers those and more. They come in two forms: a template that allows us to specify exact type (e.g., pi_v<T>) and a short name for the most common use (e.g., pi meaning pi_v<double>). For example:
void area(float r)
{
using namespace std::numbers; // this is where the mathematical constants are kept
double d = pi*r*r;
float f = pi_v<float>*r*r;
// ...
}In this case, the difference is small (we would have to print with precision 16 or so to see it), but in real physics calculation such differences quickly become significant. Other areas where the precision of constants matters are graphics and AI, where smaller representations of values are increasingly important.
In <numbers>, we find e (Euler’s number), log2e (log2 of e), log10e (log10 of e), pi, inv_pi (1/pi), inv_sqrtpi (1/sqrt(pi)), ln2, ln10, sqrt2 (sqrt(2)), sqrt3 (sqrt(3)), inv_sqrt3 (1/sqrt3), egamma (the Euler-Mascheroni constant), and phi (the golden ratio).
Naturally, we would like more mathematical constants and constants for different domains. That’s easily done because such constants are variable templates with specializations for double (or whatever type is most useful for a domain):
template<typename T> constexpr T tau_v = 2*pi_v<T>; constexpr double tau = tau_v<double>;
17.10 Advice
[1] Numerical problems are often subtle. If you are not 100% certain about the mathematical aspects of a numerical problem, either take expert advice, experiment, or do both; §17.1.
[2] Don’t try to do serious numeric computation using only the bare language; use libraries; §17.1.
[3] Consider accumulate(), inner_product(), partial_sum(), and adjacent_difference() before you write a loop to compute a value from a sequence; §17.3.
[4] For larger amounts of data, try the parallel and vectorized algorithms; §17.3.1.
[5] Use std::complex for complex arithmetic; §17.4.
[6] Bind an engine to a distribution to get a random number generator; §17.5.
[7] Be careful that your random numbers are sufficiently random for your intended use; §17.5.
[8] Don’t use the C standard-library rand(); it isn’t insufficiently random for real uses; §17.5.
[9] Use valarray for numeric computation when run-time efficiency is more important than flexibility with respect to operations and element types; §17.6.
[10] Properties of numeric types are accessible through numeric_limits; §17.7.
[11] Use numeric_limits to check that the numeric types are adequate for their use; §17.7.
[12] Use aliases for integer types if you want to be specific about their sizes; §17.8.