Minimise function with single minimum and no maximums

Question

I'm learning F#. I wrote a function to minimise a function with a single minimum and no maximums. At the bottom I test it on Math.Cos.

What do you think? I've wrote it pretty much as I would in an imperative language. Could it be done more functionally?

/// <summary>Assuming f is a continuous function with a single minimum and 
/// no maximums in (lower,upper), find the minimum point.</summary>
let rec minimise f (lower:float) (upper:float) =
 let lmid = (2.0*lower+upper)/3.0
 let umid = (lower+2.0*upper)/3.0
 if lmid = lower && umid = upper then
 Seq.minBy f [lower; upper]
 else if f lmid < f umid then 
 minimise f lower umid
 else
 minimise f lmid upper
let solution = minimise Math.Cos 0.0 6.0
printf "solution: %g" solution
printf "absolute error: %g" (solution - Math.PI)

Answer 1

This is actually pretty functional.

The only thing I'd recommend is to avoid comparing floating-point numbers for exact match. Because arithmetic happens in binary, not in decimal, multiplying and dividing by nice-looking decimal numbers will produce ugly-looking binary ones, and more importantly, lose precision. As a result, depending on the input, your terminating condition may literally never become true - e.g. lmid may come out just a bit higher than lower at every step, and your function will recurse indefinitely.

The bottom line is, you can't trust direct comparison of floating-point numbers. Instead, compare their difference with a very small number (aka "margin of error"). But even then, you can't just use a constant for this, because you never know if it will be "small enough" for the inputs. The accepted way of doing this is to use a fraction of the inputs - aka "relative margin of error" (as opposed to "absolute").

 if x = y ... // bad
 if abs (x-y) <= 0.00001 ... // better
 if abs (x-y) <= (abs x * 0.00001) ... // even better

Answer 2

This looks pretty good to me. A few little tips:

• The type annotations on the lower and upper parameters are not strictly necessary since they would be inferred by the compiler from usage. However, you may prefer to be explicit and keep them there.

• You can write elif instead of else if.

• The <summary> tags are not necessary in your doc comment. They are added in automatically. You only need them if if you also want to use other tags like <param>.