This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch test/cpc-table-generators in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 618f72a0939096ff672ba44b468024c911c036ac Author: tison <[email protected]> AuthorDate: Mon Nov 16 00:15:20 2026 +0800 test(cpc): correct the ICON polynomial fitting notes The notes on the polynomial reconstruction overstated or misquoted some of the evidence: - They said the stored rows stay at the 1e-7 level "up to exactly C = 6K and degrade abruptly beyond it" for every lg_k. That is sharp only for small K: lg_k = 4 reaches 8.7e-8 on C = 2..=96 and 2.2e-6 at C = 97, but lg_k = 8 is still at -6.6e-8 at C = 6K + 1. Across all rows the error stays below 5e-7 up to 6K and reaches 4e-6 to 1.3e-4 at 6.25K; the exact end at 6K comes from the grid experiments for lg_k <= 7. - The guard band against endpoint oscillation was stated as the reason for fitting past the runtime threshold. It is a plausible reading, not documented, so say so. - The condition number of the monomial basis was quoted as ~1e12. The unscaled basis on the C = 1..=6K grids has a 2-norm condition number of about 1e17 (1.19e17 for lg_k = 4), and about 1e14 after column scaling. - The 1/(82.6K) finite-K bias at the splice point was said to explain the 1/(80K) bound in the Java test. It matches that bound with a small margin, but why the bound was chosen is not recorded. Also note that the integer-grid agreement identifies the grid but not the original numerics. --- datasketches/src/cpc/estimator.rs | 47 ++++++++++++++++++++++----------------- 1 file changed, 26 insertions(+), 21 deletions(-) diff --git a/datasketches/src/cpc/estimator.rs b/datasketches/src/cpc/estimator.rs index 3c3feb5..cdde71a 100644 --- a/datasketches/src/cpc/estimator.rs +++ b/datasketches/src/cpc/estimator.rs @@ -555,21 +555,25 @@ mod tests { // of `0.12698`, because least squares optimizes uniform accuracy on `[0, 3]` rather than // Taylor accuracy at `0`. // - // * Fitting domain `C in [1, 6 * K]` (`x in (0, 3]`): evaluating the stored rows past the - // runtime threshold (`5.6 * K` or `5.7 * K`) shows that their relative error against - // `exact_icon_estimate` stays at the `1e-7` level up to exactly `C = 6.0 * K` and degrades - // abruptly beyond it (for `lg_k = 4`: `1.3e-8` at `C = 96`, `2.2e-6` at `C = 97`). The - // polynomials were therefore fit up to `6 * K`, leaving `[5.6 * K, 6.0 * K]` as a guard band - // against endpoint oscillation. + // * Fitting domain `C in [1, 6 * K]` (`x in (0, 3]`): past the runtime threshold (`5.6 * K` or + // `5.7 * K`) the stored rows keep a relative error below `5e-7` against `exact_icon_estimate` + // up to `C = 6 * K`, and diverge within a few percent beyond it (at `6.25 * K` every row is + // off by `4e-6` to `1.3e-4`). The end is sharp for small `K`: `lg_k = 4` has at most `8.7e-8` + // up to `C = 96` and `2.2e-6` at `C = 97`. For larger `lg_k` an integer step is too fine to + // locate it: `lg_k = 8` is still at `-6.6e-8` at `C = 6 * K + 1`. The end at exactly `6 * K` + // rests on the grid experiments for `lg_k <= 7` below. Why the fit extends past the runtime + // threshold, e.g. as a guard band against endpoint oscillation, is not documented. // // * Sample grid for `lg_k <= 7` (`6 * K <= 768`): ordinary least squares on `g_K` over every // integer `C = 1 ..= 6 * K` reproduces the stored coefficients within `0.07%` to `1.4%` and - // the stored polynomial to `< 2e-8` relative prediction difference, despite the `~1e12` - // condition number of the monomial basis on `[0, 3]`. The agreement is discriminating: moving - // either end of the grid by one integer, dropping `C = 1` (where the exact estimator returns - // `N = 1` by definition), or halving the grid spacing makes the coefficient agreement at - // least 4x (`lg_k = 6`) to 59x (`lg_k = 5`) worse. The weighting is less certain: a - // relative-error-weighted fit agrees slightly better (`0.63%`) at `lg_k = 4`. + // the stored polynomial to `< 2e-8` relative prediction difference, although the unscaled + // monomial basis on these grids has a 2-norm condition number of about `1e17` (`1e14` after + // scaling its columns). The agreement is discriminating: moving either end of the grid by one + // integer, dropping `C = 1` (where the exact estimator returns `N = 1` by definition), or + // halving the grid spacing makes the coefficient agreement at least 4x (`lg_k = 6`) to 59x + // (`lg_k = 5`) worse. This identifies the grid, not the original numerics; the weighting is + // less certain as well: a relative-error-weighted fit agrees slightly better (`0.63%`) at + // `lg_k = 4`. // // * Sample grid for `lg_k >= 8`: not identified. A discontinuity between `lg_k = 7` and `8` // (`a_2`: `0.12534 -> 0.12667`; `a_19`: `4.28e-5 -> 2.91e-5`) and the irregular high-order @@ -735,10 +739,11 @@ mod tests { // In the exponential region (`> threshold * K`) two effects add up. The finite-`K` // correction makes the Poisson-based approximation overestimate `N` by about // `1 / (2 * K * lambda)` with `lambda = N / K`; this decays with `C` and peaks at - // the splice point, where `lambda ≈ 41.3` gives `1 / (82.6 * K)`. That explains the - // `1.0 / (80 * k)` bound in `IconEstimatorTest::quickIconEstimatorTest`. For large - // `K` the periodic term of FM85 theory dominates instead, with relative amplitude - // `1.09e-6`; the dense-sweep maximum for `lg_k >= 14` is `1.53e-6`. + // the splice point, where `lambda ≈ 41.3` gives `1 / (82.6 * K)`. The + // `1.0 / (80 * k)` bound in `IconEstimatorTest::quickIconEstimatorTest` matches + // this peak with a small margin. For large `K` the periodic term of FM85 theory + // dominates instead, with relative amplitude `1.09e-6`; the dense-sweep maximum + // for `lg_k >= 14` is `1.53e-6`. let tol = if (c as f64) <= threshold_factor * kf { 3e-7 } else { @@ -822,11 +827,11 @@ mod tests { if lg_k <= 7 { // On `lg_k <= 7`, the exact exhaustive integer grid `C = 1 ..= 6 * K` reproduces - // `a_0` to `< 1e-6`, `a_1` to `< 2e-5`, and all 20 monomials within `2.5%` - // despite the `kappa(V) ~ 1e12` conditioning of the unorthogonalized degree-19 - // Vandermonde basis on `[0, 3]` (where a 1-ULP `ln_1p`/`exp_m1` difference gets - // amplified by `~1e12` in the high-degree monomials while leaving `P(x)` invariant - // to `< 2e-8`). + // `a_0` to `< 1e-6`, `a_1` to `< 2e-5`, and all 20 monomials within `2.5%`. + // Closer agreement is not expected: the unscaled degree-19 monomial basis on these + // grids is ill-conditioned (2-norm condition number `~1e17`), so tiny differences + // in the target values move the high-degree coefficients by percents while leaving + // `P(x)` invariant to `< 2e-8`. assert_that!(fitted[0], near(stored[0], 1e-6)); assert_that!(fitted[1], near(stored[1], 2e-5)); for deg in 0..ICON_POLYNOMIAL_NUM_COEFFICIENTS { --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
