Monday, 12 March 2012

Optimizing Black-Scholes in F#

Dave Thomas published an interesting post called Black-Scholes Taste Test 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 | Put

let a1 = 0.31938153
let a2 = -0.356563782
let a3 = 1.781477937
let a4 = -1.821255978
let a5 = 1.330274429
let b = 0.2316419
let 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 x

let 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

No comments: