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 a2b45f50b4b1c3b88308a6b9918bbe451948c1e7 Author: tison <[email protected]> AuthorDate: Mon Nov 16 00:13:59 2026 +0800 test(cpc): correct two numerical notes in the table reconstruction - zero_prob claimed that 1.0 - one_prob(...) rounds to 0.0 once p_0 < f64::EPSILON / 2 (2^-53). Below 1.0 the f64 spacing is 2^-53, so with round-to-nearest-even one_prob rounds to exactly 1.0 only once p_0 <= 2^-54; for p_0 in (2^-54, 2^-53) the subtraction yields 2^-53 instead. Both lose every digit of p_0, and the case that matters (p_0 = 2.22e-17 at phase 19/32) is below 2^-54, so the generator is unaffected. - The steady-state model notes argued against a matrix-edge effect by quoting p_0 of column 1, which is not the quantity that couples the edge to the window: lambda is solved over all 128 columns. State the actual bound instead. The Poisson identity f(2 * lambda) = f(lambda) + 1 - exp(-lambda) means that raising the base by one doubles lambda and shifts the window by one column up to a relative ln(2) * exp(-lambda), about 2e-23 at C/K = 6 + 1/32. --- datasketches/src/cpc/compression_data.rs | 19 ++++++++++++------- 1 file changed, 12 insertions(+), 7 deletions(-) diff --git a/datasketches/src/cpc/compression_data.rs b/datasketches/src/cpc/compression_data.rs index 74f5702..2da9646 100644 --- a/datasketches/src/cpc/compression_data.rs +++ b/datasketches/src/cpc/compression_data.rs @@ -12014,11 +12014,14 @@ mod tests { /// steady-state headers within `1.1e-14`, whereas the binomial model at `K = 2^32` misses /// them by `6.1e-12`. That residual halves with every unit added to the base (`3.1e-12` at /// `7.0 + phase`, `1.5e-12` at `8.0 + phase`), which is the `2^-col / K` signature of the - /// finite-`K` correction at the window columns, not an effect of the matrix edge: the left - /// edge (column 1 has `p_0 ≈ 5.3e-12` at `C / K = 6 + 1/32`) moves `lambda / 2^offset` by - /// less than one ULP. Consequently "`K = 2^32` with base `>= 16`" fits the byte tables - /// equally well; the Poisson limit is preferred because a single operating point then - /// explains both the byte tables and the permutations, which are insensitive to `K`. + /// finite-`K` correction at the window columns, not an effect of the matrix edge. Although + /// `lambda` is solved over all 128 columns, the Poisson identity + /// `f(2 * lambda) = f(lambda) + 1 - exp(-lambda)` for `f(lambda) = E[C] / K` means that raising + /// the base by one doubles `lambda` and shifts the window by one column up to a relative + /// `ln(2) * exp(-lambda)`, about `2e-23` at `C / K = 6 + 1/32` (`lambda ≈ 51.9`). + /// Consequently "`K = 2^32` with base `>= 16`" fits the byte tables equally well; the Poisson + /// limit is preferred because a single operating point then explains both the byte tables and + /// the permutations, which are insensitive to `K`. const STEADY_STATE_MODEL: Occupancy = Occupancy::Poisson; /// Integer part of the steady-state operating point `C / K = 6.0 + phase`, where @@ -12064,8 +12067,10 @@ mod tests { /// Probability `p_0` that a cell in 1-based column `col` is still `0`. /// - /// Evaluated as `exp(...)` rather than `1.0 - one_prob(...)`, which rounds to `0.0` once - /// `p_0 < f64::EPSILON / 2` and would misrank tiny surprise probabilities in + /// Evaluated as `exp(...)` rather than `1.0 - one_prob(...)`: `one_prob` cannot hold a + /// difference from `1.0` below the `2^-53` spacing there, so it rounds to exactly `1.0` + /// once `p_0 <= 2^-54` (`f64::EPSILON / 4`) and the subtraction then yields `0.0`. That + /// cancellation would misrank tiny surprise probabilities in /// `generate_sliding_column_permutation`. fn zero_prob(self, lambda: f64, col: u8) -> f64 { self.ln_zero_prob(lambda, col).exp() --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
