MovaMova algorithms
mova-algorithms is a Rust library of two hundred deterministic algorithms, implemented for Mova using only the standard library. It forbids unsafe code and has no crate dependencies. Implementations and test fixtures are repository-owned; no LeetCode problem statements, solutions or imports are included. GCD reuses the Euclidean recurrence already present in Mova's math crate. The existing Elamur Cosmic License applies.
Each algorithm has its own src/<algorithm>/ directory. Each directory holds its implementation in mod.rs, executable checks in tests.rs, and adjacent mod.rs.groupant/ and tests.rs.groupant/ models. The shared public boundary remains src/lib.rs with src/lib.rs.groupant/.
For example:
algorithms/src/bfs/
├── mod.rs
├── mod.rs.groupant/
├── tests.rs
└── tests.rs.groupant/
Import public modules through mova_algorithms. For example:
use mova_algorithms::{binary_search, merge_sort};
let mut values = [7, 2, 7, 1];
merge_sort::merge_sort(&mut values);
assert_eq!(binary_search::binary_search_first(&values, &7), Some(2));
Costs below count comparisons, clones and fixed-width arithmetic as constant-cost operations. Space excludes input and returned output unless stated. Here n,m are sequence lengths, V,E are vertex/edge counts, C is knapsack capacity, L,R are bipartite partition sizes, S is a counting-sort span, w is a window width, and N is a sieve limit.
| Algorithm and public API | Time; auxiliary space | Contract and boundaries |
|---|---|---|
Binary search: binary_search::{lower_bound, binary_search_first} | O(log(n+1)); O(1) | Sorted &[T], T: Ord; sorting is not checked. Lower bound returns the first index with value >= target, or n. First-match returns Option<usize>; duplicates choose the first. Empty input gives 0 / None. |
Stable merge sort: merge_sort::merge_sort | O(n log(n+1)); O(n) elements plus O(log(n+1)) stack | Mutates &mut [T], T: Ord + Clone. Equal-key order is preserved. Empty/singleton inputs need no scratch allocation. Requires lawful ordering and value-preserving cloning. |
GCD: gcd::gcd | O(1+log(min(a,b)+1)); O(1) | Two u64 inputs, u64 output. gcd(0,0)=0; gcd(a,0)=a. No signed conversion or multiplication. |
Breadth-first search: bfs::bfs | O(V+E); O(V) | Directed adjacency lists and source index; returns Result<Vec<Option<usize>>, BfsError>. None means unreachable. Rejects invalid source, then every invalid edge, including unreachable edges. Empty graph has no valid source. |
Dijkstra: dijkstra::dijkstra | O(V+E log(E+1)); O(V+E) | Directed edges with u64 weights; exact u128 distances or None. Zero weights allowed. Validates source and all endpoints; checked addition reports DistanceOverflow. Lazy heap space includes stale entries. |
Topological sort: topological_sort::topological_sort | O(E+V log(V+1)); O(V) | Returns the lexicographically smallest vertex ordering. Parallel edges count separately; cycles and invalid endpoints return typed errors. All endpoints are validated before cycle processing. Empty graph returns an empty ordering. |
Disjoint sets: disjoint_set::DisjointSet | O(n) construction; amortized O(alpha(n)) per find/union/query; O(n) storage | Fixed universe 0..n; new, find, union, connected, components, len, is_empty. Invalid indices return IndexError without changing representation. Union reports whether components merged. Equal-size roots choose the smaller index; representatives need not be minimum members. |
KMP matching: kmp::find_all | O(n+m); O(m), plus returned matches | Byte slices; returns every matching byte offset, including overlaps. Empty needle matches all n+1 boundaries. UTF-8 byte offsets are not character indices. |
0/1 knapsack: knapsack::{Item, max_value} | O((n+1)(C+1)); O(C+1) | Each item has usize weight and u64 value; returns Result<u128, Error>. Each item is selectable once, including zero-weight items. Equal items are separate choices. Capacity dimension overflow and allocation refusal return errors. Exact value accumulation assumes supported Rust targets with usize <=64 bits. |
Levenshtein distance: levenshtein::distance | O(1+nm); O(min(n,m)) | Generic T: Eq slices; unit insertion/deletion/substitution costs, usize result. Empty input returns the other length. Caller chooses bytes, Unicode scalars or graphemes. With both inputs nonempty, usize::MAX length is rejected by panic. |
Heap sort: heap_sort::heap_sort | O(n log(n+1)); O(1) | In-place lawful Ord, no Clone bound. Deterministic but not stable for equal-key payloads. |
Selection: quickselect::select_nth | O(n²) worst case; O(1) | Mutates a slice to place the requested rank; prefix <= selected <= suffix. Invalid rank returns None without mutation. Deterministic pivot; no unconditional linear-time claim. |
Strict LIS: longest_increasing_subsequence::indices | O(n log(n+1)); O(n) | Returns original indices of one maximum-length strictly increasing subsequence. Equal minimum tails use the latest index; earliest lexicographic witness is not promised. |
Strong components: strongly_connected_components::components | O(V+E+V log(V+1)); O(V+E) | Iterative traversal with all endpoints validated. Vertices inside each component are sorted; components are ordered by their smallest vertex. |
Minimum spanning forest: kruskal::minimum_spanning_forest | O(V+E log(E+1)+E alpha(V)); O(V+E) | Undirected u64-weight edges. Returns original edge indices, u128 total and component count. Ties use weight, canonical endpoints, then original index; self loops ignored after validation. |
All-pairs shortest paths: floyd_warshall::floyd_warshall | O(V³+E); O(V²) including output | Nonnegative u64 weights, exact optional u128 distances. Diagonal zero, parallel-edge minimum, global endpoint validation and checked candidate addition. |
Dynamic sums: fenwick::Fenwick | O(n) build, O(log(n+1)) update/query; O(n) | i64 points with exact i128 sums on usize<=64 targets. Invalid or overflowing point updates preserve state. Prefix/range queries use exclusive ends; empty sums are zero. |
Immutable minima: sparse_table::SparseTable | O(n log(n+1)) build, O(1) query; O(n log(n+1)) | Ord + Clone; leftmost equal minimum. Nonempty half-open ranges return a reference; empty, reversed and out-of-bounds ranges return None. |
Integer square root: integer_sqrt::integer_sqrt | At most 33 iterations; O(1) | Exact floor root for every u64, with u128 square comparisons and no floating point. |
Modular power: modular_power::modular_power | At most 64 exponent iterations; O(1) | u64 base/exponent/modulus with exact u128 products. Modulus zero errors; modulus one returns zero; exponent zero returns 1 modulo the modulus. |
Signed shortest paths: bellman_ford::bellman_ford | O(V(V+E)); O(V) | Directed i64 weights; optional exact i128 distances. Validates source then all endpoints, including unreachable edges. Reports reachable negative cycles and checked-add overflow; unreachable negative cycles do not fail the call. |
Bipartite matching: bipartite_matching::bipartite_matching | O((L+1)(L+R+E)); O(L+R) | Left adjacency lists and right vertex count; returns one optional right mate per left vertex. Maximum cardinality with deterministic traversal ties; no lexicographic minimality guarantee. Validates every endpoint; duplicate edges allowed. |
Z prefix matches: z_algorithm::z_algorithm | O(n); O(1), plus O(n) output | Byte slices; each entry is the common-prefix length with that suffix. First entry is n; empty input returns an empty vector. Offsets count bytes. |
Palindrome radii: manacher::{manacher, PalindromeRadii} | O(n); O(1), plus O(n) output | Byte slices; odd radius includes its center, even radius is centered before its index. Returns both maximal-radius vectors; empty input returns two empty vectors. |
Dynamic minima: segment_tree::SegmentTree | O(n) build, O(log(n+1)) update/query; O(n) | Ord + Clone; point replacement and nonempty half-open range queries with leftmost minimum ties. Invalid updates preserve state; empty, reversed and out-of-bounds queries return None. Trait panics and allocation failure are outside the typed error contract. |
Sliding minima: sliding_window_minimum::minimum_indices | O(n); O(w), plus output | Ord slices; source indices of leftmost minima for complete windows. Zero or oversized widths return an empty vector. No input mutation or Clone bound. |
Counting sort: counting_sort::counting_sort | O(n+S); O(S) | Mutable usize slice and caller bucket budget. Histogram spans min..=max; range overflow, budget excess and allocation refusal return typed errors before mutation. Empty input needs no buckets; a singleton needs one. |
Radix sort: radix_sort::radix_sort | O(8(n+256)); O(n+256) | Mutable u64 slice; eight stable LSD byte passes, independent of host endianness. Scratch reserve failure returns TryReserveError before mutation. Scalar API exposes no attached payloads. |
Extended GCD: extended_gcd::{extended_gcd, Bezout} | O(1+log(max(a,b)+1)); O(1) | u64 inputs; u64 gcd and i128 coefficients satisfying ax+by=gcd. Deterministic coefficients; (0,0) returns three zeros. |
Prime sieve: sieve::sieve | O(N log log N) for N>=3; O(N) | Inclusive usize limit; returns ascending primes. Limits below two return empty output. Checked storage sizing and fallible allocation return SizeOverflow or AllocationFailed. |
Binary-weight paths: zero_one_bfs::zero_one_bfs | O(V+E); O(V+E) including stale deque entries | Optional usize distances; source, all endpoints and all u8 weights validated. Weights zero or one; zero cycles allowed. |
DAG paths: dag_shortest_paths::shortest_paths | O(E+V log(V+1)); O(V+E) | Signed i64 weights, optional checked i128 distances. Reuses deterministic topological sort; even unreachable cycles reject. |
Multi-pattern matching: aho_corasick::AhoCorasick | Search O(n log 256+z); stored automaton O(M+H+P) | Byte matches ordered by (end, pattern ID), overlaps, duplicate and empty patterns. M total pattern bytes, H inherited outputs, P pattern count, z emitted matches. Sparse construction and output sorting have the fuller bound in the leaf model. |
Suffix array: suffix_array::suffix_array | O(n log²(n+1)); O(n) | Byte offsets sorted by suffix; empty suffix excluded. Prefix doubling with comparison sort. |
Common subsequence: longest_common_subsequence::length | O(1+nm); O(min(n,m)) for nonempty inputs | Lawful Eq, exact length in one row; no witness. Dimension overflow panics; allocation/trait panics follow Rust behavior. |
Interval scheduling: weighted_interval_scheduling::select | O(n log(n+1)); O(n) | Positive-length half-open i64 intervals, u64 weights, checked u128 optimum and original-index witness. Adjacency allowed; sorted-DP ties skip candidate. |
Convex hull: convex_hull::{Point,convex_hull} | O(n log(n+1)); O(n) | Exact i32 points with i128 cross products. CCW extreme vertices from lexicographic minimum; duplicate/interior collinear points omitted. |
Closest pair: closest_pair::closest_pair | O(n log²(n+1)); O(n) | Shares hull Point type; exact u128 squared distance and lexicographically smallest original-index pair. Fewer than two points gives None. |
Prime factors: prime_factorization::factorize | O(sqrt(n)) trial divisions; O(log(n+1)) output | Ascending prime/exponent pairs; one empty, zero errors. Division-based bounds avoid overflow; large primes can be slow. |
Generalized CRT: chinese_remainder::solve | O(k log U); O(1) auxiliary, U=u64::MAX | Noncoprime moduli allowed; normalized combined u64 class or None. Zero moduli preflight, then left-to-right checked merge; overflow can precede later contradiction. Empty system 0 mod 1. |
Bridges: bridges::bridges | O(V+E); O(V+E) | Undirected indexed multigraph, loops and parallel edges; sorted original edge IDs, global endpoint validation. Iterative lowlink traversal. |
Articulation points: articulation_points::articulation_points | O(V+E); O(V+E) | Reuses Edge; sorted cut vertices with removed-vertex connectivity semantics, including disconnected graphs. |
Euler trail: eulerian_trail::eulerian_trail | O(V+E); O(V+E) | Optional deterministic edge-ID trail; nonisolated support connected, zero/two odd degrees. Loops count twice. Empty universe yields empty trail; edgeless nonempty universe starts at zero. |
Maximum flow: max_flow::max_flow | O(V+E+VE(V+E)); O(V+E) | Edmonds-Karp with u64 capacities, indexed edge flows, u128 total and residual source-side cut. Parallel/antiparallel edges retained; loops carry zero. Distinct valid terminals required. |
Forest LCA: lowest_common_ancestor::Lca | Build O(V log(V+1)), query O(log(V+1)); O(V log(V+1)) | Validated parent forest, iterative cycle detection and binary lifting. Invalid parents/vertices error; separate trees return None. |
Suffix automaton: suffix_automaton::SuffixAutomaton | Build O(n log 256), membership O(m log 256), distinct count O(n); O(n) fixed-byte states/edges | Byte substring language, empty query included; exact count of distinct nonempty substrings in u128. Deterministic sparse transitions. |
Huffman codes: huffman::codes | Heap O(n log(n+1)) plus emitted code length; O(n) tree plus output | Binary code per original symbol, deterministic ties, nonnegative u64 weights. Empty input no codes, singleton one false bit. Code lengths can make output quadratic. |
Palindromic subsequence: longest_palindromic_subsequence::length | O(n²); O(n) | Generic lawful Eq; one-row interval recurrence returns exact length, not a witness. Empty input zero. |
Unlimited coin change: coin_change::minimum_coins | O(k+(A+1)(k+1)); O(A+1) | Minimum count or None; positive usize denominations, duplicate values harmless. Zero denomination preflight, checked table dimension and fallible reserve. |
Matrix chain: matrix_chain::minimum_cost | O(n³); O(n²), n matrices | Positive u64 dimensions, checked u128 cost. Overflowing candidates are skipped; CostOverflow only when final optimum cannot fit. Empty chain zero, zero dimensions reject. |
A* paths: a_star::shortest_path | O(V+E+(V+E) log(V+E+1)); O(V+E) | Directed u64 weights and u64 heuristic vector; validates all endpoints, h(goal)=0 and every consistency inequality before search. Returns optional Path with checked u128 distance and vertex witness. Arbitrary inadmissible heuristics reject; deterministic ties do not promise a lexicographically smallest path. |
Two-SAT: two_sat::{Literal, solve} | O(V+C+V log(V+1)); O(V+C), V variables/C clauses | Clause pairs of indexed positive/negative literals; optional satisfying Boolean vector, None for unsatisfiable. Checks doubled node-count overflow and every literal. Reuses SCC plus explicit condensation topological ranks; canonical SCC IDs alone are insufficient. Empty formula is allowed; assignment is deterministic, not lexicographically minimal. |
Global minimum cut: stoer_wagner::minimum_cut | O(V³); O(V²) | Square symmetric u64 capacities, diagonal ignored. Checked u128 cut total and sorted nonempty proper side containing vertex zero; fewer than two vertices returns None, disconnected graphs have zero cut. Phase ties are deterministic; no globally lexicographic minimum-cut witness promise. |
Verified rolling-hash search: rabin_karp::find_all | O(1+nm) worst case for nonempty patterns, O(n+1) for empty; O(1) plus output | Exact increasing byte offsets with overlaps. Wrapping modulo-2^64 hashes are only a filter: every candidate is byte-verified, including collisions. Empty pattern matches all n+1 boundaries; no Unicode normalization. |
Horspool search: boyer_moore_horspool::find_all | O(nm+256) worst case for nonempty patterns, O(n+1) for empty; O(256) plus output | Byte-alphabet shift table and backward comparisons return all exact offsets, including overlaps. Empty pattern matches every boundary; longer-than-text pattern returns empty. No linear worst-case guarantee. |
Common substring: longest_common_substring::longest_common_substring | O(1+nm); O(m) for nonempty inputs | Generic Eq contiguous Match {a_start,b_start,len}; maximum length then minimum start pair. No match returns (0,0,0). Caller selects element units; no normalization. Checked second dimension; allocation/trait failures follow Rust behavior. |
Restricted alignment: optimal_string_alignment::distance | O(1+nm); O(min(n,m)) for nonempty inputs | Unit insert/delete/substitute/adjacent-transpose costs on Eq slices. Optimal string alignment restricts repeated edits; it is not unrestricted Damerau distance and need not satisfy the triangle inequality. Empty input costs the other length; maximal nonempty dimension panics. |
Subset sum: subset_sum::subset_sum | O((n+1)(T+1)); O(T+1), T target | Nonnegative usize values and target <= MAX_TARGET=1,000,000, checked before allocation even for empty input. Increasing distinct-index witness or None; zero target returns empty witness and zero-valued items are omitted. First discovery is deterministic; no minimum-cardinality guarantee. Typed target/allocation errors. |
Binomial coefficient: binomial_coefficient::binomial_coefficient | O(min(k,n-k) log(n+1)); O(1) | u64 n,k; exact u128 n-choose-k. k>n errors; k=0 or n gives one. Cancel denominator factors before checked multiplication, so Overflow denotes genuine result overflow rather than a removable intermediate product. |
Interval union: interval_union::interval_union | O(n log(n+1)); O(n) | i64 half-open intervals, all validated before allocation. Empty intervals disappear; overlap and touching merge into increasing disjoint intervals. Union includes u128 covered length using widened differences; reversed input reports its index, reserve failure errors, input unchanged. |
Johnson all-pairs paths: johnson::johnson | O(V(V+E)+VE log(E+1)); O(V²+V+E), including output | Directed i64 weights; optional exact i128 distances. Limits V<=1024 and E<=1,000,000 precede global endpoint validation, then global negative-cycle detection. Reweighting stays i128; unreachable negative cycles reject. Empty graph returns an empty matrix; arithmetic errors are checked, allocation failures follow Rust behavior. |
Prim forest: prim::minimum_spanning_forest | O(V+E log(E+1)); O(V+E) | Shares Kruskal Edge/Forest records; u64 weights, checked u128 total, original edge indices in acceptance order. At most 1,000,000 vertices and edges, checked before endpoints. Loops ignored after validation; deterministic heap ties use weight, canonical endpoints and original index. Same optimum as Kruskal need not mean identical edge order. |
Packed reachability: transitive_closure::{transitive_closure, Closure} | O(V² ceil(V/64)+E); O(V ceil(V/64)) including stored result | Reflexive directed closure with vertices() and reachable(from,to); invalid queries return None. Limits V<=8192 and E<=1,000,000 precede endpoint validation. Loops/duplicates do not change reachability; empty graph is valid. Allocation failures follow Rust behavior. |
Adjacent suffix prefixes: lcp_array::lcp_array | O(n log²(n+1)) including suffix construction; O(n) | Returns byte suffix order and adjacent LCP vectors of length n; first LCP is zero and no empty suffix is included. Kasai stage itself is O(n); the reused comparison-sort suffix construction determines total cost. |
Burrows-Wheeler transform: burrows_wheeler::{transform, inverse} | Transform O(n log²(n+1)); inverse O(n log²(n+1)+256); O(n+256) | Arbitrary bytes without a sentinel. Equal cyclic rotations tie by original offset; transform returns last column and primary row. Empty maps to ([],0). Inverse checks primary bounds then retransforms to reject unreachable columns/noncanonical periodic rows; an in-range row alone is insufficient. |
Wildcards: wildcard_matching::wildcard_match | O((n+1)(m+1)); O(m+1) | Full byte-string match: ? consumes exactly one byte, * consumes any number including zero. Every other byte, including backslash, is literal; no escapes, Unicode decoding or filesystem semantics. Empty text matches precisely all-star patterns, including empty. |
Bounded knapsack: bounded_knapsack::{Item, bounded_knapsack} | O(items+(C+1)(B+1)), B binary bundles; O(C+1) | usize weight/count, u128 value and exact optimum without witness. Zero weights select every copy; counts of positive weights are truncated by feasibility. Capacity<=1,000,000, items<=100,000 and updates<=20,000,000 precede allocation and value checks. ValueOverflow denotes an overflowing feasible optimum; duplicate items remain independent. |
LCS reconstruction: hirschberg::hirschberg | O(1+nm); O(min(n,m)+log(max(n,m)+1)), plus output | Lawful Eq inputs; increasing index pairs witness an exact LCS. Each length<=1,000,000 and product<=16,000,000 before allocation, even for empty inputs. Shorter row axis, smallest maximizing split and first singleton row match fix deterministic ties, without global lexicographic minimality. |
Linear recurrence: linear_recurrence::nth_term | O(k² log(n+1)) for n>=k, O(1) for initial prefix; O(k) | u64 seeds/coefficients, index n and nonzero modulus; a[t]=sum c[j]a[t-1-j]. Validates modulus, nonempty order, equal dimensions and k<=4096 before the prefix shortcut. Normalizes inputs and uses u128 products; composite moduli allowed. Allocation refusal is typed. |
Finite-field convolution: number_theoretic_transform::convolution | O(L log(L+1)), L padded power of two; O(L) | Ascending-degree u64 coefficients normalized modulo 998244353. Exact modular output of length a.len+b.len-1; either empty operand gives empty. Checked dimensions and L<=2²³ precede fallible allocation. This is modular polynomial multiplication, not unreduced integer convolution. |
Hopcroft-Karp matching: hopcroft_karp::maximum_matching | O((L+R+E) sqrt(L+R+1)); O(L+R) | Left adjacency lists and right count; one optional right mate per left vertex. Combined vertices and edges each <=1,000,000, checked before endpoints. Duplicates allowed; deterministic optimum without lexicographic guarantee. Iterative paths; allocation failure follows Rust behavior. |
Blocking flow: dinic::max_flow | O(V²E+V²+E) conservative; O(V+E) | Shares max_flow::{Edge, Flow}: u64 capacities, u128 total, indexed edge flows and residual source-side cut. V,E<=1,000,000 before source, sink, distinctness and endpoint validation. Parallel/antiparallel edges remain distinct; loops carry zero. Checked arithmetic; allocation failure is not typed. |
Tarjan components: tarjan_scc::components | O(V+E+V log(V+1)); O(V) excluding output | Iterative lowlink without reverse graph; sorted members and components ordered by minimum vertex match the existing SCC API. V,E<=1,000,000 before endpoints. Empty graphs, loops and duplicates supported; sorting adds to linear traversal cost. |
Unrestricted Damerau distance: damerau_levenshtein::distance | O((n+2)(m+2)); O((n+2)(m+2)) | Unit byte insertion/deletion/substitution/adjacent-transposition, including repeated edits unlike OSA. Empty inputs immediately return the other length. Otherwise checked dimensions precede the 1,000,000-cell cap including sentinels. Allocation follows Vec behavior. |
Eertree: palindromic_tree::{build, PalindromicTree, Palindrome} | O(n log 256) amortized; O(n) | Distinct nonempty byte palindromes in discovery order, first occurrence ranges, overlapping counts and suffix links. Queries palindromes, distinct_count, longest; longest ties choose earliest start. n<=1,000,000 before allocation; empty tree has no longest palindrome. |
Lyndon factors: lyndon_factorization::factorize | O(n) comparisons; O(1) plus O(k) output | Duval scan returns the unique nonincreasing sequence of nonempty Lyndon factors as byte ranges. Unsigned lexicographic byte order, no normalization; empty input has no factors. Allocation follows Vec behavior. |
Recurrence synthesis: berlekamp_massey::minimal_recurrence | O(n²+n log p); O(n), p=998244353 | Normalizes u64 terms, returns minimum compatible recurrence in lag order accepted by Kitamasa. n<=4096 before fallible allocation. Empty/all-zero prefixes return empty order; finite prefixes can admit multiple minimum-order continuations and do not identify an infinite source. |
XOR convolution: fast_walsh_hadamard::{transform, xor_convolution} | Transform O(N log N+log p) with inverse, O(1) space; convolution O(N log N+log p), O(N) | Exact residues modulo p=998244353. Transform needs nonempty power-of-two N<=2²⁰; validation errors preserve input. Convolution checks caps before empty shortcut, otherwise pads to next_power_of_two(max lengths), returning the full XOR domain. Inverse divides by N; no primitive-root premise. |
Hungarian assignment: hungarian::{hungarian, Assignment} | O(r²c); O(r+c) | Rectangular i64 costs, distinct column per row, i128 objective and dual potentials. Limits r<=512, c<=4096, r²c<=20,000,000; validates row cap, first-row column cap, shape, r<=c, then work/allocation. Empty assignment costs zero; deterministic ties need not be lexicographically first. |
Held-Karp tour: held_karp::{held_karp, Tour} | O(n²2^n); O(n2^n) | Square directed optional-u64 arc matrix; optional u128 minimum Hamiltonian cycle starting/ending at zero. n<=18 before shape/allocation. Missing arcs remain absent; self-arcs ignored. Empty input gives empty zero-cost tour; singleton gives [0,0] at zero cost. Deterministic ties need not be lexicographically first. |
Minimum bipartite cover: bipartite_vertex_cover::{minimum_vertex_cover, Cover} | O((L+R+E) sqrt(L+R+1)); O(L+R) | Sorted left/right vertex indices of a minimum cover, using Hopcroft-Karp and alternating reachability. Combined vertices<=1,000,000, then stored edges<=1,000,000, then endpoints validated. Empty partitions and duplicate edges allowed; deterministic witness without lexicographic minimum guarantee. Allocation failures are not typed. |
Stable marriage: stable_marriage::stable_matching | O(n²); O(n²) | Complete strict preference permutations for two equal populations; returns receiver index per proposer, deterministically proposer-optimal. Equal sizes, checked 2nn<=2,000,000, then proposer rows before receiver rows; each row length precedes its first invalid/duplicate entry. Empty populations return empty; ties/incomplete lists reject. Allocation failures are not typed. |
Deterministic primality: miller_rabin::is_prime | O(log(n+1)) modular operations for seven fixed witnesses; O(1) | Every u64 input; values below two are false. Exact u128 modular products and the finite-range seven-witness result give deterministic full-u64 testing, not a randomized confidence score. No allocation or resource cap. |
Prime-field square root: tonelli_shanks::sqrt_mod | O(p log p+log² p) worst-case modular operations; O(1) | Validates p>=2 and primality before reducing the u64 radicand or taking zero shortcuts. Returns the smaller root or None for a nonresidue; p=2 supported. Ascending nonresidue search can examine up to p-2 candidates, so no uniformly fast search bound is promised. No allocation; composite moduli reject. |
Minimum cyclic rotation: minimal_rotation::minimal_rotation | O(n); O(1) | Returns the smallest byte index among lexicographically minimum cyclic rotations; empty input gives zero. Unsigned byte order, including periodic ties; no Unicode normalization. No allocation, doubled input or arbitrary length cap. |
Shift-And matching: shift_and::find_all | O(256+m+n+z), z matches; O(256) words plus output | Exact increasing byte offsets with overlaps; empty pattern matches all n+1 boundaries. Pattern length>64 returns PatternTooLong before scanning, including empty text. No text cap or Unicode normalization; output allocation follows Rust behavior. |
Subset zeta: subset_zeta::transform | O(N log(N+1)); O(1) | In-place subset sums over Z/modulus Z with arbitrary nonzero u64 modulus, including composite moduli and one. Validates zero modulus, empty input, non-power-of-two length, then N>2²⁰ before mutation. Normalizes all entries even for N=1; u128 additions avoid overflow. No allocation. |
Subset Möbius: subset_mobius::transform | O(N log(N+1)); O(1) | In-place signed subset inclusion-exclusion, inverse of subset zeta on normalized residues over any nonzero u64 modulus. Validates zero modulus, empty input, non-power-of-two length, then N>2²⁰ before mutation. Normalization loses original residue representatives; conditional subtraction avoids overflow. No field or division premise, no allocation. |
Inversion count: inversion_count::count_inversions | O(n log(n+1)); O(n) indices plus O(log(n+1)) stack | Lawful Ord without Clone; exact u128 count of i<j with values[i]>values[j], preserving input. Equal values are not inversions. n<=2²⁰ checked before fallible allocation; typed TooLong/AllocationFailed. Trait panics remain outside typed errors. |
Minimum Cartesian tree: cartesian_tree::{min_cartesian_tree, CartesianTree} | O(n) comparisons; O(n) stack plus O(n) output | Lawful Ord without Clone; root and parent/left/right index vectors preserve inorder positions. Equal minima choose the leftmost interval index; empty input has no root. n<=2²⁰ checked before fallible allocation; typed TooLong/AllocationFailed. Input unchanged; trait panics remain outside typed errors. |
Borůvka forest: boruvka::minimum_spanning_forest | O((V+E) log(V+1) alpha(V)); O(V) plus output | Undirected i64 weights, exact i128 total, sorted original edge indices and component count. V<=1,000,000, E<=4,000,000 before endpoints; validated loops ignored, parallel edges allowed. Each component chooses by (weight,input index); disconnected and empty graphs supported. |
Prüfer coding: prufer::{encode, decode} | O(V log(V+1)); O(V) | Zero-based labeled trees, V<=1,000,000. Encode removes the smallest leaf; decode returns lexicographically sorted canonical edges. Vertex count disambiguates empty codes for V=0,1,2. Wrong lengths, labels, loops, duplicate edges and nontrees reject. |
Bron–Kerbosch clique: bron_kerbosch::maximum_clique | Conservative O(V² 2^V); O(V²) | Lexicographically least sorted maximum clique of a simple undirected graph with V<=64 and E<=V(V-1)/2. Loops and reversed duplicates reject. Zero-vertex graph gives empty clique; the representation cap does not promise practical runtime on adversarial inputs. |
Banded edit distance: banded_levenshtein::distance | O(max(n,m) min(min(n,m)+1,2k+1)); O(min(min(n,m)+1,2k+1)) | Byte Levenshtein distance as Some(d) when d<=threshold, otherwise None; k=min(threshold,max(n,m)). At most 4096 cells per rolling row. Length-difference and empty-input shortcuts precede band-budget validation; usize::MAX threshold is safe. |
Bit-parallel LCS: bit_parallel_lcs::length | O(256+n+m); O(256) words | Exact byte LCS length when the shorter side has at most 64 bytes, otherwise typed rejection. Empty side returns zero. Full 64-bit masks use wrapping subtraction; no Unicode normalization or witness reconstruction. |
Totient sieve: totient_sieve::totient_sieve | O(N log log N) for N>=3; O(N) output | Inclusive usize table phi(0)..=phi(N), with phi(0)=0 and phi(1)=1. N<=1,000,000 before allocation; prime-factor elimination. |
Möbius sieve: mobius_sieve::mobius_sieve | O(N); O(N) | Inclusive i8 table mu(0)..=mu(N), with mu(0)=0 and mu(1)=1. N<=1,000,000 before allocation; linear least-prime sieve. Distinct from the subset Möbius transform. |
Fibonacci: fibonacci::fibonacci_mod | O(log(n+1)); O(1) | Every u64 index and nonzero u64 modulus, including composite moduli and one. Fast doubling with reduced u128 products; zero modulus errors even for n=0. |
Discrete Li Chao tree: li_chao_tree::{LiChaoTree, Line, Minimum} | Build O(n log(n+1)), insert/query O(log(U+1)); O(n) allocated storage | Nonempty supplied i64 coordinates, raw count<=2^18 before deduplication; U unique coordinates. i64 slope/intercept, exact i128 minimum and earliest insertion-ID ties. At most 2^20 lines; unknown coordinates and queries before insertion error. |
Offline connectivity: offline_dynamic_connectivity::{solve, Operation, Answer} | O(q log(q+1) log(V+1)+V); O(q log(q+1)+V) | V,q<=2^18 before validating the operation timeline. Undirected simple-edge Add/Remove and Connected/Components queries; self-loops allowed, reversed endpoints identify the same edge. Duplicate add or absent remove errors; answers retain query order. Time-segment tree and rollback DSU. |
Biconnected edge blocks: biconnected_components::biconnected_components | O(V+E); O(V+E), including output | Undirected indexed multigraph; partition into vertex-biconnected edge blocks with ascending IDs, ordered by minimum ID. Parallel edges may share a block; every loop and bridge is a singleton; isolates produce no block. All endpoints validated in edge order, u before v, before allocation. Iterative DFS, no configured size cap; allocation failures are not typed. |
DAG path counts: dag_path_count::dag_path_count | O(E+V log(V+1)); O(V) plus output | Exact checked u128 source-to-vertex counts; empty path to source counts once, parallel edges are distinct choices, unreachable counts are zero. Validates source, all endpoints, then global acyclicity, including unreachable cycles. First overflowing addition follows lexicographically smallest topological order and input adjacency order. No configured size cap; allocation failures are not typed. |
Two-way matching: two_way_matching::find_all | O(n+m+z), z matches; O(1) plus output | Exact increasing byte offsets with overlaps, using critical factorization and periodic memory. Empty pattern matches all n+1 boundaries; oversized pattern returns empty. No arbitrary length cap or Unicode normalization; output allocation failures are not typed. |
Global alignment: needleman_wunsch::{align, Scoring, Alignment} | O((n+1)(m+1)); O((n+1)(m+1)) plus O(n+m) output | Byte alignment maximizing signed i64 match/mismatch/linear-gap scores; returns score and optional-byte column pairs. Ties prefer diagonal, deletion, insertion. Checked matrix dimensions precede caller max_cells budget, then fallible reservations. Every score addition is checked, including losing candidates: any overflow rejects the call. Empty inputs still require matrix cells; allocation refusal returns an error. |
Run-length encoding: run_length_encoding::{encode, decode, Run} | Encode O(n), decode O(r+n); O(1) plus O(r)/O(n) output | Canonical maximal byte runs. Decoder checks each run in input order for zero count, adjacent equal byte, then cumulative length overflow; only after full validation checks max_output and reserves. Empty runs decode to empty output. Decode allocation refusal is typed; encode allocation failures follow Rust behavior. |
Euclidean floor sum: floor_sum::floor_sum | O(log(max(a,m)+1)); O(1) | Exact sum of floor((a*i+b)/m) for 0<=i<n, with all parameters u64 and checked u128 result. Zero modulus rejects before the empty-sum shortcut; genuine result overflow returns an error. No allocation or additional input cap. |
Segmented prime sieve: segmented_sieve::segmented_sieve | O(sqrt(H) loglog(max(H,3))+W loglog(max(H,3))+sqrt(H)+W); O(sqrt(H)+W) plus output | Ascending primes in inclusive [low,H], W=H-low+1. Validates reversed interval, H<=10^12, then W<=10^6 before allocation. Fresh base sieve through floor(sqrt(H)) is included in cost, even for narrow intervals. Zero and one excluded; allocation failures are not typed. |
Bounded Pollard rho: pollard_rho::factorize | Conservative O((B+64) log(n+1)); O(log(n+1)), including output | Sorted prime factors with multiplicity for u64 n; one yields empty. Rejects zero before checking B<=10^7. Budget counts global Floyd iterations across all splits/restarts; each uses three modular squares and one GCD. Primality checks and even splits consume no iterations. Deterministic restarts, exact u128 products, explicit exhaustion instead of a partial successful result; no success guarantee for any budget. Allocation failures are not typed. |
Persistent sums: persistent_segment_tree::PersistentSegmentTree | Build O(n); query/update O(log(n+1)); O(n+u log(n+1)) stored nodes and roots after u updates | from_slice, set, range_sum, length/version/node counts. i64 values with checked exact i128 sums on <=64-bit targets; half-open index ranges, empty sum zero. Version zero exists even for empty input. Replacement may branch from any version and preserves older versions; version validation precedes index/range checks. Returned errors preserve roots and arena. No configured memory cap; allocation failures are outside Result semantics. |
Wavelet matrix: wavelet_matrix::WaveletMatrix | Build O(64(n+1)); queries O(64); 64(n+1) usize prefixes plus 64 totals, O(n) construction scratch | Static u64 from_slice, rank, count_less, range_count, kth, len, is_empty. Index and value ranges are half-open; kth is zero-based with duplicates. Invalid bounds/rank return None; empty count ranges give zero. Value upper bounds are u64, so [lower,upper) cannot include u64::MAX; use rank separately or interval length minus count_less(lower). Reversed value bounds are checked before index bounds. No configured size cap; allocation/dimension panics are outside query Option semantics. |
Except where a typed allocation error is specified, allocation failures follow standard Rust collection behavior. User-provided comparison, equality and cloning behavior must satisfy their trait contracts.
See Testing the algorithms for per-algorithm commands, test sources and oracle limits. Run from the repository root:
cargo test -p mova-algorithms --offline
cargo test -p mova-algorithms --offline --release
cargo clippy -p mova-algorithms --offline --all-targets -- -D warnings
Each algorithm has deterministic edge tests and bounded independent oracles. The library root holds composition tests (ordering/ranks/LIS, distances and connectivity, spanning forests, prefix reconstruction, restricted square/root inversion and the further interactions listed in Testing the algorithms) and a runnable documentation example. External composition harnesses are tests/composition_wave{4,5,7,10,11,14,16,18,19,20,25}.rs and tests/groupant_wave26_transforms.rs; Testing the algorithms describes their joins, and each harness has an adjacent groupant binding its adapters.
Each implementation and test module has an adjacent groupant with source-bound partial syntax projections, forward models, invariants, costs, typed obernants and evidence (groupants). The first obernant is a scoped behavior complement; the second reconstructs potentially ambiguous compatible inputs. The parent algorithm-library groupant describes library wiring and interaction obligations. Model counts are distinct from executable test counts.
Models and finite oracles are not general proofs. Syntax projections omit expansion and semantic analysis, and structural validation establishes artifact consistency rather than algorithm correctness. The library is not automatically integrated into school learning or inference.
Executable approximation models
The integer-root, quickselect, knapsack, Levenshtein, increasing-subsequence and sparse-table implementation groupants contain executable Rust surrogates with four error caps: 1%, 2%, 5%, 10%. Their metrics and APIs differ where explicitly documented; those six ordinary reference APIs remain exact; the separately listed numerical and approximation modules have explicit scoped contracts. Run the shared mova-approx example for differential checks, including standard-library comparisons and fallback overhead. See executable Rust approximants.
Validation and measurements
The commands above run the library tests in debug and release and the strict package Clippy check. Each algorithm also has a compiled source mutation that a specifically selected test must reject, and the groupant report rejects stale source bindings and wrong child identities; these are the negative controls. Evidence receipts, coverage and structural checks, and bounded CPU comparisons of selected kernels live in the parent groupant: start from its evidence index. Finite checks and timings establish no general proof, approximation gain or whole-Mova speedup.
References and adapter limits
The implementations are original. Algorithm references are retained beside their sources: Borůvka (1926), Prüfer (1918), Bron and Kerbosch, Algorithm 457 (1973), Ukkonen (1985) for banded edit distance, Allison and Dix (1986) for bit-string LCS, Hardy and Wright for arithmetic functions, Knuth volume 1 §1.2.8 for Fibonacci, and the CP-Algorithms descriptions of Li Chao trees and offline deletion with rollback. These references describe established methods; finite native correspondence remains separate evidence.
Coordinates, modulus domains, tie rules and resource limits remain explicit in the APIs and join models. In particular, the signed-forest adapter adds a constant only with fixed forest cardinality, and the clique cap is not a runtime guarantee.
Optimization and approximation kernels
These APIs expose their numerical assumptions, stopping conditions and resource limits. In this table, space includes returned vectors but excludes caller-owned inputs; n is input length/dimension, k is the iteration budget, B is histogram bucket count, c is sketch capacity, and L is the maximum retained trimmed-list length. Callback costs are additional. For supported percentage tiers, epsilon is percent/100.
| Algorithm and public API | Time; space | Contract and boundaries |
|---|---|---|
Bisection: bisection_root::solve | O(k) callback evaluations; O(1) | Deterministic continuous callback and sign-changing bracket; absolute bracket width or computed zero stops. Reports convergence, exhausted budget or stagnation; finite bounded endpoints and evaluations required. |
Golden-section search: golden_section_search::minimize | O(k) callback evaluations; O(1) | Caller supplies deterministic strictly unimodal function. Absolute interval-width stopping; explicit budget/stagnation statuses. Interval width is not an objective-error certificate. |
Diagonal quadratic descent: gradient_descent_quadratic::minimize_diagonal | O((k+1)n); O(n) | Positive diagonal quadratic, dimension 1..256; step is reciprocal maximum diagonal. Absolute gradient-norm stopping, budget/stagnation reports and arithmetic errors; no general dense objective API. |
Conjugate gradients: conjugate_gradient::solve | O((k+1)n²); O(n) | Dense matrix, dimension 1..256; caller guarantees SPD. Checks symmetry and encountered curvature; stopping uses freshly computed absolute residual. Budget/stagnation and arithmetic errors remain explicit. |
Knapsack FPTAS: knapsack_fptas::max_value | O(n³/epsilon); O(n²/epsilon) | Reuses knapsack::Item; exact integer profit scaling gives feasible objective and rational loss certificate <=epsilon*OPT. Zero optimum exact; no selected-item witness; explicit work/allocation/overflow errors. |
Subset-sum FPTAS: subset_sum_fptas::max_sum | O(n L log(L+1)); O(L) | u64 values/target, rational list trimming; feasible sum >=(1-epsilon)*OPT, zero optimum exact. L=O(1+n log(target+1)/epsilon); candidate budget excludes sorting comparisons. |
Integer quantized dot: quantized_dot::dot | O(n); O(1) | i64 vectors truncated toward zero by positive integer step. Checked absolute error <=epsilonsum(abs(a_ib_i)); zero L1 scale requires zero certificate. Uncertified calls error, with no exact fallback. |
Piecewise linear interpolation: piecewise_linear::{Knot, interpolate} | O(n) validation + O(log n) lookup; O(1) | Integer knots/query, exact rational chord, no extrapolation. Conditional absolute error <=M*h²/8 requires exact samples of a C² function with curvature bound M; samples cannot establish that premise. |
Misra–Gries: misra_gries::MisraGries::{new, update, bounds} | O(c) worst-case update, O(log(c+1)) query; O(c) | u64 keys/counts; deterministic lower/upper frequency bounds, c=100/percent. Error is additive relative to total stream length; overflow rejects update. BTreeMap allocation follows standard behavior. |
Space-Saving: space_saving::SpaceSaving::{new, update, bounds} | O(c) worst-case update/query; O(c) | Deterministic minimum-count/key victim; frequency intervals include absent keys. Additive error scaled by stream length; checked count overflow, standard BTreeMap allocation behavior. |
Histogram quantiles: histogram_quantiles::HistogramQuantiles::{new, update, quantile} | O(B) construction/query, O(1) update; O(B) | Fixed inclusive u64 domain and positive bucket width, B<=1,000,000. Zero-based rank returns value/rank interval; no relative-value or normalized-rank percentage promise. |
Streaming moments: streaming_moments::StreamingMoments::{update, merge, mean, population_variance, sample_variance} | O(1) per operation; O(1) | Welford/Chan f64 mean and variance, count<=2^53. Errors preserve state; overflow rejected, tiny variance may underflow. Merge order can change rounded results. |
Isotonic regression: isotonic_regression::isotonic_regression | O(n); O(n) | Unit-weight nondecreasing least squares via PAVA, n<=1,000,000. Finite inputs, fallible allocation; block-sum overflow rejected even when a real mean exists. Rounded projection has no universal accuracy bound. |
Simplex projection: simplex_projection::project_simplex | O(n log(n+1)); O(n) | Nonnegative mass radius, n<=1,000,000; empty input needs zero radius. Maximum shift, sorted threshold and checked relative mass residual <=64nEPSILON; arithmetic failure explicit. |
L1-ball projection: l1_ball_projection::project_l1_ball | O(n log(n+1)) worst case; O(n) | Reuses simplex on magnitudes outside ball and restores signs; computed interior path returns input. Nonnegative radius, finite inputs; norm overflow rejects. Rounded mass tolerance permits slight radius excess. |
Soft threshold: soft_threshold::soft_threshold | O(n); O(n) | Coordinate proximal map of lambda*L1, finite lambda>=0 and n<=1,000,000. Magnitudes shrink, zero plateau preserves sign; subtraction/underflow are rounded. |
Adaptive Simpson: adaptive_simpson::integrate | O(E) callback evaluations/panel work; fixed 65-panel stack | E bounded by evaluation budget; depth<=64. Reports estimated tolerance, evaluation/depth budget or stagnation. Richardson error estimate is heuristic; unresolved-panel error is unknown. |
Compensated sum: compensated_sum::sum | O(n); O(1) | Input-order Neumaier compensation; empty sum zero. Rejects nonfinite input/intermediates; compensation is not generally exact and has no universal relative-error certificate. |
Horner evaluation: horner::evaluate | O(n); O(1) | Ascending f64 coefficients; returns polynomial value and derivative together. Empty polynomial gives (0,0); finite arithmetic checked, rounding remains. |
Chebyshev evaluation: chebyshev_clenshaw::evaluate | O(n); O(1) | Full-coefficient series on [-1,1], constant coefficient not halved; empty series zero. Clenshaw recurrence rejects nonfinite intermediates; no universal relative bound. |
Only 1%, 2%, 5% and 10% are selectable in the percentage APIs. Integer objective loss, additive frequency error divided by stream length, and dot error divided by the L1 sum of products are different metrics. None certifies floating-point optimizer, moment, projection or quadrature error; a small residual also needs conditioning assumptions to bound solution error. Integer certificates use checked arithmetic, while numerical kernels expose rounded observations and failure/status paths.
The family groupants record wiring, typed behavior complements, nonunique reverse fibers, costs and scoped assumptions: optimization solvers, certified approximation, streaming statistics, convex projections and numerical evaluation. Leaf models distinguish mathematical targets from executable finite arithmetic.
Linear algebra, optimization, interpolation and structured DP
Space includes returned values but excludes caller inputs; n is dimension/input length, m is row count, k is iteration budget, L is Romberg level count, g is partition count, and W=floor(target/64)+1. Callback costs are additional. Numerical APIs validate finite bounded inputs and expose arithmetic failures; their observations are not universal floating-point error certificates.
| Algorithm and public API | Time; space | Contract and boundaries |
|---|---|---|
Cholesky: cholesky::factor | O(n³); O(n²) | n=1..64; intended SPD input, exact symmetry and positive encountered pivots checked. Returns lower factor and Frobenius reconstruction residual; floating pivots do not certify conditioning. |
Triangular substitution: triangular_solve::{Triangle, solve} | O(n²); O(n) | n=1..64, exact lower/upper structural zeros and nonzero diagonal. Returns solution and fresh Euclidean residual; no solution-error bound without conditioning. |
Householder QR: householder_qr::least_squares | O(mn²); O(mn) | 1<=n<=64, n<=m<=128; unpivoted least squares. Rejects exact-zero encountered pivots, not all numerical rank deficiency; returns primal and normal residuals. |
Gauss–Seidel: gauss_seidel::solve | O((k+1)n²); O(n) | n=1..64, k<=10000, nonzero diagonal; ascending in-place sweep. Fresh residual stopping, budget and stagnation reports; convergence assumptions remain with caller. |
Jacobi: jacobi_iteration::solve | O((k+1)n²); O(n) | n=1..64, k<=10000, nonzero diagonal; simultaneous update from previous vector. Fresh residual stopping and explicit budget/stagnation; SPD alone does not ensure Jacobi convergence. |
Brent minimization: brent_minimize::minimize | O(k+1) callbacks; O(1) | Deterministic strictly unimodal callback assumed, ordered bounded bracket, k<=100000. Safeguarded parabolic/golden steps; absolute bracket-width stopping, budget/stagnation reports. |
Armijo search: armijo_line_search::search | O(k+1) callbacks; O(1) | Caller supplies true value and negative directional derivative at zero. Positive step, contraction and decrease factors in (0,1); sampled sufficient decrease plus strict objective decrease, budget/stagnation reports. |
Box projected gradient: projected_gradient_box::minimize | O((k+1)n²); O(n) | n<=64, k<=100000; exact symmetry and conservative diagonal-dominance PSD admission checked. Clips initial point; residual is projected-step infinity norm, not distance to optimum. |
Lasso coordinate descent: coordinate_descent_lasso::minimize | O((k+1)m*n); O(m+n) | m<=256, n<=64; minimizes half the squared L2 residual plus lambda times the L1 norm, lambda>=0, starts at zero. Cyclic updates and fresh KKT violation; zero columns stay zero, arithmetic/budget/stagnation explicit. |
Frank–Wolfe: frank_wolfe::minimize | O((k+1)n²); O(n) | Unit-simplex quadratic, n<=64; same checked convexity admission as box solver. Initial mass within 64nEPSILON of one; leftmost gradient tie and quadratic line step. Computed dual gap is not a rigorous floating objective bound. |
Barycentric Lagrange: barycentric_lagrange::interpolate | O(n²); fixed 64-value stack | 1..64 sorted nodes in [-1,1], gaps>=1e-8, bounded ordinates; no extrapolation, exact-node shortcut. Real polynomial reproduction does not certify machine accuracy; ill-scaled weights can error. |
Monotone cubic: monotone_cubic::interpolate | O(n); O(1) | 2..64 nodes under the same spacing/domain limits. PCHIP harmonic slopes and endpoint limiters; real shape preservation and affine reproduction, no error bound against an unknown sampled function. |
Bernstein evaluation: bernstein_de_casteljau::evaluate | O(n²); fixed 128-value stack | 1..128 finite bounded controls, t in [0,1]; in-place de Casteljau triangle, exact endpoints. Convex-hull identity holds in the real model; rounding remains separate. |
Gauss–Legendre: gauss_legendre::integrate | O(order) callbacks; O(1) | Fixed orders1..5, finite bounded ordered interval/callback values. Zero interval makes no calls; real degree<=2*order-1 exactness excludes rounded constants and arithmetic. No error estimate. |
Romberg: romberg_integration::integrate | O(2^L+L²); fixed 20-value stack | L<=20 and explicit evaluation budget; nested trapezoids plus Richardson extrapolation. Reports convergence, work/level limits or coordinate stagnation. Diagonal-difference error is heuristic and can miss unsampled structure. |
Bitset subset sum: bitset_subset_sum::reachable | O(n*W); O(W) words | Exact 0/1 reachability for usize values/target; descending word updates prevent item reuse. max_words bounds storage, not total work; checked dimensions and fallible allocation. |
Meet-in-middle knapsack: meet_in_middle_knapsack::max_value | O(n*2^ceil(n/2)); O(2^ceil(n/2)) | Reuses knapsack::Item; exact u128 objective without item witness. Capacity-independent half enumeration and sorted envelope; max_states bounds sum of worst-case half counts, with checked arithmetic/allocation. |
SMAWK: smawk::row_minima | O(rows+cols) callbacks; O(rows+cols) | Deterministic i128 matrix callback must be totally monotone for leftmost minima in every submatrix; premise is not checked. Leftmost ties, callback budget, fallible allocation; zero rows return empty. |
Divide-and-conquer DP: divide_conquer_dp::partition | O(gnlog(n+1)) callbacks; O(n) | Exact u128 cost of g nonempty intervals; caller guarantees nondecreasing leftmost optimal splits in every layer. Checked candidate sums and callback budget; impossible partitions return None. |
Knuth optimal BST: knuth_optimal_bst::min_cost | O(n²); O(n²) | Nonnegative u64 successful-key weights imply monotone roots; root depth one, leftmost ties, exact checked u128 cost. max_cells limits each of two square tables; no unsuccessful-search frequencies. |
Caller premises differ from validation: Cholesky targets SPD systems, stationary convergence needs suitable iteration-matrix properties, and SMAWK/partition monotonicity is assumed. Box and simplex quadratic optimizers conservatively validate a sufficient convexity condition and may reject other valid PSD matrices. Residuals, shape preservation, polynomial identities and heuristic estimates are distinct observations; none supplies a general relative-error percentage.
Family groupants document composition, complements, nonunique reverse fibers and assumptions: numerical linear algebra, optimization methods, approximation and interpolation and dynamic-programming optimization.
Optimization, graphs, numerical methods, algebra and byte transforms
These 25 modules expose bounded deterministic operations with adjacent source/test groupants. Costs below describe the implementation. Space includes working state and returned output, but excludes borrowed inputs. Numerical residuals and refinement differences are not general solution-error or integral-error guarantees.
Notation: k is committed optimizer updates; m × n is matrix shape; V,E are vertices and supplied adjacency entries (or flow edges); F is requested flow; q is callback evaluations; o is decoded output length; t is tokens/codes; r is BPE merges; D=4096 and ell is maximum dictionary phrase length. All modular modules use the fixed prime p=998244353.
| Module | Public API within module | Domain and principal caveat | Time | Space |
|---|---|---|---|---|
barzilai_borwein | minimize_diagonal(D,b,x0,tol,budget) | 1<=n<=256, diagonal [1e-6,1e6], other magnitudes <=1e6, budget <=100000; safeguarded BB1 step, gradient norm reported | O(n(k+1)) | O(n) |
heavy_ball_quadratic | minimize_diagonal(D,b,x0,tol,budget) | Same diagonal domain; Polyak momentum uses actual previous iterate, no one-step stagnation inference | O(n(k+1)) | O(n) |
nesterov_quadratic | minimize_diagonal(D,b,x0,tol,budget) | Same diagonal domain; gradient evaluated at extrapolated point, report evaluated at actual iterate | O(n(k+1)) | O(n) |
proximal_gradient_lasso | minimize(A,b,lambda,tol,budget) | 1<=m<=256,1<=n<=64, finite magnitudes <=1e6, lambda>=0, budget <=100000; nonzero design requires squared Frobenius norm >=1e-12; starts at zero | O(mn(k+1)) | O(n) |
fista_lasso | minimize(A,b,lambda,tol,budget) | Same LASSO domain; two gradient/objective evaluations per update, objective may increase between updates | O(mn(k+1)) | O(n) |
minimum_cost_flow | minimum_cost_flow(V,edges,source,sink,limit) | V<=64,E<=512,F<=1024; distinct valid terminals, u64 capacities/i64 costs; rejects every positive-capacity negative cycle, even disconnected or with limit zero | O((F+1)V(E+V)) | O(V+E) |
maximum_cardinality_search | maximum_cardinality_search(graph) | V<=256,E<=65536, simple undirected; maximum selected-neighbor count, smallest-ID ties; order alone is no chordality certificate | O(V²+E) | O(V²+E) |
k_core | k_core(graph,k) | Same simple-undirected limits; sorted maximal induced minimum-degree-k vertex set, including all vertices for k=0 | O(V²+E) | O(V²+E) |
dominators | dominators(graph,start) | V<=256,E<=65536, valid start; directed loops/duplicates allowed; sorted sets, unreachable rows empty; iterative fixed point | O(V²(V+E)) conservative | O(V²+E) |
transitive_reduction_dag | transitive_reduction_dag(graph) | V<=256,E<=65536; duplicate edges normalize, cycles reject; preserves reachability but may change dominators and shortest paths | O(V³+E) | O(V²) |
neville_interpolation | neville_interpolation(xs,ys,x) | Nonempty matched finite samples, strictly increasing nodes, finite query; extrapolation allowed, no conditioning guarantee | O(n²) per query | O(n) |
newton_divided_differences | NewtonPolynomial::new, coefficients, evaluate | Same sample domain; reusable Newton basis, finite extrapolation allowed | Build O(n²); query O(n); accessor O(1) | O(n) |
natural_cubic_spline | NaturalCubicSpline::new, evaluate | At least two matched finite samples, strictly increasing nodes; zero endpoint second derivatives; queries restricted to closed knot interval | Build O(n); query O(log n) | O(n) |
adaptive_trapezoid | integrate(f,a,b,tol,max_evaluations) | Finite a<b and span, positive finite tolerance, budget >=2; reuses samples, funds complete levels; difference/3 is heuristic | O(q) excluding callback cost | O(1) |
tanh_sinh_quadrature | integrate(f,a,b,tol,max_evaluations) | Same interval/tolerance requirements, budget >=7; fixed transformed window [-3,3], repeats samples; estimator omits truncation tails | O(q) excluding callback cost | O(1) |
fast_fourier_transform | transform(input,inverse), Complex | Nonempty power-of-two n<=65536, finite components of magnitude <=1e100; negative forward phase, inverse divides by n; no relative-error guarantee | O(n log n) | O(n) |
karatsuba_polynomial | multiply(a,b) | Each length <=4096; ascending field coefficients, empty accepted after cap checks; preserves output length/trailing zeros | O(N^log2(3)), padded N | O(N) live |
subset_convolution | convolve(a,b) | Equal nonempty power-of-two lengths 2^d<=4096; exact disjoint-subset convolution, not OR convolution | O((d+1)²2^d) | O((d+1)2^d) |
gaussian_elimination_modular | solve(A,b,variables), Solution | Rows/variables <=128, exact shape; returns particular solution and ordered nullspace basis, or None for inconsistency; empty equations/zero variables supported | O(m(n+1)(min(m,n)+1)+n²) at fixed p | O(m(n+1)+n²) |
baby_step_giant_step | discrete_log(base,target) | Raw u64 operands normalize modulo p; least nonnegative exponent, 0^0=1; None means no exponent; 31596 table entries | O(sqrt(p) log p) | O(sqrt(p)) |
myers_bitvector | distance(pattern,text) | Pattern <=64, text <=65536; global byte Levenshtein distance, not substring or Unicode-character distance | O(pattern.len+text.len+256) | O(1), no allocation |
byte_pair_encoding | Model::train, merges, encode, decode | Bytes/tokens <=65536, merges <=3840; frequency ties lexicographic, replacement left-to-right; decoding requires the exact ordered model | Train O((r+1)n log(n+1)); encode O((r+1)n); decode O(r+t+o+1) | O(n+r); decode O(r+o+1) |
lz77 | encode(input,window,max_match), decode(tokens,max_output) | Input/tokens <=65536, window/match cap 1..4096; greedy longest match, nearest-distance tie; overlapping matches allowed | Encode O(n*window*max_match); decode O(t+o) | O(n) encode; O(o) decode |
lzw | encode(input), decode(codes,max_output) | Input/codes <=65536; byte dictionary freezes at 4096, no clear/end codes or bit packing; accepts valid noncanonical streams | Encode O((n+D)ell log D); decode O(D+t*ell+o) | O(D*ell+n) encode; O(D*ell+o) decode |
patience_diff | diff(old,new), apply(old,edits,max_output) | Diff inputs each <=4096; apply source <=4096, edits <=8192; deterministic byte anchors, valid patch without edit-minimality guarantee | Diff O(N³) conservative, N=old.len+new.len; apply O(old.len+edits.len+o) | Diff O(N²) conservative; apply O(o) |
All optimizer tolerances are finite, positive and absolute. Convergence is checked before budget exhaustion; zero budget evaluates the initial iterate. The LASSO residual is KKT infinity violation, not the quadratic Euclidean gradient norm or coordinate error. Optimizers map checked reserve failures to allocation errors; standard allocations elsewhere may panic/abort.
Decoded byte output is capped at min(max_output,65536) for BPE, LZ77, LZW and patch application. Codec streams may have multiple encodings for the same bytes. Token IDs are not bytes and need an explicit reversible representation before passing through a byte codec.
Interpolation has no hard sample-count cap. Nonfinite checked intermediates return errors. Quadrature budgets count callback calls, require complete levels and preserve call order; callback panic propagates. Interpreting repeated calls as an integral assumes a deterministic integrand. Tanh-sinh may report geometry stagnation before its first complete level; its initial zero value is then a sentinel.
Gaussian complexity includes the augmented right-hand-side column and row processing: zero variables still require O(m) work/storage. Field products normalize inputs before multiplication and fit u64; this exact arithmetic does not extend to FFT rounding. Polynomial/subset/field identities establish no universal floating-point percentage accuracy.
Linear algebra, transforms, structured probability and exact indexes
Each module link below points to its implementation, public contract and algorithm citation; adjacent source/test groupants retain mathematical models and finite evidence. Costs describe the implementation, including validation and reported residuals. Space excludes borrowed inputs and includes outputs.
Notation: n is sample count or square matrix dimension; m is row count; b is an iteration/rotation budget; k is completed Lanczos steps or query-result count as indicated; T is sequence length; d is feature dimension/polynomial degree; V,E count input vertices/edges. All 25 APIs are callback-free.
| Module | Public API within module | Domain/status and principal caveat | Time; space |
|---|---|---|---|
| LU decomposition | factor(A) | Square n=1..64, finite entries of magnitude <=1e100; partial pivoting, earliest maximum tie. Returns L,U,permutation and fresh Frobenius(LU-PA); exact-zero pivots fail, tiny pivots do not certify conditioning. | O(n³); O(n²) |
| Modified Gram–Schmidt | factor(A,tolerance) | 1<=n<=64,n<=m<=128, finite magnitudes <=1e100, absolute tolerance [0,1e100]; one pass, positive diagonal. Column norm at/below tolerance returns its dependent-column index; successful rank is n, not a rank-revealing estimate. | O(mn²); O(mn+n²) |
| Power iteration | solve(A,start,tolerance,max_iterations) | Square n=1..64, finite matrix/start magnitudes <=1e100, nonzero start, tolerance [0,1e100], budget <=4096. Rayleigh value and fresh eigenpair residual; statuses Converged/Budget/Breakdown. A converged start can miss the dominant eigenspace. | O((b+1)n²); O(n) |
| Jacobi eigenvalues | solve(A,tolerance,max_rotations) | Same square/value/tolerance limits, exact symmetry, budget <=4096; unsorted eigenpairs with canonical column signs. Converged/Budget uses fresh Frobenius(AV-VD); also reports orthogonality. Distinct from stationary Jacobi linear iteration. | O((b+1)n³) because all-vector residuals are recomputed; O(n²) |
| Lanczos | tridiagonalize(A,start,tolerance,max_steps) | Square n=1..64, exact symmetry, finite magnitudes <=1e100, nonzero start, beta tolerance [0,1e100]; budget <=4096, capped by n. Two full reorthogonalization passes; Complete/Breakdown/Budget. Zero budget returns an empty projection, not convergence. | O(n²+kn²+nk²), including validation; O(n(k+1)) conservative |
| Discrete cosine transform | transform(input,inverse) | n<=2048, finite abs(x)<=1e50; empty accepted. Orthonormal DCT-II on half-shifted cosine grid; inverse is its transpose. DC scale 1/sqrt(n), other modes sqrt(2/n); no extension. | O(n²); O(n) |
| Haar wavelet | transform(input,inverse) | Power-of-two n=1..65536, finite abs(x)<=1e50; no padding. Full orthonormal packing: coarsest average followed by detail levels, left-minus-right sign. Empty/nondyadic lengths reject. | O(n); O(n) |
| Bluestein FFT | transform(input,inverse) | Arbitrary n=1..16384, complex components finite with magnitude <=1e50. Negative forward phase; positive inverse divides by n. Chirp convolution uses radix-two length M=next_power_of_two(2n-1)<=32768. | O(M log M); O(M) |
| Goertzel | bins(input,indices) | Real unit-grid input, n<=65536, requested-bin count q<=65536, each integer bin <n, finite abs(x)<=1e50. Unnormalized negative-phase DFT, preserving request order/duplicates. Empty input requires empty bins; empty bins still validate input. Endpoint cancellation can magnify roundoff. | O(n+nq+q); O(q) |
| Savitzky–Golay | smooth(input,window,degree) | n<=4096, odd 1<=w<=31, w<=n, d<=6,d<w, finite abs(x)<=1e50. Unit grid; full windows shift inside the data at edges, without padding. Scaled local polynomial fit predicts target coordinate zero. | O(nw(d+1)²); O(n+w(d+1)) |
| Viterbi | viterbi(initial,transition,emissions) | 1..64 states, T<=4096; finite probabilities [0,1], initial/transition sums within 1e-10 of one. Time-major emissions need not sum to one. Returns path/log score or None for impossible evidence; empty sequence has log score zero. Ties choose lowest predecessor/terminal, not globally lexicographically least path. | O((T+1)n²); O(Tn+n) conservative |
| Forward–backward | forward_backward(initial,transition,emissions) | Same HMM dimensions/probability conventions. Log-sum-exp recurrences return normalized posterior rows and log likelihood; impossible sequence returns None, empty sequence returns no rows/log zero. Marginals do not reconstruct the joint path distribution. | O((T+1)n²); O(Tn+n); bounded temporary log-sum-exp vectors |
| Sinkhorn scaling | sinkhorn_scaling(matrix,rows,columns,tolerance,max_iterations) | Dimensions r,c=1..64; strictly positive matrix/marginals in [1e-100,1e100], marginal totals agree within relative 1e-12, positive finite absolute tolerance, budget <=10000. Returns matrix, maximum absolute marginal discrepancy, iteration count and convergence flag; nonpositive/nonfinite iterates error. | O((b+1)rc); O(rc) |
| Weighted covariance | WeightedCovariance::{new,push,merge,weight,mean,covariance} | d=1..64, finite coordinates abs(x)<=1e100, observation weights [0,1e100]; population covariance M2/W, empty moments None. Zero weight is neutral after validation; failed updates are atomic. Floating results depend on grouping. | Push/merge O(d²); weight/mean O(1); covariance O(d²); storage O(d²) |
| Alias method | AliasTable::{new,draw,len,is_empty} | 1..4096 finite nonnegative weights with positive mass; constructor normalizes by maximum then total. Caller supplies a valid column and finite coin in [0,1); no hidden RNG. Distributional interpretation requires appropriately uniform draw coordinates. | Build O(n); draw/accessors O(1); O(n) |
| Blossom matching | maximum_matching(vertices,edges) | V<=512,E<=131072; undirected endpoints validated, loops ignored, duplicates collapsed. Returns symmetric optional mates for a maximum-cardinality matching; deterministic sorted adjacency, empty graph accepted. | O(V³+E log(E+1)); O(V+E) |
| Minimum arborescence | minimum_arborescence(vertices,root,edges) | 1<=V<=512,E<=131072, valid root, directed i64 weights. Returns only minimum outward-spanning objective Option<i128>; None is infeasibility. Loops ignored; limits/root/endpoints checked before contraction. | O(VE+V²); O(V+E) storage |
| Maximum-weight closure | maximum_weight_closure(weights,implications) | V<=512,E<=131072, i64 weights; (u,v) requires v if u selected. Positive-weight sum plus one must fit u64; i64::MIN supported. Returns sorted selected set and i128 weight; no unique/canonical optimal-set promise. | Dinic on V+2 vertices and <=E+V arcs: O((V+2)²(E+V+1)); O(V+E+1) |
| Exact cover | solve(columns,rows,node_budget) | C<=64,R<=4096; distinct valid columns per row; empty rows ignored. Bitmask Algorithm X, minimum-compatible-count column and ascending ties. Every visited state, including success, consumes budget. None requires completed infeasibility search; interrupted search is ResourceExhausted. | Validation O(S+R) for S supplied entries, search O(B(C+1)(R+1)) conservative for B visited states; O((C+1)(R+1)) space |
| Functional graph decomposition | decompose(successor) | n<=1000000, valid successor per vertex. Returns cycles, cycle IDs, original entry coordinates and distances. Cycles start at minimum vertex, follow successors and are ordered by minimum; empty accepted. | O(n); O(n) |
| Treap | Treap::{default,insert,contains,remove,keys} | Up to 4096 unique live i64 keys; explicit u64 priorities, heap ties by key. Duplicate insert preserves priority; removal recycles slots. Caller priorities can force linear height; random-priority expected bounds are not API guarantees. | Search/insert/remove O(height)<=O(n); keys O(n); arena O(maximum live count) |
| Splay tree | SplayTree::{default,insert,access,root,keys} | Up to 4096 unique i64 keys. Access splays match or last visited node on miss; duplicate insertion splays existing key. Root/keys are observations only; no deletion API. | Individual access/insert O(n), amortized O(log(n+1)) with initial potential; root O(1), keys O(n); O(n) storage |
| Interval tree | IntervalTree::{new,overlapping} | Up to 4096 closed i64 intervals, duplicates retained; reversed endpoints reject. Query returns sorted original indices; touching endpoints overlap, without endpoint arithmetic. | Build O(n log(n+1)); query worst O(n+k log(k+1)); resident O(n), query scratch O(log(n+1)+k) |
| KD tree | KdTree::{new,nearest} | Up to 4096 2D points with coordinates [-1000000,1000000]; queries accept any i32 coordinates. Exact squared distance in u64; smallest original index breaks distance ties, duplicates retained; empty returns None. | Repeated-sort build O(n log²(n+1)); worst query O(n); resident O(n), query stack O(log(n+1)) |
| BK tree | BkTree::{new,within} | Up to 4096 byte strings, each/query at most 256 bytes; byte Levenshtein metric, arbitrary usize radius. Duplicates keep original indices; matches return (index,distance) sorted by index. No guaranteed sublinear query. | Worst build O(n²(1+L²)); query O(n(1+L²)+k log(k+1)); resident O(n(L+1)), query scratch O(n+k+L) |
Bluestein reuses the radix-two FFT and its Complex type; Savitzky–Golay reuses Householder least squares. Maximum-weight closure reuses Dinic and max_flow::Edge; BK trees reuse byte Levenshtein. The five linear-algebra modules share checked numeric/allocation helpers hosted in lu_decomposition; the HMM routines expose separate max-plus and log-sum-exp outputs rather than treating paths and marginals as interchangeable.
Citations in the linked sources identify Golub–Van Loan, Björck, von Mises–Pollaczek-Geiringer, Jacobi and Lanczos for linear algebra; Ahmed–Natarajan–Rao, Haar, Bluestein, Goertzel and Savitzky–Golay for transforms/smoothing; Viterbi, Rabiner, Sinkhorn–Knopp, West/Chan–Golub–LeVeque and Walker/Vose for probability/statistics; Edmonds, Chu–Liu, Picard, Knuth and Kahn for combinatorial methods; Seidel–Aragon, Sleator–Tarjan, Cormen et al., Bentley and Burkhard–Keller for indexes. These are identifiable algorithm references, not imported implementations.
Numerical residuals measure the stated reconstruction, eigenpair, orthogonality or marginal discrepancy; they are not universal relative solution-error guarantees. Transform inverse identities also require intermediate coefficients to satisfy the next call's magnitude cap. Local polynomial reproduction does not establish denoising accuracy against an unknown signal. Standard allocations may panic/abort; checked linear-algebra reservations and propagated QR failures have explicit allocation errors.
The supported surrogate caps remain 1%, 2%, 5% and 10%, with an explicit metric/domain/evidence requirement. These modules have no generic accuracy profiles, and profiles above 10% are unsupported. They are not automatically substituted into Mova.
This page in Markdown → https://md.mova.elamur.ai/free/en/docs/algorithms/