Module search 

One-dimensional searches: bisection, regula falsi and golden-section maximisation, the largest element of a sequence, and the greatest common divisor.

Model

bisect halves a bracket $[a, b]$ of a predicate that holds below a threshold $x^{\star}$ and fails above it: at every step, with $c = \frac{1}{2}(a + b)$,

$$ [a, b] \leftarrow \begin{cases} [c, b] & \text{if the predicate holds at } c, \\ [a, c] & \text{otherwise,} \end{cases} $$

and it returns the middle of the last bracket, within $2^{-(n+1)}(b - a)$ of $x^{\star}$ after $n$ steps.

regula_falsi finds a root of a continuous function $f$ whose values at the ends of the bracket have opposite signs, by the Illinois variant of the false position (Dowell & Jarratt 1971): the next point is the root of the chord,

$$ c = \frac{a f(b) - b f(a)}{f(b) - f(a)}, $$

which replaces the end of the same sign; when the same end is replaced twice in a row, the value kept at the other end is halved, which restores a superlinear convergence.

golden_max shrinks a bracket of a unimodal function by the golden ratio $\varphi^{-1} = (\sqrt{5} - 1)/2$ at every step, with the two interior points $c = b - \varphi^{-1}(b - a)$ and $d = a + \varphi^{-1}(b - a)$; one evaluation per step, the bracket length multiplied by $\varphi^{-n}$ after $n$ steps (Kiefer 1953).

They keep the order of their operations (0.5 * (lo + hi), no f64::midpoint; docs/adr/0005-lint-exceptions.md), so that the published values computed with them do not change.

Examples

use comnum_math::{bisect, gcd, golden_max};
// √2: x² < 2 below the root
let r = bisect(|x| x * x < 2.0, 0.0, 2.0, 60);
assert!((r - 2f64.sqrt()).abs() < 1e-15);
// the maximum of 1 - (x - 0.3)² on [0, 1]
let x = golden_max(|x| 1.0 - (x - 0.3) * (x - 0.3), 0.0, 1.0, 60);
assert!((x - 0.3).abs() < 1e-8);
assert_eq!(gcd(12, 18), 6);

References

1. J. Kiefer, “Sequential minimax search for a maximum,” Proc. Amer. Math. Soc., 4(3), 502–506, 1953.
2. W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes, 3rd ed., Cambridge University Press, 2007, Sec. 9.1 (bisection) and Sec. 10.2 (golden section search).
3. M. Dowell and P. Jarratt, “A modified regula falsi method for computing the root of an equation,” BIT 11(2), 168–174, 1971.

Functions

argmax

The index and the value of the largest element of values, the first one on ties (None for an empty sequence or one of NaN only; NaN elements are skipped): the decision of the detectors that pick the strongest candidate.

bisect

The threshold of a predicate by iters bisection steps of the bracket [lo, hi]: below(x) must hold below the threshold and fail above it (see the module).

gcd

The greatest common divisor of a and b (Euclid’s algorithm; gcd(a, 0) = a).

golden_max

The maximiser of a unimodal function f on [a, b] by iters steps of the golden section search (see the module): the middle of the last bracket.

regula_falsi

A root of f between a and b, where f takes values of opposite signs, by at most iters steps of the Illinois regula falsi (see the module): the first point $c$ of $|f(c)| <$ f_tol, or the point computed when the bracket is shorter than x_tol; the middle of the bracket after iters steps.