pub fn brentq<F>(mut f: F, xa: f64, xb: f64) -> f64
where
F: FnMut(f64) -> f64,
{
brentq_tol(&mut f, xa, xb, 2e-12, 8.881_784_197_001_252e-16, 100)
}
pub fn brentq_tol<F>(f: &mut F, xa: f64, xb: f64, xtol: f64, rtol: f64, maxiter: usize) -> f64
where
F: FnMut(f64) -> f64,
{
let mut xpre = xa;
let mut xcur = xb;
let mut xblk = 0.0_f64;
let mut fpre = f(xpre);
let mut fcur = f(xcur);
let mut fblk = 0.0_f64;
let mut spre = 0.0_f64;
let mut scur = 0.0_f64;
if fpre == 0.0 {
return xpre;
}
if fcur == 0.0 {
return xcur;
}
if fpre.signum() == fcur.signum() {
return xcur;
}
for _ in 0..maxiter {
if fpre != 0.0 && fcur != 0.0 && (fpre.signum() != fcur.signum()) {
xblk = xpre;
fblk = fpre;
spre = xcur - xpre;
scur = xcur - xpre;
}
if fblk.abs() < fcur.abs() {
xpre = xcur;
xcur = xblk;
xblk = xpre;
fpre = fcur;
fcur = fblk;
fblk = fpre;
}
let delta = (xtol + rtol * xcur.abs()) / 2.0;
let sbis = (xblk - xcur) / 2.0;
if fcur == 0.0 || sbis.abs() < delta {
return xcur;
}
if spre.abs() > delta && fcur.abs() < fpre.abs() {
let stry = if xpre == xblk {
-fcur * (xcur - xpre) / (fcur - fpre)
} else {
let dpre = (fpre - fcur) / (xpre - xcur);
let dblk = (fblk - fcur) / (xblk - xcur);
-fcur * (fblk * dblk - fpre * dpre) / (dblk * dpre * (fblk - fpre))
};
if 2.0 * stry.abs() < spre.abs().min(3.0 * sbis.abs() - delta) {
spre = scur;
scur = stry;
} else {
spre = sbis;
scur = sbis;
}
} else {
spre = sbis;
scur = sbis;
}
xpre = xcur;
fpre = fcur;
if scur.abs() > delta {
xcur += scur;
} else {
xcur += if sbis > 0.0 { delta } else { -delta };
}
fcur = f(xcur);
}
xcur
}
pub fn fminbound<F>(mut f: F, x1: f64, x2: f64) -> (f64, f64)
where
F: FnMut(f64) -> f64,
{
fminbound_opts(&mut f, x1, x2, 1e-5, 500)
}
pub fn fminbound_opts<F>(f: &mut F, x1: f64, x2: f64, xatol: f64, maxfun: usize) -> (f64, f64)
where
F: FnMut(f64) -> f64,
{
let sqrt_eps = 2.2e-16_f64.sqrt();
let golden_mean = 0.5 * (3.0 - 5.0_f64.sqrt());
let (mut a, mut b) = (x1, x2);
let mut fulc = a + golden_mean * (b - a);
let mut nfc = fulc;
let mut xf = fulc;
let mut rat = 0.0_f64;
let mut e = 0.0_f64;
let mut x;
let mut fx = f(xf);
let mut num = 1usize;
let mut ffulc = fx;
let mut fnfc = fx;
let mut xm = 0.5 * (a + b);
let mut tol1 = sqrt_eps * xf.abs() + xatol / 3.0;
let mut tol2 = 2.0 * tol1;
while (xf - xm).abs() > (tol2 - 0.5 * (b - a)) {
let mut golden = true;
if e.abs() > tol1 {
golden = false;
let mut r = (xf - nfc) * (fx - ffulc);
let mut q = (xf - fulc) * (fx - fnfc);
let mut p = (xf - fulc) * q - (xf - nfc) * r;
q = 2.0 * (q - r);
if q > 0.0 {
p = -p;
}
q = q.abs();
r = e;
e = rat;
if p.abs() < (0.5 * q * r).abs() && p > q * (a - xf) && p < q * (b - xf) {
rat = p / q;
x = xf + rat;
if (x - a) < tol2 || (b - x) < tol2 {
let si = sign_with_zero(xm - xf);
rat = tol1 * si;
}
} else {
golden = true;
}
}
if golden {
if xf >= xm {
e = a - xf;
} else {
e = b - xf;
}
rat = golden_mean * e;
}
let si = sign_with_zero(rat);
x = xf + si * rat.abs().max(tol1);
let fu = f(x);
num += 1;
if fu <= fx {
if x >= xf {
a = xf;
} else {
b = xf;
}
fulc = nfc;
ffulc = fnfc;
nfc = xf;
fnfc = fx;
xf = x;
fx = fu;
} else {
if x < xf {
a = x;
} else {
b = x;
}
if fu <= fnfc || nfc == xf {
fulc = nfc;
ffulc = fnfc;
nfc = x;
fnfc = fu;
} else if fu <= ffulc || fulc == xf || fulc == nfc {
fulc = x;
ffulc = fu;
}
}
xm = 0.5 * (a + b);
tol1 = sqrt_eps * xf.abs() + xatol / 3.0;
tol2 = 2.0 * tol1;
if num >= maxfun {
break;
}
}
(xf, fx)
}
fn sign_with_zero(v: f64) -> f64 {
if v > 0.0 {
1.0
} else if v < 0.0 {
-1.0
} else {
1.0
}
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_abs_diff_eq;
#[test]
fn brentq_finds_simple_root() {
let r = brentq(|x| x * x - 2.0, 0.0, 2.0);
assert_abs_diff_eq!(r, 2.0_f64.sqrt(), epsilon = 1e-12);
}
#[test]
fn brentq_handles_endpoint_root() {
let r = brentq(|x| x - 1.0, 1.0, 3.0);
assert_abs_diff_eq!(r, 1.0, epsilon = 1e-15);
}
#[test]
fn fminbound_minimizes_parabola() {
let (xopt, fval) = fminbound(|x| (x - 1.0).powi(2), -4.0, 4.0);
assert_abs_diff_eq!(xopt, 1.0, epsilon = 1e-5);
assert_abs_diff_eq!(fval, 0.0, epsilon = 1e-9);
}
}