Monday, 12 March 2012

Optimizing Black-Scholes in F#

Dave Thomas published an interesting post called where he describes Black-Scholes calculators written in idiomatic C# and F# and finds that the F# is 30% faster than the C#. This is primarily due to the use of floating-point exponentiation in the C# vs the pown function in F#.
We found there is still considerable room for improvement. Specifically, the following optimizations make our F# solution 40% faster than Dave's F#:

• Hoist the constants including the magic number 0.2316419 and 1.0 / sqrt(2.0 * Math.PI).
• Consolidate the call to abs and the final branch in the cns function into a single branch using F#'s inline to factor out the commonality.
• Do common subexpression elimination (CSE) on the k*k*k etc. by hand.
• Replace /2.0 with *0.5.
• In the blackscholes function, eliminate the common subexpression sqrt t.
• Potentially use partial application to precompute a blackscholes function for either Call or Put in order to remove dynamic dispatch from the inner loop (but this depends upon how the function is called).

This resulted in the following F# solution:
`type Style = Call | Putlet a1 = 0.31938153let a2 = -0.356563782let a3 = 1.781477937let a4 = -1.821255978let a5 = 1.330274429let b = 0.2316419let c = 1.0 / sqrt(2.0 * System.Math.PI)let cnd x =  let inline w l =    let k  = 1.0 / (1.0 + b * l)    let k2 = k * k    let k4 = k2 * k2    c * exp(-0.5 * l * l) * (a1 * k + a2 * k2 + a3 * k * k2 + (a4 * k4 + a5 * k * k4))  if x < 0.0 then w -x else 1.0 - w xlet blackscholes style s x t r v =  let sqrtt = sqrt t  let d1 = (log(s / x) + (r + v * v / 2.0) * t) / (v * sqrtt)  let d2 = d1 - v * sqrtt  let x = x * exp(-r * t)  match style with  | Call -> s * cnd d1 - x * cnd d2  | Put -> x * cnd -d2 - s * cnd -d1`