cl-iterative
2016-03-18
Generic iterative algorithm with multiple controls
Upstream URL
Author
License
1Introduction
All linearly iterative algorithms can be transformed into the formx=f(x)
for some value x
and some function f(x)
. This systemprovides a way to perform an iterative algorithm as a process offinding the solution of this equation.Furthermore, many existing implementations provide very limited
control over how iterations are performed: what if the value is bound
and the iterative step takes it out the boundaries? what if one wants
to log the progress of computation? what if the computation needs to
be stopped after some iterations?.. CL-ITERATIVE
system provides the
refined control over the progress of iterations by means of special
structures called (unsurprisingly) controls.
The library was tested with SBCL (1.2.14) and ECL (15.3.7) on Linux (Ubuntu 15.10 x86-64).
2Modus operandi
The key idea of the method is to perform the computation only if
ITERATOR:ITERATOR
object is in state CONTINUE
and stop otherwise
(for category theory lovers and purists: ITERATOR:ITERATOR
is
amalgamated Either
monad on top of another Either
monad).
The state of computation can be changed by means of controls. This system provides the following controls:
FINISHED-VALUE
- successfully stops the computation if certaincondition on computation value is reached.
FAILED-VALUE
- stops the computation with a failure if certaincondition on computation value is reached.
LIMIT-ITERATIONS
- stops the computation with a failure if numberof iterations exceeds the limit.
LOG-COMPUTATION
- logs the progress of iterative computation, canbe viewed as a probe.
CONVERGED-VALUE
- successfully stops the computation if the valuehas converged in some sense (using user-specified predicate ofcloseness
CLOSE-P
; for mathematical purists: user specifies thetopology of the computation space). CONVERGED-NUMBER
- simplified version of
CONVERGED-VALUE
fornumbers where closeness is defined as|x-y|<eps
. ALTER-VALUE
- general control that changes the value according tospecified function. This control can be used, for example, tokeep the value bound.
Packaged CL-ITERATIVE-EX
provides the extension for some of these
controls to add extra info to the ITERATOR:ITERATOR
(or rather to
extended ITERATOREX:ITERATOREX
) computation object (useful to
identify why computation had stoped).
A control, in general, is any object on which two methods
INIT-CONTROL
and APPLY-CONTROL
are specialized. This way the
library of available controls can be extended by a user. A sequence of
controls can be combined together into a single control using
COMBINE-CONTROLS
.
Functions ITERATE
and FIXED-POINT
provide the entry point into
iterative algorithms. FIXED-POINT
is a bit more end-user
oriented. It accepts as arguments:
FUNCTION
- the implementation of
f(x)
. INIT-VALUE
- initial approximation.
PRE-TREAT
- the control applied before the iterative algorithmstarts.
CONTROLS
- a combined control that is applied after each updateof the value by
f(x)
. This control should contain the way tostop the computation. POST-TREAT
- final treat of the computation value after all theiterations are finished.
ITERATE
is similar, except it accepts the initial computation object
instead of INIT-VALUE
and iterations are defined by controls only
(in fact, FIXED-POINT
calls ITERATE
with FUNCTION
wrapped into
the control (ALTER-VALUE FUNCTION)
).
3Example
Consider the problem of computing the square root of a number S
using Heron's method:
--- x = \/ S : 1 / S \ x = - |x + --- | n+1 2 \ n x / n x = 1 0
The following function implements it:
(defun sqrt-heron (s)
(flet ((improve (x)
(* 0.5d0 (+ x (/ s x)))))
(multiple-value-bind (final-x successful-p info)
(fixed-point
#'improve 1d0
:pre-treat (add-info) ; add stopping info
:controls (combine-controls
(converged-number-with-id) ; converge with default precision
(limit-iterations-with-id 20))) ; limit to 20 iterations
;; Just in case did not converge: shouldn't happen for any reasonable S > 0
;; due to quadratic convergence of the algorithm
(assert successful-p () "Could not find the square root of S = ~A" s)
;; Just for illustrative purposes: return extra info - why computation
;; was stopped?
(values final-x info))))
If want to find square root of 4,
> (sqrt-heron 4d0) 2.0d0 ((:CONVERGED-NUMBER))
If we want to peek into how the computation proceeds, we can add the logging function:
(defun sqrt-heron (s)
(flet ((improve (x)
(* 0.5d0 (+ x (/ s x))))
(log-function (indicator x) ; log computation
(if (eq indicator :init)
(format t "~&INIT: x = ~A~%" x)
(format t "~&x = ~A~%" x))))
(multiple-value-bind (final-x successful-p info)
(fixed-point
#'improve 1d0
:pre-treat (add-info)
:controls (combine-controls
(log-computation #'log-function) ; add it before convergence test
(converged-number-with-id)
(limit-iterations-with-id 20)))
(assert successful-p () "Could not find the square root of S = ~A" s)
(values final-x info))))
Then, the output and the result will look as follows:
> (sqrt-heron 4d0) INIT: x = 1.0d0 x = 2.5d0 x = 2.05d0 x = 2.000609756097561d0 x = 2.0000000929222947d0 x = 2.000000000000002d0 x = 2.0d0 2.0d0 ((:CONVERGED-NUMBER))
Check the system CL-ITERATIVE-TESTS
for more examples.
4License
Copyright (c) 2016 Alexey Cherkaev
Distributed under LGPLv3 license.