use crate::Scalar;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum RootError {
NoSignChange,
NotConverged {
iterations: usize,
},
}
impl core::fmt::Display for RootError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
RootError::NoSignChange => write!(f, "f(a) and f(b) have the same sign"),
RootError::NotConverged { iterations } => {
write!(f, "root finder did not converge in {iterations} iterations")
}
}
}
}
pub fn bisect<T, F>(f: F, a: T, b: T, tol: T, max_iter: usize) -> Result<T, RootError>
where
T: Scalar,
F: Fn(T) -> T,
{
let (mut lo, mut hi) = (a, b);
let mut flo = f(lo);
let fhi = f(hi);
if flo == T::zero() {
return Ok(lo);
}
if fhi == T::zero() {
return Ok(hi);
}
if (flo > T::zero()) == (fhi > T::zero()) {
return Err(RootError::NoSignChange);
}
let two = T::one() + T::one();
for _ in 0..max_iter {
let mid = lo + (hi - lo) / two;
if (hi - lo) / two <= tol {
return Ok(mid);
}
let fmid = f(mid);
if fmid == T::zero() {
return Ok(mid);
}
if (fmid > T::zero()) == (flo > T::zero()) {
lo = mid;
flo = fmid;
} else {
hi = mid;
}
}
Err(RootError::NotConverged {
iterations: max_iter,
})
}
pub fn brent<T, F>(f: F, a: T, b: T, tol: T, max_iter: usize) -> Result<T, RootError>
where
T: Scalar,
F: Fn(T) -> T,
{
let two = T::one() + T::one();
let (mut a, mut b) = (a, b);
let (mut fa, mut fb) = (f(a), f(b));
if fa == T::zero() {
return Ok(a);
}
if fb == T::zero() {
return Ok(b);
}
if (fa > T::zero()) == (fb > T::zero()) {
return Err(RootError::NoSignChange);
}
if fa.abs() < fb.abs() {
core::mem::swap(&mut a, &mut b);
core::mem::swap(&mut fa, &mut fb);
}
let mut c = a;
let mut fc = fa;
let mut d = b - a;
let mut used_bisection = true;
for _ in 0..max_iter {
if fb == T::zero() || (b - a).abs() <= tol {
return Ok(b);
}
let mut s = if fa != fc && fb != fc {
a * fb * fc / ((fa - fb) * (fa - fc))
+ b * fa * fc / ((fb - fa) * (fb - fc))
+ c * fa * fb / ((fc - fa) * (fc - fb))
} else {
b - fb * (b - a) / (fb - fa)
};
let three = two + T::one();
let quarter_point = (three * a + b) / (two + two);
let (min_ab, max_ab) = if quarter_point < b {
(quarter_point, b)
} else {
(b, quarter_point)
};
let bisect_needed = !(s > min_ab && s < max_ab)
|| (used_bisection && (s - b).abs() >= (b - c).abs() / two)
|| (!used_bisection && (s - b).abs() >= (c - d).abs() / two)
|| (used_bisection && (b - c).abs() < tol)
|| (!used_bisection && (c - d).abs() < tol);
if bisect_needed {
s = (a + b) / two;
used_bisection = true;
} else {
used_bisection = false;
}
let fs = f(s);
d = c;
c = b;
fc = fb;
if (fa > T::zero()) != (fs > T::zero()) {
b = s;
fb = fs;
} else {
a = s;
fa = fs;
}
if fa.abs() < fb.abs() {
core::mem::swap(&mut a, &mut b);
core::mem::swap(&mut fa, &mut fb);
}
}
Err(RootError::NotConverged {
iterations: max_iter,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn bisect_and_brent_find_known_roots() {
let root = 2f64.sqrt();
let b = bisect(|x: f64| x * x - 2.0, 0.0, 2.0, 1e-13, 200).unwrap();
assert!((b - root).abs() < 1e-11);
let r = brent(|x: f64| x * x - 2.0, 0.0, 2.0, 1e-14, 100).unwrap();
assert!((r - root).abs() < 1e-12);
}
#[test]
fn brent_handles_a_transcendental_root() {
let r = brent(|x: f64| x * x.exp() - 1.0, 0.0, 1.0, 1e-14, 100).unwrap();
assert!((r - 0.567_143_290_409_783_8).abs() < 1e-12);
}
#[test]
fn unbracketed_intervals_are_rejected() {
assert_eq!(
bisect(|x: f64| x * x + 1.0, -1.0, 1.0, 1e-9, 100),
Err(RootError::NoSignChange)
);
assert_eq!(
brent(|x: f64| x * x + 1.0, -1.0, 1.0, 1e-9, 100),
Err(RootError::NoSignChange)
);
}
#[test]
fn exact_endpoint_roots_are_returned() {
assert_eq!(brent(|x: f64| x, 0.0, 1.0, 1e-9, 10), Ok(0.0));
assert_eq!(bisect(|x: f64| x - 1.0, 0.0, 1.0, 1e-9, 10), Ok(1.0));
}
}