sketch_tdigest.nx

sketch_tdigest.nx -- T-Digest (Dunning 2019) tail-tight quantile sketch. Maintain centroids (mean, weight) sorted by mean. Each centroid covers a window of the cumulative-distribution domain [q_left, q_right]. The MAX WEIGHT a centroid may absorb depends on its q-position via a scale function that gives more room to centroids in the middle of the distribution and TIGHTLY BOUNDS centroids near the tails -- the headline T-Digest property. COMPLEMENTS KLL: - KLL: provable uniform rank-error bound, lighter at middle quantiles, looser at tails. - T-Digest: empirically tail-tight (p99/p99.9 accuracy is the headline), no global rank-error guarantee. Together: both shipping means callers pick the right tool per query. DUNNING k1 vs SIMPLIFIED SCALE FUNCTION (v1 trade-off): Dunning's k1(q) = (delta / 2π) · arcsin(2q - 1) → w_max_norm(q) = k1_inv(k1(q) + 1) - q exact: tail w_max ~ sqrt-like; middle ~ delta-bounded. v1 here: w_max_norm(q) = 4·q·(1-q) · π / delta The simplified scale UNDERESTIMATES tail capacity (more conservative = MORE centroids near tails, better tail accuracy than spec). At q=0.5 it gives 0.0314·N matching Dunning within 1%. Trade-off: memory uses slightly more centroids than necessary; queried accuracy is no worse than Dunning's bound, often better at tails. v2 will swap in a tabulated arcsin-based scale. LOSSLESS-LANGUAGE DISCIPLINE (doc 20): Query returns ApproxI64 with envelope_kind = NX_ENV_RANK_ERROR, param_a = ~1% absolute rank error (conservative bound for delta=100), maturity = ReferenceImpl, adv = Honest.