- Joined
- 8/5/14
- Messages
- 312
- Points
- 303
Yesterday I cracked upon Hull Chapter 13 and read the chapter on binomial trees. I decided it would be a cool project to code it up. About 6 hours later, I've got a nice Binomial Option (call) pricing application (I could easily extend it for put options later).
What I learned: In the end, the application showed that the Binomial Tree model converged to the exact solution as the number of time steps got large.
How I did it: First I wrote a general binomial lattice template class. Then I wrote a class which contained all the Binomial Tree data (using composition of the lattice) needed in order to solve the problem (i.e. find the option price today). The lattice data member stored a tuple<double, double>, which contained the stock price and option price of the respective position in the tree. Algorithms were implemented to solve the problem.
I was wondering if any of the experts (@APalley , @Daniel Duffy ) could give me some feedback on my implementation in C++. I know I get the right answer, but I would like to improve efficiency. Thanks in advance.
Binomial Lattice Class:
Binomial Tree Problem Solver Class:
Main Function for Testing:
What I learned: In the end, the application showed that the Binomial Tree model converged to the exact solution as the number of time steps got large.
How I did it: First I wrote a general binomial lattice template class. Then I wrote a class which contained all the Binomial Tree data (using composition of the lattice) needed in order to solve the problem (i.e. find the option price today). The lattice data member stored a tuple<double, double>, which contained the stock price and option price of the respective position in the tree. Algorithms were implemented to solve the problem.
I was wondering if any of the experts (@APalley , @Daniel Duffy ) could give me some feedback on my implementation in C++. I know I get the right answer, but I would like to improve efficiency. Thanks in advance.
Binomial Lattice Class:
Code:
// Ryan Shrott: Aug 11, 12
#ifndef BinomialLattice_h
#define BinomialLattice_h
#include <vector>
#include <iostream>
template <typename T>
class BinomialLattice
{
private:
std::vector< std::vector<T> > m_lat;
unsigned m_timeSteps;
unsigned m_intial;
public:
BinomialLattice();
BinomialLattice(unsigned timeSteps, const T& intial);
BinomialLattice(const BinomialLattice<T>& rhs);
virtual ~BinomialLattice();
// Assignment operator
BinomialLattice<T>& operator= (const BinomialLattice<T>& rhs);
// Data fetching (and Modifying, since we return by reference) (Remark: A data pounsigned is uniquely defined by a timeStep and a state)
T& operator()(const unsigned& timeStep, const unsigned& state); // define the 0th state to be the bottom most state of lattice (for fixed time step)
const T& operator()(const unsigned& timeStep, const unsigned& state) const; // const method of fetching state data for some time step
// Accessing size of lattice
unsigned get_timeSteps() const;
// Access and change member variables
const std::vector< std::vector<T> >& Lat(void) const;
std::vector< std::vector<T> >& Lat(void);
unsigned Steps(void) const;
// Mutate member variables
void Lat(const std::vector< std::vector<T> > lat);
void Steps(const unsigned steps);
// Print Lattice data to console window
template <typename T>
friend std::ostream& operator<< (std::ostream& os, const BinomialLattice<T>& lat);
};
#ifndef BinomialLattice_cpp
#include "BinomialLattice.cpp"
#endif
#endif
Code:
// Ryan Shrott: Aug 11, 12
#ifndef BinomialLattice_cpp
#define BinomialLattice_cpp
#include "BinomialLattice.h"
template<typename T>
BinomialLattice<T>::BinomialLattice()
{
m_lat.resize(2 + 1); // Define time(0) = first time step, so size is timeSteps + 1
for (unsigned i = 0; i < m_lat.size(); ++i)
{
m_lat[i].resize(i + 1, 0.0); // The i'th time step has i+1 possible states
}
m_timeSteps = 2;
}
template <typename T>
BinomialLattice<T>::BinomialLattice(unsigned timeSteps,const T& intial)
{
m_lat.resize(timeSteps + 1); // Define time(0) = first time step, so size is timeSteps + 1
for (unsigned i = 0; i < m_lat.size(); ++i)
{
m_lat[i].resize(i + 1, intial); // The i'th time step has i+1 possible states
}
m_timeSteps = timeSteps;
}
template <typename T>
BinomialLattice<T>::BinomialLattice(const BinomialLattice<T> & rhs)
{
m_lat = rhs.m_lat; // vector assignment overload
m_timeSteps = rhs.m_timeSteps;
}
template <typename T>
BinomialLattice<T>::~BinomialLattice()
{
}
template<typename T>
BinomialLattice<T>& BinomialLattice<T>::operator=(const BinomialLattice<T>& rhs)
{
if (this != &rhs)
{
m_timeSteps = rhs.m_timeSteps;
m_lat.resize(m_timeSteps + 1); //resize time steps
for (unsigned i = 0; i < m_lat.size(); ++i)
{
m_lat[i].resize(i + 1, 0.0); // The i'th time step has i+1 possible states
}
for (unsigned t = 0; t <= m_timeSteps; ++t) // traversing time
{
for (unsigned s = 0; s <= t; ++s) // traversing possible states
{
(*this)(t, s) = rhs(t, s);
}
}
}
return *this;
}
template <typename T>
T& BinomialLattice<T>::operator()(const unsigned & timeStep, const unsigned & state)
{
return m_lat[timeStep][state];
}
template <typename T>
const T& BinomialLattice<T>::operator()(const unsigned & timeStep, const unsigned & state) const
{
return m_lat[timeStep][state];
}
template <typename T>
unsigned BinomialLattice<T>::get_timeSteps() const
{
return m_timeSteps;
}
template<typename T>
const std::vector< std::vector<T> >& BinomialLattice<T>::Lat() const
{
return m_lat;
}
template<typename T>
std::vector<std::vector<T>>& BinomialLattice<T>::Lat(void)
{
return m_lat;
}
template<typename T>
unsigned BinomialLattice<T>::Steps() const
{
return m_timeSteps;
}
template<typename T>
void BinomialLattice<T>::Lat(const std::vector<std::vector<T>> lat)
{
m_lat = lat;
}
template<typename T>
void BinomialLattice<T>::Steps(const unsigned steps)
{
m_timeSteps = steps;
}
template <typename T>
std::ostream& operator<< (std::ostream& os, const BinomialLattice<T>& lat)
{
std::cout << "Lattice: " << std::endl;
for (unsigned t = 0; t <= lat.get_timeSteps(); ++t) // traversing time
{
for (unsigned s = 0; s <= t; ++s) // traversing possible states
{
std::cout << lat(t, s) << "\t";
}
std::cout << std::endl;
}
return os;
}
#endif
Binomial Tree Problem Solver Class:
Code:
// Ryan Shrott: Aug 11, 12
#ifndef BinomialTree_h
#define BinomialTree_h
#include "BinomialLattice.h"
#include <algorithm>
#include <cmath>
#include <boost/tuple/tuple.hpp> // Tuple class
#include <boost/tuple/tuple_io.hpp> // I/O for tuples
typedef boost::tuple<double, double> data; // format: (stock price, option price)
class BinomialTree // contains all the data which conmprise a binomial tree model for the underlying
{
private:
BinomialLattice<data> m_lat; // each point of lattice stores the stock price and option price, as a tuple
unsigned m_timeSteps;
double m_u; // UP multiplier
double m_d; // DOWN multiplier
double m_riskFree; // risk free interest rate
double m_K; // strike price
double m_delta_T; // length of a time-step
double m_S_zero; // intitial value of stock
public:
BinomialTree(double timeExpiration, double numSteps, double sigma, double r, double k, double s);
~BinomialTree();
BinomialTree(const BinomialTree& rhs);
BinomialTree& operator=(const BinomialTree& rhs);
// Solve option prices director
void Solve(void); // calculates all option prices at each time step and modify lattice structure
// Calculate Risk Free probability measure
double RiskFreeProb(void) const;
// Data fetching (and Modifying, since we return by reference) (Remark: A data pounsigned is uniquely defined by a timeStep and a state)
data& operator()(const unsigned& timeStep, const unsigned& state); // define the 0th state to be the bottom most state of lattice (for fixed time step)
const data& operator()(const unsigned& timeStep, const unsigned& state) const; // const method of fetching state data for some time step
// Accessing size of lattice
unsigned get_timeSteps() const;
// Print Lattice data to console window
friend std::ostream& operator<< (std::ostream& os, const BinomialTree& lat);
};
#endif
Code:
// Ryan Shrott: Aug 11, 12
#include "BinomialTree.h"
BinomialTree::BinomialTree(double timeExpiration, double numSteps, double sigma, double r, double k, double s)
{
m_timeSteps = numSteps;
m_delta_T = timeExpiration/ (numSteps + 1);
m_lat = BinomialLattice<data>(m_timeSteps, boost::make_tuple(0.0,0.0));
m_u = exp(sigma * sqrt(m_delta_T));
m_d = exp(-1 * sigma * sqrt(m_delta_T));
m_riskFree = r;
m_S_zero = s;
m_K = k;
// Assigning Stock Prices at each time step
for (unsigned t = 0; t <= this->get_timeSteps(); ++t) // traversing time
{
for (unsigned s = 0; s <= t; ++s) // unsign stock prices as a function of stock price, up multiplier and down multiplier
{
(*this)(t, s).get<0>() = m_S_zero * pow(m_u, s) * pow(m_d, t - s);
}
}
// Assigning option prices for last time step
for (unsigned s = 0; s <= this->get_timeSteps(); ++s)
{
(*this)(this->get_timeSteps(), s).get<1>() =( (*this)(this->get_timeSteps(), s).get<0>() > m_K ? (*this)(this->get_timeSteps(), s).get<0>() - m_K: 0.0 ); // intialize option prices at each time step to zero
}
}
BinomialTree::~BinomialTree()
{
}
BinomialTree::BinomialTree(const BinomialTree & rhs)
{
m_lat.BinomialLattice<data>::operator=(rhs.m_lat);
m_u = rhs.m_u;
m_d = rhs.m_d;
m_riskFree = rhs.m_riskFree;
m_delta_T = rhs.m_delta_T;
m_S_zero = rhs.m_S_zero;
}
BinomialTree & BinomialTree::operator=(const BinomialTree & rhs)
{
if (this != &rhs)
{
m_lat.BinomialLattice<data>::operator=(rhs.m_lat);
m_u = rhs.m_u;
m_d = rhs.m_d;
m_riskFree = rhs.m_riskFree;
m_delta_T = rhs.m_delta_T;
m_S_zero = rhs.m_S_zero;
}
return *this;
}
void BinomialTree::Solve(void)
{
for (unsigned t = this->get_timeSteps() - 1; t != -1; --t) // traversing time backwards
{
for (unsigned s = 0; s <= t; ++s) // unsign stock prices as a function of stock price, up multiplier and down multiplier
{
if ((*this)(t + 1, s + 1).get<1>() == 0 && (*this)(t + 1, s).get<1>() == 0)
{
(*this)(t, s).get<1>() = 0.0;
}
else // the expected value (using risk free prob) discounted continuously
{
(*this)(t, s).get<1>() = exp(-m_riskFree * m_delta_T) *
(this->RiskFreeProb() * (*this)(t + 1, s + 1).get<1>() + (1 - this->RiskFreeProb()) * (*this)(t + 1, s).get<1>());
}
}
}
}
double BinomialTree::RiskFreeProb(void) const
{
return (exp(m_riskFree * m_delta_T) - m_d) / (m_u - m_d);
}
data& BinomialTree::operator()(const unsigned& timeStep, const unsigned& state)
{
return m_lat.Lat()[timeStep][state]; // return a double tuple
}
const data& BinomialTree::operator()(const unsigned & timeStep, const unsigned & state) const
{
return m_lat.Lat()[timeStep][state]; // return a double tuple
}
unsigned BinomialTree::get_timeSteps() const
{
return m_timeSteps;
}
std::ostream& operator<< (std::ostream& os, const BinomialTree& lat)
{
std::cout << "Lattice: " << std::endl;
for (unsigned t = 0; t <= lat.get_timeSteps(); ++t) // traversing time
{
for (unsigned s = 0; s <= t; ++s) // traversing possible states
{
std::cout << lat(t, s) << "\t";
}
std::cout << std::endl;
}
return os;
}
Main Function for Testing:
Code:
// Ryan Shrott: Aug 11, 12
#include "BinomialTree.h"
#include <iostream>
using namespace std;
#include <cmath>
#include <boost/tuple/tuple.hpp> // Tuple class
#include <boost/tuple/tuple_io.hpp> // I/O for tuples
typedef boost::tuple<double, double> data; // data = (stock price, option price)
int main()
{
double numSteps, timeToExp;
cout << "Enter time to expiration (T): "; cin >> timeToExp;
cout << "Enter the number of time steps: "; cin >> numSteps;
BinomialTree TreeProblem(timeToExp, numSteps, 0.30, 0.08, 65.0, 60.0); // notation: BinomialTreedouble(timeExpiration, numSteps, sigma, r, K, S_0)
TreeProblem.Solve();
//cout << TreeProblem << endl;
cout << "The option price today should be: " << TreeProblem(0, 0).get<1>() << endl;
return 0;
}