EML-NOVA · Standard library

Every function is a graph.

The standard library is NOVA’s working corpus: real functions, written as typed graphs, built on one another with Call, and verified before they ship. People read the diagrams; AIs read the same structure.

functions
554
modules
12
test cases
22,160
verified results
135,547
all passing
554/554
also verified at float32
551/554

Six levels so far. L0 is composed from NOVA’s original primitives. L1 also uses the standard math primitives of Round 13.1: square root, exponential, logarithm, exact maximum and minimum, comparisons and Size. L2 also uses Round 13.2: windows and joins along an axis, positions as values, sorting, running sums and extremes, and Scan — a loop whose body is another function of the library. L3 also uses Round 13.3’s integer indices — Cast turns a computed position into an index, exactly or not at all; Gather and GatherAlong read at indices; ScatterAdd writes at them — and Round 13.4’s While, a loop that runs until a condition says stop, within a stated number of steps. Round 13.5 completes L3 with dense linear algebra: solving linear systems, the Cholesky factorization, and the eigenvalues and eigenvectors of symmetric matrices. L4 adds Round 13.6’s orthogonal factorizations (QR and the singular value decomposition), Round 13.7’s floor division and remainder — calendars, hashes, bins, the greatest common divisor, reproducible random numbers — and Round 13.8’s Fourier transform, on complex vectors kept as two real rows. L5 begins with Round 13.9’s special functions: erf and erfc, log-gamma, expm1 and log1p — the normal distribution, count models and stable losses — and continues with Round 13.10’s distribution functions: the normal quantile and the regularized incomplete gamma and beta functions, for p-values, quantiles and normal random draws. Round 14.1 adds their inverses: the chi-square, gamma, beta and t quantiles. Round 14.2 makes the gamma and beta functions and their inverses differentiable in their shape parameters too, which is what fitting a distribution needs. Round 14.3 adds upper tails that keep their accuracy, so p-values far below 10⁻¹⁶ no longer round to 0, and the Poisson and binomial quantiles. Round 14.4 adds bitwise integer operations and Philox4x32-10, a counter-based random number generator of modern statistical strength: every element draws its own number from its own counter, the same on every backend. Hypothesis tests follow: z, one-sample and Welch t, correlation and chi-square goodness of fit, whose p-values keep their digits far below 10⁻¹⁶, and the rank-based Spearman and Mann–Whitney tests, each stated as the approximation it is. An eighth module, optim, is where a graph learns: verified update steps (SGD, momentum, Adam) and logistic regression trained inside one Scan, which, on data where an optimum exists, reaches the optimum Newton’s method finds at 60 digits to the last bits. Round 14.5 lets an entry take a function: a template names it $f, and a caller binds it, as in rk4[f=…] or minimize_adam[df=…]; NOVA specializes the template into an ordinary graph, static, typed and hashable; each template in the library is verified through a witness binding. Round 14.6 lets the binding be a derivative: minimize_adam[df=@grad[f=loss,wrt=w]] trains a model on its loss alone, with NOVA deriving the gradient by reverse mode. Round 14.10 lets a loop carry several values, each of its own shape and dtype: lstm carries (h, c), kalman_level a mean and a variance, and bezout six integers. Rounds 14.11 to 14.21 add trigonometry; special functions, distributions and tests; quadrature, interpolation and polynomials; root finding; determinants, matrix powers and matrix functions; number theory; combinatorics, interest, recurrences and iteration; finite probability and Markov chains; graphs, automata and rank; linear programming and network flows; boundary-value problems and series. Round 14.22 adds the exact answers that need exhaustive search on small graphs: cliques, colourings, matchings and isomorphism. Rounds 14.23 to 14.28 add three new modules that decide finite structures by complete enumeration: algebra (groups on their Cayley tables, group actions, rings and fields), topology (finite topological spaces, by the full list of their open sets) and sets (relations, functions, logic and finite metrics). Alongside them come finite probability and measures, grammars by CYK, Turing machines, a rank decided exactly by fraction-free elimination, exact elementary checks and slices of analysis (fractions, the mean value theorem on quadratics, Taylor remainders and integrals of polynomials), regular expressions and pushdown runs. Round 14.29 makes the error bounds sharper where Sigmoid and Tanh saturate and for ill-conditioned QR (growing like κ, not κ³), and differentiates softplus and bce_with_logits correctly at 0, with the same values bit for bit; 21 more float32 cases are certified. Round 15.10 makes NOVA’s transcendental primitives — exponential, logarithm, the trigonometric functions, erf, log-gamma and the rest — correctly rounded: each value is the exact one rounded once, the same bits on every machine.

How each function is verified

Three checks, all automatic

  1. 01

    The right function

    In exact arithmetic, the graph must equal an independent reference formula, usually the NumPy library call. Exactly, with rational numbers; to 80 digits where roots, exponentials, logarithms, eigenvalues, singular values, Fourier transforms or special functions appear.

  2. 02

    A guaranteed accuracy

    Every float64 result must lie inside an error bound computed from the graph itself, by running error analysis. The bound holds whatever order NumPy adds in. Where a step is a transcendental primitive — exp, tanh, erf or log-gamma, correctly rounded since NOVA Round 15.10, so within half a unit in the last place — or is handed to a routine — LAPACK for linear algebra, or NOVA’s own normal quantile and incomplete gamma and beta functions — the bound rests on a stated bound for that step’s error. Since NOVA Round 14.7 the same check also runs at float32: each case is rounded to float32, and the bound is computed at u = 2⁻²⁴. Three functions whose stopping rules are written in float64 terms are float64-only, and their pages say why.

  3. 03

    The same answer everywhere

    NOVA’s reference interpreter and its NumPy backend must return bit-identical results.

Before any of this, the signature is proven: NOVA’s shape solver checks every broadcast and every contraction, for every size.

Elementwise

std.elementwise · 83
absL0
(x: f64[n]) → f64[n]

Absolute value, built from Relu. Exact: one of the two terms is always zero.

40exact
squareL0
(x: f64[n]) → f64[n]

Elementwise square.

40exact
cubeL0
(x: f64[n]) → f64[n]

Elementwise cube.

40
lerpL0
(a: f64[n], b: f64[n], t: f64[]) → f64[n]

Linear interpolation from a to b by a scalar t.

40
leaky_reluL0
(x: f64[n], alpha: f64[]) → f64[n]

Leaky ReLU with slope alpha for negative inputs, built from Relu.

40exact
siluL0
(x: f64[n]) → f64[n]

SiLU (also called swish): x times its own sigmoid.

40
gelu_tanhL0
(x: f64[n]) → f64[n]

GELU, tanh approximation, as used in GPT-style networks.

40calls cube
softsignL0
(x: f64[n]) → f64[n]

Softsign: a smooth, bounded alternative to tanh. Calls abs.

40calls abs
clipL1
(x: f64[n], lo: f64[], hi: f64[]) → f64[n]

Clamp every element into [lo, hi] with exact Maximum and Minimum.

40exact
relu6L1
(x: f64[n]) → f64[n]

ReLU capped at 6, as in mobile networks.

40exact
hard_sigmoidL1
(x: f64[n]) → f64[n]

Piecewise-linear sigmoid: relu6(x + 3) / 6. Calls relu6.

40calls relu6
signL1
(x: f64[n]) → f64[n]

Sign of each element (−1, 0 or 1), from two comparison masks. Exact.

40exact
softplusL1
(x: f64[n]) → f64[n]

Softplus in its overflow-free form, as two smooth branches: x + log(1 + e^(−x)) for x ≥ 0 and log(1 + eˣ) for x < 0. Mathematically identical to log(1 + eˣ), which the reference uses.

40
sigmoidL0
(x: f64[n]) → f64[n]

The logistic function σ(x) = 1/(1 + e⁻ˣ), between 0 and 1: the derivative of softplus, and the inverse of the log-odds. NOVA's Sigmoid primitive, which uses eˣ/(1 + eˣ) where e⁻ˣ would overflow.

40exact
eluL1
(x: f64[n], alpha: f64[]) → f64[n]

ELU: the identity for positive inputs, α(eˣ − 1) otherwise.

40
mishL1
(x: f64[n]) → f64[n]

Mish: x · tanh(softplus(x)). Calls softplus.

40calls softplus
wrap_angleL4
(theta: f64[n]) → f64[n]

An angle wrapped into [0, 2π): the remainder after dividing by 2π, which takes the divisor's sign, so negative angles come out positive.

40exact
day_of_weekL4
(days: i64[n]) → i64[n]

The day of the week of a date given as days since 1970-01-01, Monday = 0: that day was a Thursday, so (days + 3) mod 7. Dates before 1970 work too, because the remainder is never negative.

40exact
is_leap_yearL4
(year: i64[n]) → f64[n]

1 for a leap year of the proleptic Gregorian calendar, else 0: divisible by 4, except centuries, except every fourth century.

40exact
days_from_civilL4
(year: i64[n], month: i64[n], day: i64[n]) → i64[n]

Days since 1970-01-01 for a date of the proleptic Gregorian calendar, by Howard Hinnant's algorithm: the year is counted from March, so the leap day falls last, and every division is a floor.

40exact
civil_from_daysL4
(days: i64[n]) → i64[n, 3]

The year, month and day of a date given as days since 1970-01-01, by Howard Hinnant's algorithm: floor divisions by the 400-year era, the year of the era, and a year that starts in March.

40exact
euclid_stepL4
(state: i64[2, n]) → i64[2, n]

One step of Euclid's algorithm on pairs stored as two rows: (a, b) becomes (b, a mod b); a finished pair, with b = 0, stays as it is. gcd repeats it.

40exact
gcd_unfinishedL2
(state: i64[2, n]) → f64[]

Whether any pair still has a non-zero second number, for pairs stored as two rows of non-negative integers: 1 or 0. The condition gcd's loop tests.

40exact
gcdL4
(a: i64[n], b: i64[n]) → i64[n]

The greatest common divisor of each pair of positive integers, by Euclid's algorithm: a While loop of euclid_step until every remainder is zero.

40exactcalls euclid_step, gcd_unfinished
bezout_runningL1
(r0: i64[n], r1: i64[n], s0: i64[n], s1: i64[n], t0: i64[n], t1: i64[n]) → f64[]

Whether the extended Euclidean algorithm still has a pair to reduce: some remainder r1 above 0, as 1 or 0. The condition bezout loops on.

40exact
bezout_stepL4
(r0: i64[n], r1: i64[n], s0: i64[n], s1: i64[n], t0: i64[n], t1: i64[n]) → i64[n], i64[n], i64[n], i64[n], i64[n], i64[n]

One step of the extended Euclidean algorithm on each pair: where r1 is above 0, with q = ⌊r0 / r1⌋, each of the pairs (r0, r1), (s0, s1), (t0, t1) becomes (second, first − q·second); a finished pair stays. The body that bezout runs.

40exact
bezoutL4
(a: i64[n], b: i64[n]) → i64[n], i64[n], i64[n]

The extended Euclidean algorithm on each pair of non-negative integers: their greatest common divisor g and Bézout coefficients x and y with a·x + b·y = g. A While with six int64 states (Round 14.10): the remainders and both coefficient sequences, carried side by side.

40exactcalls bezout_running, bezout_step
complex_multiplyL2
(z: f64[2, n], w: f64[2, n]) → f64[2, n]

The elementwise product of two complex vectors, each stored as a [2, n] array of real parts and imaginary parts: (a + bi)(c + di) = (ac − bd) + (ad + bc)i.

40
log1mexpL5
(x: f64[n]) → f64[n]

log(1 − e^(−x)) for x > 0, accurate everywhere (Mächler's rule): log(−expm1(−x)) below log 2, log1p(−e^(−x)) above. Each naive form loses its digits on one side.

40
sincL5
(x: f64[n]) → f64[n]

The normalized sinc function, sin(πx)/(πx), and 1 at x = 0: the Fourier transform of a box, zero at every other integer. π is computed as arccos(−1), so in exact arithmetic the graph means π itself.

40
gammaL5
(x: f64[n]) → f64[n]

The gamma function Γ(x) for x > 0, as e^(log Γ(x)): (n − 1)! at the positive integers, √π at ½.

40
log_betaL5
(a: f64[n], b: f64[n]) → f64[n]

The logarithm of the beta function, log B(a, b) = log Γ(a) + log Γ(b) − log Γ(a + b), for a, b > 0: finite where B itself underflows.

40
betaL5
(a: f64[n], b: f64[n]) → f64[n]

The beta function B(a, b) = Γ(a)Γ(b)/Γ(a + b) for a, b > 0, as e^(log B). Calls log_beta.

40calls log_beta
erfinvL5
(x: f64[n]) → f64[n]

The inverse error function: the y with erf(y) = x, for −1 < x < 1. Written as −sign(x)·Φ⁻¹((1 − |x|)/2)/√2, so that near ±1, where erfinv grows without bound, the tail 1 − |x| is computed exactly and keeps its digits; for |x| < ½ one Newton step on erf restores the low bits of x that (1 − |x|)/2 rounds away (in exact arithmetic the step is zero).

40
pow_mod_runningL1
(base: i64[n], k: i64[n], acc: i64[n], m: i64[n]) → f64[]

Whether binary exponentiation still has an exponent bit to use: some k above 0, as 1 or 0. The condition pow_mod loops on.

40exact
pow_mod_stepL4
(base: i64[n], k: i64[n], acc: i64[n], m: i64[n]) → i64[n], i64[n], i64[n]

One step of binary exponentiation modulo m: if k is odd, multiply the result by the base; square the base; halve k. Each product is reduced modulo m at once, so nothing grows past m². The body that pow_mod runs.

40exact
pow_modL4
(a: i64[n], k: i64[n], m: i64[n]) → i64[n]

Modular exponentiation aᵏ mod m, elementwise, by binary exponentiation: a While over pow_mod_step, one exponent bit per step. Python's pow(a, k, m). The base is reduced modulo m first, so a may be negative.

40exactcalls pow_mod_running, pow_mod_step
mod_inverseL4
(a: i64[n], m: i64[n]) → i64[n], f64[n]

The inverse of a modulo m, elementwise: the x in 0 … m − 1 with a·x ≡ 1 (mod m), from the Bézout certificate a·x + m·y = 1 that bezout gives. Where gcd(a, m) ≠ 1 there is no inverse: inv is 0 and ok is 0. Python's pow(a, −1, m).

40exactcalls bezout
crt_stepL4
(x: i64[], M: i64[], ri: i64[], mi: i64[]) → i64[], i64[]

Fold one congruence x ≡ rᵢ (mod mᵢ) into a solution x modulo M: x + M·t, with t = (rᵢ − x)·M⁻¹ mod mᵢ, and the modulus becomes M·mᵢ. The inverse comes from bezout. The body crt scans.

40exactcalls bezout
crtL4
(r: i64[n], m: i64[n]) → i64[], i64[]

The Chinese remainder theorem: the x in 0 … M − 1, M = m₁·…·mₙ, with x ≡ rᵢ (mod mᵢ) for every i, for pairwise coprime moduli. A Scan of crt_step over the congruences. The solution is unique modulo M, not as an integer.

40exactcalls crt_step
legendre_symbolL4
(a: i64[n], p: i64[n]) → i64[n]

The Legendre symbol (a/p) for an odd prime p, elementwise: 0 if p divides a, 1 if a is a non-zero square modulo p, and −1 otherwise. Computed by Euler's criterion, a^((p−1)/2) mod p, through pow_mod. The reference instead searches for a square root, so the two routes are independent.

40exactcalls pow_mod
order_runningL4
(k: i64[s], pw: i64[s], a: i64[s], n: i64[s]) → f64[]

Whether some power aᵏ mod n has not yet returned to 1, as 1 or 0. The condition multiplicative_order loops on.

40exact
order_stepL4
(k: i64[s], pw: i64[s], a: i64[s], n: i64[s]) → i64[s], i64[s]

One more power: where aᵏ mod n is not yet 1, multiply it by a modulo n and count one more step. The body multiplicative_order runs.

40exact
multiplicative_orderL4
(a: i64[s], n: i64[s]) → i64[s]

The multiplicative order of a modulo n, elementwise: the smallest k ≥ 1 with aᵏ ≡ 1 (mod n), for gcd(a, n) = 1, found by taking powers until the first return to 1. Where gcd(a, n) ≠ 1 there is no order, and the result is 0.

40exactcalls gcd, order_running, order_step
valuation_runningL4
(m: i64[s], k: i64[s], p: i64[s]) → f64[]

Whether p still divides some m, as 1 or 0. The condition padic_valuation loops on.

40exact
valuation_stepL4
(m: i64[s], k: i64[s], p: i64[s]) → i64[s], i64[s]

Where p divides m, divide it out once and count it. The body padic_valuation runs.

40exact
padic_valuationL4
(a: i64[s], p: i64[s]) → i64[s]

The p-adic valuation vₚ(a), elementwise: the exponent of the highest power of p dividing a ≠ 0, found by dividing p out of |a| until it no longer divides. A negative a is taken by its absolute value. vₚ(0) is infinite, so for a = 0 the loop reaches max_steps and fails rather than return a number.

40exactcalls valuation_running, valuation_step
trial_runningL1
(m: i64[s], d: i64[s], last: i64[s], spf: i64[s], omega: i64[s], sqf: i64[s], phi: i64[s]) → f64[]

Whether trial division still has a candidate divisor d with d² ≤ m somewhere, as 1 or 0. The condition factor_summary loops on.

40exact
trial_stepL4
(m: i64[s], d: i64[s], last: i64[s], spf: i64[s], omega: i64[s], sqf: i64[s], phi: i64[s]) → i64[s], i64[s], i64[s], i64[s], i64[s], i64[s], i64[s]

One step of trial division that records the factorization as it goes. Where d² ≤ m and d divides m, divide d out and record it: the smallest prime factor, the first time; a new distinct prime, with φ multiplied by (1 − 1/d) exactly; or a repeat, which makes the number not squarefree. Where d does not divide, move to the next candidate: 3 after 2, then odd numbers. The body factor_summary runs.

40exact
factor_summaryL4
(n: i64[s]) → i64[s], i64[s], i64[s], i64[s]

Trial division of each n ≥ 1, and four facts read from it: the smallest prime factor (0 for n = 1), ω(n), the number of distinct primes, whether n is squarefree, and Euler's φ(n). A While over trial_step that tries 2 and then odd d up to √n; what remains above 1 at the end is one more prime. The reference factors each n independently.

40exactcalls trial_running, trial_step
smallest_prime_factorL4
(n: i64[s]) → i64[s]

The smallest prime factor of each n ≥ 2, by trial division (factor_summary).

40exactcalls factor_summary
is_primeL4
(n: i64[s]) → f64[s]

Whether each n ≥ 1 is prime, as 1 or 0: its smallest prime factor is n itself. 1 is not prime.

40exactcalls factor_summary
totientL4
(n: i64[s]) → i64[s]

Euler's totient φ(n) for each n ≥ 1: how many k in 1 … n are coprime to n, as n·Π(1 − 1/p) over its prime factors (factor_summary). The reference counts the k directly.

40exactcalls factor_summary
mobiusL4
(n: i64[s]) → i64[s]

The Möbius function μ(n) for each n ≥ 1: 0 if a square divides n, and otherwise (−1)ᵏ for k distinct prime factors (factor_summary). μ(1) = 1.

40exactcalls factor_summary
factorial_mod_runningL1
(k: i64[s], acc: i64[s], n: i64[s], m: i64[s]) → f64[]

Whether some k is still at most n, as 1 or 0. The condition factorial_mod loops on.

40exact
factorial_mod_stepL4
(k: i64[s], acc: i64[s], n: i64[s], m: i64[s]) → i64[s], i64[s]

Where k ≤ n, multiply the running product by k modulo m, and move to k + 1. The body factorial_mod runs.

40exact
factorial_modL4
(n: i64[s], m: i64[s]) → i64[s]

n! mod m, elementwise, multiplying 1 … n and reducing modulo m at every step, so nothing grows past m·n. Wilson's theorem says (p − 1)! ≡ −1 (mod p) exactly when p is prime.

40exactcalls factorial_mod_running, factorial_mod_step
diophantineL4
(a: i64[s], b: i64[s], c: i64[s]) → i64[s], i64[s], f64[s]

A solution of the linear Diophantine equation a·x + b·y = c, for a, b ≥ 0: where d = gcd(a, b) divides c, the particular solution x₀ = x·(c/d), y₀ = y·(c/d) from bezout's certificate, and ok = 1. Every solution is then (x₀ + (b/d)t, y₀ − (a/d)t). Where d does not divide c there is none, and ok = 0. a = b = 0 is solvable only for c = 0, by every pair.

40exactcalls bezout
count_runningL1
(i: i64[s], acc: i64[s], n: i64[s], k: i64[s]) → f64[]

Whether some counter i is still at most k, as 1 or 0. The condition the permutation and binomial loops test.

40exact
falling_stepL1
(i: i64[s], acc: i64[s], n: i64[s], k: i64[s]) → i64[s], i64[s]

One factor of the falling product n(n − 1)…(n − k + 1): where i ≤ k, multiply by n − i + 1 and count. The body permutations runs.

40exact
permutationsL3
(n: i64[s], k: i64[s]) → i64[s]

The number of ordered selections of k from n distinct objects, P(n, k) = n!/(n − k)!, elementwise, as the falling product n(n − 1)…(n − k + 1): a While over falling_step. P(n, 0) = 1, and P(n, k) = 0 for k > n, since a factor n − n is reached.

40exactcalls count_running, falling_step
factorialL3
(n: i64[s]) → i64[s]

n! for each n ≥ 0, as P(n, n) through permutations. 0! = 1. Exact through 18! = 6.4·10¹⁵ < 2⁵³; 21! overflows int64.

40exactcalls permutations
binomial_stepL4
(i: i64[s], acc: i64[s], n: i64[s], k: i64[s]) → i64[s], i64[s]

One factor of the multiplicative formula for C(n, k): where i ≤ k, multiply by n − k + i and divide by i. The division is exact, since the running value is C(n − k + i − 1, i − 1). The body binomial runs.

40exact
binomialL4
(n: i64[s], k: i64[s]) → i64[s]

The binomial coefficient C(n, k) = n!/(k!(n − k)!), elementwise, by the multiplicative formula on the shorter side, min(k, n − k): a While over binomial_step. C(n, 0) = 1, and C(n, k) = 0 for k > n.

40exactcalls binomial_step, count_running
catalanL4
(n: i64[s]) → i64[s]

The Catalan number Cₙ = C(2n, n)/(n + 1), elementwise: 1, 1, 2, 5, 14, 42, … The division is exact. The reference uses the recurrence Cₙ₊₁ = Σ CᵢCₙ₋ᵢ instead.

40exactcalls binomial
ipow_runningL1
(base: f64[n], k: i64[n], acc: f64[n]) → f64[]

Whether binary exponentiation still has an exponent bit to use, as 1 or 0. The condition ipow loops on.

40exact
ipow_stepL4
(base: f64[n], k: i64[n], acc: f64[n]) → f64[n], i64[n], f64[n]

One step of binary exponentiation on floats: if k is odd, multiply the result by the base; square the base; halve k. The body ipow runs.

40exact
ipowL4
(x: f64[n], k: i64[n]) → f64[n]

xᵏ for a real x and an integer k ≥ 0, elementwise, by binary exponentiation: at most 2·log₂k + 1 multiplications. x⁰ = 1, 0⁰ included.

40calls ipow_running, ipow_step
quadratic_rootsL1
(a: f64[n], b: f64[n], c: f64[n]) → f64[n], f64[n], f64[n]

The roots of a·x² + b·x + c = 0, a ≠ 0, elementwise, in the form that avoids cancellation: q = −(b + sign(b)·√D)/2 with D = b² − 4ac, then x₁ = q/a and x₂ = c/q. For D < 0 the roots are re ± i·im, with re₁ = re₂ = −b/(2a) and im = √(−D)/|2a|; for D ≥ 0, im = 0. The naive (−b ± √D)/(2a) loses the smaller root to cancellation when b² ≫ |4ac|.

40
complex_absL2
(z: f64[2, n]) → f64[n]

The modulus |z| = √(a² + b²) of each element of a complex vector stored as a [2, n] array of real and imaginary parts.

40
complex_conjL2
(z: f64[2, n]) → f64[2, n]

The conjugate a − bi of each element of a complex vector stored as a [2, n] array. z·z̄ = |z|², a real number.

40exact
compound_balanceL5
(B0: f64[m], i: f64[m], n: f64[m]) → f64[m]

The balance after n periods of compound interest at rate i per period, with no deposits, withdrawals or fees: B₀(1 + i)ⁿ, computed as B₀·exp(n·log1p(i)) so that a small rate keeps its digits. n may be fractional.

40
present_valueL5
(F: f64[m], i: f64[m], n: f64[m]) → f64[m]

The present value of an amount F due n periods ahead, at rate i per period: F/(1 + i)ⁿ, computed as F·exp(−n·log1p(i)). It inverts compound_balance.

40
poly_derivative_kL3
(c: f64[n], k: i64[]) → f64[n]

The k-th derivative of a polynomial, coefficients highest degree first and the length kept: each coefficient of xᵈ is multiplied by the falling factorial d(d − 1)…(d − k + 1) and moved k places toward the constant term, and the k leading places become 0. Past the degree the derivative is 0. k = 1 is poly_derivative with a leading 0.

40exactcalls permutations
fraction_equalL3
(p: i64[n], q: i64[n], r: i64[n], s: i64[n]) → f64[n]

Whether the fractions p/q and r/s (integers, q and s nonzero) are equal, as 1 or 0: ps = rq, exactly, without dividing. The same test decides a proportion a : b = c : d, ad = bc.

40exact
fraction_normalizeL4
(p: i64[n], q: i64[n]) → i64[n], i64[n]

The reduced form of the fraction p/q (q ≠ 0): numerator and denominator divided by gcd(|p|, |q|), with the denominator made positive. It changes the representation and not the value; 0/q becomes 0/1.

40exactcalls gcd
approximation_errorL1
(a: f64[n], x: f64[n], tol: f64[]) → f64[n], f64[n], f64[n], f64[n]

The errors of an approximation a to a reference value x: the absolute error |a − x|; the relative error |a − x|/|x|, defined only when x ≠ 0 (has_rel says whether it is, and rel is 0 otherwise); and whether |a − x| ≤ τ for the tolerance τ ≥ 0, as 1 or 0. Truncation, rounding and data error are different sources and are not interchangeable.

40
dimension_opsL1
(u: f64[3], v: f64[3], k: f64[]) → f64[3], f64[3], f64[3], f64[]

Dimensional analysis with the base dimensions L, M and T, each quantity's dimension an exponent vector (a, b, c) for L^a M^b T^c: the dimension of a product (exponents add), of a quotient (they subtract), of the k-th power (they scale by k), and whether u and v have the same dimension, which an equality or a sum of the two quantities needs, as 1 or 0. Consistent dimensions are necessary for a physical equation, not sufficient.

40exact
piecewise_limitsL1
(lm: f64[], lb: f64[], rm: f64[], rb: f64[], a: f64[], V: f64[]) → f64[], f64[], f64[], f64[]

Limits and continuity at a for the function equal to lm·x + lb left of a, to rm·x + rb right of a, and to V at a itself: the left limit lm·a + lb, the right limit rm·a + rb, whether the two-sided limit exists (they agree), and whether the function is continuous at a (both equal V), each decided exactly for exact inputs. The limit does not need V; continuity does.

40exact
affine_lineL1
(x1: f64[], y1: f64[], x2: f64[], y2: f64[]) → f64[], f64[], f64[]

The affine function f(x) = m·x + b through two points (x₁, y₁) and (x₂, y₂): whether it is defined (x₁ ≠ x₂, as 1 or 0), its slope m = (y₂ − y₁)/(x₂ − x₁), and its intercept b (both 0 when undefined). With m = 0 it is constant; it is linear in the sense of linear algebra only when b = 0.

40
solution_setL1
(lhs: f64[n], rhs: f64[n], defined: f64[n]) → f64[n]

The solution set of an equation L(x) = R(x) over a finite domain, from the values of both sides on every candidate x and whether both sides are defined there: x is a solution exactly when both sides are defined and their values are equal.

40exact
mvt_quadraticL0
(A: f64[], B: f64[], C: f64[], a: f64[], b: f64[]) → f64[], f64[], f64[]

The mean value theorem for f(t) = A·t² + B·t + C on [a, b], a < b: the secant slope (f(b) − f(a))/(b − a), the midpoint c = (a + b)/2, which lies strictly inside, and f′(c) = 2A·c + B, which equals the secant slope: for a quadratic the midpoint is always a witness. When A = 0 every point of (a, b) is one; the witness need not be unique.

40exact
power_tail_integralL1
(scale: f64[], p: f64[], lower: f64[]) → f64[], f64[]

The improper integral ∫_lower^∞ scale/x^p dx for lower > 0, defined as the limit of the integrals up to b as b → ∞: it converges exactly when p > 1, to scale·lower^(1 − p)/(p − 1) (0 is returned when it diverges). Integrals up to finitely many cut-offs, however stable they look, do not show convergence.

40

Linear algebra

std.linalg · 111
dotL0
(x: f64[n], y: f64[n]) → f64[]

Inner product of two vectors.

40
norm_sqL0
(x: f64[n]) → f64[]

Squared Euclidean norm. Calls dot.

40calls dot
matvecL0
(A: f64[m, n], x: f64[n]) → f64[m]

Matrix times vector.

40
vecmatL0
(x: f64[m], A: f64[m, n]) → f64[n]

Row vector times matrix.

40
outerL0
(x: f64[m], y: f64[n]) → f64[m, n]

Outer product: every product xᵢ·yⱼ, by broadcasting. Exact up to one rounding per entry.

40exact
gramL0
(X: f64[m, n]) → f64[n, n]

Gram matrix of the columns of X.

40
bilinearL0
(x: f64[m], A: f64[m, n], y: f64[n]) → f64[]

Bilinear form xᵀ·A·y. Calls matvec, then dot.

40calls dot, matvec
axpbyL0
(a: f64[], x: f64[n], b: f64[], y: f64[n]) → f64[n]

Linear combination of two vectors with scalar weights.

40
projL0
(x: f64[n], u: f64[n]) → f64[n]

Orthogonal projection of x onto the line spanned by u. Calls dot twice.

40calls dot
rejectL0
(x: f64[n], u: f64[n]) → f64[n]

The part of x orthogonal to u: x minus its projection. Calls proj.

40calls proj
frobenius_sqL0
(A: f64[m, n]) → f64[]

Squared Frobenius norm: the sum of every squared entry.

40
normL1
(x: f64[n]) → f64[]

Euclidean norm. Calls norm_sq.

40calls norm_sq
normalizeL1
(x: f64[n]) → f64[n]

Scale a non-zero vector to unit length. Calls norm.

40calls norm
cosine_similarityL1
(x: f64[n], y: f64[n]) → f64[]

Cosine of the angle between two non-zero vectors. Calls dot and norm.

40calls dot, norm
frobeniusL1
(A: f64[m, n]) → f64[]

Frobenius norm of a matrix. Calls frobenius_sq.

40calls frobenius_sq
jacobi_stepL0
(x: f64[k], R: f64[k, k], b: f64[k], d: f64[k]) → f64[k]

One Jacobi step for A·x = b, with A split into its diagonal d and the rest R: solve each row for its own unknown, using the others' current values. The body that jacobi_solve runs.

40
residual_unconvergedL1
(x: f64[k], R: f64[k, k], b: f64[k], d: f64[k]) → f64[]

Whether x still misses A·x = b, with A given as its off-diagonal part R and diagonal d: ‖b − R·x − d⊙x‖² above 10⁻²⁰·‖b‖² (a relative residual of 10⁻¹⁰), as 1 or 0. The condition jacobi_solve loops on.

40exact
jacobi_solveL3
(A: f64[k, k], b: f64[k]) → f64[k]

Solve A·x = b by Jacobi iteration for a diagonally dominant A, from x = 0 until the relative residual is below 10⁻¹⁰. The diagonal comes from an Iota mask; the loop is a While.

40calls jacobi_step, residual_unconverged
solveL3
(A: f64[k, k], b: f64[k]) → f64[k]

The solution of A·x = b, by Gaussian elimination with partial pivoting (the Solve primitive).

40
inverseL3
(A: f64[k, k]) → f64[k, k]

The inverse of A: Solve against the identity, which is built from two Iotas.

40
choleskyL3
(A: f64[k, k]) → f64[k, k]

The Cholesky factor of a symmetric positive-definite A: the lower-triangular L with L·Lᵀ = A.

40
cholesky_solveL3
(A: f64[k, k], b: f64[k]) → f64[k]

Solve A·x = b for a symmetric positive-definite A the way it is done in practice: factor A = L·Lᵀ, then one forward and one back substitution.

40
logdet_spdL3
(A: f64[k, k]) → f64[]

The log-determinant of a symmetric positive-definite A, from its Cholesky factor: twice the sum of the logs of L's diagonal. No determinant is ever formed, so nothing overflows.

40
eigvalshL3
(A: f64[k, k]) → f64[k]

The eigenvalues of a symmetric matrix, ascending.

40
eigh_vectorsL3
(A: f64[k, k]) → f64[k, k]

The unit eigenvectors of a symmetric matrix, as columns in ascending order of eigenvalue, each signed so its largest component is positive.

40
ridgeL3
(X: f64[n, p], y: f64[n], lam: f64[]) → f64[p]

Ridge regression: the coefficients β minimizing ‖X·β − y‖² + λ‖β‖², from the regularized normal equations. λ > 0 keeps them solvable for any X.

40
qr_qL4
(A: f64[n+k, n]) → f64[n+k, n]

The orthonormal factor Q of A = Q·R, for a tall matrix of full column rank: its columns are an orthonormal basis of A's column space.

40
qr_rL4
(A: f64[n+k, n]) → f64[n, n]

The triangular factor R of A = Q·R, upper triangular with a positive diagonal.

40
lstsqL4
(A: f64[n+k, n], b: f64[n+k]) → f64[n]

Least squares: the x minimizing ‖A·x − b‖ for a tall A of full column rank, through QR: R·x = Qᵀ·b. Unlike the normal equations, it does not square A's condition number.

40
projectorL4
(A: f64[n+k, n]) → f64[n+k, n+k]

The orthogonal projection onto A's column space, Q·Qᵀ from the QR factorization.

40
svdvalsL4
(A: f64[n+k, n]) → f64[n]

The singular values of A, largest first.

40
norm2L4
(A: f64[n+k, n]) → f64[]

The spectral norm of A: its largest singular value, the most A can stretch a unit vector.

40
cond2L4
(A: f64[n+k, n]) → f64[]

The condition number of A in the 2-norm, largest over smallest singular value: how much A can amplify a relative error.

40
nuclear_normL4
(A: f64[n+k, n]) → f64[]

The nuclear norm of A: the sum of its singular values, the convex stand-in for rank in low-rank recovery.

40
pinvL4
(A: f64[n+k, n]) → f64[n, n+k]

The Moore–Penrose pseudo-inverse of a tall A of full column rank, from its SVD: V·diag(1/σ)·Uᵀ. It maps b to the least-squares solution.

40
polarL4
(A: f64[k, k]) → f64[k, k]

The orthogonal factor of the polar decomposition A = W·H: the orthogonal matrix nearest to A, U·Vᵀ from the SVD.

40
rank1_approxL4
(A: f64[n+k, n]) → f64[n+k, n]

The best rank-1 approximation of A (Eckart–Young): σ₁·u₁·v₁ᵀ, from the leading singular triplet.

40
vandermonde_stepL0
(v: f64[m], k: f64[], x: f64[m]) → f64[m]

One more power of x: v ← v·x, elementwise. The body that vandermonde scans; it does not read its sequence element, only counts the steps.

40exact
vandermondeL2
(x: f64[m], k: f64[p]) → f64[m, p]

The Vandermonde matrix with decreasing powers, Vᵢⱼ = xᵢ^(p−1−j), p the length of k (only its length is read): V·c evaluates the polynomial c, highest degree first, at every x. NumPy's np.vander(x, p). Each power is the previous one times x, by a reverse Scan of vandermonde_step.

40calls vandermonde_step
poly_fitL4
(x: f64[p+r], y: f64[p+r], k: f64[p]) → f64[p]

The least-squares polynomial of degree p − 1 through the points (xᵢ, yᵢ), p the length of k (only its length is read), coefficients highest degree first. NumPy's np.polyfit: the columns of the Vandermonde matrix are scaled to unit norm, the scaled system is solved by QR (lstsq), and the scaling is undone. Scaling does not change the solution, only the conditioning.

40calls lstsq, vandermonde
traceL2
(A: f64[k, k]) → f64[]

The trace of a square matrix: the sum of its diagonal, which is also the sum of its eigenvalues.

40
lu_det_stepL3
(U: f64[n, n], d: f64[], k: f64[]) → f64[n, n], f64[]

One step of Gaussian elimination with partial pivoting, on column k: bring the row at or below k with the largest |U[i, k]| to row k, subtract multiples of it from the rows below, and multiply the running determinant d by the pivot, and by −1 for a swap. Columns and rows are taken by Gather, which is exact, so a choice between equal candidates is certain. The body that det scans.

40
detL3
(A: f64[n, n]) → f64[]

The determinant of a square matrix, by Gaussian elimination with partial pivoting: the product of the pivots, with a sign for each row swap. A Scan of lu_det_step over the columns, carrying the matrix and the determinant so far. The reference is Bareiss's fraction-free elimination, in exact arithmetic.

40calls lu_det_step
matpow_stepL0
(Mt: f64[n, n], t: f64[], A: f64[n, n]) → f64[n, n]

One more factor of A: M ← M·A. The body that matrix_power scans; it does not read its sequence element, only counts the steps.

40
matrix_powerL2
(A: f64[n, n], k: f64[p]) → f64[n, n]

The matrix power Aᵖ, p the length of k (only its length is read), by p − 1 multiplications after the first: a Scan of matpow_step from the identity. NumPy's np.linalg.matrix_power(A, p).

40calls matpow_step
crossL2
(u: f64[n, 3], v: f64[n, 3]) → f64[n, 3]

The cross product of 3-vectors, row by row: u × v, perpendicular to both, with length |u||v| sin θ. NumPy's np.cross.

40
sym_applyL3
(A: f64[n, n]) → f64[n, n]

A function of a symmetric matrix, f(A) = V·f(Λ)·Vᵀ: f applied to the eigenvalues, the eigenvectors kept. A template over f, verified through f = square, where f(A) is A·A.

40
expm_symL3
(A: f64[n, n]) → f64[n, n]

The matrix exponential of a symmetric matrix, V·e^Λ·Vᵀ. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's expm at 100 digits, which does not diagonalize.

40
sqrtm_spdL3
(A: f64[n, n]) → f64[n, n]

The principal square root of a symmetric positive-definite matrix, V·√Λ·Vᵀ: the symmetric positive-definite S with S·S = A. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's sqrtm at 100 digits, which does not diagonalize.

40
logm_spdL3
(A: f64[n, n]) → f64[n, n]

The principal logarithm of a symmetric positive-definite matrix, V·log Λ·Vᵀ: the symmetric L with e^L = A. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's logm at 100 digits, which does not diagonalize.

40
eig2L2
(M: f64[2, 2]) → f64[], f64[], f64[]

The eigenvalues of a real 2×2 matrix, symmetric or not: the roots of λ² − tr(M)·λ + det(M) = 0, through quadratic_roots. A complex pair is λ ± i·imag, and imag = 0 for real eigenvalues.

40calls quadratic_roots
reach_stepL1
(R: f64[n, n], t: f64[], A: f64[n, n]) → f64[n, n]

One more edge of reachability: R ← min(1, R + R·A), so R picks up every vertex one step further along an edge. The body reachability scans; it does not read its sequence element.

40exact
reachabilityL2
(A: f64[n, n]) → f64[n, n]

Which vertices each vertex can reach in a finite directed graph, given as a 0/1 adjacency matrix: Rᵢⱼ = 1 when there is a path from i to j, of any length including 0. A Scan of reach_step, n steps from the identity. The reference runs a breadth-first search from every vertex.

40exactcalls reach_step
component_labelsL2
(A: f64[n, n]) → f64[n]

The connected components of a finite undirected graph (a symmetric 0/1 adjacency matrix): each vertex is labelled by the smallest vertex it can reach, so two vertices share a label exactly when a path joins them. An isolated vertex is a component of its own.

40exactcalls reachability
component_countL2
(A: f64[n, n]) → f64[]

The number of connected components of a finite undirected graph: the vertices that are their own label.

40exactcalls component_labels
walk_checkL3
(A: f64[n, n], w: i64[L]) → f64[], f64[], f64[]

Whether a given sequence of vertices w₀ … w_k of a finite undirected simple graph is a walk, as 1 or 0: every two consecutive vertices are adjacent, so vertices and edges may repeat; whether it is a simple path, a walk with no vertex twice; and its length k, the number of edges. A single vertex is a simple path of length 0. Whether some path joins two vertices is reachability's question, not this one.

40exact
is_treeL2
(A: f64[n, n]) → f64[]

Whether a finite undirected simple graph is a tree, as 1 or 0: connected, with exactly n − 1 edges. Connected with n − 1 edges is a complete certificate; n − 1 edges alone is not.

40exactcalls component_count
is_bipartiteL2
(A: f64[n, n]) → f64[]

Whether a finite undirected graph is bipartite, as 1 or 0: it has no closed walk of odd length, which is tr(Aᵏ) = 0 for every odd k ≤ n. The odd traces are read off without a parity test, as (tr(Aᵏ) − tr((−A)ᵏ))/2. The reference two-colours the graph by breadth-first search instead.

40exactcalls matpow_step
eulerian_trail_existsL4
(A: f64[n, n]) → f64[], f64[]

Whether a finite undirected simple graph has an Euler trail (a walk using every edge once) and an Euler circuit (one that ends where it started), as 1 or 0 each. Euler's criterion: every vertex with an edge lies in one component, and 0 or 2 vertices have odd degree (0 for a circuit). Isolated vertices do not matter, and a graph with no edges has the empty circuit.

40exactcalls component_labels
topo_stepL3
(indeg: f64[n], removed: f64[n], ok: f64[], pick: f64[], t: f64[], A: f64[n, n]) → f64[n], f64[n], f64[], f64[]

One step of Kahn's algorithm: take the smallest vertex with no incoming edge left among those not yet taken, remove its outgoing edges from the in-degrees, and record it. If none is left, the graph has a cycle and ok becomes 0. The body topological_order scans.

40exact
topological_orderL3
(A: f64[n, n]) → f64[n], f64[]

A topological order of a finite directed graph by Kahn's algorithm, always taking the smallest available source, so the order is the lexicographically first one. dag is 1 when every vertex was taken, which is exactly when the graph has no cycle. A Scan of topo_step, n steps.

40exactcalls topo_step
prim_stepL3
(dist: f64[n], intree: f64[n], total: f64[], t: f64[], W: f64[n, n]) → f64[n], f64[n], f64[]

One step of Prim's algorithm: bring in the vertex outside the tree nearest to it, the smallest on a tie, add that distance to the total, and lower every distance to the new vertex's edges. Once every vertex is in, the step changes nothing. The body mst_prim scans.

40exact
mst_primL3
(W: f64[n, n]) → f64[]

The weight of a minimum spanning tree of a complete undirected graph with positive edge weights W, by Prim's algorithm from vertex 0: a Scan of prim_step, n steps. The reference is Kruskal's algorithm with union-find, a route independent of Prim's. On ties the tree may differ, but its weight is the same.

40calls prim_step
matrix_rankL4
(A: f64[n+k, n], rtol: f64[]) → f64[]

The numerical rank of a matrix with at least as many rows as columns (transpose a wide one first): how many singular values exceed rtol times the largest. NumPy's np.linalg.matrix_rank with tol = rtol·σ₁. For a rank-deficient matrix stored in floating point the exact rank is usually full, with tiny singular values; the tolerance is what makes the question answerable.

40exact
bfs_stepL2
(visited: f64[n], parent: f64[n], t: f64[], open: f64[n, n]) → f64[n], f64[n]

One layer of breadth-first search on a 0/1 matrix of open edges: every unvisited vertex with an edge from a visited one is visited, with the smallest such vertex as its parent. The body residual_bfs scans; it does not read its sequence element.

40exact
residual_bfsL2
(R: f64[n, n]) → f64[n], f64[n]

Breadth-first search from vertex 0 along the edges with positive residual capacity R: which vertices are reached, and each one's parent on a shortest path. A Scan of bfs_step, n layers.

40exactcalls bfs_step
path_stepL3
(v: f64[], bot: f64[], done: f64[], Pm: f64[n, n], t: f64[], parent: f64[n], R: f64[n, n]) → f64[], f64[], f64[], f64[n, n]

One edge of the walk back from the sink along BFS parents: take the edge (parent(v), v), lower the bottleneck to its residual capacity, mark it, and move to the parent; at the source, stop. The body augment scans.

40exact
augmentL3
(F: f64[n, n], C: f64[n, n]) → f64[n, n]

One Edmonds–Karp augmentation of a net flow F, skew-symmetric: breadth-first search in the residual network C − F, then push the bottleneck along the shortest path found, adding it forward and subtracting it backward. The body max_flow loops on.

40exactcalls path_step, residual_bfs
augmentableL2
(F: f64[n, n], C: f64[n, n]) → f64[]

Whether the sink n − 1 is reachable from the source 0 in the residual network C − F, as 1 or 0: an augmenting path exists. The condition max_flow loops on.

40exactcalls residual_bfs
max_flowL3
(C: f64[n, n]) → f64[], f64[n, n], f64[n]

The maximum flow from vertex 0 to vertex n − 1 in a network with capacities C, by Edmonds–Karp: a While over augment until no augmenting path is left. Returns the value, the flow on each edge, and the source side of a minimum cut, the vertices still reachable in the final residual network. By the max-flow min-cut theorem the cut's capacity equals the value. The reference is Ford–Fulkerson with depth-first paths, a different route to the same value and cut.

40exactcalls augment, augmentable, residual_bfs
cut_capacityL0
(C: f64[n, n], S: f64[n]) → f64[]

The capacity of the cut with source side S (a 0/1 vector): the total capacity of the edges from S to its complement. Edges back into S do not count. Every feasible flow's value is at most every cut's capacity.

40exactcalls dot, matvec
flow_checkL2
(C: f64[n, n], f: f64[n, n]) → f64[], f64[], f64[]

Whether f is a feasible flow in the network with capacities C, from vertex 0 to vertex n − 1, as 1 or 0: 0 ≤ f ≤ C on every edge, and inflow equals outflow at every inner vertex. Also its value twice, as the source's net outflow and as the sink's net inflow; for a feasible flow the two are equal.

40exact
clique_openL1
(c: f64[], best: f64[], count: f64[], wit: f64[n], A: f64[n, n], pow2: f64[n], total: f64[]) → f64[]

Whether the subset counter c has not yet passed every subset, c < 2ⁿ, as 1 or 0. The condition max_clique loops on.

40exact
clique_stepL4
(c: f64[], best: f64[], count: f64[], wit: f64[n], A: f64[n, n], pow2: f64[n], total: f64[]) → f64[], f64[], f64[], f64[n]

Test one vertex subset, the bits of c: it is a clique when every pair in it is adjacent, which is bitsᵀ·A·bits = k(k − 1) for k vertices. Keep the largest clique found so far, the first of its size in counter order, and count the cliques of that size. The body max_clique runs.

40exactcalls dot, vecmat
max_cliqueL4
(A: f64[n, n]) → f64[], f64[n], f64[]

The clique number ω(G) of a finite undirected simple graph, a maximum clique as a 0/1 vector (the first in counter order), and the number of maximum cliques: every vertex subset is tested, 2ⁿ of them, in a While over clique_step. A maximal clique (one no vertex can join) need not be maximum; only the full search shows that none is larger. ω(G) ≤ χ(G), and the two can differ.

40exactcalls clique_open, clique_step, growth_step
max_independent_setL4
(A: f64[n, n]) → f64[], f64[n], f64[]

The independence number α(G), a maximum independent set (no two of its vertices adjacent), and the number of maximum independent sets, as the maximum cliques of the complement graph.

40exactcalls max_clique
min_vertex_coverL4
(A: f64[n, n]) → f64[], f64[n], f64[]

The size τ(G) of a minimum vertex cover (a set of vertices touching every edge), one such cover, and the number of minimum covers: the complements of the maximum independent sets, so τ(G) = n − α(G), and the minimizers correspond one to one. A smaller cover than a given one is a witness that the given one is not minimum. An inclusion-minimal cover, from which no vertex can be dropped, need not be minimum.

40exactcalls max_independent_set
is_vertex_coverL1
(A: f64[n, n], C: f64[n]) → f64[]

Whether a set of vertices C (a 0/1 vector) covers every edge of a finite undirected simple graph, as 1 or 0: an edge with neither end in C is a counterexample. The empty set covers a graph with no edges, and a superset of a cover is a cover.

40exactcalls dot, vecmat
is_proper_coloringL1
(A: f64[n, n], colors: f64[n]) → f64[]

Whether a colouring of the vertices is proper, as 1 or 0: no edge joins two vertices of the same colour. Vertices that are not adjacent may share a colour. A proper colouring with k colours shows χ(G) ≤ k, and only that.

40exact
color_runningL1
(p: f64[], col: f64[n], A: f64[n, n], k: f64[]) → f64[]

Whether the colouring search is still running: 0 ≤ p < n, as 1 or 0. It ends with p = n when a colouring is complete, and with p = −1 when none exists. The condition k_colorable loops on.

40exact
color_stepL3
(p: f64[], col: f64[n], A: f64[n, n], k: f64[]) → f64[], f64[n]

One move of a backtracking search for a proper colouring with k colours: give vertex p its next colour; if it runs past k (past 1 for vertex 0, since colours are interchangeable), clear it and step back; if it clashes with an earlier neighbour, try the next colour; otherwise go on to vertex p + 1. The body k_colorable runs.

40exact
k_colorableL3
(A: f64[n, n], k: f64[]) → f64[], f64[n]

Whether a finite undirected simple graph has a proper colouring with k colours, as 1 or 0, and the first one in the search order (colours 1 … k), by backtracking: a While over color_step. A failure is a complete search, and so a proof that χ(G) > k.

40exactcalls color_running, color_step
chromatic_stepL3
(k: f64[], found: f64[], col: f64[n], A: f64[n, n]) → f64[], f64[], f64[n]

Try one more colour: k ← k + 1 and run k_colorable. The body chromatic_number runs.

40exactcalls k_colorable
chromatic_openL0
(k: f64[], found: f64[], col: f64[n], A: f64[n, n]) → f64[]

Whether no colouring has been found yet, as 1 or 0. The condition chromatic_number loops on.

40exact
chromatic_numberL3
(A: f64[n, n]) → f64[], f64[n]

The chromatic number χ(G) of a finite undirected simple graph with at least one vertex, and a proper colouring with χ(G) colours: k_colorable for k = 1, 2, …, until one succeeds. Each failure is a complete search, so the answer is exact; a greedy colouring is only an upper bound. A graph with no edges has χ = 1.

40exactcalls chromatic_open, chromatic_step
is_matchingL1
(A: f64[n, n], M: f64[n, n]) → f64[], f64[]

Whether a symmetric 0/1 selection of edges M is a matching of the graph A, as 1 or 0: every selected edge is an edge of A, and no vertex meets two of them. Also its size. A maximal matching, to which no edge can be added, need not be maximum.

40exact
tutte_stepL4
(c: f64[], best: f64[], U: f64[n], A: f64[n, n], pow2: f64[n], total: f64[]) → f64[], f64[], f64[n]

One term of the Tutte–Berge formula: for the vertex set U given by the bits of c, (n + |U| − odd(G − U))/2, where odd counts the components of G − U with an odd number of vertices. Keep the smallest so far, and the first U that gives it. The body of max_matching's first loop.

40exactcalls component_labels
tutte_openL1
(c: f64[], best: f64[], U: f64[n], A: f64[n, n], pow2: f64[n], total: f64[]) → f64[]

Whether the subset counter c is still below 2ⁿ, as 1 or 0. The condition of max_matching's first loop.

40exact
matching_runningL1
(p: f64[], ch: f64[n], A: f64[n, n], nu: f64[]) → f64[]

Whether the matching search is still running: 0 ≤ p < n, as 1 or 0. The condition of max_matching's second loop.

40exact
matching_stepL3
(p: f64[], ch: f64[n], A: f64[n, n], nu: f64[]) → f64[], f64[n]

One move of a backtracking search for a matching of ν edges: vertex p takes its next choice, a later free neighbour as its partner or, last, no partner of its own. A vertex an earlier one took has only that last choice. Leaving p unmatched is allowed only while at most n − 2ν vertices stay unmatched. Past the last choice, clear p and step back; on a choice not allowed, try the next; otherwise go on to p + 1. The body of max_matching's second loop.

40exact
max_matchingL4
(A: f64[n, n]) → f64[], f64[n, n], f64[n]

A maximum matching of a finite undirected simple graph with its two certificates. First ν(G) by the Tutte–Berge formula, ν(G) = min over U of (n + |U| − odd(G − U))/2, a While over tutte_step through all 2ⁿ vertex sets U; the first U that attains it is returned, and it bounds every matching from above. Then a matching of ν edges, by a backtracking While over matching_step, as a symmetric 0/1 matrix. The two meet, so the matching is maximum. A maximum matching need not be perfect or unique, and a maximal one (no edge can be added) need not be maximum.

40exactcalls matching_running, matching_step, tutte_open, tutte_step, growth_step
iso_runningL1
(p: f64[], assign: f64[n], A: f64[n, n], B: f64[n, n]) → f64[]

Whether the isomorphism search is still running: 0 ≤ p < n, as 1 or 0. The condition are_isomorphic loops on.

40exact
iso_stepL3
(p: f64[], assign: f64[n], A: f64[n, n], B: f64[n, n]) → f64[], f64[n]

One move of a backtracking search for an isomorphism: give vertex p its next candidate image; if none is left, clear it and step back; if the image is already used, or the edges and non-edges to the earlier vertices do not match, try the next one; otherwise go on to vertex p + 1. The body are_isomorphic runs.

40exact
are_isomorphicL3
(A: f64[n, n], B: f64[n, n]) → f64[], f64[n]

Whether two finite undirected simple graphs on n vertices are isomorphic, as 1 or 0, and the first isomorphism in the search order, as the image of each vertex: a bijection f with {u, v} an edge of A exactly when {f(u), f(v)} is an edge of B. Preserving edges alone is not enough; non-edges must map to non-edges too. By backtracking, a While over iso_step.

40exactcalls iso_running, iso_step
is_isomorphismL3
(A: f64[n, n], B: f64[n, n], perm: i64[n]) → f64[]

Whether a map f, given as the image of each vertex, is an isomorphism from graph A to graph B, as 1 or 0: f is a bijection, and A(u, v) = B(f(u), f(v)) for every pair, edges and non-edges alike.

40exact
bareiss_stepL4
(M: f64[m, n], r: f64[], prev: f64[], c: f64[]) → f64[m, n], f64[], f64[]

One column of fraction-free Gaussian elimination (Bareiss) on an integer matrix: if some row at or below r has a nonzero entry in column c, swap the first such row into row r and replace each later row by (p·row − M[i, c]·row r)/prev, which is exact (p the new pivot, prev the one before), then r ← r + 1; otherwise nothing changes. The body rank_exact scans.

40exact
rank_exactL4
(A: f64[m, n]) → f64[]

The rank of an integer matrix, decided exactly by fraction-free Gaussian elimination: a Scan of bareiss_step over the columns, every entry an integer and every division exact. Unlike matrix_rank, which reads singular values against a tolerance, there is no threshold; the entries must stay below 2⁵³, which the intermediate minors (Hadamard's bound) make the limit.

40exactcalls bareiss_step
independenceL4
(V: f64[k, n]) → f64[], f64[], f64[], f64[]

For k integer vectors in Rⁿ (the rows of V), by exact rank: the rank (the dimension of their span); whether they are linearly independent (rank k, only the zero combination gives 0); whether they span Rⁿ (rank n); and whether they are a basis, which needs both. Neither property stands in for the other.

40exactcalls rank_exact
in_spanL4
(V: f64[k, n], t: f64[n]) → f64[]

Whether an integer vector t lies in the span of the integer vectors V (rows), as 1 or 0: adding t does not raise the exact rank. Spans are finite linear combinations; this decides membership over the reals, which a bounded search for coefficients could not. y is in the image of a matrix A exactly when it is in the span of A's columns.

40exactcalls rank_exact
combination_checkL1
(V: f64[k, n], coef: f64[k], t: f64[n]) → f64[n], f64[]

A linear combination Σ cᵢvᵢ of the rows of V with coefficients c, and whether it equals the target t, as 1 or 0: a witness that t is in the span. With integer data the check is exact.

40exactcalls vecmat
direct_sumL4
(U: f64[a, n], W: f64[b, n]) → f64[], f64[], f64[], f64[]

Whether Rⁿ is the internal direct sum of the subspaces U and W, each given by a basis (the rows of U and of W), by exact ranks: dim(U ∩ W) = dim U + dim W − dim(U + W); U ∩ W = {0} gives uniqueness of the decomposition inside U + W, and U + W = Rⁿ is a separate condition; the direct sum needs both. For three or more subspaces, pairwise trivial intersections are not enough.

40exactcalls rank_exact
kernel_dimensionL4
(A: f64[m, n]) → f64[], f64[]

The rank of an integer matrix A (m × n, a linear map Rⁿ → Rᵐ) and the dimension of its kernel, n − rank by rank-nullity, decided exactly. The kernel is the solution set of Ax = 0; a nonzero right-hand side gives an affine set, not the kernel.

40exactcalls rank_exact
in_kernelL1
(A: f64[m, n], x: f64[n]) → f64[]

Whether an integer vector x is in the kernel of an integer matrix A, Ax = 0, as 1 or 0, exactly. The solution set of homogeneous equations is a subspace; a set such as a line not through the origin is not.

40exactcalls matvec
same_cosetL4
(W: f64[k, n], u: f64[n], v: f64[n]) → f64[], f64[]

Whether integer vectors u and v represent the same element of the quotient space Rⁿ/W, as 1 or 0: v − u ∈ W, decided by exact rank; and dim(Rⁿ/W) = n − dim W. The elements of the quotient are cosets, not chosen representatives; the zero coset is W itself.

40exactcalls in_span, rank_exact
minor_stepL4
(M: f64[n, n], prev: f64[], minors: f64[n], k: f64[]) → f64[n, n], f64[], f64[n]

One step of fraction-free elimination without row exchanges: the pivot M[k, k] is the k-th leading principal minor, and the later rows are eliminated exactly by it over the previous pivot. The body leading_minors scans.

40exact
leading_minorsL4
(A: f64[n, n]) → f64[n], f64[n]

The leading principal minors Δ₁, …, Δₙ of an integer matrix (the determinants of its top-left k × k blocks), exactly, by fraction-free elimination without row exchanges: a Scan of minor_step. Each Δ_k is right as long as the earlier ones are nonzero; valid marks those, and after the first zero minor the later values are not minors.

40exactcalls minor_step
is_positive_definiteL4
(A: f64[n, n]) → f64[], f64[]

Whether an integer matrix is symmetric, and whether it is positive definite, each as 1 or 0, by Sylvester's criterion: a symmetric matrix is positive definite exactly when every leading principal minor is positive, decided exactly by leading_minors. Then ⟨x, y⟩ = xᵀAy is an inner product on Rⁿ. Testing ⟨x, x⟩ > 0 on finitely many vectors would not prove it.

40exactcalls leading_minors
induced_normsL1
(A: f64[m, n]) → f64[], f64[]

The operator norms of a matrix A : Rⁿ → Rᵐ induced by ℓ₁ and by ℓ∞: ‖A‖₁ = max over columns of Σ|a_ij|, and ‖A‖∞ = max over rows of Σ|a_ij|. They are the least C with ‖Ax‖ ≤ C‖x‖ for every x, so A is a bounded operator; a few vectors x satisfying the bound would not be a certificate.

40
lp_normsL1
(v: f64[n]) → f64[], f64[]

The ℓ₁ and ℓ∞ norms of a vector: Σ|vᵢ| and max |vᵢ|. Each is a norm on Rⁿ: zero only at 0, absolutely homogeneous, and subadditive (the triangle inequality).

40
dual_basisL3
(B: f64[n, n]) → f64[n, n]

The dual basis of a basis b₁ … bₙ of Rⁿ (the rows of B): the covectors φ₁ … φₙ (the rows of Φ) with φᵢ(bⱼ) = δᵢⱼ, which is Φ = (B⁻¹)ᵀ. A covector is a linear functional, not a vector of the space; without an inner product V and V* are not identified.

40calls inverse
vector_space_instanceL1
(u: f64[n], v: f64[n], w: f64[n], a: f64[], b: f64[]) → f64[]

The eight vector-space axioms on given coordinate vectors u, v, w in Rⁿ and scalars a, b, as 1 or 0 when all hold: associativity and commutativity of addition, the zero vector, additive inverses, both distributive laws, compatibility of scalar multiplication, and 1u = u. With integer data they are checked exactly. Instances that pass do not prove that a candidate structure is a vector space; one that fails disproves it.

40exact

Geometry

std.geometry · 22
sqdistL0
(x: f64[n], y: f64[n]) → f64[]

Squared Euclidean distance between two points. Calls norm_sq.

40calls norm_sq
pairwise_sqdistL0
(X: f64[m, d], Y: f64[k, d]) → f64[m, k]

Squared distances between every point of X and every point of Y, with one matrix product.

40
centroidL0
(X: f64[m, d]) → f64[d]

Centroid (mean point) of a set of points.

40
centerL0
(X: f64[m, d]) → f64[m, d]

Shift a set of points so that its centroid is the origin.

40
distL1
(x: f64[n], y: f64[n]) → f64[]

Euclidean distance between two points. Calls sqdist.

40calls sqdist
pairwise_distL1
(X: f64[m, d], Y: f64[k, d]) → f64[m, k]

Distances between every point of X and every point of Y. Calls pairwise_sqdist, and clamps at zero before the square root.

40calls pairwise_sqdist
segment_lengthsL2
(P: f64[n, d]) → f64[n−1]

Lengths of the segments of a polyline through the points P, in order.

40
polyline_lengthL2
(P: f64[n, d]) → f64[]

Total length of the polyline through the points P. Calls segment_lengths.

40calls segment_lengths
path_arclengthL2
(P: f64[n, d]) → f64[n]

Arc length along the polyline at every point, starting from 0: the running sum of the segment lengths. Calls segment_lengths.

40calls segment_lengths
polygon_areaL2
(P: f64[n, 2]) → f64[]

Signed area of a polygon by the shoelace formula: positive when the vertices run counter-clockwise. The next vertex of each one comes from joining P[1:] and P[:1].

40
nearest_labelL2
(q: f64[d], points: f64[m, d], labels: f64[m]) → f64[]

One-nearest-neighbour classification: the label of the point closest to q. ArgMin gives the position; a mask built from Iota reads the label there.

40exact
knn_regressL3
(q: f64[d], points: f64[m, d], values: f64[m], k: f64[]) → f64[]

k-nearest-neighbour regression: the mean value of the k points closest to q (ties by index). The ranks of the distances become a mask, so k can be an input.

40calls rank
rotate2dL5
(P: f64[n, 2], theta: f64[]) → f64[n, 2]

Rotate points of the plane counterclockwise by the angle θ (radians) about the origin: each row p of P becomes R(θ)·p.

40
angle_betweenL5
(u: f64[n], v: f64[n]) → f64[]

The angle between two non-zero vectors, in [0, π], by Kahan's formula 2·atan2(‖|v|u − |u|v‖, ‖|v|u + |u|v‖): its absolute error stays near one unit of roundoff (about 10⁻¹⁷ radians here) at every angle, where acos of the normalized dot product errs by up to √u ≈ 10⁻⁸ near 0 and π, and returns 0 for angles below about 10⁻⁸. Calls norm.

40calls norm
polar_to_cartesianL5
(r: f64[n], theta: f64[n]) → f64[n], f64[n]

From polar coordinates (r, θ) to Cartesian ones: x = r·cos θ, y = r·sin θ.

40
cartesian_to_polarL5
(x: f64[n], y: f64[n]) → f64[n], f64[n]

From Cartesian coordinates (x, y) to polar ones: r = √(x² + y²) and θ = atan2(y, x) in [−π, π].

40
haversineL5
(lat1: f64[n], lon1: f64[n], lat2: f64[n], lon2: f64[n]) → f64[n]

The central angle between two points on a sphere, given their latitudes and longitudes in radians, by the haversine formula in its atan2 form, which stays accurate for nearby and for nearly antipodal points. Multiply by the radius for the great-circle distance.

40
circle_positionL1
(pts: f64[n, 2], center: f64[2], r: f64[]) → f64[n]

Where each point lies relative to the circle with centre O and radius r ≥ 0: −1 inside, 0 on the circle, 1 outside, from the squared distance against r². No square root is taken, so for exact inputs the decision is exact. r = 0 is the degenerate circle {O}.

40exact
quadrantL3
(pts: f64[m, 2]) → f64[m]

The quadrant of each point (x, y) of the coordinate plane: 1 for x > 0 and y > 0, 2 for x < 0 and y > 0, 3 for both negative, 4 for x > 0 and y < 0, and 0 on an axis (y = 0 is the x-axis, x = 0 the y-axis, meeting at the origin).

40exact
triangle_checkL3
(P: f64[3, 2]) → f64[], f64[]

Whether three points A, B, C of the plane (the rows of P) form a non-degenerate triangle, as 1 or 0: they are distinct and not collinear, which is (B − A) × (C − A) ≠ 0; and that cross product, twice the signed area (positive when A, B, C run counterclockwise). Exact for integer coordinates.

40exact
sss_similarL3
(A: f64[3, 2], B: f64[3, 2], p: f64[], q: f64[]) → f64[]

Whether triangle B is similar to triangle A with ratio k = p/q > 0 under the given correspondence Aᵢ ↔ Bᵢ (rows of A and B), as 1 or 0, by side-side-side: every corresponding side has |BᵢBⱼ| = k·|AᵢAⱼ|, checked exactly as q²·|BᵢBⱼ|² = p²·|AᵢAⱼ|² for integer coordinates. A reflection keeps the ratio. A failure rules out this ratio and correspondence only, not similarity by another.

40exact
convex_set_membershipL1
(X: f64[m, n], lo: f64[n], hi: f64[n], w: f64[n], beta: f64[]) → f64[m], f64[m]

Membership of points (the rows of X) in two convex sets: the closed box lo ≤ x ≤ hi, and the closed half-space w·x ≤ β, each as 1 or 0 per point. Both sets are convex for every choice of their data, which is the algebraic certificate; sampling convex combinations would not prove convexity, but one combination of members that falls outside refutes a set's convexity.

40exactcalls matvec

Statistics

std.stats · 109
varianceL0
(x: f64[n]) → f64[]

Population variance, two-pass: the mean first, then the mean squared deviation.

40
covarianceL0
(x: f64[n], y: f64[n]) → f64[]

Population covariance of two paired samples.

40
weighted_meanL0
(x: f64[n], w: f64[n]) → f64[]

Weighted mean with positive weights. Calls dot.

40calls dot
stdL1
(x: f64[n]) → f64[]

Population standard deviation. Calls variance.

40calls variance
sample_varianceL1
(x: f64[n]) → f64[]

Sample variance, dividing by n − 1. The count comes from the Size primitive. Calls variance.

40calls variance
zscoreL1
(x: f64[n]) → f64[n]

Standard scores: each element's distance from the mean, in standard deviations. Calls std.

40calls std
cov_matrixL1
(X: f64[m, d]) → f64[d, d]

Population covariance matrix of the columns of X. Calls center; the row count comes from Size.

40calls center
correlationL1
(x: f64[n], y: f64[n]) → f64[]

Pearson correlation of two paired samples. Calls covariance and std.

40calls covariance, std
logsumexpL1
(x: f64[n]) → f64[]

log Σ eˣ, computed stably by shifting by the maximum first.

40
minmax_scaleL1
(x: f64[n]) → f64[n]

Rescale to [0, 1] by the minimum and the maximum.

40
quantileL2
(x: f64[n], q: f64[]) → f64[]

The q-quantile with linear interpolation (NumPy's default): sort, then weigh each sorted value by a tent 1 − |i − h| at position h = (n − 1)·q.

40
medianL2
(x: f64[n]) → f64[]

The median: the 0.5-quantile, the mean of the two middle values when n is even. Calls quantile.

40exactcalls quantile
iqrL2
(x: f64[n]) → f64[]

Interquartile range: the 0.75-quantile minus the 0.25-quantile. Calls quantile twice.

40calls quantile
madL2
(x: f64[n]) → f64[]

Median absolute deviation, a robust spread: the median distance from the median. Calls median and abs.

40calls abs, median
trimmed_meanL2
(x: f64[n]) → f64[]

Mean without the smallest and the largest value, which makes it resistant to one outlier at each end.

40
max_drawdownL2
(x: f64[n]) → f64[]

Maximum drawdown: the largest fall from a running peak to a later value, as used for price series.

40exact
histogramL3
(x: f64[n], edges: f64[m]) → f64[m−1]

Counts per bin for increasing bin edges, with NumPy's rules: half-open bins, the last one closed, values outside the edges not counted. Each value's bin comes from comparisons, becomes an integer slot with Cast, and is counted with ScatterAdd.

40exact
segment_sumL3
(base: f64[m], seg: i64[n], x: f64[n]) → f64[m]

Add each value into its segment: x[k] goes to base[seg[k]], and segments that repeat accumulate. A ScatterAdd.

40
sort_by_keyL3
(keys: f64[n], values: f64[n]) → f64[n]

Reorder the values by the stable order of the keys: ArgSort the keys, Cast the positions to indices, Gather the values.

40exact
rankL3
(x: f64[n]) → f64[n]

The rank of each value, 0 for the smallest; ties are ranked in input order. The argsort of the argsort.

40exact
gaussian_logpdfL3
(x: f64[k], mu: f64[k], S: f64[k, k]) → f64[]

The log-density of a multivariate normal N(μ, S) at x, computed the stable way: one Cholesky factorization gives both the log-determinant and, by a triangular solve, the quadratic form.

40
mahalanobisL3
(x: f64[k], mu: f64[k], S: f64[k, k]) → f64[]

The Mahalanobis distance of x from μ under covariance S: the length of x − μ after whitening by S's Cholesky factor.

40
pca_explained_varianceL3
(X: f64[n, p]) → f64[p]

Principal component analysis, as the share of variance along each principal axis, largest first: the eigenvalues of the covariance matrix over their sum.

40
pca_componentsL4
(X: f64[p+k, p]) → f64[p, p]

The principal axes of a data set, as columns, largest variance first: the right singular vectors of the centred data, each signed so its largest component is positive.

40
bin_indexL4
(x: f64[n], lo: f64[], width: f64[]) → i64[n]

The bin each value falls into, for bins of equal width starting at lo: ⌊(x − lo)/width⌋, as an integer index. Values below lo get negative bins; nothing is clipped.

40exact
normal_cdfL5
(x: f64[n], mu: f64[], sigma: f64[]) → f64[n]

The normal distribution's cumulative probability, Φ((x − μ)/σ), written with erfc so the lower tail keeps its relative accuracy where 1 + erf would cancel to 0.

40
log_binomialL5
(k: i64[n], m: i64[n]) → f64[n]

The logarithm of the binomial coefficient C(k + m, k), from log-gamma: log Γ(k+m+1) − log Γ(k+1) − log Γ(m+1). The coefficient itself would overflow long before its logarithm does.

40
poisson_logpmfL5
(k: i64[n], lam: f64[n]) → f64[n]

The log-probability of k events under a Poisson distribution with mean λ: k·log λ − λ − log k!, with log k! as log Γ(k + 1).

40
gamma_logpdfL5
(x: f64[n], shape: f64[], rate: f64[]) → f64[n]

The log-density of the gamma distribution with shape a and rate b: a·log b + (a − 1)·log x − b·x − log Γ(a).

40
beta_logpdfL5
(x: f64[n], a: f64[], b: f64[]) → f64[n]

The log-density of the beta distribution on (0, 1): (a − 1)·log x + (b − 1)·log(1 − x) − log B(a, b), with log(1 − x) as log1p(−x) and log B from log-gamma.

40
student_t_logpdfL5
(x: f64[n], nu: f64[]) → f64[n]

The log-density of Student's t distribution with ν degrees of freedom: log Γ((ν+1)/2) − log Γ(ν/2) − ½·log(νπ) − ((ν+1)/2)·log1p(x²/ν).

40
normal_quantileL5
(p: f64[n], mu: f64[], sigma: f64[]) → f64[n]

The normal distribution's quantile: the x with Φ((x − μ)/σ) = p, as μ + σ·Φ⁻¹(p).

40
normal_drawsL5
(state: i64[3], x: f64[n]) → f64[n]

One standard normal number for each element of x, by inverse-transform sampling: Φ⁻¹ of the Wichmann–Hill uniform draws. Reproducible from its state.

40calls uniform_draws
chi2_cdfL5
(x: f64[n], k: i64[]) → f64[n]

The chi-square distribution's cumulative probability with k degrees of freedom: P(k/2, x/2), the regularized lower incomplete gamma function.

40
poisson_cdfL5
(k: i64[n], lam: f64[n]) → f64[n]

The probability of at most k events under a Poisson distribution with mean λ: Q(k + 1, λ), the upper incomplete gamma function, so a small probability keeps its relative accuracy (Round 14.3; 1 − P(k + 1, λ) before).

40
gamma_cdfL5
(x: f64[n], shape: f64[], rate: f64[]) → f64[n]

The gamma distribution's cumulative probability with shape a and rate b: P(a, b·x).

40
beta_cdfL5
(x: f64[n], a: f64[], b: f64[]) → f64[n]

The beta distribution's cumulative probability: I_x(a, b), the regularized incomplete beta function.

40
student_t_cdfL5
(x: f64[n], nu: f64[]) → f64[n]

Student's t distribution's cumulative probability with ν degrees of freedom, through the incomplete beta function: ½·I_{ν/(ν+x²)}(ν/2, ½) on the left, one minus that on the right.

40
binomial_cdfL5
(k: i64[n], m: i64[n], prob: f64[n]) → f64[n]

The probability of at most k successes in k + m independent trials with success probability p (m ≥ 1): I_{1−p}(m, k + 1).

40
chi2_quantileL5
(p: f64[n], k: i64[]) → f64[n]

The chi-square distribution's quantile with k degrees of freedom: the x with F(x; k) = p, as 2·P⁻¹(k/2, p).

40
gamma_quantileL5
(p: f64[n], shape: f64[], rate: f64[]) → f64[n]

The gamma distribution's quantile with shape a and rate b: P⁻¹(a, p)/b.

40
beta_quantileL5
(p: f64[n], a: f64[], b: f64[]) → f64[n]

The beta distribution's quantile: the x with I_x(a, b) = p, the inverse incomplete beta function.

40
student_t_quantileL5
(p: f64[n], nu: f64[]) → f64[n]

Student's t distribution's quantile with ν degrees of freedom, through the inverse incomplete beta function: with z = I⁻¹_{2·min(p, 1−p)}(ν/2, ½), x = ±√(ν(1 − z)/z), negative below the median.

40
chi2_sfL5
(x: f64[n], k: i64[]) → f64[n]

The chi-square distribution's upper tail with k degrees of freedom, the p-value of a chi-square statistic: Q(k/2, x/2), the regularized upper incomplete gamma function. A small p-value keeps its relative accuracy, where 1 − chi2_cdf would round it to 0.

40
gamma_sfL5
(x: f64[n], shape: f64[], rate: f64[]) → f64[n]

The gamma distribution's upper tail with shape a and rate b: Q(a, b·x).

40
poisson_quantile_stepL5
(lohi: i64[2, n], p: f64[n], lam: f64[]) → i64[2, n]

One bisection step for the Poisson quantile, on every element at once: where the bracket [lo, hi] is still open, mid = ⌊(lo + hi)/2⌋ moves lo up to mid + 1 if F(mid) < p, else hi down to mid. F(mid) is Q(mid + 1, λ) below p = ½ and 1 − P(mid + 1, λ) above it. The body that poisson_quantile runs.

40exact
poisson_bracket_openL2
(lohi: i64[2, n], p: f64[n], lam: f64[]) → f64[]

Whether any Poisson-quantile bracket is still open (lo < hi somewhere), as 1 or 0. The condition poisson_quantile loops on; it takes the loop's operands, of which only the bracket matters.

40exact
poisson_quantileL5
(p: f64[n], lam: f64[]) → i64[n]

The Poisson distribution's quantile with mean λ: the smallest whole k with P(K ≤ k) ≥ p. A bisection on whole numbers (a While over poisson_quantile_step), from [0, ⌊λ + t⌋ + 2] with t from Bernstein's inequality for the upper tail.

40exactcalls poisson_bracket_open, poisson_quantile_step
binomial_quantile_stepL5
(lohi: i64[2, n], p: f64[n], trials: i64[], prob: f64[]) → i64[2, n]

One bisection step for the binomial quantile, on every element at once: where [lo, hi] is still open, mid = ⌊(lo + hi)/2⌋ moves lo up to mid + 1 if F(mid) < p, else hi down to mid. F(mid) is I_{1−π}(n − mid, mid + 1) below p = ½ and 1 − I_π(mid + 1, n − mid) above it. The body that binomial_quantile runs.

40exact
binomial_bracket_openL2
(lohi: i64[2, n], p: f64[n], trials: i64[], prob: f64[]) → f64[]

Whether any binomial-quantile bracket is still open (lo < hi somewhere), as 1 or 0. The condition binomial_quantile loops on; it takes the loop's operands, of which only the bracket matters.

40exact
binomial_quantileL5
(p: f64[n], trials: i64[], prob: f64[]) → i64[n]

The binomial distribution's quantile for n trials with success probability π: the smallest k in [0, n] with P(K ≤ k) ≥ p. A bisection on whole numbers (a While over binomial_quantile_step) from [0, n].

40exactcalls binomial_bracket_open, binomial_quantile_step
z_test_pL5
(z: f64[n]) → f64[n]

The two-sided p-value of a standard normal statistic z: P(|Z| > |z|) = erfc(|z|/√2). erfc keeps a small p-value's relative accuracy.

40
t_test_1sampL5
(x: f64[n], mu0: f64[]) → f64[3]

One-sample t-test of the mean against μ₀: [t, ν, p] with t = (x̄ − μ₀)/(s/√n), ν = n − 1, and the two-sided p = I_{ν/(ν+t²)}(ν/2, ½). The incomplete beta function's lower tail keeps a small p-value's relative accuracy.

40calls sample_variance
welch_t_testL5
(x: f64[n], y: f64[m]) → f64[3]

Welch's two-sample t-test, without assuming equal variances: [t, ν, p] with t = (x̄ − ȳ)/√(sₓ²/n + s_y²/m), ν from the Welch–Satterthwaite formula, and the two-sided p = I_{ν/(ν+t²)}(ν/2, ½).

40calls sample_variance
pearson_r_testL5
(x: f64[n], y: f64[n]) → f64[2]

The test of a Pearson correlation against zero: [r, p], with the two-sided p from Student's t with ν = n − 2. Since ν/(ν + t²) = 1 − r² for t = r·√(ν/(1 − r²)), the p-value is I_{1−r²}((n − 2)/2, ½) directly. Calls correlation.

40calls correlation
chi2_gof_testL5
(observed: f64[n], expected: f64[n]) → f64[2]

Pearson's chi-square goodness-of-fit test: [X², p] with X² = Σ (oᵢ − eᵢ)²/eᵢ over n categories and p = Q((n − 1)/2, X²/2), the chi-square upper tail with n − 1 degrees of freedom.

40
midrankL1
(x: f64[n]) → f64[n]

Midranks, 1 for the smallest value, with tied values sharing the average of the ranks they span. Each value's midrank is the number of values below it plus (the number equal to it + 1)/2, counted by exact comparisons of every pair.

40exact
spearman_rL1
(x: f64[n], y: f64[n]) → f64[]

Spearman's rank correlation: the Pearson correlation of the two samples' midranks, so ties are handled by average ranks. Calls midrank and correlation.

40calls correlation, midrank
spearman_r_testL5
(x: f64[n], y: f64[n]) → f64[2]

The test of Spearman's rank correlation against zero, by the usual t approximation: [ρ, p] with the two-sided p = I_{1−ρ²}((n − 2)/2, ½), Student's t with n − 2 degrees of freedom. An approximation to the exact permutation distribution, closer as n grows. Calls spearman_r.

40calls spearman_r
mann_whitney_u_testL5
(x: f64[n], y: f64[m]) → f64[2]

The Mann–Whitney U test (Wilcoxon rank-sum) by the normal approximation with the tie correction, without a continuity correction: [U, p] with U = Rₓ − n(n + 1)/2 from x's midranks in the combined sample, σ² = nm/12·((N + 1) − Σ(t³ − t)/(N(N − 1))) and the two-sided p = erfc(|U − nm/2|/(σ√2)). An approximation to the exact distribution, closer as n and m grow.

40
kalman_level_stepL0
(m: f64[k], P: f64[k], z: f64[k], Q: f64[k], R: f64[k]) → f64[k], f64[k]

One step of the Kalman filter for a local-level model, independently in each coordinate: predict the variance P + Q, weigh the observation z by the gain K = (P + Q)/(P + Q + R), and update the mean m and the variance. The body that kalman_level scans.

40
kalman_levelL2
(m0: f64[k], P0: f64[k], Z: f64[n, k], Q: f64[k], R: f64[k]) → f64[n, k], f64[n, k]

Filter a sequence of noisy observations with a local-level Kalman filter: a random walk observed with noise, in each coordinate independently. Returns the filtered mean and variance after every observation. A Scan with two carries, m and P (Round 14.10).

40calls kalman_level_step
circular_meanL5
(theta: f64[n]) → f64[]

The mean direction of angles (radians): the direction of the sum of their unit vectors, atan2(Σ sin θ, Σ cos θ), in [−π, π]. The arithmetic mean of 359° and 1° is 180°; their circular mean is 0°.

40
circular_varianceL5
(theta: f64[n]) → f64[]

The circular variance of angles (radians): 1 − R̄, with R̄ the length of the mean of their unit vectors; 0 when every angle is the same, near 1 when they spread evenly around the circle.

40
exponential_cdfL5
(x: f64[n], rate: f64[]) → f64[n]

The exponential distribution's cumulative probability, 1 − e^(−λx) for x ≥ 0 and 0 below, written as −expm1(−λx) so that it keeps its relative accuracy for small λx.

40
exponential_quantileL5
(p: f64[n], rate: f64[]) → f64[n]

The exponential distribution's quantile: −log(1 − p)/λ, written with log1p so that small p keep their relative accuracy.

40
exponential_logpdfL1
(x: f64[n], rate: f64[]) → f64[n]

The exponential distribution's log density at x ≥ 0: log λ − λx.

40
lognormal_cdfL5
(x: f64[n], mu: f64[], sigma: f64[]) → f64[n]

The log-normal distribution's cumulative probability: Φ((log x − μ)/σ) for x > 0. Calls normal_cdf.

40calls normal_cdf
lognormal_logpdfL5
(x: f64[n], mu: f64[], sigma: f64[]) → f64[n]

The log-normal distribution's log density at x > 0: −log x − log σ − ½log 2π − (log x − μ)²/(2σ²), with π as arccos(−1).

40
weibull_cdfL5
(x: f64[n], k: f64[], lam: f64[]) → f64[n]

The Weibull distribution's cumulative probability with shape k and scale λ: 1 − e^(−(x/λ)ᵏ) for x > 0, written with expm1.

40
weibull_quantileL5
(p: f64[n], k: f64[], lam: f64[]) → f64[n]

The Weibull distribution's quantile: λ·(−log(1 − p))^(1/k), written with log1p.

40
f_cdfL5
(x: f64[n], d1: f64[], d2: f64[]) → f64[n]

The F distribution's cumulative probability with d₁ and d₂ degrees of freedom: I_{d₁x/(d₁x+d₂)}(d₁/2, d₂/2), the regularized incomplete beta function.

40
f_sfL5
(x: f64[n], d1: f64[], d2: f64[]) → f64[n]

The F distribution's upper tail P(F > x): I_{d₂/(d₂+d₁x)}(d₂/2, d₁/2), the same beta integral read from the other end, so that a small tail keeps its relative accuracy.

40
paired_t_testL5
(x: f64[n], y: f64[n]) → f64[3]

Paired t-test of two matched samples: the one-sample t-test of their differences against 0, giving [t, ν, p]. Calls t_test_1samp.

40calls t_test_1samp
anova_onewayL5
(X: f64[g, n]) → f64[4]

One-way analysis of variance for g groups of n observations each, the rows of X: [F, d₁, d₂, p] with F the ratio of the between-group to the within-group mean square, d₁ = g − 1, d₂ = g(n − 1), and p = P(F_{d₁,d₂} > F). Calls f_sf.

40calls f_sf
bayes_posteriorL0
(prior: f64[k], likelihood: f64[k]) → f64[k]

Bayes' theorem on a finite partition of hypotheses: the posterior P(Hᵢ | E) = P(Hᵢ)·P(E | Hᵢ) / Σⱼ P(Hⱼ)·P(E | Hⱼ). The evidence in the denominator is the law of total probability, and it must be positive.

40
marginalsL0
(joint: f64[m, n]) → f64[m], f64[n]

The two marginals of a finite joint distribution given as a table of masses P(X = i, Y = j): P(X = i) = Σⱼ, and P(Y = j) = Σᵢ.

40
conditional_from_jointL0
(joint: f64[m, n]) → f64[m, n]

The conditional distributions P(Y = j | X = i) = P(X = i, Y = j) / P(X = i) of a finite joint table, one row per value of X. Each row sums to 1; a row of zero mass has no conditional distribution.

40
conditional_expectationL0
(joint: f64[m, n], y: f64[n]) → f64[m]

The conditional expectation E[Y | X = i] = Σⱼ yⱼ·P(Y = yⱼ | X = i) for a finite joint table and the values yⱼ of Y. Averaging it over P(X) gives E[Y], the law of total expectation.

40calls conditional_from_joint
markov_stepL0
(pi: f64[k], t: f64[], Pm: f64[k, k]) → f64[k]

One step of a finite Markov chain: the distribution π over the states becomes π·P, for the transition matrix P with Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i). The body markov_distribution scans; it does not read its sequence element.

40exactcalls vecmat
markov_distributionL2
(pi0: f64[k], Pm: f64[k, k], steps: f64[s]) → f64[s, k]

The distributions of a finite Markov chain after 1 … s steps from π₀, s the length of steps (only its length is read): row n is π₀·Pⁿ⁺¹. A Scan of markov_step.

40exactcalls markov_step
stationary_distributionL3
(Pm: f64[k, k]) → f64[k]

The stationary distribution π of a finite Markov chain, with π·P = π and Σπ = 1: one solve of (Pᵀ − I)·π = 0 with its last equation replaced by the normalization. Unique for an irreducible chain. The reference solves the full system with every equation and the normalization, by least squares, which is exact for a consistent system.

40
event_probabilityL0
(p: f64[k], E: f64[k]) → f64[]

The probability of an event E on a finite sample space with masses p: the sum of the masses of the outcomes in E, given as a 0/1 indicator. Only when the outcomes are equally likely is it |E|/|S|.

40exactcalls dot
modesL2
(x: f64[n]) → f64[n], f64[n]

The modes of a finite list of observations: the values that occur most often. Returned as the sorted observations with a 0/1 mark on the first occurrence of each mode, so the mode set is the marked values in increasing order. When every value occurs once, every value is a mode.

40exact
estimator_biasL0
(p: f64[k], t: f64[k], theta: f64[]) → f64[]

The bias E_θ[T] − θ of an estimator T whose finite sampling law under θ gives the value tᵢ the probability pᵢ.

40calls dot
estimator_varianceL0
(p: f64[k], t: f64[k]) → f64[]

The variance of an estimator T under its finite sampling law: Σ pᵢ(tᵢ − E[T])².

40calls dot
estimator_mseL0
(p: f64[k], t: f64[k], theta: f64[]) → f64[]

The mean squared error of an estimator T under its finite sampling law at θ, computed directly: Σ pᵢ(tᵢ − θ)². It equals bias² + variance, a theorem the tests check rather than the definition used. MSE = 0 exactly when T = θ almost surely.

40calls dot
pushforwardL3
(P: f64[r, n], X: i64[n], cod: f64[k]) → f64[r, k]

The law of a random variable X on a finite sample space, for one law or a family of laws (one per row of P): P(X = t) = Σ over the outcomes s with X(s) = t of P(s). With a statistic T and a parametric family P_θ it is T's sampling distribution, one row per θ. X is given by value indices into 0 … k − 1 (a carrier vector of length k, only its length read). It is not a likelihood or a posterior.

40exact
event_independenceL0
(p: f64[n], A: f64[n], B: f64[n]) → f64[], f64[], f64[]

The two sides of independence for events A and B on a finite probability space: P(A ∩ B) and P(A)·P(B), and their difference; A and B are independent when it is 0. When P(B) > 0 this is the same as P(A | B) = P(A); when P(B) = 0 the product form still applies and A and B are independent. Two events only: pairwise independence of three events does not give mutual independence.

40exactcalls dot
rv_independenceL1
(J: f64[a, b]) → f64[a], f64[b], f64[a, b], f64[]

Independence of two finite random variables from their joint table J (J[x, y] = P(X = x, Y = y)): the marginals of X and Y, the deviation J − P(X)·P(Y)ᵀ, and its largest magnitude. X and Y are independent exactly when every entry of the deviation is 0. Zero covariance is a consequence of independence, not a test for it.

40exact
total_varianceL3
(p: f64[n], x: f64[n], g: i64[n], cells: f64[k]) → f64[], f64[], f64[]

The law of total variance on a finite probability space, with the conditioning given by a partition of the outcomes into cells (g[s] the cell of s): the expected conditional variance E[Var(X | G)], the variance of the conditional mean Var(E[X | G]), and Var(X), which is their sum. A zero-mass cell contributes nothing; its conditional values are determined only almost surely, so it is never divided by. The two parts are not interchangeable, and the cells need not be independent.

40calls dot
markov_boundL1
(p: f64[n], x: f64[n], a: f64[]) → f64[], f64[]

Markov's inequality on a finite law, for X ≥ 0 and a > 0: the actual tail P(X ≥ a) and the bound E[X]/a. The bound is not the tail, and it does not apply to a variable that takes negative values.

40calls dot
chebyshev_boundL1
(p: f64[n], x: f64[n], eps: f64[]) → f64[], f64[]

Chebyshev's inequality on a finite law, for ε > 0: the actual tail P(|X − μ| ≥ ε), decided as (X − μ)² ≥ ε², and the bound Var(X)/ε². It is Markov's inequality applied to the squared deviation; it needs no independence, and the bound is not the tail.

40calls dot
ci_coverageL1
(P: f64[r, n], theta: f64[r], L: f64[n], U: f64[n]) → f64[r], f64[]

The coverage of an interval procedure [L(x), U(x)], fixed for every possible sample x before the data are seen, over a finite family of laws P_θ (one row per θ, with the θ values given): for each θ, Σ_x P_θ(x)·[L(x) ≤ θ ≤ U(x)], and the worst case, the minimum over θ. A high average coverage does not make the worst case high, and coverage is not a posterior probability. A selection rule must be part of the procedure before coverage is computed.

40exact
finite_mleL2
(P: f64[r, n]) → f64[n], f64[n], f64[n], f64[n]

The maximum-likelihood estimator on a finite parametric model, one law P_θ per row: for every possible sample x, the likelihood θ ↦ P_θ(x) is maximized over all θ, and the estimate is the first θ attaining it, a fixed tie order that does not depend on the unknown θ. Also the maximal likelihood, whether there is a tie, and whether every likelihood is 0 there. The MLE maximizes the likelihood, not a posterior; it need not be unique, unbiased or consistent.

40exact
fiber_conditionalL3
(P: f64[r, n], T: i64[n], cod: f64[k]) → f64[r, n], f64[n]

Sufficiency of a statistic T on a finite parametric model: the conditional law P_θ(x | T = T(x)) for every θ and sample x (0 on a zero-mass cell, where it is undefined), and for each x the spread of that conditional probability across the θ for which its cell has positive mass. T is sufficient exactly when every spread is 0: within each fibre of T the conditional law does not depend on θ. The factorization theorem is not used.

40calls pushforward
estimator_expectationsL0
(P: f64[r, n], t: f64[n]) → f64[r]

The expectation E_θ[T] of a statistic T (its value t(x) on each sample x, never indexed by θ) under every law of a finite parametric family, one per row: the vector P·t. It says nothing by itself about bias, consistency or sufficiency.

40calls matvec
process_marginalsL3
(paths: i64[N, T], p: f64[N], states: f64[k]) → f64[T, k]

The one-time marginals of a discrete-time process on a finite horizon, given by the complete list of its paths (each a row of state indices over the times) and their probabilities: P(X_t = s) for every time t and state s. A finite-horizon joint law gives the marginals and the two-time joints; it does not by itself give the Markov property or stationarity.

40exact
process_jointL3
(paths: i64[N, T], p: f64[N], states: f64[k], t1: i64[], t2: i64[]) → f64[k, k]

The two-time joint law P(X_{t1} = s, X_{t2} = s′) of a finite-horizon process given by its complete list of paths and their probabilities.

40exact
word_stepL0
(acc: f64[], w: f64[], prob: f64[]) → f64[]

One factor of a Bernoulli cylinder probability: acc·p for a 1, acc·(1 − p) for a 0. The body bernoulli_word scans.

40exact
bernoulli_wordL2
(w: f64[m], prob: f64[]) → f64[]

The probability that an IID Bernoulli(p) sequence begins with a given finite 0/1 word: p^(number of 1s)·(1 − p)^(number of 0s), the cylinder probability of the product law. A finite prefix defines a finite IID family; it does not by itself establish an infinite IID sequence.

40calls word_step
refine_stepL1
(ok: f64[], a: f64[n], b2: f64[n]) → f64[]

One step of a filtration check: the later partition (labels b2) refines the earlier one (labels a), so two outcomes in one block later were in one block before. The body is_filtration scans.

40exact
is_filtrationL2
(L: f64[T, n]) → f64[]

Whether a sequence of at least two partitions of one finite sample space (row t gives each outcome's block label at time t) is a filtration, as 1 or 0: each partition refines the one before, which is the inclusion F_s ⊆ F_t of the σ-algebras they generate, every pair of outcomes checked. A Scan of refine_step. A filtration only nests information; it does not make a process adapted, natural or Markov.

40exactcalls refine_step
martingale_stepL1
(adapted: f64[], gap: f64[n], a: f64[n], xt: f64[n], xn: f64[n], p: f64[n]) → f64[], f64[n]

One time step of a martingale check on a finite probability space: on each block of the partition F_t, E[X_{t+1} | F_t] − X_t (0 on a zero-mass block, which is determined only almost surely), and whether X_t is constant on the blocks of F_t (adapted). The body martingale_check scans.

40
martingale_checkL2
(L: f64[T, n], X: f64[T, n], p: f64[n]) → f64[], f64[], f64[T−1, n]

The martingale conditions for a process X_0 … X_T (one row per time) on a finite probability space with a filtration given by partitions L (one row per time): whether L is a filtration; whether X is adapted (each X_t constant on the blocks of F_t); and the gaps E[X_{t+1} | F_t] − X_t for t < T, which are all 0 for a martingale. Integrability is automatic on a finite space. A martingale need not have independent increments, be Markov, or converge.

40calls is_filtration, martingale_step
sigma_algebra_axiomsL3
(F: f64[m, n]) → f64[], f64[], f64[], f64[]

The axioms of a σ-algebra on a finite set, given as the complete list of its members (one subset per row), as 1 or 0: it contains ∅ and X, it is closed under complements, and under unions. On a finite set a countable union reduces to finitely many distinct sets, so pairwise unions suffice.

40exactcalls members_open, topology_axioms
measure_checkL3
(F: f64[m, n], mu: f64[m]) → f64[], f64[], f64[]

The axioms of a measure on a finite σ-algebra (its members one per row, with their measures μ): whether μ ≥ 0 and whether μ(∅) = 0, each as 1 or 0; and the additivity gap, the largest |μ(A ∪ B) − μ(A) − μ(B)| over disjoint members A, B, which is 0 for a measure. On a finite σ-algebra countable additivity reduces to additivity over pairs of disjoint sets.

40
is_measurableL3
(SX: f64[m, n], SY: f64[p, k], f: i64[n]) → f64[]

Whether a map f between finite measurable spaces (X, Σ_X) and (Y, Σ_Y), each σ-algebra listed in full, is measurable, as 1 or 0: the preimage f⁻¹(B) of every B ∈ Σ_Y is in Σ_X. The same preimage test as continuity; measurability implies neither continuity nor integrability.

40exactcalls is_continuous
tail_indexL4
(c: i64[m], d: i64[m], p: i64[], q: i64[]) → i64[m], i64[]

The least N ≥ 0 with |u_n − L| = |c|/(n + d) < ε for every n ≥ N, for the sequences u_n = L + c/(n + d) (d ≥ 1) and ε = p/q > 0 given by positive integers, in exact integer arithmetic: N = max(0, ⌊|c|q/p⌋ − d + 1). The error never grows along the tail, so this one N works for the whole tail, which a finite sample of terms could not show; equality |c|/(n + d) = ε does not count. Over a finite domain, one c and d per point, it is a pointwise witness at each point, and their maximum is a uniform one.

40exact

Sequences

std.seq · 90
diffL2
(x: f64[n]) → f64[n−1]

First differences: each element minus the one before it. One element shorter than x.

40exact
cumsumL2
(x: f64[n]) → f64[n]

Running total: element i is the sum of x₀ … xᵢ.

40
cummeanL2
(x: f64[n]) → f64[n]

Running mean: element i is the mean of x₀ … xᵢ. The counts 1, 2, … come from Iota.

40
sum_of_squares_toL2
(x: f64[n]) → f64[]

1² + 2² + … + n², with n the length of x (its values are not used): Iota counts 1 … n, each count is squared, and the squares are added. This is the intent the family home follows through EML-U, EML-P and EML-NOVA; for x of length 100 it is 338350.

40exact
trapezoidL2
(y: f64[n]) → f64[]

Trapezoid rule with unit spacing: the area under the samples y.

40
trapezoid_xyL2
(x: f64[n], y: f64[n]) → f64[]

Trapezoid rule over sample points x (any spacing, in order). Calls diff.

40calls diff
moving_average3L2
(x: f64[n]) → f64[n−2]

Moving average over a window of three, at every position where the window fits.

40
conv1d_k3L2
(x: f64[n], w: f64[3]) → f64[n−2]

One-dimensional convolution with a three-tap kernel w, valid positions only — cross-correlation, as deep-learning libraries define it.

40
ema_stepL0
(s: f64[], x: f64[], alpha: f64[]) → f64[]

One step of an exponential moving average: blend the new value into the running one. The body that ema scans.

40
emaL2
(x: f64[n], alpha: f64[]) → f64[n]

Exponential moving average of a series, started at its first value: a Scan of ema_step.

40calls ema_step
discount_stepL0
(g: f64[], r: f64[], gamma: f64[]) → f64[]

One step of a discounted return: this reward plus γ times the return after it. The body that discounted_returns scans, backwards.

40
discounted_returnsL2
(r: f64[n], gamma: f64[]) → f64[n]

Discounted returns of a reward sequence, as in reinforcement learning: a reverse Scan of discount_step.

40calls discount_step
horner_stepL0
(acc: f64[], c: f64[], t: f64[]) → f64[]

One step of Horner's rule: multiply by t, add the next coefficient. The body that horner scans.

40
hornerL2
(c: f64[n], t: f64[]) → f64[]

Evaluate a polynomial at t by Horner's rule, coefficients from the highest degree down: a Scan of horner_step, keeping the last value.

40calls horner_step
euler_stepL0
(x: f64[k], dt: f64[], A: f64[k, k]) → f64[k]

One forward-Euler step of the linear system x′ = A·x over a time step dt. The body that euler_linear scans.

40
euler_linearL2
(x0: f64[k], A: f64[k, k], dts: f64[n]) → f64[n, k]

Integrate x′ = A·x from x₀ by forward Euler over the time steps dts; returns the state after every step. A Scan of euler_step.

40calls euler_step
permuteL3
(x: f64[n], perm: i64[n]) → f64[n]

Reorder a vector by a permutation: element i of the result is x[perm[i]]. A Gather.

40exact
inverse_permutationL3
(perm: i64[n]) → i64[n]

The inverse of a permutation: inv[perm[i]] = i. Each position is scattered to where it came from, then Cast back to integers.

40exact
newton_sqrt_stepL0
(s: f64[], a: f64[]) → f64[]

One step of Newton's method for √a: average the guess with a divided by it. The body that sqrt_newton runs.

40
sqrt_unconvergedL1
(s: f64[], a: f64[]) → f64[]

Whether a square-root guess still misses: |s² − a| above 10⁻¹² of a, as 1 or 0. The condition sqrt_newton loops on.

40exact
sqrt_newtonL3
(a: f64[]) → f64[]

√a by Newton's method, starting from (a + 1)/2 and stopping once |s² − a| ≤ 10⁻¹²·a: a While over newton_sqrt_step until sqrt_unconverged says stop.

40calls newton_sqrt_step, sqrt_unconverged
bisect_cube_stepL2
(lohi: f64[2], a: f64[]) → f64[2]

One bisection step for x³ = a: halve the bracket [lo, hi], keeping the half where x³ − a changes sign. The body that cbrt_bisect runs.

40exact
bracket_unconvergedL2
(lohi: f64[2], a: f64[]) → f64[]

Whether a bisection bracket is still too wide: hi − lo above 10⁻¹²·(|a| + 1), as 1 or 0. The condition cbrt_bisect loops on.

40exact
cbrt_bisectL3
(a: f64[]) → f64[]

∛a by bisection: start from the bracket ±(|a| + 1), which always contains the root, and halve it until it is narrower than 10⁻¹²·(|a| + 1). A While whose state is the bracket itself.

40calls bisect_cube_step, bracket_unconverged
hash_stepL4
(h: i64[], c: i64[]) → i64[]

One step of a polynomial rolling hash: multiply by 131, add the next code, reduce modulo the prime 1 000 000 007. Every value stays below 2⁵³, so the arithmetic is exact. The body poly_hash scans.

40exact
poly_hashL4
(codes: i64[n]) → i64[]

A polynomial rolling hash of a sequence of byte codes: a Scan of hash_step from 0, keeping the last value. Equal sequences hash equally; it is not a cryptographic hash.

40exactcalls hash_step
fftL4
(z: f64[2, n]) → f64[2, n]

The discrete Fourier transform of a complex vector, unnormalized: yₖ = Σⱼ zⱼ·e^(−2πi·jk/n).

40
ifftL4
(y: f64[2, n]) → f64[2, n]

The inverse discrete Fourier transform: zⱼ = (1/n)·Σₖ yₖ·e^(2πi·jk/n), so ifft(fft(z)) = z.

40
power_spectrumL4
(x: f64[n]) → f64[n]

The power spectrum of a real signal: |yₖ|² for its discrete Fourier transform y, the energy at each frequency.

40
circular_convolveL4
(a: f64[n], b: f64[n]) → f64[n]

The circular convolution of two real signals through the Fourier transform: transform both, multiply, transform back, keep the real part. Takes n log n operations instead of n².

40calls complex_multiply
circular_autocorrelationL4
(x: f64[n]) → f64[n]

The circular autocorrelation of a real signal, rₖ = Σⱼ xⱼ·x₍ⱼ₊ₖ₎ mod n, by the Wiener–Khinchin theorem: the inverse transform of the power spectrum.

40
wichmann_hill_stepL4
(state: i64[3], x: f64[]) → i64[3]

One step of the Wichmann–Hill generator (AS 183, 1982): three small multiplicative congruential generators side by side, each sᵢ ↦ aᵢ·sᵢ mod mᵢ. It is the body uniform_draws scans; the element it is handed only sets how many steps there are.

40exact
uniform_drawsL4
(state: i64[3], x: f64[n]) → f64[n]

One uniform number in [0, 1) for each element of x, from the Wichmann–Hill generator started at state: a Scan of wichmann_hill_step, then the fractional part of s₁/m₁ + s₂/m₂ + s₃/m₃. The same state always gives the same numbers, on every backend. Its period is about 7·10¹²; it is not for cryptography.

40calls wichmann_hill_step
shuffleL4
(x: f64[n], state: i64[3]) → f64[n]

A reproducible random permutation of x: draw one uniform number per element, then sort the elements by their numbers.

40exactcalls uniform_draws
mulhilo32L4
(a: i64[n], b: i64[n]) → i64[2, n]

The 64-bit product of two 32-bit words, as its high and low halves: [⌊a·b/2³²⌋, a·b mod 2³²]. Composed from 16-bit halves, so every intermediate stays below 2³⁴ and int64 holds it exactly; a·b itself would not fit.

40exact
philox4x32_roundL5
(ctr: i64[4, n], r: i64[], key: i64[2]) → i64[4, n]

One round of Philox4x32 on every counter at once: with the round key k = key + r·W mod 2³² and (hi, lo) the halves of M·x, the words (x₀, x₁, x₂, x₃) become (hi₁ ⊕ x₁ ⊕ k₀, lo₁, hi₀ ⊕ x₃ ⊕ k₁, lo₀). The body that philox4x32_10 scans, once per round r.

40exactcalls mulhilo32
philox4x32_10L5
(ctr: i64[4, n], key: i64[2]) → i64[4, n]

Philox4x32-10: ten rounds of philox4x32_round (a Scan over r = 0 … 9) on four-word counters under a two-word key. Random123's generator: each output depends only on its counter and the key, so a tensor of counters draws all its numbers at once. Its authors report that it passes TestU01's BigCrush.

40exactcalls philox4x32_round
philox_uniformL5
(counter: i64[n], key: i64[2]) → f64[n]

Uniform draws in (0, 1) from Philox4x32-10, one per counter, under a key: 52 bits, the high 20 of the first word and all 32 of the second, as (v + ½)/2⁵². Exact in float64, and never 0 or 1. A key is a stream; counters 0, 1, 2, … are its draws, reproducible on every backend.

40exactcalls philox4x32_10
philox_normalL5
(counter: i64[n], key: i64[2]) → f64[n]

Standard normal draws from Philox4x32-10, one per counter: Φ⁻¹ of philox_uniform. Inverse-transform sampling; the uniform never reaches 0 or 1, so every draw is finite (|z| < 8.3).

40calls philox_uniform
simpsonL2
(y: f64[2*m+1], h: f64[]) → f64[]

Composite Simpson's rule on 2m + 1 equally spaced samples y with spacing h: (h/3)(y₀ + 4y₁ + 2y₂ + … + 4y₂ₘ₋₁ + y₂ₘ). It is exact for cubics, and for smooth functions its error falls as h⁴. The samples are read in pairs by reshaping 2m values into m rows of two, which the shape checker proves for every m.

40
legendre_stepL0
(p: f64[n], q: f64[n], k: f64[], x: f64[n]) → f64[n], f64[n]

One step of the Legendre recurrence (k + 1)Pₖ₊₁(x) = (2k + 1)·x·Pₖ(x) − k·Pₖ₋₁(x), at every point of x at once: from (Pₖ₋₁, Pₖ) to (Pₖ, Pₖ₊₁). The body that gauss_legendre scans.

40
gauss_legendreL3
(points: f64[n]) → f64[n], f64[n]

The n-point Gauss–Legendre rule on [−1, 1], n the length of points (only its length is read): nodes x ascending and weights w, so that Σ wᵢ·f(xᵢ) is exact for every polynomial of degree up to 2n − 1. By Golub–Welsch: the nodes are the eigenvalues of the symmetric tridiagonal Jacobi matrix with off-diagonal βₘ = m/√(4m² − 1), then one Newton step on Pₙ, which is zero in exact arithmetic and brings each node to within about a unit of roundoff; each weight is 2(1 − x²)/(n·Pₙ₋₁(x))², with Pₙ and Pₙ₋₁ from the three-term recurrence.

40calls legendre_step
interp_linearL3
(xq: f64[q], x: f64[n], y: f64[n]) → f64[q]

Piecewise-linear interpolation through the points (xⱼ, yⱼ), x increasing, at each query point xq; beyond either end, the end value. NumPy's np.interp. The segment is found by counting the xⱼ at or below each query, exactly.

40
divided_difference_stepL0
(d: f64[n], m: f64[n], g: f64[n], S: f64[n, n]) → f64[n]

One column of Newton's divided-difference table: where the mask m is 1, dᵢ becomes (dᵢ − dᵢ₋₁)/gᵢ, with gᵢ = xᵢ − xᵢ₋ₖ; where it is 0, dᵢ stays. S shifts a vector down by one. The body that divided_differences scans, one order k per step.

40
divided_differencesL2
(x: f64[n], y: f64[n]) → f64[n]

The coefficients of Newton's form of the polynomial through (xⱼ, yⱼ), x distinct: cₖ = f[x₀, …, xₖ], the divided differences. A Scan of divided_difference_step, one order per step, so that p(t) = c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂).

40calls divided_difference_step
newton_horner_stepL0
(p: f64[q], ck: f64[], xk: f64[], t: f64[q]) → f64[q]

One step of Horner's rule for Newton's form: p ← cₖ + (t − xₖ)·p, at every t. The body that newton_eval scans, from the last coefficient down.

40
newton_evalL2
(c: f64[n], x: f64[n], t: f64[q]) → f64[q]

Evaluate a polynomial in Newton's form, c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂), at each t, by Horner's rule: a reverse Scan of newton_horner_step.

40calls newton_horner_step
poly_interpL2
(xq: f64[q], x: f64[n], y: f64[n]) → f64[q]

The polynomial of degree n − 1 through the n points (xⱼ, yⱼ), x distinct, evaluated at each query point xq: Newton's divided differences, then Horner's rule for Newton's form. The same polynomial as Lagrange's formula, the reference.

40calls divided_differences, newton_eval
poly_derivativeL2
(c: f64[n]) → f64[n−1]

The derivative of a polynomial, coefficients from the highest degree down as horner takes them: cₖ·(n − 1 − k) for every coefficient but the constant. NumPy's np.polyder.

40exact
poly_integralL2
(c: f64[n]) → f64[n+1]

The antiderivative of a polynomial that is 0 at t = 0, coefficients from the highest degree down: cₖ/(n − k), then a zero constant term. NumPy's np.polyint.

40exact
poly_multiplyL3
(f: f64[a], g: f64[c]) → f64[a+c−1]

The product of two polynomials, coefficients highest degree first as horner takes them: (fg)ₖ = Σᵢ fᵢ·gₖ₋ᵢ, the finite convolution, computed as a Toeplitz matrix of g times f. Exact for integer coefficients, where every product and sum is an integer. NumPy's np.polymul.

40
poly_identityL3
(p: f64[a+c], f: f64[a], g: f64[c+1]) → f64[], f64[a+c]

Whether p = f·g as polynomials, as 1 or 0: the product's coefficients, every list highest degree first, compared with p's one by one, not at sample points; and the product itself. Factors and product are compared as given, so leading zeros must be removed first, and a rescaled or reordered factor is the caller's to normalize. Exact for integer coefficients; for rational ones, multiply p by the product of the factors' denominators, and each factor by its own, first.

40exact
poly_degreeL2
(c: f64[n]) → f64[], f64[], f64[]

The degree of a polynomial, coefficients highest degree first: whether it has one (1 or 0: the zero polynomial has no degree), the degree n − 1 − k for the first nonzero coefficient cₖ, and that leading coefficient; 0 for both when there is no degree. Leading zeros do not change the polynomial, and −0 counts as zero. Exact.

40exact
npvL2
(c: f64[T], i: f64[]) → f64[]

The net present value of a cash flow c₀, c₁, … at one per period, at rate i per period: Σ cₜ/(1 + i)ᵗ, with c₀ undiscounted. Computed as the discounted return at factor 1/(1 + i), by Horner's rule from the last cash flow back.

40calls discounted_returns
recurrence_stepL0
(w: f64[r], t: f64[], C: f64[r, r], bv: f64[r]) → f64[r]

One step of a linear recurrence in companion form: the window of the last r terms becomes C·window + b, where C shifts the window up and puts Σ coefficients·window in the last place. The body linear_recurrence scans.

40
linear_recurrenceL2
(init: f64[r], coeffs: f64[r], constant: f64[], steps: f64[s]) → f64[s]

The next s terms of a linear recurrence of order r: aₙ = constant + Σⱼ coeffsⱼ·aₙ₋ᵣ₊ⱼ, from the initial values a₀ … aᵣ₋₁, s the length of steps (only its length is read). A Scan of recurrence_step on the companion matrix. Fibonacci is r = 2, coefficients (1, 1), constant 0.

40calls recurrence_step
growth_stepL0
(x: f64[m], t: f64[], rate: f64[m]) → f64[m]

One step of the discrete exponential model: x ← r·x. The body geometric_growth scans.

40exact
geometric_growthL2
(x0: f64[m], rate: f64[m], steps: f64[s]) → f64[s, m]

The trajectory of the discrete exponential model xₙ₊₁ = r·xₙ for s steps, s the length of steps (only its length is read): row n is x₀·rⁿ⁺¹. A Scan of growth_step.

40calls growth_step
logistic_stepL0
(x: f64[m], t: f64[], rate: f64[m], K: f64[m]) → f64[m]

One step of the discrete logistic model: x ← x + r·x·(1 − x/K). The body logistic_growth scans.

40
logistic_growthL2
(x0: f64[m], rate: f64[m], K: f64[m], steps: f64[s]) → f64[s, m]

The trajectory of the discrete logistic model xₙ₊₁ = xₙ + r·xₙ(1 − xₙ/K) for s steps, s the length of steps (only its length is read). With K > 0, 0 ≤ r ≤ 1 and 0 ≤ x ≤ K, every step stays in [0, K], and 0 and K are fixed points. A Scan of logistic_step.

40calls logistic_step
dfa_stepL3
(state: i64[], symbol: i64[], delta: i64[q, a]) → i64[]

One transition of a deterministic finite automaton: state ← δ(state, symbol), read from the transition table δ. The body dfa_run scans.

40exact
dfa_runL3
(delta: i64[q, a], start: i64[], accept: f64[q], word: i64[L]) → f64[], i64[]

Run a deterministic finite automaton on a word: from the start state, one transition per symbol through dfa_step, then accept when the final state is accepting. accept is 1 or 0 per state. The empty word is accepted exactly when the start state is accepting.

40exactcalls dfa_step
nfa_stepL3
(S: f64[k], symbol: i64[], T: f64[a, k, k], C: f64[k, k]) → f64[k]

One symbol of a nondeterministic finite automaton run on the set of current states (a 0/1 vector): every transition on the symbol, then every ε-move, through the ε-closure C. The body nfa_accepts scans.

40exactcalls vecmat
nfa_acceptsL3
(T: f64[a, k, k], E: f64[k, k], start: f64[k], accept: f64[k], word: i64[L]) → f64[]

Whether a nondeterministic finite automaton with ε-moves accepts a word, as 1 or 0: the subset simulation, carrying the set of reachable states as a 0/1 vector. T[σ] is the 0/1 transition relation of symbol σ, E the ε-moves, and C its reflexive transitive closure (reachability). The reference follows the sets of states directly.

40exactcalls dot, reachability, vecmat, nfa_step
poisson_fd_1dL3
(f: f64[n], h: f64[], ua: f64[], ub: f64[]) → f64[n]

The finite-difference solution of the boundary-value problem −u″ = f on a uniform grid with spacing h and Dirichlet values u_a, u_b at the two ends: the values at the n interior points, from (2uᵢ − uᵢ₋₁ − uᵢ₊₁)/h² = fᵢ. One solve of the tridiagonal system. It is exact for every quadratic u. The reference is the Thomas algorithm.

40
laplacian_2dL2
(U: f64[m+2, n+2], h: f64[]) → f64[m, n]

The five-point Laplacian (uᵢ₋₁,ⱼ + uᵢ₊₁,ⱼ + uᵢ,ⱼ₋₁ + uᵢ,ⱼ₊₁ − 4uᵢⱼ)/h² at the interior points of a grid of values with spacing h. It equals the exact Laplacian for every polynomial of degree at most 3, so a candidate solution of Poisson's equation can be checked on a grid.

40
quadratic_laplacianL2
(c: f64[6]) → f64[]

The Laplacian of the quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y², a constant: 2c₃ + 2c₅. Poisson's equation Δu = f holds inside a domain for a quadratic candidate exactly when f is that constant.

40exact
quadratic_on_xL2
(c: f64[6], x0: f64[]) → f64[3]

The quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y² restricted to the line x = x₀: a quadratic in y, coefficients highest degree first, (c₅, c₂ + c₄x₀, c₀ + c₁x₀ + c₃x₀²). Comparing them with the Dirichlet data on an edge, coefficient by coefficient, checks the boundary condition exactly.

40
quadratic_on_yL2
(c: f64[6], y0: f64[]) → f64[3]

The quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y² restricted to the line y = y₀: a quadratic in x, coefficients highest degree first, (c₃, c₁ + c₄y₀, c₀ + c₂y₀ + c₅y₀²).

40
geometric_seriesL4
(a: f64[s], r: f64[s], N: i64[s]) → f64[s], f64[s], f64[s], f64[s]

The geometric series Σ_{k≥0} a·rᵏ, elementwise: the partial sum of its first N terms, a(1 − rᴺ)/(1 − r) (N·a for r = 1); and, where |r| < 1, its limit a/(1 − r) and the remainder a·rᴺ/(1 − r) after N terms, with converges = 1. Where |r| ≥ 1 the series diverges (or, for r = −1, oscillates), and the limit, remainder and converges are 0. The reference adds the N terms one by one.

40calls ipow
telescoping_sumL2
(bseq: f64[n]) → f64[]

The telescoping sum Σ_{k=0}^{N−1} (b_k − b_{k+1}) = b_0 − b_N of a sequence b_0 … b_N: every inner term cancels. The infinite series converges exactly when b_N has a limit, to b_0 − lim b_N.

40exact
radius_estimatesL2
(a: f64[n]) → f64[], f64[]

Two estimates of the radius of convergence R of Σ aₙ(x − c)ⁿ from its coefficients a₀ … a_N: the ratio |a_{N−1}/a_N| and the root |a_N|^(−1/N). Each converges to R when the corresponding limit exists, and for aₙ = qⁿ both equal 1/|q|. A finite prefix of coefficients does not determine R, so these are estimates, not the radius.

40
harmonic_oscillatorL5
(x0: f64[], v0: f64[], m: f64[], k: f64[], t: f64[s]) → f64[s], f64[s]

The motion of the linear harmonic oscillator m·x″ + k·x = 0 with mass m > 0 and stiffness k > 0, from x(0) = x₀ and x′(0) = v₀: x(t) = x₀ cos ωt + (v₀/ω) sin ωt and v(t) = v₀ cos ωt − x₀ω sin ωt, with ω = √(k/m). The energy ½mv² + ½kx² is constant.

40
synth_stepL0
(prev: f64[], cj: f64[], mj: f64[], a: f64[]) → f64[]

One coefficient of a synthetic-division pass: out = cⱼ + mⱼ·a·(the previous output), where the mask mⱼ says whether this coefficient takes part in the pass. The body taylor_pass scans.

40
taylor_passL2
(c: f64[n], t: f64[], a: f64[]) → f64[n]

Pass t of the Taylor shift by repeated synthetic division: coefficients 1 … n − 1 − t each add a times the coefficient just before them, as already updated. The body poly_taylor_at scans.

40calls synth_step
poly_taylor_atL2
(c: f64[n], a: f64[]) → f64[n]

The Taylor coefficients of a polynomial at a: the coefficients of p in powers of (x − a), highest degree first, so the last is p(a), the one before it p′(a), and the k-th from the end p⁽ᵏ⁾(a)/k!. By repeated synthetic division, n passes of taylor_pass. A polynomial of degree at most n − 1 is reconstructed exactly. The reference is the closed form with binomial coefficients.

40calls taylor_pass
cyk_stepL3
(X: f64[k, n, n], t: f64[], RB: i64[q], RC: i64[q], OHt: f64[k, q]) → f64[k, n, n]

One closure step of the CYK recognizer for a grammar in Chomsky normal form: X[A, i, j] = 1 when A derives the part w[i:j] of the word; for every rule A → B C (listed as RB, RC with the one-hot heads OHt) and every split point, a derivation of w[i:k] is added. The body cyk scans.

40exact
cykL3
(Tm: f64[k, s], RA: i64[q], RB: i64[q], RC: i64[q], start: i64[], word: i64[L]) → f64[], f64[k, L+1, L+1]

Whether a grammar in Chomsky normal form derives a word, as 1 or 0, by the CYK recognizer, and the table X[A, i, j] of which nonterminals derive which parts w[i:j]. The grammar is k nonterminals, terminal rules Tm[A, σ] for A → σ, binary rules A → B C listed as RA, RB, RC, and a start symbol. The table is closed under the binary rules by L steps of cyk_step, each one batched product per rule. A word of length L ≥ 1; CYK decides membership, unlike a bounded search, whose failure would prove nothing.

40exactcalls cyk_step
tm_stepL3
(state: f64[], head: f64[], tape: f64[T], fell: f64[], t: f64[], Next: i64[g, c], Write: i64[g, c], Move: i64[g, c], halting: f64[g]) → f64[], f64[], f64[T], f64[]

One step of a deterministic Turing machine on a tape of T listed cells (unlisted cells are blank and never needed while fell stays 0): in state q reading σ, write Write[q, σ], move by Move[q, σ] ∈ {−1, 0, +1}, and enter Next[q, σ]; a halting state (accept or reject) has no transitions and stays put. fell becomes 1 if the head would leave the listed tape. The body tm_run scans.

40exact
tm_runL3
(start: f64[], tape: f64[T], steps: f64[s], Next: i64[g, c], Write: i64[g, c], Move: i64[g, c], halting: f64[g]) → f64[], f64[], f64[T], f64[], f64[]

Run a deterministic Turing machine for s steps (s the length of steps, only its length read) from the start state with the head on cell 0 of the listed tape: a Scan of tm_step. Returns the final state, head and tape, whether the head ever tried to leave the listed tape, and whether the machine has halted. A finite trace settles that one input only: a run that has not halted proves neither rejection nor non-termination, and one halting trace does not make the machine a decider.

40exactcalls tm_step
taylor_remainderL2
(c: f64[m], a: f64[], x: f64[], n: f64[]) → f64[], f64[], f64[]

For a polynomial p (coefficients highest degree first), a center a, a point x and an order n: p(x), the Taylor polynomial T_n(x) of p at a, and the remainder p(x) − T_n(x), computed directly. The remainder is 0 when n ≥ deg p. A finite jet says nothing about the Taylor series of a non-polynomial function, or about analyticity.

40exactcalls horner, poly_taylor_at
poly_definite_integralL2
(c: f64[m], a: f64[], b: f64[]) → f64[m+1], f64[]

The fundamental theorem of calculus for a polynomial f (coefficients highest degree first): an antiderivative F with F(0) = 0, and the directed integral ∫_a^b f = F(b) − F(a); reversed limits change its sign and equal ones give 0.

40calls horner, poly_integral
antiderivative_checkL2
(F: f64[m+1], f: f64[m]) → f64[]

Whether a candidate polynomial F is an antiderivative of the polynomial f, F′ = f, checked coefficient by coefficient (coefficients highest degree first, F one longer than f), as 1 or 0. A candidate that fails does not show that f has no antiderivative; agreement at sampled points would not show F′ = f.

40exact
quadratic_pde_residualL3
(u: f64[6], coef: f64[6], g: f64[6]) → f64[6], f64[]

The residual of a quadratic candidate u = u₀ + u₁x + u₂y + u₃x² + u₄xy + u₅y² in the linear constant-coefficient equation a·u_xx + b·u_xy + c·u_yy + d·u_x + e·u_y + f·u = g, where g is a quadratic in the same basis, as a coefficient vector: u solves the equation everywhere exactly when every coefficient is 0 (a zero residual at one point proves only that point). Also the discriminant b² − 4ac of the principal part (by this convention: negative elliptic, zero parabolic, positive hyperbolic).

40exact
quadratic2_evalL3
(u: f64[6], pts: f64[m, 2]) → f64[m]

The values of the two-variable real polynomial u₀ + u₁x + u₂y + u₃x² + u₄xy + u₅y² (coefficients in that fixed order) at given points (x, y), the rows of pts.

40exactcalls matvec
regex_node_stepL3
(Ms: f64[K, n, n], k: f64[], kind: i64[K], sym: i64[K], left: i64[K], right: i64[K], W: f64[n]) → f64[K, n, n]

One node of a regular expression's syntax tree, evaluated on the word's parts: the node's 0/1 span matrix over the fenceposts, from its children's matrices: ε the identity, a symbol the single steps that read it, union the elementwise or, concatenation the boolean product, star the reflexive transitive closure (reachability), the empty language 0. The body regex_match scans.

40exactcalls reachability
regex_matchL3
(kind: i64[K], sym: i64[K], left: i64[K], right: i64[K], word: i64[L]) → f64[]

Whether a word is in the language of a regular expression, as 1 or 0, decided exactly: the syntax tree is listed node by node, children first (kind 0 empty, 1 ε, 2 symbol, 3 union, 4 concatenation, 5 star), the last node the root, and each node's span matrix over the word's fenceposts comes from its children's by regex_node_step. Star is the full closure, not a bounded unrolling, so membership is decided rather than searched. Two expressions agreeing on all words up to some length are not shown equal.

40exactcalls regex_node_step
pda_stepL3
(state: f64[], pos: f64[], stack: f64[H], h: f64[], valid: f64[], x: f64[], Tfrom: i64[t], Tin: i64[t], Ttop: i64[t], Tto: i64[t], Tlen: i64[t], Tpush: i64[t, 2], wordf: f64[L]) → f64[], f64[], f64[H], f64[], f64[]

One step of checking a pushdown automaton's run: apply transition x if it fits the configuration (its from-state is the current state, it reads the next input symbol or ε, and the stack top is the symbol it needs): pop that top, push its replacement bottom to top, and move to its to-state. A transition that does not fit, or would overflow the listed stack, makes the run invalid and leaves the configuration as it was. The body pda_run_check scans.

40exact
pda_run_checkL3
(start: f64[], stack0: f64[H], h0: f64[], Tfrom: i64[t], Tin: i64[t], Ttop: i64[t], Tto: i64[t], Tlen: i64[t], Tpush: i64[t, 2], accept: f64[Q], word: i64[L], run: i64[m]) → f64[], f64[]

Whether a given run, a list of transition indices, is an accepting run of a pushdown automaton on a word, as 1 or 0: every step fits its configuration (pda_step), the whole input is read, and the final state is accepting (acceptance by final state, not by empty stack); and whether every step fitted. A run is a witness of membership; failing to find one by a bounded search proves nothing, and says nothing about the automaton's determinism or its grammar.

40exactcalls pda_step
dfa_pumping_splitL3
(delta: i64[q, a], start: i64[], word: i64[L]) → f64[], f64[], f64[], f64[]

The pumping-lemma split of a word read by a DFA: the first repeated state among the states after 0, 1, …, L symbols gives w = xyz with x the part before the first visit, y the loop (|y| > 0), and |xy| ≤ the number of states when the word is at least that long (pigeonhole). Reading y returns the automaton to the same state, so xyⁱz is accepted exactly when w is, for every i ≥ 0: the loop is a certificate for all i, not a check of a few. Also whether a repeat exists and the loop's state.

40exactcalls dfa_step

Neural networks

std.nn · 15
linearL0
(X: f64[m, k], W: f64[k, n], b: f64[n]) → f64[m, n]

Affine layer: a batch of rows times a weight matrix, plus a bias.

40
mlp2L0
(X: f64[m, k], W1: f64[k, h], b1: f64[h], W2: f64[h, n], b2: f64[n]) → f64[m, n]

Two-layer perceptron with a ReLU between the layers. Calls linear twice.

40calls linear
attentionL0
(Q: f64[m, d], K: f64[t, d], V: f64[t, e], scale: f64[]) → f64[m, e]

Scaled dot-product attention for one head.

40
log_softmaxL1
(x: f64[n]) → f64[n]

Log of the softmax, computed as x − logsumexp(x) without forming the softmax. Calls logsumexp.

40calls logsumexp
layernormL1
(x: f64[n], gamma: f64[n], beta: f64[n], eps: f64[]) → f64[n]

Layer normalisation of one feature vector, with scale γ, shift β and a small ε. Calls variance.

40calls variance
attention_scaledL1
(Q: f64[m, d], K: f64[t, d], V: f64[t, e]) → f64[m, e]

Scaled dot-product attention with the standard 1/√d scale computed inside the graph (Size, then Sqrt). Calls attention.

40calls attention
rnn_cellL0
(h: f64[k], x: f64[m], W: f64[k, k], U: f64[k, m], b: f64[k]) → f64[k]

One step of an Elman recurrent network: the next hidden state from the current one and an input. The body that rnn scans.

40
rnnL2
(h0: f64[k], X: f64[n, m], W: f64[k, k], U: f64[k, m], b: f64[k]) → f64[n, k]

Run an Elman recurrent network over a sequence of inputs; returns every hidden state. A Scan of rnn_cell, differentiable end to end.

40calls rnn_cell
lstm_cellL3
(h: f64[k], c: f64[k], x: f64[m], W: f64[4, k, k], U: f64[4, k, m], b: f64[4, k]) → f64[k], f64[k]

One step of a long short-term memory (LSTM) cell: from the hidden state h, the cell state c and an input x, the next h and c. The four gates (input, forget, output, candidate) each take their weights from W, U and b by index. The body that lstm scans.

40
lstmL3
(h0: f64[k], c0: f64[k], X: f64[n, m], W: f64[4, k, k], U: f64[4, k, m], b: f64[4, k]) → f64[n, k], f64[n, k]

Run an LSTM over a sequence of inputs; returns every hidden state and every cell state. A Scan of lstm_cell with two carries, h and c (Round 14.10), differentiable end to end.

40calls lstm_cell
accuracyL2
(logits: f64[n, c], labels: f64[n, c]) → f64[]

Classification accuracy: the share of rows whose largest logit is at the position of the largest label entry (one-hot labels).

40exact
causal_attentionL2
(Q: f64[n, d], K: f64[n, d], V: f64[n, d]) → f64[n, d]

Causal (decoder) self-attention: row i attends only to rows j ≤ i. The mask compares positions from Iota (j > i is the future); future scores are replaced by the row minimum before the stable softmax, so nothing can overflow, and their weights are set to zero after it.

40
embedding_lookupL3
(E: f64[v, d], ids: i64[k]) → f64[k, d]

Embedding lookup: the rows of the table E at the integer ids, in order (repeats allowed).

40exact
embedding_bag_meanL3
(E: f64[v, d], ids: i64[k]) → f64[d]

The mean of the embeddings of a bag of ids: one vector for a whole set of tokens. Calls embedding_lookup.

40calls embedding_lookup
gp_posterior_meanL3
(X: f64[n, d], y: f64[n], Xs: f64[m, d], ell: f64[], noise: f64[]) → f64[m]

The posterior mean of a Gaussian process with a squared-exponential kernel of length scale ℓ and noise variance σ², at new points Xs. The training system is solved by Cholesky (calls cholesky_solve).

40calls cholesky_solve

Losses

std.loss · 11
mseL0
(y: f64[n], t: f64[n]) → f64[]

Mean squared error.

40
maeL0
(y: f64[n], t: f64[n]) → f64[]

Mean absolute error. Calls abs.

40calls abs
hingeL0
(s: f64[n], y: f64[n]) → f64[]

Hinge loss for labels ±1 and real-valued scores.

40
l2_penaltyL0
(W: f64[k, n], lam: f64[]) → f64[]

L2 weight penalty. Calls frobenius_sq.

40calls frobenius_sq
cross_entropyL1
(logits: f64[n], target: f64[n]) → f64[]

Cross-entropy between a target distribution and the softmax of logits. Calls log_softmax.

40calls log_softmax
huberL1
(y: f64[n], t: f64[n], delta: f64[]) → f64[]

Huber loss: quadratic for small errors, linear beyond δ. Calls abs.

40calls abs
binary_cross_entropyL1
(p: f64[n], t: f64[n]) → f64[]

Binary cross-entropy for probabilities strictly between 0 and 1.

40
log_coshL1
(y: f64[n], t: f64[n]) → f64[]

Log-cosh loss, in a form that never overflows. Calls abs.

40calls abs
nll_labelsL3
(logp: f64[n, c], labels: i64[n]) → f64[]

Negative log-likelihood with integer class labels: minus the mean of each row's log-probability at its label.

40
cross_entropy_labelsL3
(logits: f64[n, c], labels: i64[n]) → f64[]

Softmax cross-entropy over rows of logits with integer labels, the way classifiers are trained: a stable log-softmax per row, then nll_labels.

40calls nll_labels
bce_with_logitsL5
(z: f64[n], t: f64[n]) → f64[]

Binary cross-entropy taken from logits: max(z, 0) − z·t + log1p(e^(−|z|)), computed as two smooth branches (z ≥ 0 and z < 0). It never forms the probability, so it stays finite and accurate where sigmoid would round to 0 or 1.

40

Optimization

std.optim · 21
sgd_stepL0
(params: f64[n], grad: f64[n], lr: f64[]) → f64[n]

One step of gradient descent: params − lr·grad.

40
momentum_stepL2
(state: f64[2, n], grad: f64[n], lr: f64[], beta: f64[]) → f64[2, n]

One step of gradient descent with heavy-ball momentum, on the state [params; velocity]: v ← β·v + grad, then params ← params − lr·v.

40
adam_stepL2
(state: f64[3, n], grad: f64[n], t: f64[], lr: f64[], beta1: f64[], beta2: f64[], eps: f64[]) → f64[3, n]

One step of Adam (Kingma and Ba) on the state [params; m; v] at step t (1, 2, …): m ← β₁m + (1 − β₁)g, v ← β₂v + (1 − β₂)g², then params ← params − lr·m̂/(√v̂ + ε) with the bias corrections m̂ = m/(1 − β₁ᵗ), v̂ = v/(1 − β₂ᵗ).

40
clip_by_normL1
(grad: f64[n], max_norm: f64[]) → f64[n]

Gradient clipping by norm: the gradient scaled by min(1, max_norm/‖g‖), computed as max_norm/max(‖g‖, max_norm) so a zero gradient stays zero.

40
logistic_gradL1
(w: f64[d], X: f64[n, d], y: f64[n]) → f64[d]

The gradient of logistic regression's mean binary cross-entropy in the weights: Xᵀ(σ(Xw) − y)/n. Written out; a test checks it against NOVA's reverse mode applied to bce_with_logits.

40
logistic_adam_stepL2
(state: f64[3, d], tl: f64[2], X: f64[n, d], y: f64[n]) → f64[3, d]

One training step of logistic regression with Adam (β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸): the gradient from logistic_grad, then adam_step at the step's (t, lr). The body that logistic_fit_adam scans.

40calls adam_step, logistic_grad
logistic_fit_adamL3
(X: f64[n, d], y: f64[n], lr: f64[s]) → f64[d]

Logistic regression trained inside the graph: a Scan of logistic_adam_step over a learning-rate schedule, one step per entry of lr, from zero weights. Returns the weights after the last step. Every step is verified like any other entry, so the trained model is reproducible to the bit on every backend.

40calls logistic_adam_step
adam_descent_stepL2
(state: f64[3, d], tl: f64[2], X: f64[n, d], y: f64[n]) → f64[3, d]

One Adam step (β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸) for any model, given its gradient df(w, X, y): a template over df. With df = logistic_grad it is logistic_adam_step.

40calls adam_step
minimize_adamL3
(X: f64[n, d], y: f64[n], lr: f64[s]) → f64[d]

Training for any model with Adam, from zero weights, one step per entry of the learning-rate schedule lr: a Scan of adam_descent_step. A template over the model's gradient df(w, X, y). With df = logistic_grad it is logistic_fit_adam, bit for bit.

40calls adam_descent_step
logistic_lossL5
(w: f64[d], X: f64[n, d], y: f64[n]) → f64[]

Logistic regression's loss: the mean binary cross-entropy of the logits Xw against y, through bce_with_logits. Bind its gradient as @grad[f=std.optim.logistic_loss,wrt=w] and minimize_adam trains on the loss alone; NOVA derives the gradient by reverse mode.

40calls bce_with_logits
gd_stepL1
(w: f64[d], lr: f64[], X: f64[n, d], y: f64[n]) → f64[d]

One step of gradient descent for any model, given its gradient df(w, X, y): w − η·df(w, X, y). A template over df; the body minimize_gd scans.

40
minimize_gdL2
(X: f64[n, d], y: f64[n], lr: f64[s]) → f64[d]

Plain gradient descent for any model, from zero weights, one step per entry of the learning-rate schedule lr: a Scan of gd_step. A template over the model's gradient df(w, X, y); bound to @grad of a loss, NOVA derives the gradient by reverse mode.

40calls gd_step
lp_standard_formL2
(A: f64[m, n], b: f64[m]) → f64[m, n+m]

The standard form of the constraints A·x ≤ b, x ≥ 0: the matrix [A | I], so that A·x + s = b with slacks s ≥ 0. Feasibility and the objective cᵀx carry over both ways between x and (x, s). The other conversions are done before it: a ≥ row is multiplied by −1, an equality becomes two ≤ rows, a free variable is x⁺ − x⁻, and minimizing cᵀx is maximizing −cᵀx.

40exact
lp_slacksL0
(A: f64[m, n], b: f64[m], x: f64[n]) → f64[m]

The slacks s = b − A·x of the constraints A·x ≤ b at a point x: x satisfies them exactly when every slack is non-negative.

40calls matvec
simplex_runningL1
(T: i64[m+1, n+m+1], basis: i64[m], D: i64[], status: i64[]) → f64[]

Whether the simplex method is still pivoting: status 2, as 1 or 0. It becomes 1 at an optimum and 0 when the problem is unbounded. The condition simplex_max loops on.

40exact
simplex_stepL4
(T: i64[m+1, n+m+1], basis: i64[m], D: i64[], status: i64[]) → i64[m+1, n+m+1], i64[m], i64[], i64[]

One pivot of the fraction-free simplex method on an integer tableau, by Bland's rule: the entering column is the first with a negative reduced cost; the leaving row has the smallest ratio rhs/column over positive entries, compared by cross-multiplication, ties to the smallest basic variable. Every row but the pivot row becomes (p·row − T[i, k]·row r)/D, an exact integer division, and D becomes the pivot p. With no entering column the status becomes 1 (optimal); with no leaving row, 0 (unbounded). The body simplex_max runs.

40exact
simplex_maxL4
(A: i64[m, n], b: i64[m], c: i64[n]) → i64[], i64[], i64[], i64[n], i64[m], i64[]

Maximize cᵀx subject to A·x ≤ b and x ≥ 0, for integer A, b ≥ 0 and c, by the fraction-free simplex method with Bland's rule: a While over simplex_step on the integer tableau [A | I | b; −c | 0 | 0]. Every entry stays an integer, so every decision is exact. status is 1 at an optimum and 0 when the objective is unbounded. The optimum is z_num/z_den in lowest terms; x and the duals y are x_num/den and y_num/den, and bᵀy = cᵀx by strong duality. The reference is the ordinary simplex method on Fractions.

40exactcalls gcd, simplex_running, simplex_step
lp_weak_dualityL1
(A: f64[m, n], b: f64[m], c: f64[n], x: f64[n], y: f64[m]) → f64[], f64[], f64[], f64[], f64[]

Weak duality for max cᵀx, A·x ≤ b, x ≥ 0 and its dual min bᵀy, Aᵀy ≥ c, y ≥ 0: whether x and y are feasible, and the three numbers cᵀx ≤ yᵀAx ≤ bᵀy, which feasibility guarantees. Feasible x and y with cᵀx = bᵀy are both optimal, a certificate for each.

40calls dot, matvec, vecmat
lagrange_projectionL0
(c: f64[n], g: f64[n], h: f64[]) → f64[n], f64[], f64[n], f64[]

The Lagrange condition for minimizing ‖x − c‖² subject to one linear constraint g·x = h (g ≠ 0): the minimizer x* = c − ((g·c − h)/‖g‖²)·g, the multiplier λ with ∇f(x*) = λ·∇(g·x) (this sign convention), and the residuals of stationarity, 2(x* − c) − λg, and of feasibility, g·x* − h, both 0. The condition is necessary, not sufficient, in general; here the problem is convex, so x* is the global minimizer. It is not the KKT condition for inequalities.

40calls dot
convex_quadratic_on_intervalL1
(A: f64[], B: f64[], C: f64[], lo: f64[], hi: f64[]) → f64[], f64[], f64[]

Minimizing f(x) = A·x² + B·x + C over a closed interval [lo, hi]: whether f is convex there (A ≥ 0, which makes the problem a convex optimization problem, the interval being convex), as 1 or 0; a minimizer, the vertex −B/(2A) clipped to the interval when A > 0, otherwise the better endpoint (the first, lo, on a tie); and the minimum value. Comparing two feasible points, or one Jensen instance, decides nothing in general; the global answer here comes from the closed form.

40exact
finite_optimizeL2
(f: f64[n], feasible: f64[n]) → f64[], f64[], f64[], f64[n], f64[], f64[]

An optimization problem over a finite list of candidates with their objective values and a feasibility mask: whether any candidate is feasible; the minimum over the feasible set, the first feasible minimizer, and all the minimizers (an optimum may be attained more than once); and the maximum and the first maximizer. On a finite set these are its infimum and supremum. Conclusions hold for the listed set only.

40exact

Functions

std.func · 15
composeL0
(x: f64[n]) → f64[n]

Function composition, g ∘ f: x ↦ g(f(x)), for any two functions from a vector to a vector of the same length. A template: bind f and g with an instance id, std.func.compose[f=…,g=…].

40
map_rows_stepL0
(carry: f64[n], x: f64[n]) → f64[n]

One row of map_rows: f(x), ignoring the carry. The body map_rows scans; a template over f.

40exact
map_rowsL2
(X: f64[n, m]) → f64[n, m]

f applied to every row of a matrix: a Scan over the rows whose body, map_rows_step, ignores its carry. A template over f, verified through f = log_softmax, where mapping row by row matters.

40calls map_rows_step
rk4_stepL0
(y: f64[n], h: f64[]) → f64[n]

One classical Runge–Kutta step for y′ = f(y): y + (h/6)(k₁ + 2k₂ + 2k₃ + k₄) with k₁ = f(y), k₂ = f(y + (h/2)k₁), k₃ = f(y + (h/2)k₂), k₄ = f(y + h·k₃). The body rk4 scans; a template over the vector field f.

40
rk4L3
(y0: f64[n], h: f64[s]) → f64[n]

Integrate y′ = f(y) by classical Runge–Kutta from y₀, one step per entry of h (the step sizes): a Scan of rk4_step, returning the final state. A template over the vector field f, verified through f = silu; a test integrates y′ = −y and checks e^(−t) to the method's fourth order.

40calls rk4_step
gauss_quadL3
(a: f64[], b: f64[], points: f64[n]) → f64[]

∫ₐᵇ f(t) dt by n-point Gauss–Legendre quadrature, n the length of points: the rule's nodes moved from [−1, 1] to [a, b], (b − a)/2 · Σ wᵢ·f(tᵢ). Exact for polynomials of degree up to 2n − 1. A template over the integrand f, verified through f = silu; a test integrates eᵗ and cos t to 10⁻¹⁵.

40calls gauss_legendre
bisect_stepL1
(lo: f64[n], hi: f64[n], tol: f64[]) → f64[n], f64[n]

One bisection step for a root of f in each bracket [lo, hi]: halve it at the midpoint and keep the half where f changes sign. The body bisect loops on; it takes the loop's tolerance and does not use it. A template over f.

40exact
bracket_openL1
(lo: f64[n], hi: f64[n], tol: f64[]) → f64[]

Whether any bisection bracket is still wider than tol, as 1 or 0. The condition bisect loops on.

40exact
bisectL3
(lo: f64[n], hi: f64[n], tol: f64[]) → f64[n]

A root of f in each bracket [lo, hi], where f(lo) and f(hi) differ in sign: bisection until every bracket is at most tol wide, then the midpoint. A While with two carries, lo and hi. A template over f, verified through f = silu; a test finds π/2 and 3π/2 as roots of cos.

40calls bisect_step, bracket_open
newton_stepL1
(x: f64[n], y: f64[n], tol: f64[]) → f64[n]

One Newton step for f(x) = y, elementwise: x − (f(x) − y)/f′(x), with the derivative given as the function df. The body newton loops on; it takes the loop's tolerance and does not use it. A template over f and df.

40
newton_unconvergedL1
(x: f64[n], y: f64[n], tol: f64[]) → f64[]

Whether any residual |f(x) − y| is still above tol, as 1 or 0. The condition newton loops on. A template over f.

40exact
newtonL3
(x0: f64[n], y: f64[n], tol: f64[]) → f64[n]

Solve f(x) = y elementwise by Newton's method from x₀, given f and its derivative df, until every residual |f(x) − y| is at most tol. A While over newton_step. A template over f and df, verified through f = softplus and df = sigmoid, which inverts softplus; a test takes √2 as the root of x² = 2.

40calls newton_step, newton_unconverged
fixed_point_stepL0
(x: f64[n], tol: f64[]) → f64[n]

One step of fixed-point (Picard) iteration: x ← g(x), elementwise. The body fixed_point loops on; it takes the loop's tolerance and does not use it. A template over g.

40exact
fixed_point_openL1
(x: f64[n], tol: f64[]) → f64[]

Whether some |g(x) − x| is still above tol, as 1 or 0. The condition fixed_point loops on. A template over g.

40exact
fixed_pointL3
(x0: f64[n], tol: f64[]) → f64[n]

A fixed point x = g(x), elementwise, by Picard iteration from x₀ until every |g(x) − x| is at most tol. For a contraction with constant q < 1 the iteration converges to the unique fixed point, and the error is then at most q·tol/(1 − q). A While over fixed_point_step; a template over g, verified through g = sigmoid, a contraction with q = 1/4.

40exactcalls fixed_point_open, fixed_point_step

Algebraic structures

std.algebra · 31
group_axiomsL3
(T: i64[n, n]) → f64[], f64[], f64[], f64[], f64[]

The group axioms of a finite Cayley table T (T[a, b] = a·b on the elements 0 … n − 1), each checked over the whole table, as 1 or 0: closure (every entry is an element), associativity over all n³ triples, a two-sided identity, and a two-sided inverse for every element. Also the identity e, the first that works (0 when there is none). Associativity checked on some triples only would not be a proof.

40exact
is_groupL3
(T: i64[n, n]) → f64[]

Whether a finite Cayley table is a group, as 1 or 0: all four axioms of group_axioms hold.

40exactcalls group_axioms
group_inversesL3
(T: i64[n, n]) → f64[n]

The inverse of every element of a finite group, a⁻¹ with a·a⁻¹ = a⁻¹·a = e, read from the table (0 where none exists).

40exactcalls group_axioms
is_abelianL3
(T: i64[n, n]) → f64[]

Whether a finite Cayley table is an abelian group, as 1 or 0: a group in which a·b = b·a for every pair, checked over the whole table. A few commuting pairs, or commuting generators not shown to generate, are not enough.

40exactcalls is_group
power_stepL3
(pw: f64[n], order: f64[n], k: f64[], T: i64[n, n], e: f64[]) → f64[n], f64[n]

One step of computing every element's powers at once: pw(g) ← pw(g)·g, so after k steps from e it is gᵏ; an element whose power first returns to e at this step k gets order k. The body element_orders scans.

40exact
element_ordersL3
(T: i64[n, n]) → f64[n]

The order of every element of a finite group: the least k ≥ 1 with gᵏ = e, found by checking every smaller power. A Scan of power_step over k = 1 … n; in a group every order is at most n and divides n (0 would mean no power returned to e, which a group rules out).

40exactcalls group_axioms, power_step
element_of_orderL3
(T: i64[n, n], d: f64[]) → f64[], f64[]

Whether a finite group has an element of order d, as 1 or 0, and the first one (0 when there is none). Cauchy's theorem says one exists for every prime p dividing |G|; for a composite divisor d there may be none (Z₂ × Z₂ has no element of order 4).

40exactcalls element_orders
is_subgroupL3
(T: i64[n, n], H: f64[n]) → f64[]

Whether a subset H of a finite group (a 0/1 mask) is a subgroup, as 1 or 0: it contains the identity, and it is closed under products and inverses, each checked over all its elements. Closed under products alone suffices in a finite group, but all three are checked.

40exactcalls group_axioms, group_inverses
left_cosetsL3
(T: i64[n, n], H: f64[n]) → f64[n], f64[]

The left cosets gH of a subgroup H of a finite group: each element g is labelled by the smallest element of gH, so two elements share a label exactly when they lie in the same coset; and the index [G : H], the number of cosets. Lagrange: the cosets partition G and each has |H| elements, so |G| = [G : H]·|H|.

40exact
right_cosetsL3
(T: i64[n, n], H: f64[n]) → f64[n], f64[]

The right cosets Hg of a subgroup H of a finite group, labelled by their smallest element, and their number, which equals the index [G : H].

40exact
is_normal_subgroupL3
(T: i64[n, n], H: f64[n]) → f64[]

Whether a subset H of a finite group is a normal subgroup, as 1 or 0: a subgroup with gH = Hg for every g, which is equivalent to gHg⁻¹ = H. The trivial subgroup and the whole group are always normal.

40exactcalls is_subgroup, left_cosets, right_cosets
quotient_groupL3
(T: i64[n, n], H: f64[n]) → f64[], f64[], f64[n, n], f64[]

The quotient group G/H by a subgroup H: its elements are the cosets, labelled by their smallest element, and the product of the cosets of g and h is the coset of g·h, given as a table indexed by elements. Also whether H is normal and whether that product is well defined, the same for every choice of representatives. If H is not normal, representatives can give different cosets, and there is no quotient group. The number of cosets is the order of G/H.

40exactcalls is_normal_subgroup, left_cosets
group_centerL3
(T: i64[n, n]) → f64[n]

The center Z(G) of a finite group as a 0/1 mask: the elements that commute with every element, each checked against the whole group. It is a normal subgroup; it is all of G exactly when G is abelian, and z ∈ Z(G) exactly when z's conjugacy class is {z}.

40exact
conjugacy_classesL3
(T: i64[n, n]) → f64[n], f64[]

The conjugacy classes of a finite group: each x is labelled by the smallest element of its class {g·x·g⁻¹ : g ∈ G}, every g enumerated; and the number of classes. Two classes are equal or disjoint, and together they cover G. A class is not a coset.

40exactcalls group_inverses
is_homomorphismL3
(TG: i64[n, n], TK: i64[m, m], f: i64[n]) → f64[]

Whether a map f from a finite group G to a finite group K (f[a] the image of a) is a homomorphism, as 1 or 0: f(a·b) = f(a)·f(b) for every pair. A homomorphism need not be injective.

40exact
hom_kernel_imageL3
(TG: i64[n, n], TK: i64[m, m], f: i64[n]) → f64[n], f64[m], f64[]

The kernel of a homomorphism f : G → K, the full preimage of K's identity, as a 0/1 mask; its image in K as a 0/1 mask; and whether f is injective, which holds exactly when the kernel is the identity alone. The kernel is a normal subgroup of G, and the nonempty fibres of f are its cosets.

40exactcalls group_axioms
first_isomorphismL3
(TG: i64[n, n], TK: i64[m, m], f: i64[n]) → f64[], f64[], f64[]

The first isomorphism theorem on a finite example, as 1 or 0: f : G → K is a homomorphism, the induced map gH ↦ f(g) on the cosets of H = ker f gives the same value for every representative, and it is a bijection onto the image, so G/ker f ≅ im f. Also |G/ker f| and |im f|. The image need not be all of K.

40exactcalls hom_kernel_image, left_cosets
action_axiomsL3
(T: i64[n, n], A: i64[n, k]) → f64[], f64[], f64[]

The axioms of a finite group action, A[g, x] = g·x for a group with Cayley table T acting on the points 0 … k − 1, each checked over the whole table, as 1 or 0: every g·x is a point; e·x = x for every x; and (gh)·x = g·(h·x) for every g, h and x. A valid action need not be faithful, free or transitive.

40exactcalls group_axioms
orbitsL3
(T: i64[n, n], A: i64[n, k]) → f64[k], f64[]

The orbits G·x = {g·x : g ∈ G} of a finite group action, every g enumerated: each point is labelled by the smallest point of its orbit, so two points share a label exactly when some g sends one to the other; and the number of orbits. The orbits partition the points. One generator's powers, or a single g·x, are not an orbit.

40exact
stabilizerL3
(T: i64[n, n], A: i64[n, k], x: f64[]) → f64[n]

The stabilizer Stab(x) = {g : g·x = x} of a point under a finite group action, every g checked, as a 0/1 mask over G. It is a subgroup of G. It is not the orbit, and not the kernel of the action (the elements that fix every point).

40exact
orbit_stabilizerL3
(T: i64[n, n], A: i64[n, k], x: f64[]) → f64[], f64[], f64[]

The orbit-stabilizer theorem on a finite action, for the point x: |G·x|, |Stab(x)|, and whether |G| = |G·x|·|Stab(x)|, as 1 or 0. It holds for every action, faithful or not: g ↦ g·x maps G onto the orbit, and the fibre over y = g₀·x is the coset g₀·Stab(x).

40exactcalls stabilizer
ring_axiomsL3
(Ad: i64[n, n], Mu: i64[n, n]) → f64[], f64[], f64[], f64[], f64[], f64[], f64[]

The axioms of a finite ring with 1, given by its addition table Ad and multiplication table Mu, each checked over every pair or triple, as 1 or 0: addition is an abelian group; multiplication is closed and associative; it distributes over addition on both sides, a(b + c) = ab + ac and (a + b)c = ac + bc; there is a multiplicative identity 1; and 1 ≠ 0. Also the zero and the one. Multiplication need not commute.

40exactcalls group_axioms, is_abelian
is_ringL3
(Ad: i64[n, n], Mu: i64[n, n]) → f64[]

Whether two finite tables form a ring with 1 ≠ 0, as 1 or 0: every axiom of ring_axioms holds.

40exactcalls ring_axioms
ring_propertiesL3
(Ad: i64[n, n], Mu: i64[n, n]) → f64[], f64[n], f64[n]

Three properties of a finite ring with 1, each checked over every pair: whether it is a commutative ring (a ring with ab = ba for all a, b), as 1 or 0; its zero divisors, the nonzero a with ab = 0 or ba = 0 for some nonzero b, as a 0/1 mask; and its units, the a with a two-sided inverse, ab = ba = 1, as a 0/1 mask.

40exactcalls ring_axioms
is_integral_domainL3
(Ad: i64[n, n], Mu: i64[n, n]) → f64[]

Whether a finite ring is an integral domain, as 1 or 0: a commutative ring with 1 ≠ 0 and no zero divisors, ab ≠ 0 for all nonzero a and b, checked over every pair. Every finite integral domain is a field (multiplication by a nonzero a is injective, so onto), but that is a theorem, not part of the definition.

40exactcalls ring_axioms, ring_properties
is_fieldL3
(Ad: i64[n, n], Mu: i64[n, n]) → f64[]

Whether a finite ring is a field, as 1 or 0: a commutative ring with 1 ≠ 0 in which every nonzero element has a two-sided multiplicative inverse, checked for every nonzero element. Division is defined only by nonzero elements. The order of a finite field is a prime power, not necessarily a prime: there is a field with 4 elements, and Z/4 is not one.

40exactcalls ring_axioms, ring_properties
is_idealL3
(Ad: i64[n, n], Mu: i64[n, n], I: f64[n]) → f64[]

Whether a subset I of a finite ring (a 0/1 mask) is a two-sided ideal, as 1 or 0: the tables form a ring; I contains 0, is closed under addition and additive inverses; and it absorbs multiplication on both sides, r·x ∈ I and x·r ∈ I for every r in the ring and x in I. Left and right absorption are checked separately, over every pair.

40exactcalls group_axioms, group_inverses, is_ring
quotient_ringL3
(Ad: i64[n, n], Mu: i64[n, n], I: f64[n]) → f64[], f64[], f64[], f64[], f64[n, n], f64[n, n], f64[]

The quotient ring R/I by a two-sided ideal I: the classes a + I, labelled by their smallest element, with [a] + [b] = [a + b] and [a]·[b] = [ab], given as two tables indexed by elements; whether I is an ideal; whether it is proper (I ≠ R, so that 1 ≠ 0 in R/I); whether both operations are well defined, the same for every choice of representatives; and the number of classes.

40exactcalls is_ideal, left_cosets, quotient_group
ring_poly_addL3
(Ad: i64[n, n], p: i64[a], q: i64[a]) → i64[a]

The sum of two polynomials over a finite ring, coefficient by coefficient with the ring's addition table: (p + q)ᵢ = pᵢ + qᵢ. The coefficients are elements of the ring, as int64 labels, both lists the same length (pad the shorter with the ring's zero).

40exact
ring_poly_stepL3
(r: f64[L], i: f64[], p: i64[a], q: i64[c], Ad: i64[n, n], Mu: i64[n, n], zero: f64[]) → f64[L]

One pass of polynomial multiplication over a finite ring: add the term p_i·q, shifted i places, into the accumulated coefficients r, with the ring's own tables. The body ring_poly_mul scans.

40exact
ring_poly_mulL3
(Ad: i64[n, n], Mu: i64[n, n], p: i64[a], q: i64[c]) → i64[a+c−1]

The product of two polynomials over a finite commutative ring, by finite convolution with the ring's own tables: (pq)_k = Σ_{i+j=k} p_i·q_j, the sum taken with the addition table. A Scan of ring_poly_step over the coefficients of p. With zero divisors the degree of a product can fall below the sum of the degrees (over Z/4, (2x + 1)(2x + 1) = 1), so the degree formula is not used. R[x] is not a finite ring: when 1 ≠ 0 the powers 1, x, x², … are all distinct.

40exactcalls group_axioms, ring_poly_step

Finite topology

std.topology · 21
topology_axiomsL3
(tau: f64[m, n]) → f64[], f64[], f64[], f64[]

The axioms of a topology on a finite set, given as the list of its open sets τ (an m × n 0/1 matrix), as 1 or 0: the empty set and the whole set are open, and the union and the intersection of any two open sets are open. For a finite family, pairs suffice for every union and every finite intersection; the empty union is ∅ and the empty intersection is X. Each test runs over all pairs, by set sizes: the smallest open set containing U and V must have |U ∪ V| points, and the largest inside both |U ∩ V|.

40exact
is_topologyL3
(tau: f64[m, n]) → f64[]

Whether a finite family of subsets is a topology, as 1 or 0: all four axioms of topology_axioms hold.

40exactcalls topology_axioms
is_openL1
(tau: f64[m, n], A: f64[n]) → f64[]

Whether a subset A (a 0/1 mask) is open in a finite topology τ, as 1 or 0: A is one of the listed open sets.

40exact
is_closedL1
(tau: f64[m, n], A: f64[n]) → f64[]

Whether a subset A is closed in a finite topology, as 1 or 0: its complement X \ A is open. Open and closed are not opposites: ∅ and X are both, and a set may be neither.

40exactcalls is_open
interiorL1
(tau: f64[m, n], A: f64[n]) → f64[n]

The interior of a subset A in a finite topology, as a 0/1 mask: the union of all the open sets contained in A, the largest open subset of A. It depends on the topology; no metric is used.

40exact
closureL1
(tau: f64[m, n], A: f64[n]) → f64[n]

The closure of a subset A in a finite topology, as a 0/1 mask: the intersection of all the closed sets containing A, the smallest closed superset of A, computed as X \ int(X \ A).

40exactcalls interior
boundaryL1
(tau: f64[m, n], A: f64[n]) → f64[n]

The boundary of a subset A in a finite topology, as a 0/1 mask: cl A \ int A. A and its complement have the same boundary; ∅ and X have none.

40exactcalls closure, interior
is_neighborhoodL3
(tau: f64[m, n], x: f64[], N: f64[n]) → f64[]

Whether a subset N is a neighbourhood of the point x in a finite topology, as 1 or 0: some open U has x ∈ U ⊆ N, that is, x lies in the interior of N. A neighbourhood need not be open.

40exactcalls interior
basis_stepL3
(ok: f64[], i: f64[], B: f64[m, n]) → f64[]

One row of the basis check: for the basis element B_i and every B_j, each point of B_i ∩ B_j lies in some basis element inside B_i ∩ B_j. The body is_basis scans.

40exact
is_basisL3
(B: f64[m, n]) → f64[]

Whether a finite family B of subsets is a basis for some topology, as 1 or 0: its members cover X, and for any two members, each point of their intersection lies in a member inside the intersection. A Scan of basis_step over the members. A basis is not a subbasis: the subbasis condition asks only that the members cover.

40exactcalls basis_step
members_openL1
(tau: f64[m, n], B: f64[c, n]) → f64[]

Whether every member of a finite family B is an open set of the topology τ, as 1 or 0.

40exact
is_basis_forL3
(tau: f64[m, n], B: f64[c, n]) → f64[]

Whether a finite family B is a basis of the given topology τ, as 1 or 0: B is a basis, its members are open, and every open set of τ is a union of members.

40exactcalls is_basis, members_open
subspace_topologyL0
(tau: f64[m, n], Y: f64[n]) → f64[m, n]

The subspace topology on a subset Y: τ_Y = {U ∩ Y : U ∈ τ}, one row for each open set of τ (rows may repeat; the family is the set of rows). A relatively open set need not be open in X.

40exact
is_continuousL3
(tauX: f64[m, n], tauY: f64[p, k], f: i64[n]) → f64[]

Whether a map f from a finite space (X, τ_X) to (Y, τ_Y) is continuous, as 1 or 0: the preimage f⁻¹(V) of every open V of Y is open in X. It is the preimage that must be open; images of open sets need not be.

40exact
is_homeomorphismL3
(tauX: f64[m, n], tauY: f64[p, k], f: i64[n]) → f64[]

Whether a map f between finite spaces is a homeomorphism, as 1 or 0: a bijection that is continuous and whose inverse is continuous, which for a bijection means the image of every open set is open. A homeomorphism preserves the topology only: not distances, angles or smoothness.

40exactcalls is_continuous
is_hausdorffL2
(tau: f64[m, n]) → f64[]

Whether a finite topological space is Hausdorff, as 1 or 0: every two distinct points x ≠ y lie in disjoint open sets U ∋ x and V ∋ y, every pair checked. One failing pair disproves it. A finite Hausdorff space is discrete, which does not carry over to infinite spaces; the empty space and a single point are Hausdorff.

40exact
is_connectedL1
(tau: f64[m, n]) → f64[]

Whether a finite topological space is connected, as 1 or 0: no open set other than ∅ and X has an open complement, every open set checked. A disconnected space has a witness, an open set that is also closed; a connected one needs every candidate excluded. This is topological connectedness, not graph connectivity.

40exact
componentsL2
(tau: f64[m, n]) → f64[n], f64[]

The connected components of a finite topological space, each point labelled by the smallest point of its component; and how many there are. τ must be a topology, which is_topology decides. A point's component is the union of every connected subset that contains it, connected in the subspace topology. In a finite space it is found through the smallest open set U_x of each point: x and y lie in one component when a chain of points joins them, each two comparable, one in the other's smallest open set. These are components of the topology, not of a graph; and every component of a finite space is both open and closed, which fails in general (in ℚ the components are points, which are not open).

40exactcalls component_count, component_labels
is_open_coverL1
(tau: f64[m, n], C: f64[c, n], K: f64[n]) → f64[], f64[]

Whether a finite family C (one set per row) is an open cover of the subset K in the topology τ: whether every member is open, and whether the members together contain K, each as 1 or 0. A finite space is compact, since its topology itself is finite, so every open cover has a finite subcover; one cover checked does not by itself prove compactness.

40exactcalls members_open
is_subcoverL1
(C: f64[c, n], sel: f64[c], K: f64[n]) → f64[]

Whether the members of a cover C selected by sel (a 0/1 mask over the members, so a subcover takes members of the original cover only) still contain K, as 1 or 0.

40exact
quotient_openL3
(tauX: f64[m, n], q: i64[n], U: f64[k]) → f64[]

Whether a subset U of Y is open in the quotient topology of a surjection q : X → Y, as 1 or 0: its preimage q⁻¹(U) is open in X. Only saturated open sets of X are preimages, so taking images of open sets would in general be wrong.

40exactcalls is_open

Sets, relations and logic

std.sets · 25
relation_partsL1
(R: f64[a, b], C: f64[a]) → f64[a], f64[b], f64[b, a]

Three parts of a finite relation R from A to B (a 0/1 matrix): its domain Dom R = {a : a R b for some b} as a mask over A; the image R[C] = {b : a R b for some a ∈ C} of a subset C of A, as a mask over B; and the inverse relation R⁻¹ from B to A, the transpose. Ordered pairs keep their direction.

40exact
relation_propertiesL2
(R: f64[n, n]) → f64[], f64[], f64[], f64[]

Four properties of a relation R on a finite set (an n × n 0/1 matrix), each checked over every element, pair or triple, as 1 or 0: reflexive (x R x for all x), symmetric (x R y ⇒ y R x), transitive (x R y and y R z ⇒ x R z, checked as R∘R ⊆ R), and antisymmetric (x R y and y R x ⇒ x = y). One counterexample disproves the property it violates.

40exact
equivalence_classesL2
(R: f64[n, n]) → f64[], f64[n], f64[]

Whether a relation on a finite set is an equivalence relation (reflexive, symmetric and transitive), as 1 or 0, and its classes: each a labelled by the smallest element of [a] = {x : a R x}, which is the canonical projection onto the quotient set X/R; and the number of classes. Two classes are equal or disjoint and together cover X. The labels mean classes only when the relation is an equivalence.

40exactcalls relation_properties
function_graphL3
(f: i64[n], cod: f64[k]) → f64[n, k]

The graph G_f = {(a, f(a))} of a function f from A = 0 … n − 1 to B = 0 … k − 1 (B given by a carrier vector of length k, only its length read), as an n × k relation: (u, v) ∈ G_f exactly when v = f(u).

40exact
is_functionL1
(R: f64[a, b]) → f64[]

Whether a finite relation R from A to B is a (total) function, as 1 or 0: every a relates to exactly one b. The codomain B need not be the range.

40exact
function_propertiesL3
(f: i64[n], cod: f64[k]) → f64[], f64[], f64[], f64[k]

For a function f : A → B on finite sets, each as 1 or 0: injective (every fibre f⁻¹(b) has at most one element), surjective (every b is hit, the range equals the codomain), bijective (both); and the range f[A] as a mask over B. On finite sets an injection A → B shows |A| ≤ |B|, a surjection |A| ≥ |B|, a bijection |A| = |B|; equal sizes do not make a given f a bijection.

40exact
inverse_functionL3
(f: i64[n], cod: f64[k]) → f64[], i64[k]

The inverse g : B → A of a function f on finite sets, by swapping the pairs of its graph, and whether f is a bijection, as 1 or 0. Only for a bijection is g a function with g(f(a)) = a and f(g(b)) = b; otherwise the swapped table is not an inverse, and g is the first preimage, or 0 where there is none.

40exactcalls function_properties
pigeonholeL3
(f: i64[n], cod: f64[k]) → f64[], f64[], f64[], f64[]

The pigeonhole principle on a function f : A → B between finite sets: whether two elements share an image, as 1 or 0, and the first such pair a₁ < a₂ (0, 0 when there is none); and the largest load, the size of the biggest fibre. When |A| > |B| a collision must exist, and the largest load is at least ⌈|A|/|B|⌉; |A| ≤ |B| does not make f injective.

40exact
set_operationsL1
(A: f64[n], B: f64[n]) → f64[n], f64[n], f64[n], f64[n]

Union A ∪ B, intersection A ∩ B, difference A \ B and complement U \ A of subsets of one finite universe U, as 0/1 masks. The complement is always taken relative to the stated universe.

40exact
is_subsetL1
(A: f64[n], B: f64[n]) → f64[], f64[], f64[]

Whether A ⊆ B for subsets of one finite universe, as 1 or 0: every element of A is in B. Also whether A is a proper subset (A ⊆ B, A ≠ B) and whether A = B (sets with the same elements are equal).

40exact
is_memberL3
(A: f64[n], x: i64[]) → f64[]

Whether x ∈ A for a subset A of a finite universe, as 1 or 0.

40exact
ie_stepL4
(c: f64[], total: f64[], S: f64[s, m], pow2: f64[s], count: f64[]) → f64[], f64[]

One term of inclusion-exclusion: for the index set I given by the bits of c, (−1)^(|I|+1)·|∩_{i ∈ I} S_i|, added to the running total (the empty I adds nothing). The body inclusion_exclusion runs.

40exact
ie_openL1
(c: f64[], total: f64[], S: f64[s, m], pow2: f64[s], count: f64[]) → f64[]

Whether the index-set counter c is still below 2^s, as 1 or 0. The condition inclusion_exclusion loops on.

40exact
inclusion_exclusionL4
(S: f64[s, m]) → f64[], f64[]

Inclusion-exclusion for a finite indexed family S_1 … S_s of subsets of 0 … m − 1 (one row each): the size of the union counted directly, and the alternating sum Σ over all 2^s − 1 nonempty index sets I of (−1)^(|I|+1)|∩_{i ∈ I} S_i|, a While over ie_step. The two agree. Repeated sets are counted by index; stopping after singles and pairs gives only a Bonferroni bound for s ≥ 3.

40exactcalls growth_step, ie_open, ie_step
connectivesL1
(p: f64[n], q: f64[n]) → f64[n], f64[n], f64[n], f64[n], f64[n]

The truth values of the classical connectives, elementwise on truth values 0 and 1: ¬P, P ∧ Q, P ∨ Q, P → Q (false only when P is true and Q false) and P ↔ Q.

40exact
quantifiersL2
(p: f64[n]) → f64[], f64[], f64[], f64[]

Quantifiers over a finite domain U, for a predicate given by its truth values P(x): ∀x P(x) and ∃x P(x), each as 1 or 0; whether a counterexample to ∀x P(x) exists, and the first one (0 when there is none). One counterexample refutes the universal statement; failing to find one proves it only because the domain is finite and was checked completely. ¬∀x P(x) ⇔ ∃x ¬P(x).

40exact
metric_axiomsL3
(D: f64[n, n]) → f64[], f64[], f64[], f64[]

The axioms of a metric on a finite set, given as its full distance table D, each checked over every pair or triple, as 1 or 0: d(x, y) ≥ 0; d(x, y) = 0 exactly when x = y; d(x, y) = d(y, x); and the triangle inequality d(x, z) ≤ d(x, y) + d(y, z), checked for every y at once as d ≤ the min-plus square of d. A finite metric space is complete: below its smallest positive distance a Cauchy sequence is eventually constant.

40exact
min_positive_distanceL1
(D: f64[n, n]) → f64[]

The smallest positive distance δ in a finite distance table (0 for a single point). Every ε < δ forces d(x_m, x_n) < ε to mean x_m = x_n, so a Cauchy sequence in a finite metric space is eventually constant and converges: finite metric spaces are complete. A few sampled sequences would not prove it.

40exact
model_correctnessL2
(Step: f64[n, n], Init: f64[n], Halt: f64[n], Post: f64[n]) → f64[n], f64[n], f64[], f64[], f64[]

Correctness of a finite computational model (S, Init, Step, Halt), possibly nondeterministic, against a postcondition Post: the states reachable from Init (a halting state is an end, its outgoing steps cut); the stuck states, reachable, not halting, with no successor, which are not halts; partial correctness, every reachable halting state satisfies Post; termination, no execution runs forever (no reachable cycle) or gets stuck; and total correctness, both. Every execution is covered, as nondeterminism requires: one successful path proves nothing.

40exactcalls reachability
decidesL2
(D: f64[n], Y: f64[n]) → f64[], f64[]

Whether a decider's answers D(x) (0 or 1, for every input x of a finite input set) decide the problem with yes-instances Y, as 1 or 0: D(x) = 1 exactly when x ∈ Y; and the first input where they differ (0 when none). A finite table settles that finite input set only; decidability of an infinite problem needs an algorithm that halts on every input.

40exact
is_reductionL3
(A: f64[n], B: f64[k], f: i64[n]) → f64[], f64[]

Whether a total map f from a finite input set of problem A to one of problem B is a many-one reduction A ≤ₘ B, as 1 or 0: x ∈ A exactly when f(x) ∈ B, both directions checked for every x (yes-instances alone are not enough); and the first x where it fails. If A ≤ₘ B and B is decidable, computing f and then B's decider decides A; the converse does not hold. A finite table proves the reduction on that finite domain only.

40exact
orbit_stepL3
(pw: f64[n], period: f64[n], k: f64[], f: i64[n]) → f64[n], f64[n]

One step of following every point's forward orbit under a self-map f of a finite set at once: pw(x) ← f(pw(x)), so after k steps from x it is fᵏ(x); a point that first returns to itself at step k gets period k. The body orbit_periods scans.

40exact
orbit_periodsL3
(f: i64[n]) → f64[n], f64[n]

Fixed and periodic points of a self-map f of a finite set {0, …, n − 1}: the minimal period of each x, the least p ≥ 1 with fᵖ(x) = x (0 when x is not periodic: its orbit enters a cycle without returning to x), checked for every smaller power; and the fixed points, period 1. A Scan of orbit_step over n steps, enough on a finite set: every orbit repeats within n steps. Entering a cycle does not make the starting point periodic.

40exactcalls orbit_step
product_stepL0
(acc: f64[], v: f64[]) → f64[]

One factor of a product: acc·v. The body counting_rules scans.

40exact
counting_rulesL2
(counts: f64[k]) → f64[], f64[]

The two counting principles for finite choices given the number of options in each part: the sum rule, Σ counts, for choosing one option from mutually exclusive categories; and the product rule, Π counts, for a sequence of stages whose option counts do not depend on earlier choices. Overlapping categories must be corrected by inclusion-exclusion first.

40exactcalls product_step
ΣEML 2026

Efficient New Language — a high-density semantic overlay for humans and AI agents.

This site’s demos run on the real EML toolchain, in your browser.

© 2026 EveMissLab (一言諾科技有限公司) / Neo.K. All rights reserved.