QuantLib-Python: Multiprocessing Method Wrapper

In this post, I published a program for simulating term structure up to 30 years with daily time step, using Hull-White one-factor model. The resulting curve was able to replicate the given initial yield curve without any notable differences. The only serious issue here was the cost of running the program in time units.

In order to improve this specific issue, I got familiar with some multi-threading possibilities in Python. Now, there are some deep issues related to the way Python threads are actually implemented and especially the issues with thread locking known as GIL. Related stuff has been completely chewed in here. In order to avoid facing GIL-related issues, another way is to use Python multiprocessing, which allows the programmer to fully leverage multiple processors on a given machine. Moreover, separate processes are completely separate and one process cannot affect another's variables.

Comparison statistics

Again, I simulated term structure up to 30 years with daily time step, using 10000 paths. I did some quick profiling, in order to find the bottlenecks in the original program (sequential). By looking the column task share, we can see, that there are two tasks, which are consuming the most part of the complete running time: path generations (~54%) and path integrations (~46%). After this, I isolated these two parts and processed these by using multiprocessing scheme.

By using multiprocessing (two configured processes), I managed to decrease the complete running time from 163 seconds to 107 seconds. In general, for all those parts which were enjoying the benefits of multiprocessing, improvement ratio (multiprocessing per sequential) is around 0.65.

CPU puzzle

In order to understand the reason for this improvement, let us take a look at processor architecture in my laptop. First, let us check the "Grand Promise" made by System Monitor.

Based on this view, I actually expected to have four CPU for processing. I was then really surprised, that adding third and fourth process was not decreasing running time any further, than having just two processes. After some usual Stackoverflow gymnastics, I finally got the definition to calculate the real number of CPU available in my laptop.

CPU available is "Core(s) per socket * Socket(s)", which is 2 * 1 in my laptop. So, all in all I have only two CPU available for processing, not four as was shown in that System Monitor. This means, that having more than two CPU available in a laptop, one should expect even better improvement ratio than reported in my statistics here.

Wrapper method

In order to avoid code duplication and to come up with something a bit more generic, I started to dream about the possibility to create a mechanism for applying multiprocessing for any given method, if so desired. Such solution is possible by using Python lambda methods.

# method for executing given lambdas in parallel
def MultiprocessingWrapper(targetFunctionList):
    processList = []
    aggregatedResults = []
    queue = mp.Manager().Queue()

    # execute lambda from a given list based on a given index
    # storing results into queue
    def Worker(index):
        result = targetFunctionList[index]()
        queue.put(result)
    
    # start processes, call worker method with index number
    for i in range(len(targetFunctionList)):
        process = mp.Process(target = Worker, args = (i,))
        processList.append(process)
        process.start()
    
    # join processes, extract queue into results list
    for process in processList:
        process.join()
        aggregatedResults.append(queue.get())
        
    # return list of results for a client
    return aggregatedResults

Previous method is receiving a list of lambda methods as its argument. The idea is, that there would be always one lambda method for each process to be started. Why? We might face a situation, in which different set of parameters would be required for each lambda (say, all lambdas would be using the same uniform random generator, but with a different values for seeding the generator). In wrapper method, process is then created to start each configured lambda method. Results calculated by given lambda will be stored into queue. Finally, all results will be imported from queue into result list and returned for a client.

As concrete example, the following program segment is first creating two lambda methods for starting GeneratePaths method, but with different seed value for both processes. After this, wrapper method is then fed with the list of lambdas and processed paths will be received into list of results.

    # task of generating paths is highly time critical
    # use multiprocessing for path generation
    # create lambdas for multiprocessing wrapper
    # target signature: def GeneratePaths(seed, process, timeGrid, n)
    nPaths = 10000
    nProcesses = 2
    seeds = [1834, 66023]
    nPathsPerProcess = int(nPaths / nProcesses)
    target_1 = lambda:GeneratePaths(seeds[0], HW1F, grid.GetTimeGrid(), nPathsPerProcess)
    target_2 = lambda:GeneratePaths(seeds[1], HW1F, grid.GetTimeGrid(), nPathsPerProcess)
    targetFunctionList = [target_1, target_2]
    results = MultiprocessingWrapper(targetFunctionList)

The complete program can be found in my GitHub repository. Finally, a couple of discussion threads, which may be useful in order to understand some QuantLib-related issues, are given in here and here. Thanks for reading my blog and again, Merry Christmas for everyone.
-Mike
  

Excel : implementing multithreading using C# and Excel-DNA

Multithreading possibilities for VBA has been chewed in this post. My conclusion back then was, that there is no multi-threading possibilities for VBA. One reader has then been commenting this as follows :

"Correct to say there is no multithreading in VBA however, you can very easily create your multithreading functionality in a c# dll and expose the interface via Interops for VBA to consume. Then all you need to do is to pass in the data into the function and walla, you have multithreading. Interops is a very powerful feature and VBA fully supports it."

For the sake of completeness, I will present one possible program to implement such multithreading scheme for Excel, by using Parallel class for the actual multi-threading part and Excel-DNA for interfacing the program back to Excel (using Excel only as Input-Output platform). Excel interfacing part used in this post, has already been completely chewed within this post. Note, that by using instructions given in here or here, one can relatively easy interface this multithreading program back to VBA, instead of Excel.

The program

This unsurprising program is simply processing a task (simulate N amount of normally distributed random numbers) shared for M processors. Amount of simulated numbers and number of processors used is decided by the client (Excel). Finally, the program will print the aggregated time consumed for this task back to Excel. Needless to say, the effect of multithreading can be demonstrated by changing the number of processors in Excel worksheet.

Copy-Paste the following program presented below into a new C# project. Also, follow carefully all instructions given in this post.

Thanks for reading this blog.
-Mike

// ExcelInterface.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Windows.Forms;
using ExcelDna.Integration;

namespace ExcelInterface {
    // type definition, delegate for exporting data from processor to queue
    using Processor = Action<int, DataMessenger>;
    public delegate void DataMessenger(List<double> result);

    public static class ExcelInterface {
        // method available in excel
        public static void execute() {
            try {
                // create Excel application object
                dynamic Excel = ExcelDnaUtil.Application;
                //
                // get parameters from worksheet named ranges
                int n = (int)Excel.Range["_n"].Value2;
                int nProcessors = (int)Excel.Range["_nProcessors"].Value2;
                int nPerProcessor = n / nProcessors;
                // create data thread-safe queue and random processors
                RandomQueue messageQueue = new RandomQueue();
                List<Processor> processors = new List<Processor>();
                for (int i = 0; i < nProcessors; ++i) {
                    processors.Add(Factory.CreateProcessor());
                }
                // host timer, execute all processors in parallel
                Stopwatch timer = new Stopwatch();
                timer.Start();
                Parallel.For(0, nProcessors, i => {
                    processors[i].Invoke(nPerProcessor, messageQueue.Enqueue); 
                });
                timer.Stop();
                //
                // print processing time to excel
                double timeElapsed = timer.Elapsed.TotalSeconds;
                Excel.Range["_timer"] = timeElapsed;
            }
            catch (Exception e) {
                MessageBox.Show(e.Message);
            }
        }
    }
}

// RandomQueue.cs
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;

namespace ExcelInterface {
    // wrapper class for ConcurrentQueue data structure
    public class RandomQueue {
        private ConcurrentQueue<List<double>> randomQueue;
        public RandomQueue() {
            randomQueue = new ConcurrentQueue<List<double>>();
        }
        // add
        public void Enqueue(List<double> data) {
            randomQueue.Enqueue(data);
        }
        // remove
        public List<double> Dequeue() {
            List<double> data = null;
            bool hasValue = false;
            while (!hasValue) hasValue = randomQueue.TryDequeue(out data);
            return data;
        }
    }
}

// Factory.cs
using System;
using System.Collections.Generic;

namespace ExcelInterface {
    // type definition
    using Processor = Action<int, DataMessenger>;
    
    public static class Factory {
        // factory method for creating processor for random generator
        public static Processor CreateProcessor() {
            //
            // create standard normal variable generator
            // using action delegate and lambda expression
            Processor process =
            (int n, DataMessenger dataMessenger) => {
                Random generator = new Random(Guid.NewGuid().GetHashCode());
                List<double> normalRandomList = new List<double>();
                // loop through n
                for (int i = 0; i < n; ++i) {
                    double uniformRandomSum = 0.0;
                    // create standard normal random variable using CLT
                    for (int j = 0; j < 12; ++j) {
                        double uniformRandom = 0.0;
                        while (true) {
                            uniformRandom = generator.NextDouble();
                            if (uniformRandom > 0.0) break;
                        }
                        uniformRandomSum += uniformRandom;
                    }
                    normalRandomList.Add(uniformRandomSum - 6.0);
                }
                // send list of normal random variables to queue
                dataMessenger(normalRandomList);
            };
            return process;
        }
    }
}

C++11 : Multi-Threaded PathGenerator using PPL

 

FINAL DESTINATION

The circle has been closed. This post is kind of an aggregation, based on the last four posts published on generating random numbers. Initially, I started just with a simple template class for distributional random generator, then continued with a path generator using any one-factor stochastic process and finally, ended up with a multi-threaded distributional random generation scheme using Parallel algorithms. This final post (hopefully) is opening up my larger goal : to be able to generate asset price paths for any one-factor process, using multi-threading scheme.

GROUNDHOG DAY

Again, I have tested the both sequential (for_each) and parallel (parallel_for_each) schemes by using four generators, 10000 paths and 250 time steps for a single run. After this, I repeated this run for 250 times. Conclusion :

• The average running time for this sample was 17116 milliseconds (sequential) and 8209 milliseconds (parallel). So, parallel scheme will be completed about two times faster. 
• The actual CPU usage profiles during the simulation processes are behaving exactly as reported in this post. 
• I also analyzed processed asset price paths for parallel scheme, just to be absolutely sure there are no path duplicates (random number generation would not be independent). Based on my analysis made in Excel, all processed asset price paths are different and there are no duplicates. 

Presented scheme for path generator is again fulfilling my two initial requirements : faster creation of asset price paths following any one-factor process and independency of random generators.

RandomGenerator.h

The basic functionality of this template class has not been changed, except for construction part : second constructor is allowing a client to give any probability distribution for uniform generator from outside of this class. Even there is actually no need for having this kind of optionality in real-life (most of the stuff in Monte Carlo is randomized by using standard normal distribution), I decided to implement this optionality for the sake of completeness.

#pragma once
#include <algorithm>
#include <functional>
#include <vector>
#include <random>
#include <memory>
//
namespace MikeJuniperhillRandomGeneratorTemplate
{
 template <typename Generator = std::mt19937, typename Distribution = std::normal_distribution<double>>
 /// <summary>
 /// Template class for creating random number paths using mt19937 as default uniform 
 /// random generator and Standard Normal as default probability distribution.
 /// </summary> 
 class RandomGenerator
 {
 public:
  /// <summary>
  /// Constructor with explicit seed value
  /// </summary>
  RandomGenerator(unsigned long seed)
  {
   // construct function for processing distributional random number
   randomGenerator = [this](double x)-> double
   {
    x = distribution(uniformGenerator);
    return x;
   };
   // seed generator once
   uniformGenerator.seed(seed);
  }
  /// <summary> 
  /// Constructor for explicit seed value and client-given probability distribution.
  /// </summary>  
  RandomGenerator(unsigned long seed, const Distribution& distribution)
   // constructor delegation
   : RandomGenerator(seed)
  {
   // assign client-given probability distribution
   this->distribution = distribution;
  }
  /// <summary>
  /// Fill a given vector reference with distributional random numbers
  /// </summary> 
  void operator()(std::vector<double>& v) const
  {
   std::transform(v.begin(), v.end(), v.begin(), randomGenerator);
  }
 private:
  std::function<double(double)> randomGenerator;
  Generator uniformGenerator;
  Distribution distribution;
 };
}
//

OneFactorProcess.h

I decided to tag drift and diffusion functions with const declaration, since these functions should not modify the internal state of class data members.

#pragma once
//
namespace MikeJuniperhillOneFactorProcessLibrary
{
 /// <summary>
 /// Abstract base class for all one-factor processes for customizing 
 /// drift and diffusion functions for different types of processes.
 /// </summary>
 class OneFactorProcess
 {
 public:
  virtual double drift(double x, double t) const = 0;
  virtual double diffusion(double x, double t) const = 0;
 };
 //
 /// <summary>
 /// Implementation for Vasicek short-rate model.
 /// </summary>
 class Vasicek : public OneFactorProcess
 {
 public:
  Vasicek(double meanReversion, double longTermRate, double rateVolatility)
   : meanReversion(meanReversion), longTermRate(longTermRate), rateVolatility(rateVolatility) { }
  //
  double drift(double x, double t) const override { return meanReversion * (longTermRate - x); }
  double diffusion(double x, double t) const override { return rateVolatility; }
 private:
  double meanReversion;
  double longTermRate;
  double rateVolatility;
 };
}
//

PathGenerator.h

As in the case with RandomGenerator, the basic functionality of this template class has not been changed either, except for construction part : second constructor is allowing a client to give any probability distribution to be delivered for distributional random generator.

#pragma once
//
#include "RandomGenerator.h"
#include "OneFactorProcess.h"
namespace MJRandom = MikeJuniperhillRandomGeneratorTemplate;
namespace MJProcess = MikeJuniperhillOneFactorProcessLibrary;
//
namespace MikeJuniperhillPathGenerator
{
 template <typename Generator = std::mt19937, typename Distribution = std::normal_distribution<double>>
 class PathGenerator
 {
 public:
  /// <summary>
  /// Constructor for PathGenerator template class.
  /// </summary>
  PathGenerator(double spot, double maturity, unsigned long seed,
   const std::shared_ptr<MJProcess::OneFactorProcess>& process)
   : spot(spot), maturity(maturity), process(process)
  {
   // create random generator
   generator = std::unique_ptr<MJRandom::RandomGenerator<Generator, Distribution>>
    (new MJRandom::RandomGenerator<Generator, Distribution>(seed));
  }
  /// <summary>
  /// Constructor for PathGenerator template class, with a client-given probability distribution
  /// </summary>
  PathGenerator(double spot, double maturity, unsigned long seed,
   const std::shared_ptr<MJProcess::OneFactorProcess>& process, const Distribution& distribution)
   : spot(spot), maturity(maturity), process(process)
  {
   // create random generator with client-given probability distribution
   generator = std::unique_ptr<MJRandom::RandomGenerator<Generator, Distribution>>
    (new MJRandom::RandomGenerator<Generator, Distribution>(seed, distribution));
  }
  /// <summary> 
  /// Fill a given vector reference with asset prices, following a given stochastic process.
  /// </summary>  
  void operator()(std::vector<double>& v) const
  {
   // transform initialized vector into a path containing random numbers
   (*generator)(v);
   //
   double dt = maturity / (v.size() - 1);
   double dw = 0.0;
   double s = spot;
   double t = 0.0;
   v[0] = s; // 1st path element will always be the current spot price
   //
   // transform distributional random number vector into a path containing 
   // asset prices from a given stochastic one-factor process
   for (auto it = v.begin() + 1; it != v.end(); ++it)
   {
    t += dt;
    dw = (*it) * std::sqrt(dt);
    (*it) = s + (*process).drift(s, t) * dt + (*process).diffusion(s, t) * dw;
    s = (*it);
   }
  }
 private:
  double spot;
  double maturity;
  std::shared_ptr<MJProcess::OneFactorProcess> process;
  std::unique_ptr<MJRandom::RandomGenerator<Generator, Distribution>> generator;
 };
}
//

Tester.cpp

Tester program is closely tracking the program presented in previous post. For the sake of additional clarity, I have used new type definitions in order to improve code readability and get rid of some lengthy variable names. The program is again using simple factory method for creating PathGenerator (function wrapped in shared pointer). In this program, OneFactorProcess implementation is created and delivered for factory method for processing. Finally, there is a method for printing processed paths to console for testing purposes.

#include <iostream>
#include <chrono>
#include <ppl.h>
#include <concurrent_vector.h>
#include "PathGenerator.h"
namespace MJGenerator = MikeJuniperhillPathGenerator;
//
// type definitions
using Path = std::vector<double>;
using Paths = concurrency::concurrent_vector<Path>;
using Process = std::shared_ptr<MJProcess::OneFactorProcess>;
using Processor = std::function<void(void)>;
using PathGenerator = std::shared_ptr<Processor>;
//
// thread-safe container for storing asset price paths, processed by path generators
Paths paths;
//
// printer for generated asset price paths
void Printer()
{
 std::for_each(paths.begin(), paths.end(),
  [](Path path) -> void
 {
  std::for_each(path.begin(), path.end(),
   [](double s) -> void
  {
   std::cout << s << ",";
  });
  std::cout << std::endl;
 });
}
//
// factory method :
// return path-generating function as function wrapper
// input arguments are common for all types of generators
PathGenerator Factory(double spot, double maturity, int nPaths, 
 int nSteps, unsigned long seed, const Process& process, Paths& paths)
{
 // create function for processing one-factor paths
 auto generator = [=, &process, &paths]() -> void
 {
  MJGenerator::PathGenerator<> oneFactorProcess(spot, maturity, seed, process);
  Path path(nSteps);
  for (auto i = 0; i != nPaths; ++i)
  {
   oneFactorProcess(path);
   paths.push_back(path);
  }
 };
 // return generator function as function wrapper
 return PathGenerator(new Processor(generator));
}
//
int main()
{
 // create vasicek process
 double longTermRate = 0.05;
 double meanReversion = 0.2;
 double rateVolatility = 0.0075; 
 Process vasicek = Process(new MJProcess::Vasicek(meanReversion, longTermRate, rateVolatility));
 //
 // define parameters and seed values for path generators
 int nGenerators = 4;
 int nPaths = 100;
 int nSteps = (250 + 1);
 std::vector<unsigned long> seed = { 10322854, 65947, 387528, 772399573 };
 //
 // use factory method for creating path generators
 double spot = 0.0095;
 double maturity = 3.0;
 std::vector<PathGenerator> generators;
 for (auto i = 0; i < nGenerators; i++) generators.push_back(
  Factory(spot, maturity, nPaths, nSteps, seed[i], vasicek, paths));
 //
 // parallel processing
 auto start = std::chrono::steady_clock::now();
 concurrency::parallel_for_each(generators.begin(), generators.end(),
  [](PathGenerator pg) -> void { (*pg)(); });
 auto end = std::chrono::steady_clock::now();
 auto timeElapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
 std::cout << timeElapsed.count() << std::endl;
 //
 // print paths
 Printer();
 return 0;
}
//

Finally, thanks again for reading this blog.
-Mike

C++11 : Multi-Threaded Random Generator using PPL

After some woodshedding with C++11 random and publishing distributional random generator in my blog a couple of weeks ago, the next question was, how to make this thing to happen a bit faster? Since I already have been snooping PPL (Parallel Patterns Library), I realized that Parallel Algorithms in that library would be an excellent candidate for this task. There is a great and comprehensive internet book available on this topic. After getting familiar with some of the issues presented in these sources, one should be able to parallelize algorithms succesfully.

There are some very specific issues, related to random generator seeding. As I started to parallelize my random number generation (creating several generators and processing these using parallel algorithm), I realized that my random generators were not working as expected. After some further woodshedding I came to conclusion, that (in a multi-threaded setting) each generator has to be seeded independently. Finally, concerning my current generator implementation, I made a decision that a client has to provide explicit seed values for all generators. Based on my hands-on experience with a system used for counterparty credit risk simulations (widely ranked as state-of-the-art numerical software), I dare to say that this approach is well justified. Now, the question of what kind of tools will be used for creating the actual seed values, has been left to a client judgement. The rabbit hole of these profound issues related to random generators have been chewed in this blog. Do not enter, if you are not absolutely ready to take the red pill.

ROUGH DIAGNOSTICS

I tested the both sequential (for_each) and parallel (parallel_for_each) schemes by using four generators, 10000 paths and 250 time steps for a single run. After this, I repeated this run for 250 times. The average running time for this sample was 5187 milliseconds (sequential) and 2317 milliseconds (parallel). So, parallel scheme will be completed about two times faster. The actual CPU usages during simulation process for the both schemes are shown in the screenshot below. When using parallel algorithm, computer is able to utilize all four cores in my computer.

I also tested all processed random paths for the both schemes, just to be absolutely sure there are no path duplicates (random number generation would not be independent). Based on my analysis made in Excel, all processed paths for the both schemes are different and there are no duplicates. Presented scheme is hereby fulfilling my two requirements : faster creation of random paths and independency of random generators.

RandomGenerator.h

Current implementation for distributional random path generator is presented below. Note, that the actual seeder creation takes place outside of this class.

#pragma once
#include <algorithm>
#include <functional>
#include <vector>
#include <random>
//
namespace MikeJuniperhillRandomGeneratorTemplate
{
 template <typename Generator = std::mt19937, typename Distribution = std::normal_distribution<double>>
 /// <summary>
 /// Template class for creating random number paths using
 /// Mersenne Twister as default uniform random generator and
 /// Standard Normal (0.0, 1.0) as default probability distribution.
 /// </summary> 
 class RandomGenerator
 {
 public:
  /// <summary>
  /// set explicit seed value
  /// </summary>
  RandomGenerator(unsigned long seed)
  {
   // construct lambda method for processing standard normal random number
   randomGenerator = [this](double x)-> double
   {
    x = distribution(uniformGenerator);
    return x;
   };
   // seed generator
   uniformGenerator.seed(seed);
  }
  /// <summary>
  /// fill vector reference with distributional random numbers
  /// </summary> 
  void operator()(std::vector<double>& v)
  {
   std::transform(v.begin(), v.end(), v.begin(), randomGenerator);
  }
 private:
  std::function<double(double)> randomGenerator;
  Generator uniformGenerator;
  Distribution distribution;
 };
}
//

tester.cpp

First, all simulation parameters and explicit seed values for all generators are defined. Simple factory method is then used to create the actual generator function as lambda function. Next, factory method is returning generator function wrapped inside a shared pointer. Main program is then storing each created generator function into vector container and finally processing all generators (sequentially or parallel). Each generator is storing generated paths into thread-safe nested vector (std::vector inside concurrency::concurrent_vector).

#include <iostream>
#include <memory>
#include <chrono>
#include <ppl.h>
#include <concurrent_vector.h>
#include "RandomGenerator.h"
namespace MJ = MikeJuniperhillRandomGeneratorTemplate;
//
//
// thread-safe nested vector for storing random paths processed by generators
concurrency::concurrent_vector<std::vector<double>> paths;
//
// prototype for generator function
using Generator = std::function<void(void)> ;
//
// factory method :
// return generator function as function wrapper
std::shared_ptr<Generator> Factory(int nPaths, int nSteps, unsigned long seed, 
 concurrency::concurrent_vector<std::vector<double>>& paths)
{
 // create generator function
 auto generator = [=, &paths]()->void
 {
  // step 1 : create distributional random generator
  MJ::RandomGenerator<> randomGenerator(seed);
  // step 2 : create container for a random path
  std::vector<double> path(nSteps);
  // step 3 : create path using distributional generator
  // and import created path into thread-safe container
  for (auto i = 0; i != nPaths; ++i)
  {
   randomGenerator(path);
   paths.push_back(path);
  }
 };
 // return generator function as function wrapper
 return std::shared_ptr<Generator>(new Generator(generator));
}
//
int main()
{
 // define parameters and seed values for generator functions
 int nGenerators = 4;
 int nPaths = 10000;
 int nSteps = 250;
 std::vector<unsigned long> seed = { 10322854, 65947, 387528, 772399573 };
 //
 // use factory method for creating generator function
 std::vector<std::shared_ptr<Generator>> generators;
 for (auto i = 0; i < nGenerators; i++) generators.push_back(Factory(nPaths, nSteps, seed[i], paths));
 //
 // parallel processing
 auto start = std::chrono::steady_clock::now();
 concurrency::parallel_for_each(generators.begin(), generators.end(),
  [](std::shared_ptr<Generator> ppg) -> void { (*ppg)(); });
 //
 //// uncomment for sequential processing
 //std::for_each(generators.begin(), generators.end(),
 // [](std::shared_ptr<Generator> ppg) -> void { (*ppg)(); });
 //
 auto end = std::chrono::steady_clock::now();
 auto timeElapsed = (end - start);
 std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(timeElapsed).count() << std::endl;
 return 0;
}
//

Finally, thanks for reading my blog. I would like to wish Happy New Year for everybody.
-Mike

C++11 : PathGenerator Class

This blog posting is a sequel for the post I published just a couple of days ago. Having tools for generating random numbers is nice, but I still wanted to put that Random Generator template class to do something even more useful, like to produce paths for asset prices.

The idea was to create some practical means for transforming random number paths into asset price paths, following any desired (one-factor) stochastic process. For this purpose, I have created one template class (PathGenerator), which is technically just a wrapper for RandomGenerator template class and OneFactorProcess polymorphic class hierarchy. The purpose of RandomGenerator is to produce random numbers from desired probability distribution (usually that is standard normal) and the purpose of OneFactorProcess implementation is to provide information for PathGenerator on how to calculate drift and diffusion coefficients for a chosen stochastic process.

PATHS

For a marketing reasons, let us see the end product first. Simulated asset price paths for Geometric Brownian Motion and Vasicek processes are presented in Excel screenshot below. Test program (presented below) has been created in a way, that all processed asset price paths for a chosen stochastic process are exported into CSV file (which can then be imported into Excel for further investigation).

ONE-FACTOR PROCESS

Abstract base class (OneFactorProcess) is technically just an interface, which provides practical means for a client for customizing drift and diffusion functions for different types of stochastic processes. I decided to implement polymorphic class hierarchy, since class is still pretty compact place for storing private member data and corresponding algorithms using that member data.

In the first draft, I was actually implementing drift and diffusion coefficient algorithms by using functions and lambdas, which (being initially created in main program) would then have been used inside PathGenerator object. It was technically working well, but from the viewpoint of possible end user (say, having member data and algorithm implementations in different files) it would have been quite a different story.

#pragma once
//
namespace MikeJuniperhillOneFactorProcessLibrary
{
 /// <summary>
 /// Abstract base class for all one-factor processes
 /// is technically just an interface, which provides practical means
 /// for customizing drift and diffusion functions for different types of processes.
 /// </summary>
 class OneFactorProcess
 {
 public:
  virtual double drift(double x, double t) = 0;
  virtual double diffusion(double x, double t) = 0;
 };
 //
 /// <summary>
 /// Implementation for Vasicek short-rate model.
 /// </summary>
 class Vasicek : public OneFactorProcess
 {
 public:
  Vasicek(double meanReversion, double longTermRate, double rateVolatility)
   : meanReversion(meanReversion), longTermRate(longTermRate), rateVolatility(rateVolatility) { }
  double drift(double x, double t) override { return meanReversion * (longTermRate - x); }
  double diffusion(double x, double t) override { return rateVolatility; }
 private:
  double meanReversion;
  double longTermRate;
  double rateVolatility;
 };
 //
 /// <summary>
 /// Implementation for Geometric Brownian Motion.
 /// </summary>
 class GBM : public OneFactorProcess
 {
 public:
  GBM(double rate, double volatility) : rate(rate), volatility(volatility) { }
  double drift(double x, double t) override { return rate * x; }
  double diffusion(double x, double t) override { return x * volatility; }
 private:
  double rate;
  double volatility;
 };
}

PATH GENERATOR

PathGenerator object is using RandomGenerator object for creating random numbers from standard normal probability distribution, by using default seeder for default uniform generator (Mersenne Twister). At some point, this class was having several different constructors for client-given seeder and client-given probability distribution. However, for the sake of clarity, I decided to remove all that optionality. In most of the cases, we want to simulate random numbers from standard normal distribution and Mersenne Twister generator still does the uniform part pretty well. It should be noted, that if such a customizing need sometimes arises, this class can be modified accordingly.

#pragma once
//
#include "RandomGenerator.h"
#include "OneFactorProcess.h"
namespace MJRandom = MikeJuniperhillRandomGeneratorTemplate;
namespace MJProcess = MikeJuniperhillOneFactorProcessLibrary;
//
template <typename Generator = std::mt19937, typename Distribution = std::normal_distribution<double>>
class PathGenerator
{
public:
 /// <summary>
 /// Constructor for PathGenerator template class.
 /// <para> - using default seeder from chrono library </para>
 /// <para> - using standard normal distribution </para>
 /// <para> - using mersenne twister uniform generator </para>
 /// </summary>
 PathGenerator(double spot, double maturity, std::shared_ptr<MJProcess::OneFactorProcess>& process)
  : spot(spot), maturity(maturity), process(process)
 {
  // create default seeder lambda function for random generator
   this->seeder = [](void) -> unsigned long { return static_cast<unsigned long>
    (std::chrono::steady_clock::now().time_since_epoch().count()); };
  // create random generator
  generator = std::unique_ptr<MJRandom::RandomGenerator<Generator, Distribution>>
   (new MJRandom::RandomGenerator<Generator, Distribution>(this->seeder));
 }
 /// <summary> 
 /// Functor, which fills auxiliary vector reference with asset prices following a given stochastic process.
 /// </summary>  
 void operator()(std::vector<double>& v)
 {
  // transform initialized vector into a path containing random numbers
  (*generator)(v);
  //
  double dt = maturity / (v.size() - 1);
  double dw = 0.0;
  double s = spot;
  double t = 0.0;
  v[0] = s; // 1st path element is always the current spot price
  //
  // transform random number vector into a path containing asset prices
  for (auto it = v.begin() + 1; it != v.end(); ++it)
  {
   t += dt;
   dw = (*it) * std::sqrt(dt);
   (*it) = s + (*process).drift(s, t) * dt + (*process).diffusion(s, t) * dw;
   s = (*it);
  }
 }
private:
 double spot;
 double maturity;
 std::function<unsigned long(void)> seeder;
 std::shared_ptr<MJProcess::OneFactorProcess> process;
 std::unique_ptr<MJRandom::RandomGenerator<Generator, Distribution>> generator;
};

TESTER

Presented test program is creating two different one-factor processes (Geometric Brownian Motion, Vasicek) and using PathGenerator for simulating asset price paths. All processed paths for the both cases will then be printed into CSV file for further investigations (Excel). I dare to say, that the process of generating asset price paths for one-factor process is easy and straightforward with PathGenerator class. For testing purposes, RandomGenerator header file should be included in the project.

#include "PathGenerator.h"
#include <fstream>
//
// printer : after a simulation iteration, append a path content into a file
// this inefficient idiom is not suitable for anything else but crude testing
void Print(const std::vector<double>& v, const std::string& filePathName)
{
 std::ofstream file(filePathName, std::ios_base::app);
 for (auto& element : v) { file << std::to_string(element) << ";"; }
 file << std::endl;
}
//
int main()
{
 // define and delete output CSV test files
 const std::string fileForVasicekProcess = "C:\\temp\\paths.vasicek.csv";
 const std::string fileForBrownianMotion = "C:\\temp\\paths.brownianMotion.csv";
 std::remove(fileForVasicekProcess.c_str());
 std::remove(fileForBrownianMotion.c_str());
 //
 // create auxiliary vector container for path processing
 double t = 3.0; // time to maturity
 int nPaths = 250; // number of simulated paths
 int nSteps = 1095; // number of time steps in one path (3 years * 365 days = 1095 steps)
 // the size of vector must be the number of desired time steps 
 // plus one, since the first vector item will be the current asset spot price
 std::vector<double> path(nSteps + 1);
 //
 // example 1 : create paths using vasicek process
 double r = 0.0095;
 double longTermRate = 0.05;
 double meanReversion = 0.2;
 double rateVolatility = 0.0075;
 std::shared_ptr<MJProcess::OneFactorProcess> vasicek =
  std::shared_ptr<MJProcess::Vasicek>(new MJProcess::Vasicek(meanReversion, longTermRate, rateVolatility));
 PathGenerator<> shortRateProcess(r, t, vasicek);
 for (int i = 0; i != nPaths; ++i)
 {
  shortRateProcess(path); // generate a path
  Print(path, fileForVasicekProcess); // print a path
 }
 //
 // example 2 : create paths using geometric brownian process
 double s = 100.0;
 double rate = 0.02;
 double volatility = 0.25;
 std::shared_ptr<MJProcess::OneFactorProcess> brownianMotion =
  std::shared_ptr<MJProcess::GBM>(new MJProcess::GBM(rate, volatility));
 PathGenerator<> equityPriceProcess(s, t, brownianMotion);
 for (int i = 0; i != nPaths; ++i)
 {
  equityPriceProcess(path);  // generate a path
  Print(path, fileForBrownianMotion); // print a path
 }
 return 0;
}

Finally, thanks for reading my blog and have a very pleasant waiting time for Christmas.
-Mike

C++11 : Template Class for Random Generator

"Anyone who attempts to generate random numbers by deterministic means is, 
of course, living in a state of sin." - John Von Neumann

Despite of the fact that the quote above is still highly relevant, we mostly get the job done well enough using those pseudo-random generators for our Monte Carlo stuff. So, this time I wanted to present a wrapper for simulating (sinful) uniform random numbers, which are then mapped to a chosen probability distribution. The main goal was to construct a lightweight design, using C++11 uniform generators, probability distributions as well as some other extremely useful tools (function, lambda) for the task.

TEMPLATE DIET

Instead of implementing any class hierarchies, I tried to keep this design as lightweighted as possible by using template class having only two template data types to be defined by a client : Generator (uniform random generator) and Distribution (probability distribution for transforming uniformly distributed random numbers). In a nutshell, a client may use any random number engine available in C++11, for creating desired amount of uniform random numbers. Moreover, a client may use default probability distribution (Standard Normal) for transforming created uniform random numbers or additionally, use any desired probability distribution available in C++11. Available uniform random engines and probability distributions have been nicely covered in here.

ULTIMATE SIN

It should be a bit easier to sell something, if the final product is nicely presented. Random numbers processed by example program (presented later) for four different random generator implementations are presented in Excel screenshot below.

HEADER FILE

Random generator template class is presented below. Note, that this implementation does not require any auxiliary libraries, since all the required stuff is already in C++11. For usability reasons, I decided to keep all the actual method implementations in header file (RandomGenerator.h).

#pragma once
#include <algorithm>
#include <chrono>
#include <cmath>
#include <functional>
#include <iostream>
#include <math.h>
#include <memory>
#include <random>
#include <string>
#include <vector>
//
namespace MikeJuniperhillRandomGeneratorTemplate
{
 template <typename Generator = std::mt19937, typename Distribution = std::normal_distribution<double>>
 /// <summary> 
 /// Template class for creating random number paths using
 /// Mersenne Twister as default uniform random generator and 
 /// Standard Normal (0.0, 1.0) as default probability distribution.
 /// </summary>  
 class RandomGenerator
 {
 public:
  /// <summary>
  /// Constructor for using default probability distribution 
  /// for transforming uniform random numbers.
  /// </summary>  
  RandomGenerator(const std::function<unsigned long(void)>& seeder)
   : seeder(seeder)
  {
   // construct lambda method for processing standard normal random number
   randomGenerator = [this](double x)-> double
   {
    x = distribution(uniformGenerator);
    return x;
   };
   // seed uniform random generator with a client-given algorithm
   uniformGenerator.seed(seeder());
  }
  /// <summary> 
  /// Constructor for using client-given probability distribution 
  /// for transforming uniform random numbers.
  /// </summary>  
  RandomGenerator(const std::function<unsigned long(void)>& seeder, const Distribution& distribution)
   // constructor delegation for initializing other required member data
   : RandomGenerator(seeder)
  {
   // assign client-given probability distribution
   this->distribution = distribution;
  }
  /// <summary> 
  /// Functor filling vector with random numbers mapped to chosen probability distribution.
  /// </summary>  
  void operator()(std::vector<double>& v)
  {
   std::transform(v.begin(), v.end(), v.begin(), randomGenerator);
  }
 private:
  std::function<unsigned long(void)> seeder;
  std::function<double(double)> randomGenerator;
  Generator uniformGenerator;
  Distribution distribution;
 };
}

TESTER FILE

Example program (tester.cpp) for testing random generator functionality is presented below. The process of generating (pseudo) random numbers from a probability distribution is easy and straightforward with this template wrapper class.

#include "RandomGenerator.h"
namespace MJ = MikeJuniperhillRandomGeneratorTemplate;
//
// printer for a random path
void Print(const std::string& message, const std::vector<double>& v)
{
 std::cout << message << std::endl;
 for (auto& element : v) std::cout << element << std::endl;
 std::cout << std::endl;
}
//
int main()
{
 // construct lambda method for seeding uniform random generator
 std::function<unsigned long(void)> seeder = 
  [](void) -> unsigned long { return static_cast<unsigned long>
  (std::chrono::steady_clock::now().time_since_epoch().count()); };
 //
 // create vector for a path to be filled with 20 random numbers
 // from desired probability distribution, using desired uniform random generator
 int nSteps = 20;
 std::vector<double> path(nSteps);
 //
 // path generator : mersenne twister, standard normal
 MJ::RandomGenerator<> gen_1(seeder);
 gen_1(path);
 Print("mt19937 : x~N(0.0, 1.0)", path);
 //
 // path generator : minst_rand, standard normal
 MJ::RandomGenerator<std::minstd_rand> gen_2(seeder);
 gen_2(path);
 Print("minstd_rand : x~N(0.0, 1.0)", path);
 //
 // path generator : mersenne twister, normal(112.5, 1984.0)
 std::normal_distribution<double> nd(112.5, 1984.0);
 MJ::RandomGenerator<> gen_3(seeder, nd);
 gen_3(path);
 Print("mt19937 : x~N(112.5, 1984.0)", path);
 //
 // path generator : minstd_rand, exponential(3.14)
 std::exponential_distribution<double> ed(3.14);
 MJ::RandomGenerator<std::minstd_rand, std::exponential_distribution<double>> gen_4(seeder, ed);
 gen_4(path);
 Print("minstd_rand : x~Exp(3.14)", path);
 //
 return 0;
}

Finally, thanks again for reading this blog.
-Mike