📐algorithm-bisection-root

The groupant beside algorithms/src/bisection_root/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Components

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

Model text

descriptant

bisection_root mod.rs

Original standard-library numerical implementation and finite tests. Prospective predictions were saved before code in ../prospective.md.

Keep [l,r] with opposite endpoint signs; evaluate m=l+(r-l)/2 and replace the same-sign endpoint. Exact computed zero collapses the bracket. Width stopping retains the last evaluated endpoint, whose distance to any retained exact-real root is at most the width under exact signs and continuity.

sqrt(k), k=1..39, independently checks coordinates and brackets; endpoint zero, no bracket, nonfinite callbacks, budget count and adjacent-float stagnation.

Literature: Burden and Faires, Numerical Analysis (bisection); Kiefer (1953), Sequential minimax search for a maximum (golden section); Nocedal and Wright, Numerical Optimization, second edition, chapter 3 (gradient descent); Hestenes and Stiefel (1952), Methods of conjugate gradients for solving linear systems (CG). No source code was copied.

2026-10-30 epoch: scoped safe bounds and explicit failure statuses were retained; finite observations do not establish universal convergence.

model

Mathematical combiner

Inputs: authoritative mod.rs, partial syntax projection, forward model, typed complement and reconstruction relations, and named finite observations. The combiner intersects accepted-domain constraints with update invariants, then partitions outputs by convergence, budget, stagnation or error. Cost is O(k) callback invocations (at most k+2), O(1) internal storage; callback cost and allocation excluded. Tests are sibling sources, never implementation children. Source hashes bind this descriptive epoch; syntax is not semantic AST or proof.

Observation retained: sqrt(k), k=1..39, independently checks coordinates and brackets; endpoint zero, no bracket, nonfinite callbacks, budget count and adjacent-float stagnation.

Limits: callback determinism/continuity/unimodality and global SPD are assumptions; residual stopping alone says nothing universal about solution error. Conditioning, underflow, finite rounding and callback cost remain material. No speed measurements or universal accuracy certificate are claimed.

approximant

Forward approximant and invariant

Domain: Continuous deterministic callback, opposite finite endpoint signs; endpoints bounded by 1e100; positive finite absolute width tolerance and iteration budget <=100000.

Keep [l,r] with opposite endpoint signs; evaluate m=l+(r-l)/2 and replace the same-sign endpoint. Exact computed zero collapses the bracket. Width stopping retains the last evaluated endpoint, whose distance to any retained exact-real root is at most the width under exact signs and continuity.

Cost: O(k) callback invocations (at most k+2), O(1) internal storage; callback cost and allocation excluded.

Invariant: accepted reports contain finite values; successful scalar intervals stay nested and vector residuals correspond to returned coordinates. Global mathematical assumptions remain caller obligations.

Numerical claims concern additive interval widths or absolute gradient/residual norms. A relative coordinate error has undefined behavior at zero without a separate convention and is not claimed. No supported 1/2/5/10% executable surrogate is attached: this exact API is already iterative, and no independently measured faster transformation with a useful certified metric is supplied.

models

Typed obernant family

behavior_complement

On the scoped input/report universe, the complement excludes fabricated convergence when neither declared stopping observation holds, invalid accepted shapes or nonfinite arithmetic results, and reports whose estimate leaves the retained bracket or whose vector residual is inconsistent. Domain: Continuous deterministic callback, opposite finite endpoint signs; endpoints bounded by 1e100; positive finite absolute width tolerance and iteration budget <=100000. This relation is broader than enumerated rejection tests. It does not claim the solver detects violated global callback/SPD assumptions.

reverse_reconstruction

Sign-preserving positive scaling of a callback preserves the bracket path when finite; each output has infinitely many continuous functions sharing sampled values. Bracket and reported endpoint constrain compatible roots but cannot reconstruct unsampled callback values.

bracket_sign

For nonzero evaluations, replacement uses sign equality without a potentially overflowing product. An opposite-sign invariant follows inductively under exact evaluated signs.

termination_partition

The bounded loop checks convergence first, then budget, then representational stagnation. Zero budget can still converge on the initial stopping observation. Iteration count is completed updates (including an attempted unchanged vector update). No unbounded search or implicit retry.

finite_arithmetic

Inputs reject NaN/infinity and restricted magnitude violations. Scalar callback results must remain finite; bounded endpoints keep differences and convex combinations finite. Vector norms use hypot; inner products and updates check finite arithmetic. Finite precision is not an exact-real proof; CG squared norm underflow is stagnation.

resource_observation

O(k) callback invocations (at most k+2), O(1) internal storage; callback cost and allocation excluded.

tests

Checks

Run cargo test -p mova-algorithms bisection_root::tests and its release equivalent. sqrt(k), k=1..39, independently checks coordinates and brackets; endpoint zero, no bracket, nonfinite callbacks, budget count and adjacent-float stagnation.

Compiled negative control must hit root bracket oracle. Full algorithms suite runs twice per profile; normalized ordered test outcomes are compared. Strict all-target Clippy and focused rustfmt check complete validation. See validation.md for observed evidence.

prospective

Prospective numerical solver model

2026-10-30, before implementation. Original standard-library implementation, following the classical interval and quadratic optimization recurrences (Burden and Faires, Numerical Analysis; Nocedal and Wright, Numerical Optimization, second edition, chapters 3 and 5).

Scalar routines accept finite endpoints with magnitude at most 1e100 and positive finite absolute x tolerance, up to 100000 iterations. Bisection requires a continuous deterministic caller function and opposite endpoint signs; golden-section requires a deterministic strictly unimodal function (possibly with a unique boundary minimum). Function evaluations must be finite. Neither routine can validate those global caller assumptions. Nested intervals are the invariant. Width stopping is an additive coordinate observation, not relative error. Golden-section ties deterministically discard the right portion; bisection exact computed zero reports convergence but does not certify the exact-real function.

Vector routines accept 1..256 coordinates bounded by 1e100, positive finite tolerance, and up to 100000 iterations. Diagonal gradient descent requires coefficients in [1e-100,1e100], uses step 1/max diagonal, and minimizes half x'Dx - b'x. Dense conjugate gradients require exact symmetry and caller-assumed positive definiteness, with runtime positive-curvature checks. Every arithmetic vector and scalar is checked for finiteness; fresh residuals determine convergence. No residual-to-solution-error assertion without conditioning. Budget exhaustion and representational stagnation are distinct statuses. Checked reservations report allocation failure. Cost: scalar O(iterations) evaluations/O(1) storage; diagonal O(niterations)/O(n); dense O(n²iterations)/O(n) auxiliary storage. Rounding, underflow and ill-conditioning can cause stagnation; no universal accuracy or speed claim. No useful separately measured executable surrogate is claimed.

validation

Validation evidence

2026-10-30. External records under $MOVA_DATA/runs/octopus-wave19-solvers-2026-10-30/. Two debug and two release runs each passed 501 library tests (12 new focused tests); sorted named outcomes agree across four runs. Strict algorithms all-target Clippy and focused rustfmt passed.

Source SHA-256: 4c4ec376d126d910fc1ab011186742e81316adcfafad875f53d36ddb3f3eb1de. Negative production mutant failed root bracket oracle; restored bytes passed the focused suite.

• negative-bisection_root.log SHA-256 f58f8e999cebbb85fb2a182ae2550e7cb6f1ffa0ea820dec898cacac123fa569
• restored-bisection_root.log SHA-256 a430b193dcffec2efdabab7169b108eb8807ea59c4ef23f57289cb88e2c66523
• debug1.log SHA-256 61428a2e0c6dbc43cde2fa1cf9a4b021a6cebd75c04de1ecb3cf761fa95eccbf
• debug2.log SHA-256 73ffe6afebfbf497bd448639d77d254de8142e4c170e346e976eff376e95e496
• release1.log SHA-256 9a28e6d7f1af6cfbf056323b4ec824aca1899d9ed52b1635d30ed01ed8785afb
• release2.log SHA-256 17cdc616d33e1ca8add5062ebed8e5303eebab267338c981dbc2aecba57afd43
• clippy.log SHA-256 71ef179d48cc2d1e07e85d2e77009ed79e6e543be1e409886afdb92b50363422

Partial syntax projection generated independently twice and compared byte-for-byte. These are finite checks; allocation exhaustion and arbitrary caller functions/matrices are not exhaustively verified.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/bisection_root/mod.rs.groupant/