We in fact don't really need to keep all the random numbers in memory, if the option price is the only thing we want to calculate, which is the case in the simple option pricing problem we are handling. At the end of the day, what really matters and hence we have to keep track of is the sum of all simulated option payouts rather than individual simulated payouts. In other words, every time when we generate a random number to simulate an option payout, there's no harm to throw away the random number as long as we have added the simulated payout to a partial sum value we keep track of.
That's where tail recursion can help. We want to use tail recursion with the accumulator pattern to achieve constant space complexity. In the code below, the sum parameter of the loop function keeps track of the partial sum and plays the role of accumulator.
Well, here is the performance results for 10 million simulation runs on my laptop:
version

option price

CPU time (ms)

absolute time (ms)

List

10.118465

5,335

5,467

Array

10.118465

1,606

1,639

Tail Recursion

10.118465

2,730

2,732

The performance of the tailrecursive version is quite OK relative to List and Array. Anyhow, the following results show the true power of tail recursion when it comes to 100 million runs.
version

option price

CPU time (ms)

absolute time (ms)

List

out of memory

out of memory

out of memory

Array

out of memory

out of memory

out of memory

Tail Recursion

10.118305

26,800

26,898

Perhaps memory consumption is a more important factor to monitor than CPU time or absolute time. If I manually bring up Windows Task Manager, I can see that the memory use of the tailrecursive code remains steadily at the level of 1.4MB while the memory use of either the List or Array version keeps growing up to 1.8GB until it eventually throws out the outofmemory exception and crashes.
///////////////////////////////////////////////////////////////////////////////
open System
open System.Diagnostics
let N = 10000000
let rnd = new Random(1)
let box_muller_transform (u1,u2) = sqrt(2.0*log(u1)) * cos(2.0*Math.PI*u2)
let call_payout K S = max (SK) 0.0
let European_Option_Price (payout:float>float) S0 r vol T =
let S_T x = S0 * exp((r  0.5*(vol**2.0))*T + vol*sqrt(T)*x)
let rec loop n sum =
if n = N then sum
else let new_sample = (rnd.NextDouble(),rnd.NextDouble())
> box_muller_transform> S_T > payout
loop (n+1) (sum+new_sample)
(loop 0 0.0) / (float N) > (*) (exp(r*T))
let S0 = 50.0
let K = 40.0
let r = 0.01
let vol = 0.2
let T = 0.25
let price() =
let price = European_Option_Price (call_payout K) S0 r vol T
printfn "option_price = %f" price
let time f =
let proc = Process.GetCurrentProcess()
let cpu_time_stamp = proc.TotalProcessorTime
let timer = new Stopwatch()
timer.Start()
try
f()
finally
let cpu_time = (proc.TotalProcessorTimecpu_time_stamp).TotalMilliseconds
printfn "CPU time = %dms" (int64 cpu_time)
printfn "Absolute time = %dms" timer.ElapsedMilliseconds
time price
Could you please post the code in a monospaced font? Or maybe embed gists? It'd be easier to read that way. Thanks.
ReplyDeleteI'm still learning how to blog. In fact I am struggling with getting the code formatted properly. Will definitely spend time improving it. thanks
Delete