Lab #4

Templates, random numbers and a class for matrices

Cristiano De Michele

A quotation to check

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.

  • It appears in none of his books, lectures or recorded interviews.
  • The earliest attribution that can be found is from 2021: a post by @ProfFeynman, a fan account.
  • Before that, the sentence circulated without an author, and shorter: “Knowledge is knowing the right answer. Intelligence is asking the right question.”

The tool did the search, but the question came from the person using it: without that question, this slide would carry the wrong name.

Two quotations with a source

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.

A Feynman quotation with a source

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).

  • To check an answer, whether it comes from a person or from a tool, you must understand what it is about; and to understand it you must be able to build it.
  • This is why in this course you write the Monte Carlo and molecular dynamics codes yourselves, in C++, instead of using a ready-made package.

Feynman’s dozen problems

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.

Today

  1. Introduction to C++ (part IV) — generic programming: class templates (example N8) and a glimpse of template metaprogramming (example N9).
  2. Lab #3: the solution — operator(), the friend functions and <<.
  3. Random numbers — what a pseudo-random number generator is, how the generators of the C++ standard library compare, and why we use the Mersenne Twister through the class randnumgen, which you get complete.
  4. Tasks for 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).
  5. Task: a class for matrices — the first methods of pmatrixq, a class template that follows pvector closely.

Part 1
Introduction to C++ (part IV)

Where we left off

  • pvector stores NT numbers of type ntype, both fixed once for the whole program at the top of pvector.hpp:

    constexpr int NT=3;     // (it was #define NT 3: why it changed, in Part 4)
    using ntype=double;

    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).

Example N8: genvec.hpp

examples/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];
    }
  void show(void) const
    {
      std::cout << "(";
      for (int i = 0; i < NT; i++) 
        {
          std::cout << get(i);
          if (i < NT-1)
            std::cout << ",";
          else
            std::cout << ")\n";
        }
    }
  genvec()
    {
    }

  ~genvec()
    {
    }
};
  • 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.

Example N8: genvec.cpp

examples/N8_generic_programming/genvec.cpp

#include "./genvec.hpp"
int main(void)
{
  genvec<double> gv; 
  for (int i = 0; i < 3; ++i) {
    gv.set(i, i+0.1);
  }
  gv.show();
  return 0;
}
g++ -std=c++17 -Wall -o genvec genvec.cpp
./genvec
(0.1,1.1,2.1)
  • 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.
  • The template argument is part of the type: 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').

Class templates

  • 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:

    template <typename ntype, int NT>     // pmatrixq<double,3>: 3x3 matrices of double (Part 5)
    template <class ntype, class engine>  // randnumgen<double,std::mt19937_64> (Part 3)
  • 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.

Example N9: 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;
};

Example N9: 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);
}

Example N9: how it works

  • 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\).
  • Printing: 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).
  • At run time the program only prints: all the numbers are already in the executable.

Compile-time errors are a feature

g++ -std=c++17 -Wall -o myfibonacci myfibonacci.cpp && ./myfibonacci
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]
  • \(F_{93} \simeq 1.2\times 10^{19}\) does not fit in a 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).
  • We will not write metaprograms. What we use from this example: 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.
  • The folder also contains fibonacci.cpp, an alternative implementation: the sum is done by a class Sum, and << is overloaded to print any std::tuple.

Part 2
Lab #3: the solution

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]; 
    }
  • Each version is one line, 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.

Scalar times vector and rint()

project/pvector.hpp

  // scalar times vector 
  // (*this) is not implicitly passed to operator* in this case, 
  // being a friend operator of pvector class
  // pvector A;
  // double s;
  // s*A
  friend pvector operator*(ntype s, const pvector& V2)
    {
      pvector VT;
      for (int i=0; i < NT; i++)
        {
          VT.v[i] = s*V2.v[i];
        }
      return VT;
    }
  // rint() function
  // pvector A, B={1.1,2.2,3.3};
  // A = rint(B);
  friend pvector rint(const pvector& V2)
    {
      pvector VT;
      for (int i=0; i < NT; i++)
        {
          VT.v[i] = rint(V2.v[i]);
        }
      return VT;
    }
  • Both are friend functions, not methods: no *this, all the operands are arguments, and they can read V2.v[i] because they are friends of pvector.
  • In 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

  // pvector V;
  // (std::cout  <<  V ) << "\n";
  //     os      ,     vec
  friend std::ostream& operator<<(std::ostream& os, const pvector& vec)
    {
      os << "(";
      for (int i=0; i < NT; i++)
        {
          os << vec.v[i];
          if (i < NT-1)
           os << ","; 
        }
      os << ")";
      return os;
    }
  • It writes into 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).

Part 3
Random numbers

Random numbers in a simulation

  • Monte Carlo needs many random numbers: to choose a particle and its displacement, to accept or reject the move (compare \(e^{-\beta\Delta U}\) with a number in \([0,1)\)), for initial configurations and velocities: \(10^9\)–\(10^{10}\) in a long run.
  • A computer produces pseudo-random numbers: a deterministic sequence \(X_{n+1} = f(X_n)\), which starts from a seed \(X_0\). Same seed, same sequence: a run can be repeated exactly (useful for debugging); different seeds give independent runs.
  • What we want from a generator:
    • uniformity and no correlations between successive numbers, which must pass statistical tests;
    • a period (length of the sequence before it repeats) much longer than what a simulation uses;
    • speed and a small state (the memory that stores \(X_n\)).
  • Correlated numbers make the simulation sample the wrong distribution, silently.

The simplest generator: linear congruential (LCG)

Figure: Wikipedia, “Linear congruential generator”.

Limits of the LCG, and rand()

  • Fast and with a tiny state, but the period is at most \(m\) (with \(m \leq 2^{32}\): about \(4\times10^9\) numbers, less than a long simulation uses); with \(m = 2^k\) the low bits are poorly random.
  • Consecutive numbers are correlated. Use three of them, \((X_n, X_{n+1}, X_{n+2})/m\), as the position of a point in a cube: the points do not fill the cube, they all lie on a few parallel planes (only 15 for RANDU, an LCG widely used in the 1960s).
  • The C function 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.

The generators of the C++ standard library

  • Predictability: from a few outputs one can compute the next ones. It matters in cryptography, not in simulations.
  • State: memory per generator. Period: the Mersenne Twister repeats after \(2^{19937}-1\) numbers, a number with about 6000 digits; ranlux has an excellent period but is very slow.

Table: arvid.io (2018), “On C++ Random Number Generator Quality”.

Statistical tests: PractRand

  • PractRand is a battery of statistical tests applied to more and more output of a generator: 512 MB, 1 GB, …, 2 TB. ✗: the output is detected as not random.
  • LCG (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”.

Why the Mersenne Twister

  • It is in the standard library (std::mt19937, std::mt19937_64 in <random>): no external code to install.
  • Statistically good enough for us: a long MC run uses \(\sim 4\times10^{9}\) numbers of 64 bits, i.e. \(\sim 32\) GB of output, well below the 512 GB where mt19937_64 starts to fail the most demanding tests.
  • A huge period (\(2^{19937}-1\)), and an acceptable speed: in a simulation most of the time goes into the energies, not into the random numbers.
  • A good compromise between quality, speed and availability. Its weaknesses (predictability, a state of a few KB, the failure after hundreds of GB) do not matter for our simulations.

The class 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);
    }

The class 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;
#endif

How to use randnumgen

rng.seed(1);        // fixed seed: the same sequence at every run
rng.rseed();        // or: a different seed at every run (clock + std::random_device)
double xi = rng.ranf();   // uniform in [0,1)
  • randnumgen 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)\).
  • Line 59 defines one global object 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).
  • Without 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.
  • The standard does not fix the algorithm of the distributions: with the same seed, another compiler may give other numbers. Only the statistics must agree.

Part 4
New tasks for pvector: a template, random vectors

The tasks

Download 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) 
  // ============== LAB #4: skeletons, fill the bodies

  // generate a random vector inside a box and assign it to (*this) object
  void random(const ntype& L)
    {

    }

  // generate a random vector on unit sphere and assign it to (*this) object
  void random_orient(void)
    {

    }

The goal: project/pvector.cpp (in the zip) must print the output at the end of this part.

Task 1: pvector becomes a class template

In 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:

//constexpr int NT=3;

//typedef float ntype; // as in C
//using ntype=double; // use "using" to define an alias for the keyword "double"

template <typename ntype, int NT>
class pvector
{
  ntype v[NT]; // private member
  • Nothing else changes: inside the template, pvector alone means pvector<ntype,NT>, so the methods, the operators and the friend functions stay as they are.

Task 1: the template arguments

  • Where the vectors are used, the template arguments are needed: 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.
  • Check: pvector.cpp must compile (its output is meaningless until random() and random_orient() are written). Before the change: error: 'pvector' is not a template.
  • If you comment out NT and ntype but forget the template line: error: 'ntype' does not name a type.
  • If your 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 box

  • Each component uniform in \([-L/2, L/2)\): rng.ranf() is uniform in \([0,1)\), so (rng.ranf()-0.5)*L is uniform in \([-L/2, L/2)\).
  • Why centred in the origin: it is the box of the minimum image convention (Lab #3), 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.
  • A check: for \(x\) uniform in \([-L/2, L/2)\), \(\langle x\rangle = 0\) and \(\langle x^2\rangle = L^2/12\).

Spherical coordinates fail

  • Goal: \(\hat{\mathbf{u}}\) uniform on the sphere: the probability of a region \(\propto\) its area (solid angle).
  • The naive way: \(\theta\) uniform in \([0,\pi]\), \(\phi\) uniform in \([0,2\pi)\), and \(\hat{\mathbf{u}} = (\sin\theta\cos\phi, \sin\theta\sin\phi, \cos\theta)\). Wrong.
  • Think of the grid of meridians and parallels: uniform \(\theta\) and \(\phi\) put the same number of points in each cell \(\Delta\theta\,\Delta\phi\), but the cells shrink near the poles, where the meridians converge: a higher probability at the poles.
  • In formulas, the area of a cell, which vanishes at the poles, is \[d\Omega = \sin\theta\, d\theta\, d\phi\]
  • In numbers: the cap \(z > 1/2\) (\(\theta < \pi/3\)) is 1/4 of the sphere, but the naive method puts there 1/3 of the points.
  • The right distribution: \(d\Omega = d(\cos\theta)\, d\phi\) (up to the sign), so \(z = \cos\theta\) must be uniform in \([-1,1]\) (not \(\theta\)), and \(\phi\) uniform in \([0,2\pi)\).

Wrong and right

  • 4000 points each. Left: \(\theta\) and \(\phi\) uniform: the points crowd at the poles (the centre of the top view, the top and bottom of the side view). Right: Marsaglia’s algorithm: the same density everywhere.
  • See also “Sphere Point Picking” on Wolfram MathWorld.

Marsaglia’s algorithm

  1. Take \(V_1, V_2\) uniform in \((-1, 1)\) and compute \(S = V_1^2 + V_2^2\).
  2. If \(S \geq 1\) reject the pair and go back to 1: the accepted \((V_1,V_2)\) are uniform inside the unit circle (probability of acceptance \(\pi/4 \simeq 0.785\)).
  3. The unit vector is \[\hat{\mathbf{u}} = \left(2V_1\sqrt{1-S},\; 2V_2\sqrt{1-S},\; 1-2S\right)\]

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.

  • Only two random numbers per try and one square root: no sin, cos, acos.
  • Detailed proof: “Detailed proof of Marsaglia’s algorithm”, PDF on the course page (Lectures → Lab notes). Original paper: G. Marsaglia, Ann. Math. Statist. 43, 645 (1972).

random_orient(): implementation

  • A do { ... } while (S >= 1.0); loop for steps 1–2, with rng.ranf(): 2.0*rng.ranf()-1.0 is uniform in \([-1,1)\).
  • Then set the components, e.g. with the constructor with initializer_list and operator=: (*this) = {..., ..., ...};, or one by one with v[0], v[1], v[2].
  • The algorithm is for 3D vectors: if NT is not 3, print a message.
  • Checks (the goal 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\).

The goal: 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;
}

Compile, run, compare

cd ~/csm/project
g++ -std=c++17 -Wall -o pvector pvector.cpp
./pvector
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)
  • With \(M = 10^6\) samples the statistical error on the averages is \(\sim 10^{-3}\): your numbers must agree with the exact values within a few thousandths. With another compiler, or another seed, the last digits change.
  • Try the naive spherical coordinates: P(z>1/2) becomes \(\simeq 1/3\).

Part 5
A class for matrices

pmatrixq: a class template

project/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.

Constructors

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
    {
    }
  • As in 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.

The goal: pmatrix.cpp

project/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}}

Classic pitfalls

  • Seeding inside a loop: with 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.
  • No seed at all: every run gives the same numbers (the default seed). Fine for debugging, wrong for independent runs.
  • Spherical coordinates with \(\theta\) uniform: points crowd at the poles. Also normalizing a random vector of the cube \([-1,1)^3\) is not uniform (the directions of the corners are favoured), unless the points outside the unit sphere are rejected first.
  • Forgetting the rejection in Marsaglia’s algorithm: the pairs \((V_1,V_2)\) must be uniform inside the circle, not in the square.
  • A template used without its arguments: 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.

Checklist for today