Elamur Groupantsalgorithm-integer-sqrt
The groupant beside algorithms/src/integer_sqrt/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
Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.
Components
| component | label | where |
|---|---|---|
| approximant | bounded checked | Forward |
| ast | partial | syntax.json |
| cost | symbolic unmeasured | Cost |
| descriptant | present | descriptant |
| invariant | source derived | Invariant |
| tests | bounded executed | evidence |
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.
| id | type | label | where |
|---|---|---|---|
nonbehavior | behavior_complement | partial source derived | nonbehavior |
square_fibers | reverse_reconstruction | partial source derived | square_fibers |
square_boundary | boundary_specialization | partial source derived | square_boundary |
adjacent_inputs | metamorphic_relation | partial source derived | adjacent_inputs |
search_budget | resource_observation | partial source derived | search_budget |
Rust approximants
| id | metric | error | assurance |
|---|---|---|---|
integer_sqrt-1pct | abs(result-floor(sqrt(n)))/floor(sqrt(n)); zero input has zero error | 1 % cap, 0.78125 % stated | analytical |
integer_sqrt-2pct | abs(result-floor(sqrt(n)))/floor(sqrt(n)); zero input has zero error | 2 % cap, 1.5625 % stated | analytical |
integer_sqrt-5pct | abs(result-floor(sqrt(n)))/floor(sqrt(n)); zero input has zero error | 5 % cap, 3.125 % stated | analytical |
integer_sqrt-10pct | abs(result-floor(sqrt(n)))/floor(sqrt(n)); zero input has zero error | 10 % cap, 6.25 % stated | analytical |
Model text
descriptant
integer_sqrt mod epoch
2026-10-29. Repository search found math/src/calc.rs delegating arbitrary-precision roots to a dependency. This fixed-width binary search is newly authored; standard isqrt is test-only. No external solutions or LeetCode imports.
Prospective assumptions are retained in prospective.md. The mathematical combiner reviews source, partial syntax, forward/typed models, invariants and finite evidence. It preserves predictions and failed controls when revising claims; it is not an autonomous proof generator.
Replacing <= by < in the square predicate compiled and exactly tests::square_neighbors_and_maximum failed (exit 101; one failed, two filtered).
Implementation and tests form separate leaf groupants. Parent registry wiring remains integration work. Partial syntax has opaque macros and no semantic/type resolution. No universal proof or application behavior is claimed.
model
integer_sqrt mod model
Forward
For every u64 n, return r satisfying r^2<=n<(r+1)^2. Powers in this formula are mathematical integers.
Invariant
0<=lo<=hi<=2^32; all k<lo satisfy k^2<=n, all k>=hi up to 2^32 satisfy k^2>n. The interval strictly shrinks. Zero is always accepted, so final lo>=1. Midpoint squares fit u128.
Cost
At most 33 iterations, constant space; no allocations or floating point.
nonbehavior
Type: behavior_complement. U=u64 x u64; R(n,r) iff r^2<=n<(r+1)^2. U minus R contains exactly candidates violating either inequality. Evaluate candidate squares mathematically, including invalid large r; exact target with bounded evidence.
square_fibers
Type: reverse_reconstruction. Observed r<=u32::MAX admits all n in [r^2,min((r+1)^2-1,u64::MAX)]; other r admit none. Many inputs share a root, except zero.
square_boundary
Type: boundary_specialization. For r<=u32::MAX, root(r^2)=r; if r>0, root(r^2-1)=r-1. Explicit square-neighbor tests check inclusive equality.
adjacent_inputs
Type: metamorphic_relation. For n<u64::MAX, root(n)<=root(n+1)<=root(n)+1; increments occur only when n+1 is a square. Fixed-seed checks exercise the inequality.
search_budget
Type: resource_observation. Initial width 2^32 shrinks through binary splitting; at most 33 iterations with u128 comparisons and O(1) state. This is a source-derived bound, not measured throughput.
evidence
Evidence 2026-10-29
Three focused tests pass twice with identical normalized statuses. 65,537 inputs 0..=65536, nine square-root values with square/neighbor cases, u64::MAX and 4,096 fixed-seed full-width inputs with adjacent monotonicity.
Standard u64::isqrt is independent of this source; u128 square bounds provide a second constraint.
Replacing <= by < in the square predicate compiled and exactly tests::square_neighbors_and_maximum failed (exit 101; one failed, two filtered).
Commands: cargo test -p mova-algorithms --offline integer_sqrt::tests:: -- --test-threads=1; cargo clippy -p mova-algorithms --offline --all-targets -- -D warnings. Owned-source rustfmt checks pass. Temporary library exports permit local crate checks but are not committed; parent owns integration. External copies compile with rustc --edition 2024 --test and run with --exact. Production sources stay unchanged.
Source-bound syntax is generated twice after formatting and compared. Structural evidence does not establish semantic correctness, school/inference wiring or throughput.
prospective
Prospective epoch 2026-10-29
Before implementation: Use a half-open binary search over possible root values through 2^32, with u128 square comparisons; expect r^2 <= n < (r+1)^2 for every u64. Compare against standard u64::isqrt and explicit square neighbors.
Predict at most 33 search steps or 64 exponent-bit steps respectively, constant auxiliary space. Fixed-seed and boundary fixtures, two repeated focused tests, strict Clippy and a compiled source mutant rejected by one specific test will supply bounded evidence. No general proof, timing gain, imported solution or downstream integration claim.
This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/integer_sqrt/mod.rs.groupant/