Report a bug
If you spot a problem with this page, click here to create a Github issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

mir.numeric

Base numeric algorithms.
Reworked part of std.numeric.
Authors:
Ilya Yaroshenko (API, findLocalMin), Don Clugston (findRoot)
enum FindRootStatus: int;
success
Success
badBounds
nanX
nanY
struct FindRootResult(T);
T ax;
Left bound
T bx;
Rifht bound
T ay;
f(ax) or f(ax).fabs.fmin(T.max / 2).copysign(f(ax)).
T by;
f(bx) or f(bx).fabs.fmin(T.max / 2).copysign(f(bx)).
ref auto validate() return;
Returns:
self Required_versions:D_Exceptions
Throws:
FindRootStatus status();
T x();
A bound that corresponds to the minimal absolute function value.
Returns:
!(ay.fabs > by.fabs) ? ax : bx
T y();
The minimal of absolute function values.
Returns:
!(ay.fabs > by.fabs) ? ay : by
FindRootResult!T findRoot(alias f, alias tolerance = null, T)(const T ax, const T bx, const T fax = -T.nan, const T fbx = +T.nan)
if (isFloatingPoint!T && __traits(compiles, T(f(T.init))) && (is(typeof(tolerance) == typeof(null)) || __traits(compiles, () { auto _ = bool(tolerance(T.init, T.init)); } )));
Find root of a real function f(x) by bracketing, allowing the termination condition to be specified.
Given a function f and a range [a .. b] such that f(a) and f(b) have opposite signs or at least one of them equals ±0, returns the value of x in the range which is closest to a root of f(x). If f(x) has more than one root in the range, one will be chosen arbitrarily. If f(x) returns NaN, NaN will be returned; otherwise, this algorithm is guaranteed to succeed.
Uses an algorithm based on TOMS748, which uses inverse cubic interpolation whenever possible, otherwise reverting to parabolic or secant interpolation. Compared to TOMS748, this implementation improves worst-case performance by a factor of more than 100, and typical performance by a factor of 2. For 80-bit reals, most problems require 8 to 15 calls to f(x) to achieve full machine precision. The worst-case performance (pathological cases) is approximately twice the number of bits.

References "On Enclosing Simple Roots of Nonlinear Equations", G. Alefeld, F.A. Potra, Yixun Shi, Mathematics of Computation 61, pp733-744 (1993). Fortran code available from www.netlib.org as algorithm TOMS478.

Parameters:
f Function to be analyzed. f(ax) and f(bx) should have opposite signs.
tolerance tolerance = Defines an early termination condition. Receives the current upper and lower bounds on the root. The delegate must return true when these bounds are acceptable. If this function always returns false or it is null, full machine precision will be achieved.
T ax Left bound of initial range of f known to contain the root.
T bx Right bound of initial range of f known to contain the root.
T fax Value of f(ax) (optional).
T fbx Value of f(bx) (optional).
Examples:
import mir.math.common: log, exp;


auto logRoot = findRoot!log(0, double.infinity).validate.x;
assert(logRoot == 1);

auto shift = 1;
auto expm1Root = findRoot!(x => exp(x) - shift)
    (-double.infinity, double.infinity).validate.x;
assert(expm1Root == 0);

auto approxLogRoot = findRoot!(log, (a, b) => fabs(a - b) < 1e-5)(0, double.infinity).validate.x;
assert(fabs(approxLogRoot - 1) < 1e-5);
struct FindLocalMinResult(T);
T x;
T y;
T error;
ref auto validate() return;
Returns:
self Required_versions:D_Exceptions
Throws:
FindRootStatus status();
FindLocalMinResult!T findLocalMin(alias f, T)(const T ax, const T bx, const T relTolerance = sqrt(T.epsilon), const T absTolerance = sqrt(T.epsilon))
if (isFloatingPoint!T && __traits(compiles, T(f(T.init))));
Find a real minimum of a real function f(x) via bracketing. Given a function f and a range (ax .. bx), returns the value of x in the range which is closest to a minimum of f(x). f is never evaluted at the endpoints of ax and bx. If f(x) has more than one minimum in the range, one will be chosen arbitrarily. If f(x) returns NaN or -Infinity, (x, f(x), NaN) will be returned; otherwise, this algorithm is guaranteed to succeed.
Parameters:
f Function to be analyzed
T ax Left bound of initial range of f known to contain the minimum.
T bx Right bound of initial range of f known to contain the minimum.
T relTolerance Relative tolerance.
T absTolerance Absolute tolerance.

Preconditions ax and bx shall be finite reals.
relTolerance shall be normal positive real.
absTolerance shall be normal positive real no less then T.epsilon*2.

Returns:
A FindLocalMinResult consisting of x, y = f(x) and error = 3 * (absTolerance * fabs(x) + relTolerance). The method used is a combination of golden section search and successive parabolic interpolation. Convergence is never much slower than that for a Fibonacci search.

References "Algorithms for Minimization without Derivatives", Richard Brent, Prentice-Hall, Inc. (1973)