\documentclass[10pt,letterpaper]{article}
\pagestyle{headings}
\usepackage{html}
\usepackage{progdoc}
\bibliographystyle{apalike}
\begin{document}
\title {C++  Implementation of Haar systems for Black-Scholes model}
\author{
Sebastian Ferrando and Alex Korobchevsky
}

\date{\today}
\maketitle


\begin{abstract}
This technical report describes the associated C++ library
{\it localMC: A C++  Implementation of localized Monte Carlo
on trees}. This library implements some of the algorithms
described in the reference \cite{ariel}. The goal of the project 
was mainly to develop the functionality needed to obtain
the numerical output required in that paper.
\end{abstract}
\tableofcontents
%\pagebreak

\section{Goals} 

The system goal is option pricing by using a variety of underlyings, derivatives and algorithms. The underlyings implemented so far are binomial and continium. The derivatives used are European versions of the average strike, fixed strike and lookback. The algorithms used are Basic Monte Carlo, Exact values on a Tree, Local Monte Carlo and Local Monte Carlo with fast shift. Let us describe briefly each of the concepts mentioned above.

From mathematical point of view, an underlying is a relation which receives an asset value as an argument and returns it's next value. A continious underlying has an infinite number of outcomes with a given argument where as a discrete underlying has a finite number of outcomes. Therefore a binomial underlying has only two outcomes. Obviously, a continious underlying is much more realistic. For instance, if a stock has a value of a hundred dollars today it can have any value tomorrow. A binomial model would assume a stock can either go up or down so the only values it can have is 90 or 110 dollars. 

A derivative is a kind of option contract from financial point of view. We will use only European derivatives i.e. which can be exercised only at the end of the time period. The derivatives we use so far are average strike, fixed strike and lookback. Mathematically, we are looking how much each option will pay us of. Average Strike is an option which pays the difference between end value and the average along the path if positive, zero othervise. Look back is an option which pays the difference between end value and the minimum along the path and always excersiced. However, for the strike we do care about the values along the path because they make up the average. 

The main focus of our research is algorithms. So far we use Basic Monte Carlo, Local Monte Carlo and Local MC with Fast Shift. Basic Monte Carlo is based on performing a large number of simulations, accumulating the payoffs and computing an average option value. This algorithm is very simple and slow. Most of the CPU time is spent on generating random numbers. We can generate less random numbers by applying the so called shift techniques. Generic shift reuses any given by the user amount of random numbers. Fast shift uses the previous value of the stock to compute the next one. In summary, shift algorithms are faster but less reliable then standard MC and should be used when a fast approximation is required. 

\section{Design} 
\subsection{Class hierarchy}

The system we were describing above was implemented in ANSI C++. It was tested on linux with g++2.96 but hopefully will run on most modern C++ compilers if configured and customized properly. The design is based heavily on standard OO concepts: classes, inheritance and virtual functions. The extractor which invokes the g2 library is wriiten in ANSI C and connected to C++ application by \emph{system} calls.  

The underlying class hierarchy is based on Abstract Base Class underlying which has prototypes for all functions and all variables required by every particular underlying. 

\sourceinput[fontsize=8, listing, linenr]{../Src/Und/Underlying.h}{All}

Please note that this design is subject to change when we introduce more underlyings. In addition to standard underlying parameters a pointer to random generator is included (an OO concept of composition). Two most interesting methods are \emph{next()} and \emph{setBranchProb()}. Next returns the value of the asset one time increment later and uses the random generator heavily. \emph{setBranchProb()} computes the probability of the stock to go up and applies to binomial underlyings only. \emph{Binom()} and \emph{Continium()} classes implement all methods from Underlying class. As a remark, in \emph{Continium()} branch probability doesn't depend on ups and downs so \emph{setBranchProb()} method has an empty body.

As mentioned above, this project is based on using lots of random numbers. Random generator code was taken from GNU scientific library and encapsulated into a class. 

\sourceinput[fontsize=8, listing, linenr]{../Src/Rng/GSL_RandomGen.h}{All}

The interface for random generator class includes functions \emph{setSeed()}, \emph{next()} and \emph{getName()}. The user has three random number generator to chose from: \emph{mnt}, \emph{taus} and \emph{gfsr}. These three selected generators are bith best performance ratings from over 60 generators available at GSL. The default random generator is \emph{mnt}. The implementation if the generators is hidden from the user. 

All derivatives, both path dependents and independents have \emph{init()} and \emph{update()} methods. \emph{init()} is called before sampling the path, \emph{update()} is called between the timesteps to change intermediate values (sums or averages). \emph{Init()} and \emph{update()} have empty bodies for path dependent derivatives. There are two versions of update. The update with final stock, front and initial asset value is used for fast shift only.

\sourceinput[fontsize=8, listing, linenr]{../Src/Der/Derivative.h}{All}

The algorithm implementation is quite different for every algorithm. But there is one method each algorithm is required to implement: \emph{calcResults()} which computes option value and standard error. An algorithm has one parameter: starting asset value. As we already said the algorithms implemented so far are MC, Shift and Haar.


\subsection{Physical file organization}

All project files are put in \emph{mcRAsum02} directory which has these subdirectories: \emph{Doc}, \emph{Src}, \emph{Lib} and \emph{Exe}. Two additional files are there: \emph{readme} with a brief project description and \emph{regs} that performs regression testing. regs compiles and runs underlying test program and the test application (subject to change). The Doc directory contains the pdweave file to allow extraction of code fragments with progdoc. A Makefile processes the pdweaved file with latex and create dvi and/or postcript versions of the documentation. In Exe subdirectory future application code will be placed. The Lib subdirectory contains the libraries used for the project. Each library includes header files, source files in case the user wishes to recompile the library and a static library file if no recompilation is needed. Each library has a benchmark to test it's basic functionality. The libraries we use so far are MyGSL (adapted from GNU scientific library and used to generate random numbers), G2 generates plots in PostScript format. When a maintaince programmer wishes to add a library  he is adviced to follow this pattern.

We need more detailed coverage of Src subdirectory. It has four subdirectories: Rng contains the random generator code wrapped into a class. We must mention original GSL is implemented in C but we linked it in C++ and wrapped into a class for convenience. Und subdirectory contains all the underlying code. Note that all files are header files since all functions are brief and declared inline.  A test directory includes underlying testing code. Dersubdirectory contains all the derivative code. All files are header files as in the underlyings but there is no test directory since it makes little sense to test derivatives independently. However, algorithms do have  implementation .cpp files since the functions are too complex to be placed inline. In the Alg directory we have a test subdirectory which contains current application code and a makefile to run it. 

An Exe subdirectory contains the \emph{gop, ngop} applications, the input, extractor files. In addition to that, all object files are put there.
 
\sourceinput[fontsize=8, listing, linenr]{../Src/org}{All}

\section{Implementation} 

In this section we will go over some non trivial pieces of code in all directories. 

\subsection{Algorithms} 

Thats how we implement the exact value continium for the look back option:

\sourceinput[fontsize=8, listing, linenr]{../Src/Alg/ContExactValues.cpp}{Cont}

Thats how we implement the tree exact value (only critical section is shown):

\sourceinput[fontsize=8, listing, linenr]{../Src/Alg/ExactValues.cpp}{Critical}

As we mentioned above, Local Monte Carlo has been combined together with fast shift. Here is the section which includes the generic fast shift. The minimum is updated for lookback, while the average is updated for the strikes.

\sourceinput[fontsize=8, listing, linenr]{../Src/Alg/LocalMC.cpp}{Shift}

Implementation of an error with Local Monte Carlo 

\sourceinput[fontsize=8, listing, linenr]{../Src/Alg/LocalMC.cpp}{Error}

For implementation details refer to Requirements Document.

\subsection{Utilities} 

Here is a function used by Exact values on Continium. It uses numerical approximation to normal Cumulative function. Number of steps can be changed if we would like to have more presicion.

\sourceinput[fontsize=8, listing, linenr]{../Src/utilities.cpp}{Cum}

Another important function is logarithmic probability function which important for determining class probability in local Monte Carlo.

\sourceinput[fontsize=8, listing, linenr]{../Src/utilities.cpp}{Log}


\subsection{Main program}

The main generic option plotter application is straightforward. It gets data from the user by using prompts and the input file. We will only demonstrate a single line that performs the computations. It uses the underlying and derivative objects created by getting all user input and invoke \emph{calcResults} on an algorithm object created already. The ouput results are stored in vectors and saved to output files.  

\sourceinput[fontsize=8, listing, linenr]{../Exe/gop.cpp}{Critical}

\section{Test plan}

\subsection{Random generator test}

The random number generator needs to be chosen from over 60 ones found in GNU Scientific Library. We are looking for both speed and rondomness. We need to make sure a number chosen will be uniform in range 0..1 and be generated as fast as possible. For this reason a benchmark is written which accepts 3 command line arguments: generator name, fraction and number of hits. For instance, we generate one million uniform numbers and check how many are below 0.3. The ideal generator will give 300000 numbers. That's how we check the accuracy: how close we get to the theoretical number. To test the speed standard UNIX time utility can be used to check how long does it take to generate a million random numbers. Therefore, a trade off needs to be found between speed and presicion. The generator which performs best is mnt19937. We confirm that finding by gsl rating of it's generators. 

\sourceinput[fontsize=8, listing, linenr]{../Src/Rng/Test/testgen.cpp}{All}

\subsection{Underlying test}

To test the binom underlying we hardcode underlying and derivative parameters. Number of timesteps assumed to be 3 and up/down probabilities assumed identical. So we have 8 paths: UUU, UUD, UDU, UDD, DUU, DUD, DDU, DDD. Each path needs to have identical number of occurences since it has the same probability. If we get that the underlying is working. 

\sourceinput[fontsize=8, listing, linenr]{../Src/Und/Test/test.cpp}{All}
\subsection{Testing in large}

System testing is algorithm testing. For more information on testing ideas refer to Requirements Documents. In test appication we hardcode all underlying parameters. The binom2 underlying is equivalent so it's never tested in that appliction. For each algorithm we try to run all derivatives available. Basic Monte Carlo can be compared with Brendan's true values. Generic Shift ( and other variations) must converge to Basic Monte Carlo. Haar gives precise option values for relatively small number of simulations due to it's control variate. The user is encouraged to hardcode other underlying parameters and check the results. For a large number of simulation the processing time will be large. For large number of timesteps results might not be exact due to round off errors especially for Fast Shift and Haar algorithms. 

\sourceinput[fontsize=8, listing, linenr]{../Src/Alg/Test/test.cpp}{Critical}

\section{Installation manual} 

\begin{enumerate}
\item Copy the archive file \emph{mcRAsum02.tgz} to your account

\item Untar the application 
	\emph{tar xvfz mcRAsum02.tgz}

\item Copy all unpacked files to some directory on your account.
\end{enumerate}

\section{User manual}

\begin{enumerate}
\item The major application is called \emph{gop}, which stands for \emph{generic option plotter}. 
It generates data files with ouput from simulations. The user has flexibility to select random 
generator from the command line by just passing any of the following arguments to the command line:
{\it mt, taus, gfsr} (the default is {\it mt} which
does not need to be explicitly typed). The underlying, derivative and algorithm are selected by prompting 
the user, whereas other parameters are given from the input file. 

\item The \emph{extractor} application is called directly by \emph{gop} after all computations are complete. Up to five algorithm can be plotted simultaneously. Two windows will pop up: one withe error display, the other with option values.

\item Please be sure to give meaningful names to files as they will appear as labels to the plots. The error files will have the same name as the data files with the prefix of \emph{err_}.    

\item The user might want to use extractor directly after {\it gop} has been called. 
It receives the following command line arguments (where \emph{outputfile} will be a postcript file): 
Points is the number of points extractor will read from the inputfiles (starting from beginning). Recall that the file \emph{input} (used by gop to create the output data) uses \emph{M0}, \emph{gap} and \emph{steps}.So \emph{points} is actually equals to steps, where

\begin{verbatim}
M = M0 + steps * gap
\end{verbatim}

All these information is in the file \emph{E}, create dby {\it gop}. Here is an example for
this file:
\sourceinput[fontsize=8, listing, linenr]{E}{All}
One small issue is that we may run gop in several windows so \emph{E} will contain info only in one of these files. If all windows are run with compatible information, of course the output can be plotted via extractor. Output file names from \emph{gop} are used for plotting and also to create error files. 
\item \emph{ngop} is made by make \emph{ngop} this program will create data in terms of \emph{N}. At the moment is comparing Basic Monte Carlo on the tree and continuous. It goes from \emph{1} to \emph{N}, and \emph{N} is read from \emph{input} file. For each run (for fixed \emph{N}) \emph{M0}, \emph{gap} and \emph{steps} are taken from \emph{input}.

\item The user can change plot layout by editing any of the parameters below and recompiling the \emph{extractor}. To do so, type 
\begin{verbatim}
	make plot
\end{verbatim}

in the command prompt. Here is some option that can be edited,

\sourceinput[fontsize=8, listing, linenr]{../Exe/extractor.c}{extractorProperties}

\sourceinput[fontsize=8, listing, linenr]{../Exe/extractor.c}{extractorProperties2}

\item To use exact continium formula for the lookback choose \emph{Continium} Underlying, and the \emph{Exact Value Continium} algorithm.

\item Here we include a shell session when running gop

\sourceinput[fontsize=8, listing, linenr]{exampleOfRunningGop}{all}

\end{enumerate}

To run the test application just change to \emph{mcRAsum02/Src/Alg/Test} and type \emph{./test}. A command line argument can specify random generator to be chosen from \emph{mnt} (default), \emph{taus} or \emph{gfsr}. Other parameters can be changed by only recompiling the code.

 


\section{Developers guide to maintainance}

\begin{enumerate}
\item To add an underlying extend the abstract base class Underlying. Put the header file into \emph{Src/Und} directory.
\item To add a derivative extend the abstract base class Derivative. Put the header file into \emph{Src/Der} directory.
\item To add an algorithm extend the abstract base class Algorithm. Put the header and source files into \emph{Src/Alg} directory. Add a target to a main makefile.
\item We have included a shell script to run some benchmarks. Here is the file
\sourceinput[fontsize=8, listing, linenr]{../regs}{all}
\begin{thebibliography}{99}
\bibitem{ariel} S.E.~Ferrando and A.~Bernal,
Localized Monte Carlo algorithm to compute 
prices of path dependent options on trees. 
Submitted  (June 2004) to {\it International Journal 
of Theoretical and Applied
Finance}, 21 pages.
\end{thebibliography}
\end{document}
