Hi
I re-implemented golden search in ML using NRC as guidance. In doing so, I think I discovered two typos. According to me,

SHFT3(x0,x1,x2,R*x1+C*x3)

should be

SHFT3(x0,x1,x2,R*x2+C*x3)

as you're putting the new x2 between the old x2 and x3. A similar typo would exists for the other case.

*Or* is this some weird macro behavior of SHFT3, which shifts x2 to x1 before the last argument is evaluated ? In which case SHFT3 makes the code rather unreadable.

Hi Frank,

You're seeing the difference between a function call and a macro. A macro basically gets replaced by its definition in line. For the macro

SHFT3(x0,x1,x2,R*x1+C*x3)

at the time the last argument of SHFT3 is evaluated, x1 has already been replaced by its new value x2, as you suspected. So the argument

R*x1+C*x3

could equally well be written

R*x2+C*x3

However, if SHFT3 were a function call (as it is in the C++ version), then the arguments are completely evaluated before entering the function, so you *must* write

shft3(x0,x1,x2,R*x2+C*x3);

Hope this clears things up.

Saul Teukolsky

Thanks ! That is what I thought.

With all due respect, I do believe the use of shift is confusing, and a lot of its use could be replaced by a more readable tail recursion (which does not grow the call stack). FYI, my ML version of golden search:

let golden ?(tol=3e-8) f (ax,bx,cx) =
let rec step (x0,x1,x2,x3,f1,f2) =
if fabs (x3-.x0) > tol*.(fabs x1 +. fabs x2) then
(* we're not done, subdivide appropriate interval *)
if f2 < f1 then
let x2' = rr*.x2+.cc*.x3 in
step (x1,x2,x2',x3,f2,f x2')
else
let x1' = rr*.x1+.cc*.x0 in
step (x0,x1',x1,x2,f x1',f1)
else
(* we're done, return smallest value *)
if f1 < f2 then (x1,f1) else (x2,f2)
in
let (x1,x2) = (* Make initial x0 to x1 the smaller segment *)
if fabs (cx-.bx) > fabs (bx-.ax)
then bx, bx +. cc *. (cx-.bx)
else bx -. cc *. (bx-.ax), bx
in
step (ax,x1,x2,cx,f x1,f x2)

Cheers
Frank