www.digitalmars.com

D Programming Language 2.0

Last update Wed Jul 9 01:24:45 2008

std.numeric

This module is a port of a growing fragment of the numeric header in Alexander Stepanov's Standard Template Library, with a few additions.

Author:
Andrei Alexandrescu, Don Clugston

template secantMethod(alias F)
Implements the secant method for finding a root of the function f starting from points [xn_1, x_n] (ideally close to the root). Num may be float, double, or real.

Example:
float f(float x) {
    return cos(x) - x*x*x;
}
auto x = secantMethod(&f, 0f, 1f);
assert(approxEqual(x, 0.865474));


T findRoot(T,R)(R delegate(T) f, T a, T b);
Find a real root of a real function f(x) via bracketing.

Given a function f and a range [a..b] such that f(a) and f(b) have opposite signs, 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.



Tuple!(T,T,R,R) findRoot(T,R)(R delegate(T) f, T ax, T bx, R fax, R fbx, bool delegate(T lo, T hi) tolerance);
Find root of a real function f(x) by bracketing, allowing the termination condition to be specified.

Params:
f Function to be analyzed
ax Left bound of initial range of f known to contain the root.
bx Right bound of initial range of f known to contain the root.
fax Value of f(ax).
fax Value of f(ax) and f(bx). (f(ax) and f(bx) are commonly known in advance.)
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, full machine precision will be achieved.

Returns:
A tuple consisting of two ranges. The first two elements are the range (in x) of the root, while the second pair of elements are the corresponding function values at those points. If an exact root was found, both of the first two elements will contain the root, and the second pair of elements will be 0.