3
\$\begingroup\$

I implemented the golden section search algorithm recursively in Lisp. My code is:

(defconstant phi 0.618033988749895D0)    

(defun linemin (f x1 x2 &key (xi1 (- x2 (* (- x2 x1) phi)))
                             (xi2 (+ x1 (* (- x2 x1) phi)))
                             (tol 0.001))
   (if (> tol (- xi2 xi1))
      (/ (+ xi1 xi2) 2)
      (if (> (funcall f x1) (funcall f x2))
         (linemin f xi1 x2 :tol tol :xi1 xi2)
         (linemin f x1 xi2 :tol tol :xi2 xi1))))

I sought to make this tail-recursive. Does Lisp provide a way of ascertaining whether the function was optimized and turned into a loop at compile time? Btw I'm using Lispworks.

Any other input is appreciated, of course.

\$\endgroup\$
  • \$\begingroup\$ Constants aren't (which is to say, it's better to use defvar/defparameter, otherwise the compiler is free to do about anything when you're redefining the constant) and they're also named +phi+ by convention. I guess though there's a point in that pi doesn't follow that convention. \$\endgroup\$ – ferada Oct 5 '15 at 16:59
  • \$\begingroup\$ I chose defconstant to prevent the phi from being inadvertently changed by the formulae within the function. The *phi* convention has pros and cons, but I agree it looks like a good idea. \$\endgroup\$ – Paulo Mendes Oct 6 '15 at 15:44
  • \$\begingroup\$ Okay I can see that, though in that case using (one of the libraries to define it with) a symbol macro would be even safer. \$\endgroup\$ – ferada Oct 6 '15 at 16:13
3
\$\begingroup\$

The Common Lisp standard does not require implementations to eliminate tail calls, but this is an optimization supported by many implementations. It is the case for Lispworks. You can write your code so that it works portably with multiple implementations, provided you wrap your declarations as required for each one of them (e.g. #+sbcl). Otherwise, you have to use an iterative approach, which is not hard to implement in your case.

Remarks

The code looks well-formatted, but consider using meaningful names:

  • Write tolerance instead of tol
  • Write line-min (?) or golden-section-search instead of linemin
  • x1, x2, xi1 and xi2 are a little hard to read. Granted, what you write is close to mathematical notations where variable names are short and written with indices, but maybe there are more interesting name to give (low, high?), especially when those names are used as keyword arguments.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.