Templates, random numbers and a class for matrices
Knowledge is having the right answers. Intelligence is asking the right questions. Wisdom is knowing when to ask the right questions.
— Richard P. Feynman author unknown
Before using it, I asked an AI assistant to check the attribution.
The tool did the search, but the question came from the person using it: without that question, this slide would carry the wrong name.
The formulation of a problem is often more essential than its solution, which may be merely a matter of mathematical or experimental skill. To raise new questions, new possibilities, to regard old problems from a new angle requires creative imagination and marks real advances in science.
A. Einstein and L. Infeld, The Evolution of Physics (1938), p. 92.
But they are useless. They can only give you answers.
Pablo Picasso, on computers, in W. Fifield, “Pablo Picasso: A Composite Interview”, The Paris Review 32 (1964), p. 62.
Today a growing share of the skill Einstein and Infeld speak of is done by tools: an AI assistant writes code in a few seconds. Formulating the problem and checking the answer remain the job of whoever uses them.
What I cannot create, I do not understand.
Written on Feynman’s blackboard at Caltech, as he left it when he died, in February 1988 (Caltech Archives).
You have to keep a dozen of your favorite problems constantly present in your mind, although by and large they will lay in a dormant state. Every time you hear or read a new trick or a new result, test it against each of your twelve problems to see whether it helps. Every once in a while there will be a hit, and people will say: “How did he do it? He must be a genius!”
Feynman’s advice as told by G.-C. Rota, “Ten Lessons I Wish I Had Been Taught”, talk at MIT (1996), Notices of the AMS 44 (1997), 22–25.
AI tools are the newest trick: test them against your problems, and keep the problems your own.
operator(), the friend functions and <<.randnumgen, which you get complete.pvector — first it becomes a class template, pvector<double,3>; then random(L), a random vector in a box, and random_orient(), a random unit vector uniformly distributed on the sphere (Marsaglia’s algorithm).pmatrixq, a class template that follows pvector closely.pvector stores NT numbers of type ntype, both fixed once for the whole program at the top of pvector.hpp:
A program that needs vectors of double and of float, or in 3 and in 2 dimensions, would need two copies of the class with different names.
Generic programming solves this: write the class once, with the type (and the size) as parameters, and let the compiler generate the versions you use: genvec<double>, genvec<float>, … (example N8).
The same mechanism lets the compiler compute things before the program runs: template metaprogramming (example N9).
genvec.hppexamples/N8_generic_programming/genvec.hpp
#include<cstdlib>
#include<iostream>
// a generic class (a metaclass or class template)
// ntype can be float, double, long double, ...
constexpr int NT=3;// <---- like #define
template <typename ntype>
class genvec
{
// private members
ntype v[NT];
public:
void set(int i, ntype val)
{
v[i] = val;
}
ntype get(int i) const
{
return v[i];
}template <typename ntype> (line 7): genvec is a class template, a recipe for classes. Inside it ntype is a type still to be chosen; the rest is an ordinary class.constexpr int NT=3; (line 5) is a typed constant known when compiling: it can size the array v, like the macro of Lab #1, but it is a real variable with a type and a scope.genvec.cppexamples/N8_generic_programming/genvec.cpp
genvec<double> gv;: the compiler instantiates the template with ntype = double, i.e. it writes the class genvec<double> for us, and then compiles it. genvec<float> or genvec<int> would be other classes, generated in the same way.genvec gv; alone does not compile, because nothing tells the compiler which ntype to use: error: class template argument deduction failed (g++; with clang++: no viable constructor or deduction guide for deduction of template arguments of 'genvec').A template is not code yet: it becomes code only when it is used with a given type. So the compiler must see the whole template where it is used: templates are written entirely in the header (.hpp), as we already do for all our classes.
A template can have several parameters, also integer ones (non-type parameters), known when compiling:
You have already used templates of the standard library: std::initializer_list<ntype> (Lab #2) is one.
Each different instantiation is a different class: genvec<double> and genvec<float> are as different as int and double. The cost is paid at compile time; at run time a template class is exactly as fast as the class written by hand.
myfibonacci.cpp (1)examples/N9_metaprogramming/myfibonacci.cpp: the Fibonacci numbers \(F_N = F_{N-1} + F_{N-2}\), computed by the compiler.
#include<iostream>
#include<tuple>
using namespace std;
// FIBONACCI SERIES: F_{n} = F_{n-1} + F_{n-2}
template<int N>
class fib {
public:
static constexpr long int value = fib<N-1>::value + fib<N-2>::value;
// tuple_cat constructs a tuple that is a concatenation of all tuples provided as args.
// E.g. int a=1;
// string s="pippo";
// float f=1.3;
// auto t=tuple_cat(make_tuple(a), make_tuple(s));
// auto t2=tuple_cat(t, f);
// results in the tuple whose elements are:
// {1, "pippo", 1.3}
// Note that make_tuple is necessary since this way we convert value to a tuple which can be added to the present tuple
// by tuple_cat.
static constexpr auto fis = tuple_cat(fib<N-1>::fis, make_tuple(value)); // add value to the tuple
};
// stop recursion
template<>
class fib<1> {
public:
static constexpr long int value = 1;
static constexpr tuple<long int> fis = make_tuple(1);
};
template<>
class fib<0> {
public:
static constexpr long int value = 0;
};myfibonacci.cpp (2)examples/N9_metaprogramming/myfibonacci.cpp
// type to hold an integer
template<int N> struct int_{static constexpr int n=N;};
template <class T, class I>
void print_tuple(T l, I nel)
{
cout << get<tuple_size<T>::value-nel.n>(l) << ","; // print n-th element
int_<nel.n-1> nn;
print_tuple(l, nn); // recursively print remaining elements
}
// stop recursion
template <class T>
void print_tuple(T l, int_<1>) // we simply provide a type as second argument since istance of second argument is not used
{
cout << get<tuple_size<T>::value-1>(l) << "\n";
}
// the following varadic function calls print_tuple where second argument is the number of elements of the tuple
template<class T>
void print_tuple(T l)
{
print_tuple(l, int_<tuple_size<T>::value>()); // int_<tuple_size<T>::value>() is an object of type struct int_
}
int main()
{
constexpr int N = 90;
fib<N> f;
cout << "The Fibonacci sequence up to N=" << N << " is:\n";
print_tuple(f.fis);
}template<int N> class fib: one class for each integer N. value is static constexpr: a constant of the class (not of the objects), computed when compiling. fib<N>::value needs fib<N-1>::value and fib<N-2>::value, so the compiler instantiates fib<N-1>, fib<N-2>, …, recursively.template<> class fib<1> and fib<0> are full specializations: for N = 1 and 0 they replace the general template, and stop the recursion, like the base case of a recursive function.fis is a std::tuple, a fixed-size collection of values: tuple_cat appends value to the tuple of fib<N-1>, so fib<N>::fis holds \(F_1, \dots, F_N\).get<i>(t) needs an index i known when compiling, so a normal for loop cannot be used. print_tuple calls itself with the type int_<n-1>, which carries the index; the overload for int_<1> stops the recursion (function overloading, Lab #2).The Fibonacci sequence up to N=90 is:
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,...,2880067194370816120
Now set N = 100 in main and compile again:
myfibonacci.cpp:8:27: error: overflow in constant expression [-fpermissive]
long int (at most \(2^{63}-1 \simeq 9.2\times 10^{18}\)): the largest N that works is 92. In a normal program the overflow would silently give a wrong (negative) number at run time; when the compiler does the computation, the overflow is an error (clang++: constexpr variable 'value' must be initialized by a constant expression).constexpr, integer template parameters (template<int N>, the NT of pmatrixq), and the idea that whatever the compiler knows (sizes, constants) costs nothing at run time.fibonacci.cpp, an alternative implementation: the sum is done by a class Sum, and << is overloaded to print any std::tuple.operator()project/pvector.hpp
// This is needed to access elements of const vector objects
// this is like having following arguments: operator()(const pvector *this, int i)
// where (implicit, i.e. (*this) ) first argument is the "calling" object
// V(i) = 1.0;
// cout << V(0);
// V ( i )
// operand operand
ntype operator()(int idx) const
{
return v[idx];
}
// this is like having following arguments: operator()(pvector *this, int i)
// where first (implicit, i.e. (*this) ) argument is the "calling" object
// pvector A;
// double val;
// std::cout << A(1);
// A(1)=val;
ntype& operator()(int idx)
{
return v[idx];
}return v[idx];: the non-const one returns a reference to the component (A(1) = 5.0; writes in A), the const one a copy of its value, and it is the one used for const vectors and const pvector& arguments.rint()project/pvector.hpp
*this, all the operands are arguments, and they can read V2.v[i] because they are friends of pvector.rint, rint(V2.v[i]) has a number as argument: it is the rint() of <cmath>.mulcw() and divcw()project/pvector.hpp
// mulcw: component wise multiplication, i.e. C=mulcw(A,B), i.e. C(i) = A(i)*B(i)
friend pvector mulcw(const pvector& V1, const pvector& V2)
{
pvector VT;
for (int i=0; i < NT; i++)
{
VT(i) = V1(i)*V2(i);
}
return VT;
}
// divcw: component wise division, i.e. C=divcw(A,B), i.e. C(i) = A(i)/B(i)
friend pvector divcw(const pvector& V1, const pvector& V2)
{
pvector VT;
for (int i=0; i < NT; i++)
{
VT(i) = V1(i)/V2(i);
}
return VT;
}VT(i) = ... uses the non-const operator() (it writes into VT); V1(i) and V2(i) the const one, because V1 and V2 are const pvector&.friend is not strictly needed here: the body uses only the public operator(), so mulcw could be a function outside the class; we keep it inside, with the others.divcw does not check for zero components of V2: division by zero gives inf or nan.operator<<project/pvector.hpp
os, the stream on the left of <<, and returns it by reference, so that std::cout << A << " " << B << "\n" works: each << returns std::cout to the next one (left associativity, Lab #3).
Figure: Wikipedia, “Linear congruential generator”.
rand()rand() uses an algorithm that depends on the library: an LCG on Windows and macOS, a different generator on Linux. In <random> the LCG is std::minstd_rand (\(a = 48271\), \(m = 2^{31}-1\)).Planes: G. Marsaglia, PNAS 61, 25 (1968), the same Marsaglia of Part 4.
ranlux has an excellent period but is very slow.Table: arvid.io (2018), “On C++ Random Number Generator Quality”.

minstd_rand) and the lagged-Fibonacci ranlux*_base fail at once.mt19937 fails at 256 GB, mt19937_64 at 512 GB.ranlux24/ranlux48 pass, but are very slow. Those in bold (splitmix, xorshift, pcg) pass and are fast, but are not in the standard library.Table: arvid.io (2018), “A Better C++ Pseudo Random Number Generator”.
std::mt19937, std::mt19937_64 in <random>): no external code to install.mt19937_64 starts to fail the most demanding tests.randnumgen (1)project/randnumgen.hpp (complete: you do not have to change it)
#ifndef _RANDNUMGEN_
#define _RANDNUMGEN_
#include<chrono>
#include<random>
// use by default mersenne-twister rng engine
template <class ntype, class engine>
class randnumgen {
std::random_device rd;
using myclock = std::chrono::high_resolution_clock;
engine rng;
using ud = std::uniform_real_distribution<ntype>;
// we use a pointer here since if a range different from [0,1) is needed
// we can use the constructor of uniform_real_distribution class
// to provide a different range (see randnumgen())
// If a different range is not needed, the default constructor can be used
// and one can avoid to use a pointer to uniform_real_distribution class
ud* unidst;
public:
// fixed seed
void seed(int s)
{
std::seed_seq seq{s+1, s+2, s+2};
rng.seed(seq);
}
// random seed
void rseed(void)
{
// int operator()() {}
// ticks since 1/1/1970
unsigned int t=myclock::now().time_since_epoch().count();
// ^ is bitwise XOR
std::seed_seq seq{rd()^t,rd()^t, rd()^t};
rng.seed(seq);
}randnumgen (2)project/randnumgen.hpp
ntype ranf()
{
// ntype operator()(engine mt) {}
// uniform_real_distribution overloads the parenthesis operator
return (*unidst)(rng);
}
randnumgen()
{
unidst = new ud(0.0,1.0);
// equivalent way to set the range of random numbers:
// unidst->param(std::uniform_real_distribution<double>::param_type(0.0, 1.0));
}
~randnumgen()
{
delete unidst;
}
};
// ==============================================================================
// PUBLIC METHODS:
// rng.seed(<integer>) : fixed seeding
// rng.rseed(); : random seeding
// rng.ranf(); : generate a random number in [0.0,1.0)
randnumgen<double,std::mt19937_64> rng;
#endifrandnumgenrandnumgen is a class template (Part 1) with two type parameters: the number type (double) and the engine (std::mt19937_64, the 64-bit Mersenne Twister). The engine produces random integers; std::uniform_real_distribution turns them into numbers in \([0,1)\).rng: every file that includes randnumgen.hpp (pvector.hpp now does, line 41) uses the same generator, hence one sequence for the whole program. This works because our programs have a single .cpp file.unidst: created with new in the constructor, freed with delete in the destructor (N6).seed() or rseed() the engine starts from its default seed: every run gives the same numbers. Seed once, at the beginning of main, never inside a loop.pvector: a template, random vectorsDownload again project_classes.zip (unzip it elsewhere, not over your files): project/pvector.hpp has the methods of Lab #3 (Part 2) and the skeleton of random() and random_orient(); project/randnumgen.hpp is new.
// [X] overloading of << for output (friend function)
// [*] make pvector a class template: template <typename ntype, int NT> class pvector
// (then comment out the global NT and ntype defined below)
//
// Discuss random number generator class with Mersenne-Twister
// [*] random(L), random vector inside a box of length L
// [*] random_orient() random unit on unit sphere (marsaglia) The goal: project/pvector.cpp (in the zip) must print the output at the end of this part.
pvector becomes a class templateIn project/pvector.hpp, as genvec (N8) but with two parameters, like pmatrixq: comment out the global NT and ntype, and write template <typename ntype, int NT> on the line before class pvector. The result:
pvector alone means pvector<ntype,NT>, so the methods, the operators and the friend functions stay as they are.pvector.cpp declares using ntype = double;, constexpr int NT = 3; and then pvector<ntype,NT> R, U;. Without them, pvector R, U; gives error: class template argument deduction failed.pvector.cpp must compile (its output is meaningless until random() and random_orient() are written). Before the change: error: 'pvector' is not a template.NT and ntype but forget the template line: error: 'ntype' does not name a type.pvector.hpp still has the macro of Lab #1, #define NT 3, the preprocessor turns the new line into template <typename ntype, int 3>, which is not C++: error: expected '>' before numeric constant. A macro replaces every NT: it has no type and no scope. This is why pvector.hpp now uses constexpr int NT=3;.pmatrix.hpp includes pvector.hpp: it compiles both before and after Task 1.random(L): a random vector in a boxrng.ranf() is uniform in \([0,1)\), so (rng.ranf()-0.5)*L is uniform in \([-L/2, L/2)\).dr - L*rint(dr/L) has components in \([-L/2, L/2]\). The same recipe gives the random displacement of a Monte Carlo move, \(\delta\,(\xi-0.5)\) for each component.Why it works: \(S\) is uniform in \((0,1)\) and independent of the direction \((V_1, V_2)/\sqrt{S}\), so \(z = 1-2S\) is uniform in \((-1,1)\) and \((x, y) = \sqrt{1-z^2}\,(V_1,V_2)/\sqrt{S} = 2\sqrt{1-S}\,(V_1,V_2)\) has a uniform random direction.
sin, cos, acos.random_orient(): implementationdo { ... } while (S >= 1.0); loop for steps 1–2, with rng.ranf(): 2.0*rng.ranf()-1.0 is uniform in \([-1,1)\).initializer_list and operator=: (*this) = {..., ..., ...};, or one by one with v[0], v[1], v[2].NT is not 3, print a message.pvector.cpp does them): the norm is 1 up to rounding errors (\(\sim10^{-16}\)); \(\langle z\rangle = 0\), \(\langle z^2\rangle = 1/3\) (as for \(x\) and \(y\), since \(x^2+y^2+z^2=1\)); the fraction with \(z > 1/2\) is \(1/4\).pvector.cpp#include "./pvector.hpp"
int main(void)
{
using ntype = double; // type of the components (first template argument)
constexpr int NT = 3; // number of components (second template argument)
rng.seed(1); // fixed seed: the same random numbers at every run
const int M = 1000000; // number of random vectors
const ntype L = 10.0; // side of the box
pvector<ntype,NT> R, U;
// random(L): each component uniform in [-L/2, L/2)
ntype rmin = L, rmax = -L, x2 = 0;
for (int k = 0; k < M; k++)
{
R.random(L);
for (int i = 0; i < NT; i++)
{
if (R(i) < rmin) rmin = R(i);
if (R(i) > rmax) rmax = R(i);
}
x2 += R(0)*R(0);
}
std::cout << "random(L): min=" << rmin << " max=" << rmax
<< " <x^2>=" << x2/M << " (exact L^2/12=" << L*L/12 << ")\n";
// random_orient(): uniform on the unit sphere
ntype dnmax = 0, z = 0, z2 = 0, cap = 0;
for (int k = 0; k < M; k++)
{
U.random_orient();
ntype dn = fabs(U.norm() - 1.0);
if (dn > dnmax) dnmax = dn;
z += U(2);
z2 += U(2)*U(2);
if (U(2) > 0.5) cap++; // spherical cap z > 1/2: a quarter of the sphere
}
std::cout << "random_orient(): max|norm-1|=" << dnmax << "\n"
<< " <z>=" << z/M << " (exact 0) <z^2>=" << z2/M << " (exact 1/3)"
<< " P(z>1/2)=" << cap/M << " (exact 1/4)\n";
return 0;
}random(L): min=-5 max=4.99999 <x^2>=8.32859 (exact L^2/12=8.33333)
random_orient(): max|norm-1|=3.33067e-16
<z>=0.000468512 (exact 0) <z^2>=0.333328 (exact 1/3) P(z>1/2)=0.250128 (exact 1/4)
P(z>1/2) becomes \(\simeq 1/3\).pmatrixq: a class templateproject/pmatrix.hpp: a class for square matrices \(NT \times NT\) (hence the q).
// [*] constructor with initializer_list
// [*] overloading of () operator (m(i,j))
// [*] overloading of << operator to print a matrix
// [*] matrix addition and subtraction
// [ ] += and -= operators
// [ ] matrix times scalar (also *=)
// [ ] matrix divided by scalar (also /=)
// [ ] scalar times matrix <--- with friend function
// [ ] matrix times vector
// [ ] vector times matrix <--- with friend function
// [ ] matrix times matrix (also *=)
// [ ] transpose
// [ ] operator == to pmatrix class
//
#include "./pvector.hpp"
template <typename ntype, int NT>
class pmatrixq
{
ntype m[NT][NT];
public:template <typename ntype, int NT>: type and size are parameters (N8, plus an integer parameter): pmatrixq<double,3>, pmatrixq<float,2>, … Inside the class, pmatrixq alone means pmatrixq<ntype,NT>.ntype m[NT][NT];: a C 2D array, m[i][j] is row i, column j. Today the [*] methods.project/pmatrix.hpp
~pmatrixq()
{
}
pmatrixq()
{
for (int i=0; i < NT; i++)
for (int j=0; j < NT; j++)
m[i][j]=0;
}
// to initialize a matrix as follows: pmatrixq<double,2> M={1,2,3,4};
pmatrixq(std::initializer_list<ntype> list)
{
}
// to initialize a matrix as follows: pmatrixq<double,2> M={{1,2},{3,4}};
pmatrixq(std::initializer_list<std::initializer_list<ntype>> list)
{
} {1,2,3,4}: a list of \(NT^2\) numbers, row by row: element \(k\) goes to m[k/NT][k%NT] (integer division and remainder).{{1,2},{3,4}}: a list of rows (an initializer_list of initializer_list): a range-based for over the rows, with another one inside over the elements of the row. Never write outside the array if the lists are too long.operator(), <<, +, -project/pmatrix.hpp
// ============================================================
// overloading of () operator to get/set (i,j)-th element
// m(i,j)=2.0;
// std::cout << m(i, j);
ntype& operator()(int i, int j)
{
}
ntype operator()(int i, int j) const
{
}
// output (std::cout << M) << "\n";
friend std::ostream& operator<<(std::ostream& os, const pmatrixq& M1)
{
}
// addition
pmatrixq operator+(const pmatrixq &M2) const
{
}
// subtraction
pmatrixq operator-(const pmatrixq &M2) const
{
}pvector, with two indices: M(i,j) returns m[i][j] (by reference if not const).<< prints row by row, {{1,2,3},{4,5,6},{7,8,9}}, and returns os. + and -: a local MT filled with two nested loops, returned by value.pmatrix.cppproject/pmatrix.cpp
#include "./pmatrix.hpp"
int main(void)
{
pmatrixq<double,3> A = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // NT*NT numbers, row by row
pmatrixq<double,3> B = {{2, 3, 2}, {3, 4, 5}, {8, 0, 1}}; // a list of rows
pmatrixq<double,3> C; // void constructor: all 0
const pmatrixq<double,3> K = {{1, 0, 0}, {0, 2, 0}, {0, 0, 3}};
std::cout << "A=" << A << "\n";
std::cout << "B=" << B << "\n";
std::cout << "A(1,2)=" << A(1,2) << "\n"; // operator(): read
C(0,0) = 5.0; // operator(): write
std::cout << "C=" << C << "\n";
std::cout << "K(2,2)=" << K(2,2) << "\n"; // const operator()
C = A + B; std::cout << "A+B=" << C << "\n";
C = A - B; std::cout << "A-B=" << C << "\n";
std::cout << "A=" << A << " K=" << K << "\n"; // chained <<
return 0;
}A={{1,2,3},{4,5,6},{7,8,9}}
B={{2,3,2},{3,4,5},{8,0,1}}
A(1,2)=6
C={{5,0,0},{0,0,0},{0,0,0}}
K(2,2)=3
A+B={{3,5,5},{7,9,11},{15,8,10}}
A-B={{-1,-1,1},{1,1,1},{-1,8,8}}
A={{1,2,3},{4,5,6},{7,8,9}} K={{1,0,0},{0,2,0},{0,0,3}}
rng.seed(1) before each ranf() you get always the same number; with rseed() each number comes from a new seed, and the statistical properties of the Mersenne Twister sequence are lost. Seed once, at the beginning of main.pvector R; or pmatrixq M; does not compile, write pvector<double,3> R; and pmatrixq<double,3> M;.m[k/NT][k%NT] with a list longer than \(NT^2\): writes outside the matrix.