use crate::error::{BarracudaError, Result};
#[derive(Debug, Clone)]
pub struct BrentResult {
pub root: f64,
pub iterations: usize,
pub residual: f64,
pub function_evaluations: usize,
}
pub fn brent<F>(f: F, mut a: f64, mut b: f64, tol: f64, max_iter: usize) -> Result<BrentResult>
where
F: Fn(f64) -> f64,
{
let mut fa = f(a);
let mut fb = f(b);
let mut n_evals = 2;
if fa * fb > 0.0 {
return Err(BarracudaError::InvalidInput {
message: format!(
"Brent's method requires f(a) and f(b) to have opposite signs: \
f({a}) = {fa}, f({b}) = {fb}"
),
});
}
if fa.abs() < fb.abs() {
std::mem::swap(&mut a, &mut b);
std::mem::swap(&mut fa, &mut fb);
}
let mut c = a; let mut fc = fa;
let mut d = b - a; let mut e = d;
for iter in 0..max_iter {
if fb.abs() < tol {
return Ok(BrentResult {
root: b,
iterations: iter,
residual: fb.abs(),
function_evaluations: n_evals,
});
}
let m = 0.5 * (c - b);
if m.abs() <= tol || fb == 0.0 {
return Ok(BrentResult {
root: b,
iterations: iter,
residual: fb.abs(),
function_evaluations: n_evals,
});
}
let mut use_bisection = true;
if e.abs() >= tol && fa.abs() > fb.abs() {
let s = fb / fa;
let (p, q) = if (a - c).abs() < 1e-14 {
(2.0 * m * s, 1.0 - s)
} else {
let q = fa / fc;
let r = fb / fc;
(
s * (2.0 * m * q).mul_add(q - r, -((b - a) * (r - 1.0))),
(q - 1.0) * (r - 1.0) * (s - 1.0),
)
};
let (p, q) = if p > 0.0 { (p, -q) } else { (-p, q) };
if 2.0 * p < (3.0 * m).mul_add(q, -(tol * q).abs()) && p < (0.5 * e * q).abs() {
e = d;
d = p / q;
use_bisection = false;
}
}
if use_bisection {
d = m;
e = m;
}
a = b;
fa = fb;
if d.abs() > tol {
b += d;
} else {
b += if m > 0.0 { tol } else { -tol };
}
fb = f(b);
n_evals += 1;
if fb * fc > 0.0 {
c = a;
fc = fa;
e = b - a;
d = e;
}
if fc.abs() < fb.abs() {
a = b;
b = c;
c = a;
fa = fb;
fb = fc;
fc = fa;
}
}
Ok(BrentResult {
root: b,
iterations: max_iter,
residual: fb.abs(),
function_evaluations: n_evals,
})
}
pub fn brent_minimize<F>(
f: F,
mut a: f64,
b: f64,
mut c: f64,
tol: f64,
max_iter: usize,
) -> Result<(f64, f64, usize)>
where
F: Fn(f64) -> f64,
{
const GOLDEN: f64 = 0.381_966_011_250_105;
if a > c {
std::mem::swap(&mut a, &mut c);
}
let mut x = b; let mut w = b; let mut v = b; let mut fx = f(x);
let mut fw = fx;
let mut fv = fx;
let mut d: f64 = 0.0; let mut e: f64 = 0.0;
for iter in 0..max_iter {
let xm = 0.5 * (a + c);
let tol1 = tol.mul_add(x.abs(), 1e-10);
let tol2 = 2.0 * tol1;
if (x - xm).abs() <= 0.5f64.mul_add(-(c - a), tol2) {
return Ok((x, fx, iter));
}
let mut use_golden = true;
if e.abs() > tol1 {
let r = (x - w) * (fx - fv);
let q = (x - v) * (fx - fw);
let mut p = (x - v).mul_add(q, -((x - w) * r));
let mut q = 2.0 * (q - r);
if q > 0.0 {
p = -p;
} else {
q = -q;
}
let r = e;
e = d;
if p.abs() < (0.5 * q * r).abs() && p > q * (a - x) && p < q * (c - x) {
d = p / q;
let u = x + d;
if (u - a) < tol2 || (c - u) < tol2 {
d = if x < xm { tol1 } else { -tol1 };
}
use_golden = false;
}
}
if use_golden {
e = if x < xm { c - x } else { a - x };
d = GOLDEN * e;
}
let u = if d.abs() >= tol1 {
x + d
} else if d > 0.0 {
x + tol1
} else {
x - tol1
};
let fu = f(u);
if fu <= fx {
if u < x {
c = x;
} else {
a = x;
}
v = w;
fv = fw;
w = x;
fw = fx;
x = u;
fx = fu;
} else {
if u < x {
a = u;
} else {
c = u;
}
if fu <= fw || (w - x).abs() < 1e-14 {
v = w;
fv = fw;
w = u;
fw = fu;
} else if fu <= fv || (v - x).abs() < 1e-14 || (v - w).abs() < 1e-14 {
v = u;
fv = fu;
}
}
}
Ok((x, fx, max_iter))
}
#[cfg(test)]
mod tests {
use super::*;
use std::f64::consts::{PI, SQRT_2};
#[test]
fn test_brent_sqrt2() {
let f = |x: f64| x.mul_add(x, -2.0);
let result = brent(f, 0.0, 2.0, 1e-10, 100).unwrap();
assert!((result.root - SQRT_2).abs() < 1e-10);
assert!(result.residual < 1e-10);
}
#[test]
fn test_brent_sin_pi() {
let f = |x: f64| x.sin();
let result = brent(f, 3.0, 4.0, 1e-10, 100).unwrap();
assert!((result.root - PI).abs() < 1e-10);
}
#[test]
fn test_brent_exp() {
let f = |x: f64| x.exp() - 2.0;
let result = brent(f, 0.0, 1.0, 1e-10, 100).unwrap();
assert!((result.root - 2.0_f64.ln()).abs() < 1e-10);
}
#[test]
fn test_brent_cubic() {
let f = |x: f64| 2.0f64.mul_add(-x, x.powi(3)) - 5.0;
let result = brent(f, 2.0, 3.0, 1e-10, 100).unwrap();
assert!(f(result.root).abs() < 1e-10);
}
#[test]
fn test_brent_same_sign_error() {
let f = |x: f64| x - 5.0;
let result = brent(f, 0.0, 1.0, 1e-10, 100);
assert!(result.is_err());
}
#[test]
fn test_brent_faster_than_bisection() {
let f = |x: f64| x.mul_add(x, -2.0);
let result = brent(f, 1.0, 2.0, 1e-12, 100).unwrap();
assert!(
result.iterations < 15,
"Brent took {} iterations",
result.iterations
);
}
#[test]
fn test_brent_minimize_quadratic() {
let f = |x: f64| (x - 2.0).powi(2);
let (x_min, f_min, _) = brent_minimize(f, 0.0, 1.5, 4.0, 1e-10, 100).unwrap();
assert!((x_min - 2.0).abs() < 1e-8);
assert!(f_min < 1e-14);
}
#[test]
fn test_brent_minimize_cos() {
let f = |x: f64| x.cos();
let (x_min, f_min, _) = brent_minimize(f, 2.0, 3.0, 4.0, 1e-10, 100).unwrap();
assert!((x_min - PI).abs() < 1e-8);
assert!((f_min - (-1.0)).abs() < 1e-10);
}
#[test]
fn test_brent_result_fields() {
let f = |x: f64| x - 1.0;
let result = brent(f, 0.0, 2.0, 1e-10, 100).unwrap();
assert!((result.root - 1.0).abs() < 1e-10);
assert!(result.residual < 1e-10);
assert!(result.function_evaluations >= 2);
}
}