Root finding

The Nautilus.Roots module provides three scalar root-finders. Each takes a function f: f32 -> f32 and returns an approximate root. Invalid brackets, near-zero derivatives, NaN values from f or df, and exhausted iteration limits can produce NaN.

Functions

Function	Signature
bisection	(f: f32 -> f32, lo: f32, hi: f32, tol: f32, max_iters: i64) -> f32
newton	(f: f32 -> f32, df: f32 -> f32, x0: f32, tol: f32, max_iters: i64) -> f32
brent	(f: f32 -> f32, lo: f32, hi: f32, tol: f32, max_iters: i64) -> f32

Choosing a method

• bisection: Requires a bracket [lo, hi] where f changes sign. Converges linearly (one bit per iteration). Use when you have a reliable bracket and do not need speed.
• newton: Quadratic convergence near simple roots, but requires the user to supply the derivative df. Can fail if df is near zero or the initial guess is far from the root. Use when you have analytic derivatives and a good starting point.
• brent: Combines inverse quadratic interpolation, secant, and bisection fallback. Requires a sign-change bracket like bisection but converges superlinearly. Use it when you have a bracket but no derivative.

Example: Brent's method and Newton's method

module Nautilus.BookRootsExamples
import Nautilus.Roots (brent, newton)
export (find_sqrt2, find_cos_eq_x)
def find_sqrt2() -> f32 = {
  f = fn (x: f32) -> sub(mul(x, x), cast(2.0, f32))
  brent(f, cast(1.0, f32), cast(2.0, f32), cast(1e-6, f32), cast(100, i64))
}
def find_cos_eq_x() -> f32 = {
  f = fn (x: f32) -> sub(cos(x), x)
  df = fn (x: f32) -> sub(neg(sin(x)), cast(1.0, f32))
  newton(f, df, cast(0.5, f32), cast(1e-10, f32), cast(50, i64))
}

find_sqrt2 returns approximately 1.414213. find_cos_eq_x solves cos(x) = x with the analytic derivative -sin(x) - 1 and returns approximately 0.739085.

Edge cases

• No sign change: bisection and brent return NaN if f(lo) * f(hi) > 0.
• NaN input or NaN residual: all three return NaN when tol is NaN, when a bracket endpoint or starting point is NaN, or when f (or df for newton) returns NaN at any point they evaluate. NaN tolerance and coordinates are rejected before calling f; a NaN function result is rejected when the iteration reaches it. The methods cannot detect NaN in a region they never probe. Infinite residuals are accepted: -inf and +inf retain signs that bisection and Brent can use to update a bracket.
• Zero derivative: newton returns NaN if |df(x)| < 1e-30 at any step.
• Iteration limit: all three return NaN when max_iters is exhausted before any stopping condition. They can also return a finite point before reaching the requested tolerance when f32 arithmetic makes an iteration stop changing the point.
• Tolerance: bisection and Brent compare bracket width or |f(x)| with a threshold; Newton compares |f(x)|. Brent uses at least 1e-6 inside its iteration even if you pass a smaller tol. Check |f(root)| yourself when a particular residual is required.