This is an automated email from the ASF dual-hosted git repository.

tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git


The following commit(s) were added to refs/heads/main by this push:
     new 9a90f38  test(cpc): add generation and verification tests for static 
lookup tables (#355)
9a90f38 is described below

commit 9a90f385f25e72eb038a4bf779a0901be1a01ef4
Author: tison <[email protected]>
AuthorDate: Mon Nov 16 16:10:22 2026 +0800

    test(cpc): add generation and verification tests for static lookup tables 
(#355)
---
 datasketches/src/cpc/compression_data.rs | 448 ++++++++++++++++++++++++++++
 datasketches/src/cpc/estimator.rs        | 484 +++++++++++++++++++++++++++++++
 2 files changed, 932 insertions(+)

diff --git a/datasketches/src/cpc/compression_data.rs 
b/datasketches/src/cpc/compression_data.rs
index 3c9923e..38342f0 100644
--- a/datasketches/src/cpc/compression_data.rs
+++ b/datasketches/src/cpc/compression_data.rs
@@ -11962,10 +11962,458 @@ pub static DECODING_TABLES_FOR_HIGH_ENTROPY_BYTE: 
[[u16; 4096]; 22] = [
 
 #[cfg(test)]
 mod tests {
+    // Reconstructs and verifies all six static lookup tables in this module 
from first principles.
+    //
+    // In the original C/C++/Java implementations of CPC ("FM85"), only the 
generated static arrays
+    // and the runtime table-inversion helpers (`makeDecodingTable` / 
`makeInversePermutation` in
+    // `fm85Compression.c`) were checked into source control. The three 
offline OCaml generators
+    // written by Kevin J. Lang referenced in the comments above were never 
published:
+    //
+    // 1. `columnProbabilities.ml`: computes cell occupancy probabilities in 
the FM85 coupon matrix
+    //    and derives the symbol distributions for high-entropy window bytes 
and for the column
+    //    deltas of surprise pairs.
+    // 2. `generateHuffmanCodes.ml`: builds length-limited (<= 12 bits) 
canonical LSB-first Huffman
+    //    encoding tables (`LENGTH_LIMITED_UNARY_ENCODING_TABLE65` and the 22 
tables of
+    //    `ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE`).
+    // 3. `generatePermutationsForSLIDING.ml`: orders the 56 non-window 
columns by descending
+    //    surprise probability across the 16 sliding-window phases
+    //    (`COLUMN_PERMUTATIONS_FOR_ENCODING`).
+    //
+    // The helpers and tests below document which hidden parameters the 
checked-in tables and
+    // header comments identify, which ones they leave open, and verify a 
1-to-1 bit-exact match
+    // for every entry of all six tables.
+
+    use std::array::from_fn;
+
     use googletest::assert_that;
     use googletest::prelude::container_eq;
+    use googletest::prelude::near;
 
     use super::*;
+    use crate::common::inv_pow2::inv_pow2;
+
+    /// Occupancy model of the midrange tables: binomial cell marginals at 
sketch size `K = 2^32`.
+    ///
+    /// How `K = 2^32` was reverse-engineered: the midrange codewords are 
reproduced by every
+    /// `K >= 2^16`, so only the 20-digit header entropies 
(`RECORDED_HEADER_STATS`) can pin `K`.
+    /// The worst deviation over the six midrange headers is `6e-15` at `K = 
2^32`, versus
+    /// `4.9e-11` at `K = 2^31`, `2.5e-11` at `K = 2^33`, and `4.9e-11` in the 
Poisson limit
+    /// `K -> inf`. The residuals on both sides follow the `1 / K` scaling of 
the finite-`K`
+    /// correction (`ln(1 - x) = -x - x^2 / 2 - ...` multiplies the Poisson 
exponent by roughly
+    /// `1 + 1 / (2 * K * 2^col)`), and `2^32` is also the upper end of the 
`2^4 .. 2^32` range
+    /// named in the ICON estimator notes.
+    const MIDRANGE_MODEL: Occupancy = Occupancy::Binomial {
+        k: (1_u64 << 32) as f64,
+    };
+
+    /// Occupancy model of the steady-state tables and the sliding column 
permutations: the
+    /// stationary Poisson limit `K -> inf`.
+    ///
+    /// At the true base `C / K = 6.0 + phase` (`STEADY_STATE_C_OVER_K_BASE`), 
the steady-state
+    /// byte tables identify only this limit: the Poisson model matches all 16 
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. 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 any base from 
`14` to `84` also
+    /// matches both the entropy and average-length headers of all 16 
steady-state tables within
+    /// `HEADER_STATS_TOLERANCE`; the Poisson limit at base `6` 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
+    /// `phase = (2 * m + 1) / 32` is the midpoint of the `m`-th sixteenth.
+    ///
+    /// The base is pinned by `COLUMN_PERMUTATIONS_FOR_ENCODING` (see
+    /// `generate_sliding_column_permutation`). Under `STEADY_STATE_MODEL` the 
steady-state byte
+    /// tables accept any base from `6` to `84` across both entropy and 
average-length headers
+    /// within `HEADER_STATS_TOLERANCE`; below `6` the left edge starts to 
matter, and beyond `84`
+    /// the 128-column right edge does (at base `85` the average length error 
already reaches
+    /// `3.1e-14`; base `100` misses by `7e-10`).
+    const STEADY_STATE_C_OVER_K_BASE: f64 = 6.0;
+
+    /// Maximum Huffman codeword length, chosen so single-step lookup decoding 
tables occupy
+    /// `2^12 = 4096` `u16` entries.
+    const MAX_CODE_LENGTH: usize = 12;
+
+    // 
-------------------------------------------------------------------------
+    // 1. Reconstructed `columnProbabilities.ml`
+    // 
-------------------------------------------------------------------------
+
+    /// Probability model for one cell of the coupon matrix after `N = lambda 
* K` distinct items.
+    #[derive(Clone, Copy)]
+    enum Occupancy {
+        /// Finite sketch size `K`: a cell in 1-based column `col` stays `0` 
with probability
+        /// `p_0 = (1 - 1 / (K * 2^col))^N`.
+        Binomial { k: f64 },
+        /// Limit `K -> inf` at fixed `lambda = N / K`: `p_0 = exp(-lambda * 
2^-col)`.
+        Poisson,
+    }
+
+    impl Occupancy {
+        /// `ln(p_0)` for 1-based column `col` (`1..=128`) at density `lambda 
= N / K`.
+        fn ln_zero_prob(self, lambda: f64, col: u8) -> f64 {
+            match self {
+                Occupancy::Binomial { k } => k * lambda * (-inv_pow2(col) / 
k).ln_1p(),
+                Occupancy::Poisson => -lambda * inv_pow2(col),
+            }
+        }
+
+        /// Probability `q = 1 - p_0` that a cell in 1-based column `col` is 
set.
+        fn one_prob(self, lambda: f64, col: u8) -> f64 {
+            -self.ln_zero_prob(lambda, col).exp_m1()
+        }
+
+        /// Probability `p_0` that a cell in 1-based column `col` is still `0`.
+        ///
+        /// 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()
+        }
+
+        /// Expected coupon density `E[C] / K = sum_{col=1..=128} q(col)` of 
the unclipped
+        /// 128-column FM85 matrix.
+        fn expected_c_over_k(self, lambda: f64) -> f64 {
+            (1..=128).map(|col| self.one_prob(lambda, col)).sum()
+        }
+
+        /// Inverts `expected_c_over_k(lambda) = target_c_over_k` by monotone 
binary search.
+        fn solve_lambda(self, target_c_over_k: f64) -> f64 {
+            let mut lo = 0.0;
+            let mut hi = 1.0;
+            while self.expected_c_over_k(hi) < target_c_over_k {
+                hi *= 2.0;
+            }
+            for _ in 0..96 {
+                let mid = 0.5 * (lo + hi);
+                if self.expected_c_over_k(mid) < target_c_over_k {
+                    lo = mid;
+                } else {
+                    hi = mid;
+                }
+            }
+            0.5 * (lo + hi)
+        }
+    }
+
+    /// Computes the 256-entry probability distribution for the 8-bit window 
starting at 0-based
+    /// column `offset` at density `c_over_k` (`columnProbabilities.ml`).
+    ///
+    /// Within a single row, the 8 window columns `offset .. offset + 8` 
(1-based
+    /// `offset + 1 ..= offset + 8`) are treated as independent Bernoulli 
variables, giving
+    /// `P(byte) = prod_{bit=0..8} (q_bit if byte has bit set else p0_bit)`. 
Independence is exact
+    /// in the Poisson model; with `Occupancy::Binomial` the marginals are 
exact and the product
+    /// form is an approximation.
+    fn window_byte_probabilities(model: Occupancy, c_over_k: f64, offset: u8) 
-> [f64; 256] {
+        let lambda = model.solve_lambda(c_over_k);
+        let mut p_one = [0.0; 8];
+        let mut p_zero = [0.0; 8];
+        for bit in 0..8_u8 {
+            let col_1based = offset + bit + 1;
+            p_one[bit as usize] = model.one_prob(lambda, col_1based);
+            p_zero[bit as usize] = model.zero_prob(lambda, col_1based);
+        }
+
+        let mut probs = [0.0; 256];
+        for (byte_val, slot) in probs.iter_mut().enumerate() {
+            let mut prob = 1.0;
+            for bit in 0..8 {
+                if ((byte_val >> bit) & 1) != 0 {
+                    prob *= p_one[bit];
+                } else {
+                    prob *= p_zero[bit];
+                }
+            }
+            *slot = prob;
+        }
+        probs
+    }
+
+    /// Computes the 65-symbol truncated dyadic geometric distribution for
+    /// `LENGTH_LIMITED_UNARY_ENCODING_TABLE65` (`columnProbabilities.ml`):
+    /// `P(s) = 2^{-(s+1)}` for `s in 0..64` and `P(64) = 2^{-64}`, which sums 
to `1.0` and has
+    /// exact Shannon entropy `2 - 2^{-63}` bits (which rounds to `2.0` in 
`f64`).
+    ///
+    /// The symbol is the column delta `x_delta` that the pair encoder writes 
for each surprise
+    /// `(row, col)` pair (the row delta is Golomb-coded with a plain unary 
high part instead).
+    /// The geometric law is the column distribution of a single coupon, and 
"unary" describes the
+    /// shape of the resulting code: lengths `1, 2, 3, 4, 5, 7, 8, 8, 10, 10, 
11, 12, ...` follow
+    /// the unary pattern until the 12-bit limit forces a redistribution.
+    fn unary65_probabilities() -> [f64; 65] {
+        let mut probs = [0.0; 65];
+        for (s, slot) in probs.iter_mut().enumerate().take(64) {
+            *slot = inv_pow2((s + 1) as u8);
+        }
+        probs[64] = inv_pow2(64);
+        probs
+    }
+
+    fn shannon_entropy(probs: &[f64]) -> f64 {
+        probs
+            .iter()
+            .filter(|&&p| p > 0.0)
+            .map(|&p| -p * p.log2())
+            .sum()
+    }
+
+    fn expected_code_length(probs: &[f64], table: &[u16]) -> f64 {
+        probs
+            .iter()
+            .zip(table.iter())
+            .map(|(&p, &entry)| p * ((entry >> 12) as f64))
+            .sum()
+    }
+
+    // 
-------------------------------------------------------------------------
+    // 2. Reconstructed `generateHuffmanCodes.ml`
+    // 
-------------------------------------------------------------------------
+
+    /// Generates a length-limited (`<= max_length`) canonical LSB-first 
Huffman encoding table
+    /// (`generateHuffmanCodes.ml`), packing each symbol's entry as `(length 
<< 12) | codeword`.
+    ///
+    /// How the algorithm was reverse-engineered from the static tables:
+    /// 1. Length-limited optimality (Larmore-Hirschberg Package-Merge, 1990): 
symbols with tiny
+    ///    probabilities such as `2^-64` are capped at length 12 while 
strictly minimizing `sum_s
+    ///    P(s) * len[s]` subject to Kraft's equality `sum_s 2^-len[s] = 1`. 
In Package-Merge over
+    ///    `max_length` levels, each level pairs adjacent items `(2k, 2k+1)` 
from the previous level
+    ///    and stably merges `[leaves, packages]` by non-decreasing weight, 
breaking leaf ties by
+    ///    ascending symbol index. Selecting the `2 * n - 2` lightest items at 
the final level and
+    ///    counting each symbol's leaf occurrences yields the optimal code 
lengths. Exact weight
+    ///    ties between a leaf and a package do occur (e.g. `P(62) = 2^-63 == 
P(63) + P(64)`), but
+    ///    the tables do not identify a tie rule: ordering packages ahead of 
leaves yields the same
+    ///    code lengths for all 23 tables. Leaves go first here.
+    /// 2. Canonical LSB-first codeword assignment: sorting symbols by 
`(len[s], s)` ascending,
+    ///    assigning standard canonical MSB-first integers (`code <<= len - 
prev_len`, then
+    ///    incrementing), and bit-reversing the low `len` bits 
(`reverse_bits() >> (16 - len)`) so
+    ///    CPC's LSB-first bitstream writer can emit `codeword` directly 
reproduces every codeword.
+    fn generate_length_limited_huffman_table(probs: &[f64], max_length: usize) 
-> Vec<u16> {
+        let n = probs.len();
+        assert!(n >= 2 && max_length <= 15);
+
+        let mut leaves: Vec<(f64, Vec<usize>)> = probs
+            .iter()
+            .enumerate()
+            .map(|(s, &p)| (p, vec![s]))
+            .collect();
+        leaves.sort_by(|a, b| a.0.total_cmp(&b.0).then_with(|| 
a.1[0].cmp(&b.1[0])));
+
+        let mut current = leaves.clone();
+        for level in 0..max_length {
+            if level > 0 {
+                let mut packages = Vec::with_capacity(current.len() / 2);
+                for pair in current.chunks_exact(2) {
+                    let mut syms = Vec::with_capacity(pair[0].1.len() + 
pair[1].1.len());
+                    syms.extend_from_slice(&pair[0].1);
+                    syms.extend_from_slice(&pair[1].1);
+                    packages.push((pair[0].0 + pair[1].0, syms));
+                }
+                let mut merged = Vec::with_capacity(leaves.len() + 
packages.len());
+                merged.extend_from_slice(&leaves);
+                merged.extend(packages);
+                // Rust's `sort_by` is guaranteed stable, keeping `leaves` 
ahead of `packages`
+                // whenever weights tie exactly.
+                merged.sort_by(|a, b| a.0.total_cmp(&b.0));
+                current = merged;
+            }
+        }
+
+        let mut lengths = vec![0_usize; n];
+        for item in current.iter().take(2 * n - 2) {
+            for &sym in &item.1 {
+                lengths[sym] += 1;
+            }
+        }
+
+        let mut order: Vec<usize> = (0..n).collect();
+        order.sort_by(|&a, &b| lengths[a].cmp(&lengths[b]).then_with(|| 
a.cmp(&b)));
+
+        let mut table = vec![0_u16; n];
+        let mut next_code = 0_u32;
+        let mut prev_len = 0_usize;
+        for sym in order {
+            let len = lengths[sym];
+            assert!((1..=max_length).contains(&len));
+            next_code <<= len - prev_len;
+            let msb_code = next_code as u16;
+            next_code += 1;
+            prev_len = len;
+
+            let lsb_code = msb_code.reverse_bits() >> (16 - len);
+            table[sym] = ((len as u16) << 12) | lsb_code;
+        }
+        assert_eq!(next_code, 1_u32 << prev_len, "Kraft sum must equal 1");
+        table
+    }
+
+    // 
-------------------------------------------------------------------------
+    // 3. Reconstructed `generatePermutationsForSLIDING.ml`
+    // 
-------------------------------------------------------------------------
+
+    /// Generates the 56-column encoding permutation for sliding-window `phase 
= (2 * m + 1) / 32`
+    /// (`generatePermutationsForSLIDING.ml`).
+    ///
+    /// In `Sliding` mode (`c/k >= 3.375`), the 0-based window offset is 
`floor(c/k - 2.375)`.
+    /// Outside the 8-bit window `[offset, offset + 7]`, a bit at `col < 
offset` is surprising when
+    /// `0` (probability `p_0`), and a bit at `col >= offset + 8` is 
surprising when `1`
+    /// (probability `q`). Rotating column indices via `canon = (col + 56 - 
offset) % 64` places
+    /// post-window columns at `0 .. 56 - offset` and pre-window columns at 
`56 - offset .. 56`.
+    /// Ranking the 56 canonical columns by descending surprise probability 
(ties by index) assigns
+    /// shorter unary codes to more frequent surprise columns.
+    ///
+    /// What the 16 stored permutations identify:
+    /// * The base of `c/k = 6.0 + phase`. The base enters only through 
`offset`, which equals the
+    ///   base minus 3 below `phase = 3/8` and the base minus 2 above it. With 
`p_0` computed as an
+    ///   exponential, bases 5, 6, and 7 reproduce 6, 16, and 10 of the 16 
phases.
+    /// * That `p_0` was computed without cancellation. Computing it as `1.0 - 
q` reproduces 15 of
+    ///   16 phases for both base 6 and base 7, so the decisive datum is a 
single comparison at
+    ///   `phase = 19/32` (`offset = 4`): column 1 (`canon = 52`) has `p_0 ≈ 
2.22e-17` and must rank
+    ///   ahead of 1-based column 62 (`canon = 49`, `q ≈ 1.66e-17`), whereas 
`1.0 - q` rounds `p_0`
+    ///   to `0.0` and ranks it last.
+    /// * Nothing about `K`: every `K` from `2^8` to the Poisson limit yields 
identical
+    ///   permutations.
+    fn generate_sliding_column_permutation(phase_index: usize) -> [u8; 56] {
+        let model = STEADY_STATE_MODEL;
+        let phase = (2 * phase_index + 1) as f64 / 32.0;
+        let c_over_k = STEADY_STATE_C_OVER_K_BASE + phase;
+        let offset = (c_over_k - 2.375).floor() as usize;
+        let lambda = model.solve_lambda(c_over_k);
+
+        let mut surprise_prob = [0.0; 56];
+        for col in 0..64_usize {
+            if (offset..offset + 8).contains(&col) {
+                continue;
+            }
+            let canon = (col + 56 - offset) % 64;
+            let col_1based = (col + 1) as u8;
+            surprise_prob[canon] = if col < offset {
+                model.zero_prob(lambda, col_1based)
+            } else {
+                model.one_prob(lambda, col_1based)
+            };
+        }
+
+        let mut cols_by_prob: [usize; 56] = from_fn(|i| i);
+        cols_by_prob.sort_by(|&a, &b| {
+            surprise_prob[b]
+                .total_cmp(&surprise_prob[a])
+                .then_with(|| a.cmp(&b))
+        });
+
+        let mut encode_perm = [0_u8; 56];
+        for (rank, &canon) in cols_by_prob.iter().enumerate() {
+            encode_perm[canon] = rank as u8;
+        }
+        encode_perm
+    }
+
+    #[test]
+    fn unary_encoding_table65() {
+        let probs = unary65_probabilities();
+        let generated = generate_length_limited_huffman_table(&probs, 
MAX_CODE_LENGTH);
+
+        assert_that!(shannon_entropy(&probs), near(2.0, 1e-15));
+        assert_that!(
+            expected_code_length(&probs, &generated),
+            near(2.02490234375, 1e-15),
+        );
+        assert_that!(
+            generated,
+            container_eq(LENGTH_LIMITED_UNARY_ENCODING_TABLE65),
+        );
+    }
+
+    /// `(entropy, avg_length)` printed by `generateHuffmanCodes.ml` above 
each table of
+    /// `ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE`, copied verbatim from the 
header comments.
+    ///
+    /// These 20-digit values are the only continuous output of the original 
generator that
+    /// survived, so they are the evidence that discriminates between 
occupancy models: the
+    /// codewords alone are reproduced by a wide range of models (e.g. every 
`K >= 2^16` for the
+    /// midrange tables), whereas the entropies resolve differences of 
~`1e-14`.
+    #[allow(clippy::excessive_precision)]
+    const RECORDED_HEADER_STATS: [(f64, f64); 22] = [
+        (4.4619200780464778333, 4.5415773046232610355), // table 0
+        (4.4574755684414029133, 4.5336306265208552446), // table 1
+        (4.4520619712441886762, 4.5253989110544479146), // table 2
+        (4.4457680500675866853, 4.5181192844586535173), // table 3
+        (4.4386754570568340839, 4.5071584786605640716), // table 4
+        (4.4308578632493116345, 4.4996166821663301505), // table 5
+        (4.4310364988500126060, 4.5051134111084252254), // table 6
+        (4.4417871821766841123, 4.5206419191518980583), // table 7
+        (4.4505873338397474726, 4.5270058771550303334), // table 8
+        (4.4575203029748040606, 4.5315465600684730063), // table 9
+        (4.4626765653088611430, 4.5373141251902122661), // table 10
+        (4.4661524304421691411, 4.5443750890419041255), // table 11
+        (4.4680486273043946710, 4.5521643785256946657), // table 12
+        (4.4684687952964843305, 4.5509169030369793774), // table 13
+        (4.4675179140944036860, 4.5477235350841240802), // table 14
+        (4.4653007097343397902, 4.5480722016259509388), // table 15
+        (2.1627885076675394949, 2.2704182849800043087), // table 16
+        (2.9553294756640680063, 3.0766035704232641557), // table 17
+        (3.5218672531711128215, 3.6153551492375441967), // table 18
+        (3.9228873257934386842, 3.9989687586992346269), // table 19
+        (4.1937026483207340277, 4.2809622975207295426), // table 20
+        (4.3601926041863263706, 4.4384101723259572481), // table 21
+    ];
+
+    /// Tolerance for matching `RECORDED_HEADER_STATS`: a few dozen `f64` 
ULPs, two orders of
+    /// magnitude below the deviation of the rejected base-6 finite-`K` 
steady-state model
+    /// (`6.1e-12`) and the alternative midrange models (`>= 2.5e-11` away 
from `K = 2^32`).
+    const HEADER_STATS_TOLERANCE: f64 = 3e-14;
+
+    #[test]
+    fn high_entropy_byte_encoding_tables() {
+        for (idx, &(entropy, avg_length)) in 
RECORDED_HEADER_STATS.iter().enumerate() {
+            let probs = if idx < 16 {
+                // Tables 0..16: steady-state sliding window at `c/k = 6.0 + 
(2*m + 1)/32`,
+                // `offset = floor(c/k - 2.375)` (`3` for `m < 6`, `4` for `m 
>= 6`).
+                let phase = (2 * idx + 1) as f64 / 32.0;
+                let c_over_k = STEADY_STATE_C_OVER_K_BASE + phase;
+                let offset = (c_over_k - 2.375).floor() as u8;
+                window_byte_probabilities(STEADY_STATE_MODEL, c_over_k, offset)
+            } else {
+                // Tables 16..22: midrange pinned window (`offset = 0`) at 
`c/k = (2*m + 3) / 6`.
+                let m = idx - 16;
+                window_byte_probabilities(MIDRANGE_MODEL, (2 * m + 3) as f64 / 
6.0, 0)
+            };
+            let table = generate_length_limited_huffman_table(&probs, 
MAX_CODE_LENGTH);
+
+            assert_that!(
+                shannon_entropy(&probs),
+                near(entropy, HEADER_STATS_TOLERANCE)
+            );
+            assert_that!(
+                expected_code_length(&probs, &table),
+                near(avg_length, HEADER_STATS_TOLERANCE),
+            );
+            assert_that!(
+                table,
+                container_eq(ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE[idx])
+            );
+        }
+    }
+
+    #[test]
+    fn sliding_column_permutations() {
+        for phase_idx in 0..16 {
+            let generated = generate_sliding_column_permutation(phase_idx);
+            assert_that!(
+                generated.as_slice(),
+                container_eq(COLUMN_PERMUTATIONS_FOR_ENCODING[phase_idx]),
+            );
+        }
+    }
+
+    // 
-------------------------------------------------------------------------
+    // 4. Decoding table inversions (`fm85Compression.c` / 
`CompressionData.java`)
+    // 
-------------------------------------------------------------------------
 
     #[test]
     fn decoding_tables() {
diff --git a/datasketches/src/cpc/estimator.rs 
b/datasketches/src/cpc/estimator.rs
index 20e9866..c171a04 100644
--- a/datasketches/src/cpc/estimator.rs
+++ b/datasketches/src/cpc/estimator.rs
@@ -427,3 +427,487 @@ fn icon_estimate(lg_k: u8, num_coupons: u32) -> f64 {
     let result = c * factor * term;
     if result >= c { result } else { c }
 }
+
+#[cfg(test)]
+mod tests {
+    // Reference ICON estimator, least-squares polynomial reconstruction, and 
confidence-table
+    // verification.
+    //
+    // Provenance in Kevin J. Lang's original FM85 / CPC implementation:
+    // 1. `iconEstimator.c` / `icon_estimator.hpp` / `IconEstimatorTest.java`: 
Defines the exact
+    //    FM85 ICON (Inverted Coupon Number) estimator by numerically 
inverting the expected coupon
+    //    count `E[C | N] = K * sum_{col=1..=128} (1 - (1 - 1/(K*2^col))^N)`, 
together with a
+    //    validation sweep comparing `icon_estimate` against 
`exact_icon_estimate`.
+    // 2. `icon_estimator.hpp` / `IconPolynomialCoefficients.java`: only the 
fitted degree-19
+    //    coefficient matrix `ICON_POLYNOMIAL_COEFFICIENTS` and the constants 
`0.7940236163830469`,
+    //    `2.0`, and `66.774757` were checked into C/C++/Java; the offline 
fitting script was not.
+    //    What `icon_estimate`'s evaluation formula, the Maclaurin series of 
`N(C) / C`, and the
+    //    error profile beyond `5.7 * K` reveal about that script is 
documented next to
+    //    `fit_icon_polynomial_row` below, including what remains unknown.
+    // 3. `cpc_confidence.hpp` / `CpcConfidence.java` (offline Monte Carlo 
characterization):
+    //    Defines the theoretical asymptotic relative standard error constants 
(`ICON_ERROR_CONSTANT
+    //    = ln 2` and `HIP_ERROR_CONSTANT = sqrt((ln 2) / 2)`) alongside the 
empirical
+    //    ~1,000,000-trial quantile tables `ICON_{LOW,HIGH}_SIDE_DATA` and
+    //    `HIP_{LOW,HIGH}_SIDE_DATA` measured at `N = 1000 * K` for `lg_k = 
4..=14`.
+
+    use std::array::from_fn;
+    use std::f64::consts::PI;
+    use std::f64::consts::SQRT_2;
+
+    use googletest::assert_that;
+    use googletest::prelude::gt;
+    use googletest::prelude::lt;
+    use googletest::prelude::near;
+
+    use super::*;
+    use crate::common::inv_pow2::inv_pow2;
+
+    const EULER_MASCHERONI: f64 = 0.577_215_664_901_532_9;
+    const ICON_CUBIC_PRECONDITIONER: f64 = 66.774757;
+
+    // 
-------------------------------------------------------------------------
+    // 1. Exact FM85 ICON estimator (`IconEstimatorTest.java` / `fm85`)
+    // 
-------------------------------------------------------------------------
+
+    const ICON_INVERSION_TOLERANCE: f64 = 1.0e-15;
+
+    /// Precomputes `ln(1 - 1 / (K * 2^col))` for 1-based `col = 1..=128` at 
fixed `kf`, matching
+    /// `qnj` in `IconEstimatorTest.java` bit-for-bit while avoiding repeated 
`ln_1p` evaluations
+    /// inside the binary-search inner loop.
+    fn precompute_col_ln1p(kf: f64) -> [f64; 128] {
+        from_fn(|idx| (-inv_pow2((idx + 1) as u8) / kf).ln_1p())
+    }
+
+    /// Expected coupon count `E[C | N] = K * sum_{col=1..=128} (1 - (1 - 
1/(K*2^col))^N)` in the
+    /// unclipped 128-column FM85 coupon matrix (`exactCofN` in 
`IconEstimatorTest.java`).
+    fn exact_coupon_count_with_ln1p(kf: f64, col_ln1p: &[f64; 128], nf: f64) 
-> f64 {
+        let mut total = 0.0;
+        // Iterating from 128 down to 1 accumulates tiny tail probabilities 
first before large
+        // head probabilities, preserving full `f64` summation precision.
+        for &tmp2 in col_ln1p.iter().rev() {
+            total += -f64::exp_m1(nf * tmp2);
+        }
+        kf * total
+    }
+
+    /// Exact ICON estimate `N_hat` solving `exact_coupon_count(kf, N_hat) = 
target_c` by bracket
+    /// doubling and binary search (`exactIconEstimator` in 
`IconEstimatorTest.java`).
+    fn exact_icon_estimate(kf: f64, target_c: f64) -> f64 {
+        if target_c == 0.0 || target_c == 1.0 {
+            return target_c;
+        }
+        let col_ln1p = precompute_col_ln1p(kf);
+        exact_icon_estimate_with_ln1p(kf, &col_ln1p, target_c)
+    }
+
+    fn exact_icon_estimate_with_ln1p(kf: f64, col_ln1p: &[f64; 128], target_c: 
f64) -> f64 {
+        if target_c == 0.0 || target_c == 1.0 {
+            return target_c;
+        }
+        let mut lo = target_c;
+        let mut hi = 2.0 * target_c;
+        while exact_coupon_count_with_ln1p(kf, col_ln1p, hi) <= target_c {
+            lo = hi;
+            hi *= 2.0;
+        }
+        for _ in 0..100 {
+            let mid = lo + 0.5 * (hi - lo);
+            if (hi - lo) / mid < ICON_INVERSION_TOLERANCE || mid <= lo || mid 
>= hi {
+                return mid;
+            }
+            let mid_c = exact_coupon_count_with_ln1p(kf, col_ln1p, mid);
+            if mid_c == target_c {
+                return mid;
+            } else if mid_c < target_c {
+                lo = mid;
+            } else {
+                hi = mid;
+            }
+        }
+        0.5 * (lo + hi)
+    }
+
+    // 
-------------------------------------------------------------------------
+    // 2. Reconstructed generator for `ICON_POLYNOMIAL_COEFFICIENTS`
+    // 
-------------------------------------------------------------------------
+    //
+    // What the stored coefficients reveal about the offline fit, and what 
they do not:
+    //
+    // * Pre-conditioned target function: for `2 <= C <= threshold * K`, 
`icon_estimate` returns
+    //   `C*(1+(C/K)^3/66.774757)*P(x)` with `x = C / (2 * K)`, so row `lg_k` 
of
+    //   `ICON_POLYNOMIAL_COEFFICIENTS` is a degree-19 polynomial 
approximating the ratio
+    //   `g_K(x)=N_exact/(C*(1+(C/K)^3/66.774757))`. Without the cubic 
pre-conditioner, `N_exact/C`
+    //   grows by more than 8x over `C/K` in `[0, 6]` as it transitions into 
`0.794*K*2^(C/K)`; with
+    //   it, `g_K` stays within `[0.89, 1.48]`, and the stored rows reach a 
maximum relative error
+    //   of about `2e-7` on `[2, threshold * K]`.
+    //
+    //   The argument `x = C / (2 * K)` maps `C in [0, 6 * K]` onto `[0, 3]` 
instead of `[0, 6]`,
+    //   keeping `x^19` bounded by `3^19 ≈ 1.16e9` rather than `6^19 ≈ 
6.09e14`. Where the value
+    //   `66.774757` comes from is not known.
+    //
+    // * Maclaurin series check on the leading columns: For `K -> inf` and 
`lambda = N / K -> 0`,
+    //   `E[C] / K = sum_{j>=1} (1 - exp(-lambda * 2^-j)) = lambda - 
lambda^2/6 + lambda^3/42 -
+    //   ...`. Series inversion yields `N / C = 1 + (C/K)/6 + 2*(C/K)^2/63 + 
... = 1 + x/3 +
+    //   8*x^2/63 + ...`. Dividing by `1 + 8*x^3 / 66.774757` preserves the 
degree-0..2 Maclaurin
+    //   terms, so columns 0, 1, 2 of `ICON_POLYNOMIAL_COEFFICIENTS` should 
approximate `1`, `1/3`,
+    //   and `8/63`. They do so only approximately: `a_0` approaches `1` like 
`1 - O(1 / K)`, but
+    //   `a_1` wanders at the `1e-5` level and `a_2` plateaus near `0.1267` 
for `lg_k >= 8` instead
+    //   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]`): 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, 
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 strongly supports the grid but does not 
establish the original
+    //   procedure: the weighting and the numerics are not identified, and 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
+    //   coefficients afterwards suggest that the procedure changed, plausibly 
to a sampled grid,
+    //   but neither exhaustive integer grids nor the dense-then-geometric 
grid of
+    //   `icon_fitting_grid` reproduce the stored coefficients (deviations of 
14% to 65%). For these
+    //   rows the test only demonstrates functional equivalence: a fit of the 
same form attains the
+    //   same `~1e-7` accuracy.
+
+    /// Solves the overdetermined linear least-squares problem `min_a ||V * a 
- y||_2` (`m >= n`)
+    /// via Householder QR factorization without external linear-algebra 
dependencies.
+    fn solve_least_squares_qr(mut v: Vec<f64>, mut y: Vec<f64>, m: usize, n: 
usize) -> Vec<f64> {
+        assert!(m >= n && v.len() == m * n && y.len() == m);
+
+        for k in 0..n {
+            let mut norm_sq = 0.0;
+            for row in k..m {
+                let val = v[row * n + k];
+                norm_sq += val * val;
+            }
+            let norm = norm_sq.sqrt();
+            if norm == 0.0 {
+                continue;
+            }
+
+            let v_kk = v[k * n + k];
+            let alpha = if v_kk >= 0.0 { -norm } else { norm };
+            let u0 = v_kk - alpha;
+
+            let mut u_norm_sq = u0 * u0;
+            for row in (k + 1)..m {
+                let val = v[row * n + k];
+                u_norm_sq += val * val;
+            }
+            let beta = 2.0 / u_norm_sq;
+
+            v[k * n + k] = alpha;
+            for col in (k + 1)..n {
+                let mut dot = u0 * v[k * n + col];
+                for row in (k + 1)..m {
+                    dot += v[row * n + k] * v[row * n + col];
+                }
+                let scale = beta * dot;
+                v[k * n + col] -= scale * u0;
+                for row in (k + 1)..m {
+                    v[row * n + col] -= scale * v[row * n + k];
+                }
+            }
+
+            let mut dot_y = u0 * y[k];
+            for row in (k + 1)..m {
+                dot_y += v[row * n + k] * y[row];
+            }
+            let scale_y = beta * dot_y;
+            y[k] -= scale_y * u0;
+            for row in (k + 1)..m {
+                y[row] -= scale_y * v[row * n + k];
+            }
+        }
+
+        let mut coeffs = vec![0.0; n];
+        for i in (0..n).rev() {
+            let mut sum = y[i];
+            for j in (i + 1)..n {
+                sum -= v[i * n + j] * coeffs[j];
+            }
+            coeffs[i] = sum / v[i * n + i];
+        }
+        coeffs
+    }
+
+    /// Generates the sample grid of coupon counts `C in [1, 6 * K]` for 
fitting row `lg_k`.
+    ///
+    /// For `lg_k <= 7` this is the exhaustive integer grid that reproduces 
the stored
+    /// coefficients. For `lg_k >= 8` the original grid is unknown; the 
dense-then-geometric grid
+    /// below is an assumption that reproduces the accuracy of the stored 
rows, not their
+    /// coefficients.
+    fn icon_fitting_grid(lg_k: usize) -> Vec<u64> {
+        let k = 1_u64 << lg_k;
+        let max_c = 6 * k;
+        if lg_k <= 7 {
+            (1..=max_c).collect()
+        } else {
+            // Assumed grid: dense small integers, then 4% geometric steps up 
to `6 * K`.
+            let mut grid = Vec::with_capacity(512);
+            let mut c = 1_u64;
+            while c < max_c {
+                grid.push(c);
+                c = if c < 64 {
+                    c + 1
+                } else {
+                    (c + 1).max((1040 * c) / 1000)
+                };
+            }
+            grid.push(max_c);
+            grid
+        }
+    }
+
+    /// Fits the 20 degree-19 polynomial coefficients for `lg_k` by least 
squares against
+    /// `exact_icon_estimate` on `C in [1, 6 * K]` (see `icon_fitting_grid` 
for which rows this
+    /// reproduces coefficient by coefficient).
+    fn fit_icon_polynomial_row(lg_k: usize) -> Vec<f64> {
+        let kf = (1_u64 << lg_k) as f64;
+        let col_ln1p = precompute_col_ln1p(kf);
+        let grid = icon_fitting_grid(lg_k);
+        let m = grid.len();
+        let n = ICON_POLYNOMIAL_NUM_COEFFICIENTS;
+
+        let mut vandermonde = vec![0.0; m * n];
+        let mut target = vec![0.0; m];
+
+        for (row, &c_int) in grid.iter().enumerate() {
+            let cf = c_int as f64;
+            let n_exact = exact_icon_estimate_with_ln1p(kf, &col_ln1p, cf);
+            let ratio = cf / kf;
+            let precond = 1.0 + (ratio * ratio * ratio) / 
ICON_CUBIC_PRECONDITIONER;
+            target[row] = n_exact / (cf * precond);
+
+            let x = cf / (2.0 * kf);
+            let mut x_pow = 1.0;
+            for col in 0..n {
+                vandermonde[row * n + col] = x_pow;
+                x_pow *= x;
+            }
+        }
+
+        solve_least_squares_qr(vandermonde, target, m, n)
+    }
+
+    #[test]
+    fn exact_icon_estimator_matches_approximation() {
+        for lg_k in ICON_MIN_LOG_K..=ICON_MAX_LOG_K {
+            let lg_k_u8 = lg_k as u8;
+            let k = 1_u64 << lg_k;
+            let kf = k as f64;
+
+            assert_eq!(icon_estimate(lg_k_u8, 0), 0.0);
+            assert_eq!(icon_estimate(lg_k_u8, 1), 1.0);
+
+            // Verify strict monotonicity across the polynomial-to-exponential 
splice threshold
+            // (`5.7 * K` for `lg_k < 14`, `5.6 * K` for `lg_k >= 14`).
+            let threshold_factor = if lg_k < 14 { 5.7 } else { 5.6 };
+            let splice_c = (threshold_factor * kf).floor() as u32;
+            let mut prev_est = icon_estimate(lg_k_u8, splice_c - 2);
+            for c in (splice_c - 1)..=(splice_c + 2) {
+                let est = icon_estimate(lg_k_u8, c);
+                assert_that!(est, gt(prev_est));
+                prev_est = est;
+            }
+
+            // Geometric sweep from `C = 2` into the exponential regime (`60 * 
K`), matching the
+            // characterization sweep in `IconEstimatorTest.java`.
+            let max_c = (60 * k).min(u32::MAX as u64);
+            let mut c = 2_u64;
+            while c <= max_c {
+                let exact = exact_icon_estimate(kf, c as f64);
+                let approx = icon_estimate(lg_k_u8, c as u32);
+                let rel_err = ((approx - exact) / exact).abs();
+                // In the polynomial region (`<= threshold * K`) the stored 
rows stay below
+                // `2.1e-7` on a dense sweep over every `lg_k`.
+                //
+                // 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)`. 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 {
+                    (2.5e-6_f64).max(1.0 / (80.0 * kf))
+                };
+                assert_that!(rel_err, lt(tol));
+
+                c = if c < 32 {
+                    c + 1
+                } else {
+                    (c + 1).max((125 * c) / 100)
+                };
+            }
+        }
+    }
+
+    #[test]
+    fn icon_exponential_constant_matches_theory() {
+        // The coefficient used at runtime, read back from the production 
function.
+        let runtime_constant = icon_exponential_approximation(1.0, 0.0);
+
+        // Asymptotic FM85 theory (Mellin transform of the harmonic sum `E[C] 
/ K`):
+        // `E[C]/K = log2(N/K) + gamma/ln(2) - 1/2 + P(log2(N/K)) + o(1)`, 
where `P` is 1-periodic
+        // and `ln(2) * P` has the fundamental amplitude `a = 2 * 
|Gamma(2*pi*i / ln 2)|`, about
+        // `1.09e-6`. Hence `N = D * K * 2^(C/K) * exp(-ln(2) * P)`, where the 
closed form
+        // `D = sqrt(2) * exp(-gamma) = 0.7940236163832829` differs from the 
runtime constant by
+        // `2.4e-13`.
+        //
+        // The approximation `A * K * 2^(C/K)` has relative error `(A / D) * 
exp(ln(2) * P) - 1`.
+        // Choosing `A` so that this error averages to zero over a period of 
`C / K` gives
+        // `A = D / <exp(ln(2) * P)> = D * (1 - a^2 / 4)` up to `O(a^3)`, where
+        // `a^2 / 4 = |Gamma(i * y)|^2 = pi / (y * sinh(pi * y))` with `y = 2 
* pi / ln 2`. This
+        // value rounds to the runtime constant, which explains its last 
digits; whether the
+        // original fitting script used this criterion is not known.
+        let d = SQRT_2 * (-EULER_MASCHERONI).exp();
+        let y = 2.0 * PI / LN_2;
+        let zero_mean_error_constant = d * (1.0 - PI / (y * (PI * y).sinh()));
+        assert_that!(runtime_constant, near(zero_mean_error_constant, 3e-16));
+
+        // The same criterion evaluated numerically: the harmonic mean of 
`N_exact / (K * 2^(C/K))`
+        // over one period of `C / K`. At `C / K in [20, 21)` the finite-`K` 
bias
+        // `1 / (2 * K * lambda)` is below `2e-16` for `K = 2^32`, and the 
tolerance separates this
+        // criterion from `D` (`2.4e-13` away) and from the arithmetic mean 
(`4.7e-13` away).
+        let kf = (1_u64 << 32) as f64;
+        let samples = 32;
+        let mut inverse_ratio_sum = 0.0;
+        for m in 0..samples {
+            let c_over_k = 20.0 + (m as f64 + 0.5) / (samples as f64);
+            let n_exact = exact_icon_estimate(kf, c_over_k * kf);
+            inverse_ratio_sum += kf * 2.0_f64.powf(c_over_k) / n_exact;
+        }
+        let harmonic_mean = samples as f64 / inverse_ratio_sum;
+        assert_that!(runtime_constant, near(harmonic_mean, 1e-14));
+    }
+
+    #[test]
+    fn reconstruct_icon_polynomial_coefficients() {
+        // The highest-`lg_k` stored row (`lg_k = 26`) is consistent with the 
Maclaurin series
+        // `N / C = 1 + (1/3)*x + (8/63)*x^2 + ...` (`x = C / (2 * K)`) only 
up to the bias of a
+        // least-squares fit on `[0, 3]`: the stored `a_0`, `a_1`, `a_2` 
differ from the series by
+        // `2.9e-9`, `5.0e-6`, and `3.4e-4`, and `a_2` does not converge with 
growing `lg_k`.
+        let last_row_start = ICON_POLYNOMIAL_NUM_COEFFICIENTS * 
(ICON_MAX_LOG_K - ICON_MIN_LOG_K);
+        assert_that!(
+            ICON_POLYNOMIAL_COEFFICIENTS[last_row_start],
+            near(1.0, 1e-7)
+        );
+        assert_that!(
+            ICON_POLYNOMIAL_COEFFICIENTS[last_row_start + 1],
+            near(1.0 / 3.0, 1e-5),
+        );
+        assert_that!(
+            ICON_POLYNOMIAL_COEFFICIENTS[last_row_start + 2],
+            near(8.0 / 63.0, 4e-4),
+        );
+
+        for lg_k in ICON_MIN_LOG_K..=ICON_MAX_LOG_K {
+            let fitted = fit_icon_polynomial_row(lg_k);
+            let stored_start = ICON_POLYNOMIAL_NUM_COEFFICIENTS * (lg_k - 
ICON_MIN_LOG_K);
+            let stored = &ICON_POLYNOMIAL_COEFFICIENTS
+                [stored_start..stored_start + 
ICON_POLYNOMIAL_NUM_COEFFICIENTS];
+
+            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%`.
+                // 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 {
+                    let rel_diff = ((fitted[deg] - stored[deg]) / 
stored[deg]).abs();
+                    assert_that!(rel_diff, lt(0.025));
+                }
+            }
+
+            // Across every `lg_k = 4..=26`, verify that the fitted polynomial 
agrees with both
+            // the checked-in `ICON_POLYNOMIAL_COEFFICIENTS` row and 
`exact_icon_estimate`
+            // throughout the active evaluation interval `[2, threshold * K]`. 
For `lg_k >= 8` this
+            // shows functional equivalence only; the coefficients themselves 
are not reproduced.
+            let k = 1_u64 << lg_k;
+            let kf = k as f64;
+            let threshold_factor = if lg_k < 14 { 5.7 } else { 5.6 };
+            let max_active_c = (threshold_factor * kf).floor() as u64;
+
+            let pred_vs_stored_tol = if lg_k <= 7 { 2e-8 } else { 4e-7 };
+            for step in 0..=40 {
+                let c_int = 2 + ((max_active_c - 2) * step) / 40;
+                let cf = c_int as f64;
+                let x = cf / (2.0 * kf);
+                let ratio = cf / kf;
+                let precond = 1.0 + (ratio * ratio * ratio) / 
ICON_CUBIC_PRECONDITIONER;
+
+                let n_fitted = cf * precond * evaluate_polynomial(&fitted, 0, 
fitted.len(), x);
+                let n_stored = cf * precond * evaluate_polynomial(stored, 0, 
stored.len(), x);
+                let n_exact = exact_icon_estimate(kf, cf);
+
+                let rel_vs_stored = ((n_fitted - n_stored) / n_stored).abs();
+                let rel_vs_exact = ((n_fitted - n_exact) / n_exact).abs();
+                assert_that!(rel_vs_stored, lt(pred_vs_stored_tol));
+                assert_that!(rel_vs_exact, lt(4e-7));
+            }
+        }
+    }
+
+    // 
-------------------------------------------------------------------------
+    // 3. Confidence interval constants & empirical tables 
(`cpc_confidence.hpp`)
+    // 
-------------------------------------------------------------------------
+
+    #[test]
+    fn confidence_constants_and_bounds() {
+        // Both asymptotic (`K -> inf`) relative standard errors, scaled by 
`sqrt(K)`, follow from
+        // the Poisson model of the coupon matrix:
+        // - ICON: cells are independent, so `Var(C) ≈ K * sum_j q_j * (1 - 
q_j)`. Averaged over a
+        //   period, the sum equals `(1 / ln 2) * int_0^inf (exp(-u) - 
exp(-2u)) / u du = 1`
+        //   (Frullani), so `sd(C) ≈ sqrt(K)`; since `N_hat` grows like 
`2^(C/K)`, the relative
+        //   error is `ln(2) / sqrt(K)`.
+        // - HIP: a new item changes the sketch with probability `p ≈ 1 / 
(lambda * ln 2)`, and the
+        //   HIP variance `int_0^n (1/p - 1) dm ≈ n^2 * ln(2) / (2 * K)` gives 
`sqrt(ln(2) / 2)`.
+        // `HIP_ERROR_CONSTANT` is spelled out as a decimal literal, so check 
it against that form.
+        assert_that!(HIP_ERROR_CONSTANT, near((LN_2 / 2.0).sqrt(), 1e-16));
+
+        // For `lg_k <= 14` the bounds use the Monte Carlo tables instead. 
Each entry is
+        // `10_000 * sqrt(K) * eps / kappa`, where `eps` is the one-sided 
`Phi(-kappa)` tail
+        // quantile of `estimate / N - 1` (high side, used by the lower bound) 
or of
+        // `1 - estimate / N` (low side, used by the upper bound) at `N = 1000 
* K`. Being random
+        // measurements, the tables can only be re-measured statistically, not 
regenerated, and
+        // this test does not verify their values or the coverage of the 
resulting intervals. It
+        // checks only how the bounds use them: every bound brackets the 
estimate, respects `C`,
+        // and widens strictly as `kappa` grows.
+        for lg_k in 4..=16_u8 {
+            let c = 3 * (1_u32 << lg_k);
+            let icon_est = estimate(true, 0.0, lg_k, c);
+            for (merge_flag, hip_est) in [(true, 0.0), (false, icon_est)] {
+                let mut prev_lb = icon_est;
+                let mut prev_ub = icon_est;
+                for kappa in [NumStdDev::One, NumStdDev::Two, 
NumStdDev::Three] {
+                    let lb = lower_bound(merge_flag, hip_est, lg_k, c, kappa);
+                    let ub = upper_bound(merge_flag, hip_est, lg_k, c, kappa);
+                    assert!(lb >= c as f64 && lb < prev_lb && ub > prev_ub);
+                    prev_lb = lb;
+                    prev_ub = ub;
+                }
+            }
+        }
+    }
+}


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to