Integer Sequence Explorer

My integer sequence database explorer is finally up and running over at my website.  Essentially, this application allows the user to choose two integer sequences from many common sequences, then runs a query which selects common members from each sequence.

One of the interesting tasks has been to write many small applications which produce the sequences to be loaded into the database relations.  I started out a little too optimistic, and wrote code which calculated the first million primes, squares, sum of divisors, and others.  I quickly found that when I ran queries on these tables, they took way to long, and my server was timing out.  I incrementally scaled things back until I was left with the first 10,000 members of most sequences.  Now my task is to re-design the database to allow for larger searches.

I will be loading up more sequences over the next few weeks, and posting explanations and links for the sequences.

Multi-Period Binomial Options

Here is my latest program for calculating the prices of options using a multi-period binomial tree. It works, but represents a bunch of strange methods to solve unexpected problems.
First, I decided to calculate the price at each node by finding the price at the terminal nodes, then use a formula, rather than calculate the prices recursively. This technique, as you will see, led to the problem of calculating binomial coefficients.

The thing that I am most satisfied with is that I was able to get the program to output to a text file, which can be opened in Excel to visualize the data.  The only thing that the program does not do is to do the same calculation with the Black-Scholes formula, and visualize how the binomial calculation approaches the Black-Scholes result.

First, take a look at my output:

Binomial Pricing

We can see how the results approach a limit with each iteration.  The pricing for periods 34 and 35 is starting to get weird because of limits of integer sizes and floating point number sizes.

Here is a chart of the above data:

Binomial Option Tree

Finally, here is the code:

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <fstream>

//Calculates price of European call or put option, and portfolio required to duplicate option, using binomial tree

int nchoosek(int n,int k);
//choice holds the binomial tree so that it doesn’t need to be recalculated
unsigned long long choice [50][50]={};

int main() {
using namespace std;
float S0, r,div, K, h,t,sigma, u, d,pStar, uS,dS,Cu,Cd,delta, bondValue;
double optionPrice;
double prices [50];
int n;
string callPut;
int putTrue;
//fill in nchoosek tree
for (int m=1; m<50;m++)
{ choice [m][0]=1;
choice [m][m]=1;}
for (int m=2;m<(50);m++)
{ for (int l=1;l<m;l++){
choice[m][l]=choice[m-1][l-1]+choice[m-1][l];
}
}
//get data from user
cout<<“Calculate the price of a European call or put, using a one period binary tree, then find rate with n period tree.”<<endl;
cout<<“Current Stock Price?”;
cin>>S0;
cout<<“Continuously Compounded Risk Free Rate?”;
cin>>r;
cout<<“Continuous Dividend Rate?”;
cin>>div;
cout<<“Volatility?”;
cin>>sigma;
cout<<“Strike Price?”;
cin>>K;
cout<<“Time to Expiration?”;
cin>>t;
cout<<“Number of Periods? (less than 50 please)”;
cin>>n;
cout<<“Call or Put?”;
cin>>callPut;
if ((callPut == “put”)||(callPut==”p”))
putTrue=-1;
else putTrue=1;
//calculate likely upward and downward motions
u=exp((r-div)*t+sigma*sqrt(t));
d=exp((r-div)*t-sigma*sqrt(t));
uS=u*S0;
dS=d*S0;
cout<<“Upward Move “<<uS<<endl;
cout<<“Downward Move “<<dS<<endl;
//calculate payoff of call, given motions above
//the variable putTrue turns Us-K into K-Us.  Cool.
Cu=fmax(0, putTrue*(uS-K));
Cd=fmax(0, putTrue*(dS-K));
//calculate Delta, Beta, and call option price
delta=exp(-div * t)*(Cu-Cd)/(S0*(u-d));
bondValue=exp(-r * t)*((u*Cd)-(d*Cu))/(u-d);
optionPrice=delta*S0+bondValue;
cout<<“To duplicate the option, buy “<<delta<<” shares=”” of=”” the=”” stock=”” for=”” “<<delta*s0<<“=”” dollars=”” and=”” borrow=”” “<<-1=”” *=”” bondvalue<<“=”” at=”” rate=”” “<<r<<“=”” a=”” total=”” price=”” “<<optionprice<<<span=”” class=”hiddenSpellError” pre=”” data-mce-bogus=”1″>endl;
cout<<“Price of Option “<<optionPrice<<endl;
cout<<“Prices above 30 levels deep may accumulate errors wildly”<<endl;

//Multi Period tree
int j=1;
while(j<(n+1)){
h=t/j;
u=exp((r-div)*h+sigma*sqrt(h));
d=exp((r-div)*h-sigma*sqrt(h));
pStar=(exp((r-div)*h)-d)/(u-d);
optionPrice=0;

for (int m=0; m<(j+1); m++) {
//This is the big doozy.
//Instead of computing the price at each interior node, only the terminal nodes are calculated
//and the price is found using the binomial theorem
optionPrice=optionPrice+nchoosek(j,m)*pow(pStar,j-m)*pow((1-pStar),m)*fmax(0,(putTrue* ((S0*pow(u, j-m)*pow(d,m))-K)));
}
optionPrice=optionPrice*exp(-r*t);
prices [j]=optionPrice;
cout<<“Periods: “<<j<<”  “;
cout<<“Option Price:  “<<optionPrice<<endl;
++j;  }

//output prices to text file
//open the text file in excel
//data is delimited by commas
ofstream outf(“Results.txt”);
if (!outf)
{  cerr << “File Error”<<endl;
exit(1); }
outf<<“Depth of Tree”<<“,”<<“Price”<<endl;
j=1;
while(j<(n+1)){
outf << j <<“,”<< prices[j]<< endl;
++j;  }
return 0;}

int nchoosek(int n, int k)
{ if (n>49 ||k>49)return 0;
else { return choice[n][k]; }}

The heart of everything is this ugly beast:

optionPrice=optionPrice+nchoosek(j,m)*pow(pStar,j-m)*pow((1-pStar),m)*fmax(0,(putTrue* ((S0*pow(u, j-m)*pow(d,m))-K)));

This is better put as C=C+\binom j m p^{*^{j-m}}(1-p*)^m*max(0,put(S_ou^{j-m}d^m-K)

You can figure out why this works fairly easily.  I like the bit where I multiply (F_{0,T}-K) by -1 to get (K-F_{0,T}.

More than anything, this exercise shows how errors creep into these long calculations.  Looking at the graph, you can see how our numbers are already wandering away from the correct numbers after the 20th iteration.